Twist Attack, Sub-Group Attack & Pollard-Rho

[krashfire]

i realize we cannot attack the SECP256k1 directly but we could create a twist on the curve by creating another Y coordinate on the twisted curve.

This i had validated for the public key xy that i am working on, i had to first find the correct curve and validate whether the public key x and y generated are valid on the curves.

Code:

from sage.all import *

# Define the prime modulus and the original and twisted curves
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
E_original = EllipticCurve(GF(p), [0, 7])  # Original curve
E_twist = EllipticCurve(GF(p), [0, 2])  # Twisted curve

# Define the public key coordinates in hexadecimal
pubx_hex = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
puby_hex = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

# Convert hexadecimal coordinates to integers
pubx_int = int(pubx_hex, 16)
puby_int = int(puby_hex, 16)

# Check if negating y coordinate results in a valid point on the twisted curve
try:
    P_twist = E_twist(pubx_int, -puby_int)
    print("Valid point on the twisted curve:", P_twist)
except TypeError as e:
    print("The negated y-coordinate does not result in a valid point on the twisted curve. Error:", e)

then i generate the generators and its group order for the sub group attack

this is a sample code

Code:

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
E = EllipticCurve(GF(p), [0,2])
Grp = E.abelian_group()
g = Grp.gens()[0]
numElements = g.order()
print( "{0} = {1}".format(numElements, factor(numElements)) )

so i have created the twist and the sub groups, encrypted and decrypt a random message but my problem is implementing the pollard rho. i cannot seems to get my pollard rho working right. how should i implement the pollard rho to reveal the partial private keys? i already know how to combine the partial private keys by using the Chinese Remainder Theorem. im just having issues implementing the Pollard rho correctly.

to understand where i am at currently,

this was my result.

Code:

Valid point on Twist Curve 1: ( xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 1)
Valid point on Twist Curve 1: (xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx: 1)
Encrypted: b'gAAAAABmTUdg-Rk9DqTmm--qHL60H7Y-xyhsMGj-hN9b3nblwwbX1889rW_xkV4YH_CGgLoDfmhUG1kWMLbqBtvkMAkBLA1TpRorPS54bE1tq1GqRI7qBw0='
Decrypted: b'Hello, secure world!'
Valid point on Twist Curve 2: (xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx: 47708717901745451695269673872143322736860462806065126161610255669643023187654 : 1)
Valid point on Twist Curve 2: (xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx: 68083371335570743728301311136544585116409521859575437877847328338265811484009 : 1)
Encrypted: b'gAAAAABmTUdgKPTxiD2aMkmdpCzLWRS6Jf_XoAFbt9Clh-tdswEJ1FDEEHh_sq6afzgwXIRs-eKoEwNUN73OXMbbxIVAtd0X3RzEPgEP2PpfQivQP7qRhls='
Decrypted: b'Hello, secure world!'
Twist Curve 1 Group order = 38597363079105398474523661669562635951234135017402074565436668291433169282997 = 3 * 13^2 * 3319 * 22639 * 1013176677300131846900870239606035638738100997248092069256697437031
Twist Curve 1 Subgroup order = 3, Generator = (0 : 50963827496501355358210603252497135226159332537351223778668747140855667399507 : 1)
Order of Twist Curve 1 subgroup generator: 3
Twist Curve 1 Subgroup order = 169, Generator = (91164871848594737862768174215169171472460815325023337256982466157377582150694 : 54646643330104885507641247315265108556098632006153847263625810111733477892887 : 1)
Order of Twist Curve 1 subgroup generator: 169
Twist Curve 1 Subgroup order = 3319, Generator = (49641695783380705441863914470097077227662211652601803324085660923742365263160 : 89281496541081277276977076535930330329582005484476040255539757979590838221110 : 1)
Order of Twist Curve 1 subgroup generator: 3319
Twist Curve 1 Subgroup order = 22639, Generator = (10021123062458088894446150280359520640128025932612284848351832795773216324717 : 33134482615870340366158544218799569485176944747118922797673428463800194468702 : 1)
Order of Twist Curve 1 subgroup generator: 22639
Twist Curve 1 Subgroup order = 1013176677300131846900870239606035638738100997248092069256697437031, Generator = (43086371182196866264220149108646285325782077581279956481812453050446572867683 : 109763028338610447371257252989326091593538936103419315546844713211988264521923 : 1)
Order of Twist Curve 1 subgroup generator: 1013176677300131846900870239606035638738100997248092069256697437031
Twist Curve 2 Group order = 57896044618658097711785492504343953926299326406578432197819248705606044722122 = 2 * 3 * 20412485227 * 83380711482738671590122559 * 5669387787833452836421905244327672652059
Twist Curve 2 Subgroup order = 2, Generator = (115792089237316195423570985008687907853269984665640564039457584007908834671662 : 0 : 1)
Order of Twist Curve 2 subgroup generator: 2
Twist Curve 2 Subgroup order = 3, Generator = (0 : 1 : 1)
Order of Twist Curve 2 subgroup generator: 3
Twist Curve 2 Subgroup order = 20412485227, Generator = (50449539541316674207477363366507552115465638394234836904449225130473837382091 : 80363753873261753286015549575781926318984919054617925324218269836097034766859 : 1)
Order of Twist Curve 2 subgroup generator: 20412485227
Twist Curve 2 Subgroup order = 83380711482738671590122559, Generator = (83543468359757805417872841911952785816288256608507084865154631040033706800216 : 52903578783579604025064706819317913975696169589285557320540215565103030246608 : 1)
Order of Twist Curve 2 subgroup generator: 83380711482738671590122559
Twist Curve 2 Subgroup order = 5669387787833452836421905244327672652059, Generator = (17259079428563320272860564359789267099765221528537797750223165832777237041052 : 102165722087967769036780071178483201673699309749066796530810114163377241704265 : 1)
Order of Twist Curve 2 subgroup generator: 5669387787833452836421905244327672652059

im feeling like ...so close but yet so far.... thanks for your help. do PM me as well if you wish.

[COBRAS]

i realize we cannot attack the SECP256k1 directly but we could create a twist on the curve by creating another Y coordinate on the twisted curve.

This i had validated for the public key xy that i am working on, i had to first find the correct curve and validate whether the public key x and y generated are valid on the curves.

Code:

from sage.all import *

# Define the prime modulus and the original and twisted curves
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
E_original = EllipticCurve(GF(p), [0, 7])  # Original curve
E_twist = EllipticCurve(GF(p), [0, 2])  # Twisted curve

# Define the public key coordinates in hexadecimal
pubx_hex = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
puby_hex = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"

# Convert hexadecimal coordinates to integers
pubx_int = int(pubx_hex, 16)
puby_int = int(puby_hex, 16)

# Check if negating y coordinate results in a valid point on the twisted curve
try:
    P_twist = E_twist(pubx_int, -puby_int)
    print("Valid point on the twisted curve:", P_twist)
except TypeError as e:
    print("The negated y-coordinate does not result in a valid point on the twisted curve. Error:", e)

then i generate the generators and its group order for the sub group attack

this is a sample code

Code:

p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
E = EllipticCurve(GF(p), [0,2])
Grp = E.abelian_group()
g = Grp.gens()[0]
numElements = g.order()
print( "{0} = {1}".format(numElements, factor(numElements)) )

so i have created the twist and the sub groups, encrypted and decrypt a random message but my problem is implementing the pollard rho. i cannot seems to get my pollard rho working right. how should i implement the pollard rho to reveal the partial private keys? i already know how to combine the partial private keys by using the Chinese Remainder Theorem. im just having issues implementing the Pollard rho correctly.

to understand where i am at currently,

this was my result.

Code:

Valid point on Twist Curve 1: ( xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 1)
Valid point on Twist Curve 1: (xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx: 1)
Encrypted: b'gAAAAABmTUdg-Rk9DqTmm--qHL60H7Y-xyhsMGj-hN9b3nblwwbX1889rW_xkV4YH_CGgLoDfmhUG1kWMLbqBtvkMAkBLA1TpRorPS54bE1tq1GqRI7qBw0='
Decrypted: b'Hello, secure world!'
Valid point on Twist Curve 2: (xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx: 47708717901745451695269673872143322736860462806065126161610255669643023187654 : 1)
Valid point on Twist Curve 2: (xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx: 68083371335570743728301311136544585116409521859575437877847328338265811484009 : 1)
Encrypted: b'gAAAAABmTUdgKPTxiD2aMkmdpCzLWRS6Jf_XoAFbt9Clh-tdswEJ1FDEEHh_sq6afzgwXIRs-eKoEwNUN73OXMbbxIVAtd0X3RzEPgEP2PpfQivQP7qRhls='
Decrypted: b'Hello, secure world!'
Twist Curve 1 Group order = 38597363079105398474523661669562635951234135017402074565436668291433169282997 = 3 * 13^2 * 3319 * 22639 * 1013176677300131846900870239606035638738100997248092069256697437031
Twist Curve 1 Subgroup order = 3, Generator = (0 : 50963827496501355358210603252497135226159332537351223778668747140855667399507 : 1)
Order of Twist Curve 1 subgroup generator: 3
Twist Curve 1 Subgroup order = 169, Generator = (91164871848594737862768174215169171472460815325023337256982466157377582150694 : 54646643330104885507641247315265108556098632006153847263625810111733477892887 : 1)
Order of Twist Curve 1 subgroup generator: 169
Twist Curve 1 Subgroup order = 3319, Generator = (49641695783380705441863914470097077227662211652601803324085660923742365263160 : 89281496541081277276977076535930330329582005484476040255539757979590838221110 : 1)
Order of Twist Curve 1 subgroup generator: 3319
Twist Curve 1 Subgroup order = 22639, Generator = (10021123062458088894446150280359520640128025932612284848351832795773216324717 : 33134482615870340366158544218799569485176944747118922797673428463800194468702 : 1)
Order of Twist Curve 1 subgroup generator: 22639
Twist Curve 1 Subgroup order = 1013176677300131846900870239606035638738100997248092069256697437031, Generator = (43086371182196866264220149108646285325782077581279956481812453050446572867683 : 109763028338610447371257252989326091593538936103419315546844713211988264521923 : 1)
Order of Twist Curve 1 subgroup generator: 1013176677300131846900870239606035638738100997248092069256697437031
Twist Curve 2 Group order = 57896044618658097711785492504343953926299326406578432197819248705606044722122 = 2 * 3 * 20412485227 * 83380711482738671590122559 * 5669387787833452836421905244327672652059
Twist Curve 2 Subgroup order = 2, Generator = (115792089237316195423570985008687907853269984665640564039457584007908834671662 : 0 : 1)
Order of Twist Curve 2 subgroup generator: 2
Twist Curve 2 Subgroup order = 3, Generator = (0 : 1 : 1)
Order of Twist Curve 2 subgroup generator: 3
Twist Curve 2 Subgroup order = 20412485227, Generator = (50449539541316674207477363366507552115465638394234836904449225130473837382091 : 80363753873261753286015549575781926318984919054617925324218269836097034766859 : 1)
Order of Twist Curve 2 subgroup generator: 20412485227
Twist Curve 2 Subgroup order = 83380711482738671590122559, Generator = (83543468359757805417872841911952785816288256608507084865154631040033706800216 : 52903578783579604025064706819317913975696169589285557320540215565103030246608 : 1)
Order of Twist Curve 2 subgroup generator: 83380711482738671590122559
Twist Curve 2 Subgroup order = 5669387787833452836421905244327672652059, Generator = (17259079428563320272860564359789267099765221528537797750223165832777237041052 : 102165722087967769036780071178483201673699309749066796530810114163377241704265 : 1)
Order of Twist Curve 2 subgroup generator: 5669387787833452836421905244327672652059

im feeling like ...so close but yet so far.... thanks for your help. do PM me as well if you wish.

You read a twist attack example on GitHub ?

Dangerous of using twist attack or ....


You need find 1 privkey for selected genpoint order, totals of you order of subgroup mast be N. Not need infinity generator point for twist attack..Then I was on "your place,,," I try with 1 generator point

[krashfire]

Hi everyone. Thank you for messaging me and giving me links. This method has now been solved. I was hinted by 1 of the user here on using the in build function of discrete logarithm problem function within sagemath. i had tested this code on real pubx and puby on a 256 bit keys. it had lead to the real private key. i must say this is the most potent attack. the time taken to solve for private key was within 15minutes.

i will not be sharing the full code here but only to those who had message me and helped me. besides, i dont think i really can, its going to get deleted by the moderators anyways. here is the sample

Code:

 from sage.all import *


p = 115792089237316195423570985008687907853269984665640564039457584007908834671663

E1 = EllipticCurve(GF(p), [0,1])
P11 = E1([85121563011366687025707822879925964033143920255507899862530934382179124106759, 42409656727948788569510737393982221864295921023467166630061319157315739523945])
ord11 = 20412485227


E2 = EllipticCurve(GF(p), [0,2])

P21 = E2([34450129095809207277443089178970023159365999968937291419691966854030888759742, 103113457269188258644933175729489183329932073011449500633910298163941611786454])
ord21 = 3319

P22 = E2([24677754846515895310822934803022252124056730057362245386150209044791887143233, 41719207854450575864606406013013508426241430134433644860265981543689324807921])
ord22 = 22639


E3 = EllipticCurve(GF(p), [0,3])

P31 = E3([93579283295185043256820683457089915228054046133395133419577655037763911527649, 112632096923660630255684142108084503413038643268482102767008195691777477419906])
ord31 = 109903

P32 = E3([58789712228735767534689054670947929274317202597024413724449599685590434047265, 107321344524132116458593462114893821989989072136438106411838048313086057432231])
ord32 = 12977017

P33 = E3([47858481801281315626533839795712036122864957874172974111026342690985232356030, 63537630893779210652619453277142775650521136639503000828326021732442685337139])
ord33 = 383229727


E4 = EllipticCurve(GF(p), [0,4])
P41 = E4([44959049921401095561708555029356671875656137150174062590365663013295388555357, 83434812528180346320431259926231725911951822121210091498845843183726829396473])
ord41 = 18979


E6 = EllipticCurve(GF(p), [0,6])

P61 = E6([80405269462255682739463837712137497998977949201059835857866434498654712080197, 48691579481383569995627909330664108505064081380828260061217816961756876411246])
ord61 = 10903

P62 = E6([12432617283785513902347690216509117019297835774706912333697948746440679211150, 83708142459295252500884287758641092902751782412362742187118587574926797876389])
ord62 = 5290657

P63 = E6([111791420809596458879302671914977681383209776367646894239671494718518178664717, 49961896499747108603390684299676279195265984395588907081892517506172789566751])
ord63 = 10833080827

P64 = E6([68559020522988484359921009775181052297262355171078713712064230001578345410040, 5828734597053595677172176259754174961452737034616688535269967754301263707463])
ord64 = 22921299619447

Q11 = E1([34618671789393965854613640290360235391647615481000045539933705415932995630501, 99667531170720247708472095466452031806107030061686920872303526306525502090483])
Q21 = E2([68702062392910446859944685018576437177285905222869560568664822150761686878291, 78930926874118321017229422673239275133078679240453338682049329315217408793256])
Q22 = E2([36187226669165513276610993963284034580749604088670076857796544959800936658648, 78047996896912977465701149036258546447875229540566494608083363212907320694556])
Q31 = E3([14202326166782503089885498550308551381051624037047010679115490407616052746319, 30141335236272151189582083030021707964727207106390862186771517460219968539461])
Q32 = E3([92652014076758100644785068345546545590717837495536733539625902385181839840915, 110864801034380605661536039273640968489603707115084229873394641092410549997600])
Q33 = E3([13733962489803830542904605575055556603039713775204829607439941608751927073977, 70664870695578622971339822919870548708506276012055865037147804103600164648175])
Q41 = E4([46717592694718488699519343483827728052018707080103013431011626167943885955457, 6469304805650436779501027074909634426373884406581114581098958955015476304831])
Q61 = E6([47561520942485905499349109889401345889145902913672896164353162929760278620178, 23509073020931558264499314846549082835888014703370452565866789873039982616042])
Q62 = E6([54160295444050675202099928029758489687871616334443609215013972520342661686310, 61948858375012652103923933825519305763658240249902247802977736768072021476029])
Q63 = E6([80766121303237997819855855617475110324697780810565482439175845706674419107782, 43455623036669369134087288965186672649514660807369135243341314597351364060230])
Q64 = E6([27687597533944257266141093122549631098147853637408570994849207294960615279263, 8473112666362672787600475720236754473089370067288223871796416412432107486062])



x11 = discrete_log_rho(Q11, P11, ord=ord11, operation='+')

x21 = discrete_log_rho(Q21, P21, ord=ord21, operation='+')
x22 = discrete_log_rho(Q22, P22, ord=ord22, operation='+')

x31 = discrete_log_rho(Q31, P31, ord=ord31, operation='+')
x32 = discrete_log_rho(Q32, P32, ord=ord32, operation='+')
x33 = discrete_log_rho(Q33, P33, ord=ord33, operation='+')

x41 = discrete_log_rho(Q41, P41, ord=ord41, operation='+')

x61 = discrete_log_rho(Q61, P61, ord=ord61, operation='+')
x62 = discrete_log_rho(Q62, P62, ord=ord62, operation='+')

x63 = discrete_log_rho(Q63, P63, ord=ord63, operation='+')

x64 = discrete_log_rho(Q64, P64, ord=ord64, operation='+')


privkey = crt([x11, x21, x22, x31, x32, x33, x41, x61, x62, x63, x64], [ord11, ord21, ord22, ord31, ord32, ord33, ord41, ord61, ord62, ord63, ord64])

print('')

print('Discrete_log_rho:')

print('')

print(x11)
print(x21)
print(x22)
print(x31)
print(x32)
print(x33)
print(x41)
print(x61)
print(x62)
print(x63)
print(x64)


print('')

print('PRIVATE KEY:')

print('')

print(privkey)


f = open("privkey.txt", 'a')
f.write(str(privkey) + "\n")
f.close()

found on https://github.com/demining/CryptoDeepTools/blob/main/18TwistAttack/discrete.py ,

i had followed the format on this script after getting all the information needed for this DLP script to work specific to my public key xy. all i needed was to copy and paste my information. and add verification method to the found private key.

i had check, it is the real private key.

unlike what COBRAS said above, no, you do not need a private key to start this attack, that would made this method a useless attack.

unless you have given a malicious point xy to a person who is sending you btc. its like phishing. then you can follow the tutorial given on github.

but i had modified the code without relying on the private key but shared secrets on twisted curves.

i shall now lock this thread and wish all of you the best of luck in looking for answers to break the ecdsa secp256k1.

i had spent 2 years on understanding this curve in this forum and everywhere else on the net.. so take your time.

ignore those pricks that will insult you and not even help you. they too actually dont know much about network penetration testing but like to pretend that they do.

people i recommend that will help you are names like Wandering_Philosopher, Pooya87, ecdsa123.

My conclusion is whoever told you that the ECDSA SECP256k1 is safe, are out of their minds. it took me 15 mins running the code. thats it.

all those kangaroo algorithm crap is out there, dont waste your time on it. it cant solve for 256 bit keys in reasonable time. again, take care and good luck.

and again im reminding you. study twist attack on ecdsa secp256k1. the rest are useless for a 256 bit keys. dont waste time.

[gmaxwell]

This is a common post pattern people make to trick people into running malware.

Step 1. Have trouble getting things working (perhaps pretending).

Step 2. claim to have some magic attack that works and can recover private keys, explained with a bunch of opaque jargon.

Step 3. When people ask for copies of the tools, send them malware.   Usually the people at step 3 are coin thieves themselves, but not always.


Often these threads will use real terms so simple googling will "confirm" them, but they're misapplied.   A "twist attack" isn't an attack on secp256k1 but a related insecure curve.   You cannot engage in a twist attack except by getting the victim to produce an invalid pubkey or signature using faulty software.  Of course, if you could do that you could likely just have the backdoored code send you the key directly.

The only case  I'm aware of where it's perhaps more interesting is when you have a signing or key-generating device that you can potentially glitch with some kind of fault attack, getting it to temporarily produce a point on the faulty related curve rather than the real one.  Though this is why all such devices ought to verify keys and signatures after generating them, making it harder to ever get a corrupted point out of the device.

[krashfire]

This is a common post pattern people make to trick people into running malware.

Step 1. Have trouble getting things working (perhaps pretending).

Step 2. claim to have some magic attack that works and can recover private keys, explained with a bunch of opaque jargon.

Step 3. When people ask for copies of the tools, send them malware.   Usually the people at step 3 are coin thieves themselves, but not always.


Often these threads will use real terms so simple googling will "confirm" them, but they're misapplied.   A "twist attack" isn't an attack on secp256k1 but a related insecure curve.   You cannot engage in a twist attack except by getting the victim to produce an invalid pubkey or signature using faulty software.  Of course, if you could do that you could likely just have the backdoored code send you the key directly.

The only case  I'm aware of where it's perhaps more interesting is when you have a signing or key-generating device that you can potentially glitch with some kind of fault attack, getting it to temporarily produce a point on the faulty related curve rather than the real one.  Though this is why all such devices ought to verify keys and signatures after generating them, making it harder to ever get a corrupted point out of the device.

Step 1: Libellious

Step 2: its no magic. its just maths.  its not opaque. it has already been explain here. https://github.com/secp8x32/blog/blob/master/2020_05_26_secp256k1_twist_attacks/secp256k1_twist_attacks.md .. Its a good read but dont follow every steps.

Step 3: Then you obviously is not as good as you think. You still got more to learn. Coz your awareness seems to be begging for a reboot.

Step 4: I will be uploading the codes on Github soon. and i think you might need to re-read what  i wrote. i never said its an attack on secp256k1. but thanks for explaining anyways but a simple job like googling would have help anyone here explain better, weak.