lattice-attack || how to run without error - page 6.

COBRAS

member

Activity: 846

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: stanner.austin on April 25, 2022, 08:20:30 AM

@ymgve2
To generate fake r,s,z you can use public point and calculate 2 random and add it.
For example G is ecdsa SECP256k1 generator, PublicKey is ecdsa point, N is order

u = randint(1, N)
v = randint(1, N)
r = (u*G+v*PublicKey).x.num % N;
s = r * pow(v, N-2, N) % N
z = u * s % N

Now you have valid r,s,z pair for that public key.

@fxsniper
lattice attacks script leak 6 bit when use gen_data.py but you can use 4 bit too its minimum and 100 r,s,z,leak data need else this attack will not work.
Still there is no way to leak or know 4 bit even for generated or original signed R.

I thinnk posible try with MSB OR LSB 0000 OR 0000 0000

Z IS a sighned message, i thin it is in data(i dont remember exact)

garlonicon

hero member

Activity: 789

Merit: 1909

Quote

With that method, you don't know anything about the nonce, since it would be k = u + v*priv and you don't know the private key. So it will not be weak, and useless for lattice attacks.

You are almost right. Almost, because you can try using non-random values and see, what would happen then, and why it can be useful for some attacks.

ymgve2

full member

Activity: 161

Merit: 230

Quote from: stanner.austin on April 25, 2022, 08:20:30 AM

@ymgve2
To generate fake r,s,z you can use public point and calculate 2 random and add it.
For example G is ecdsa SECP256k1 generator, PublicKey is ecdsa point, N is order

u = randint(1, N)
v = randint(1, N)
r = (u*G+v*PublicKey).x.num % N;
s = r * pow(v, N-2, N) % N
z = u * s % N

Now you have valid r,s,z pair for that public key.

@fxsniper
lattice attacks script leak 6 bit when use gen_data.py but you can use 4 bit too its minimum and 100 r,s,z,leak data need else this attack will not work.
Still there is no way to leak or know 4 bit even for generated or original signed R.

With that method, you don't know anything about the nonce, since it would be k = u + v*priv and you don't know the private key. So it will not be weak, and useless for lattice attacks.

stanner.austin

member

Activity: 66

Merit: 53

@ymgve2
To generate fake r,s,z you can use public point and calculate 2 random and add it.
For example G is ecdsa SECP256k1 generator, PublicKey is ecdsa point, N is order

u = randint(1, N)
v = randint(1, N)
r = (u*G+v*PublicKey).x.num % N;
s = r * pow(v, N-2, N) % N
z = u * s % N

Now you have valid r,s,z pair for that public key.

@fxsniper
lattice attacks script leak 6 bit when use gen_data.py but you can use 4 bit too its minimum and 100 r,s,z,leak data need else this attack will not work.
Still there is no way to leak or know 4 bit even for generated or original signed R.

fxsniper

member

Activity: 406

Merit: 45

I try to test with private key 120-bit script can fine 120-bit key (just modify the script random number from curve 256bit to random 120 bit)

if like to test with puzzle 120 how to implement to hash (z)

in the sample, file generate data.json have only R and S and 8bit leak nonce
What is the data message at the end file on data.json

it is just for testing (possible not works)

ymgve2

full member

Activity: 161

Merit: 230

Quote from: garlonicon on April 22, 2022, 03:32:47 PM

Quote

Realy ? Generate someonevfakecrsz please forvwalid bupkey, and for ex valid s...

No problem. There are fake r,s,z values for the public key from the Genesis Block:

Quote

Code:

fake_signatures.py 04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f
981c008269574d9bb73a2e781270e2163297b3d3ca9645b5e0664ffcbb19e78a,3cc2a888bae4811e75e64e19f2ce668951a3520e93e31a74b4cd4e9ce9508839,ed97aea4f9b66aca0c41ac88c2f0d90ef2ad269af0951ba2b07c70f7d1542b3c
53b9632a4250eb518426a545daa99fc6a72addfcb62714fbe81e269cd9ee39e8,62cbe3cc5eec2cbcbf61793a1d94414b43536c0e9219da703be5f141c46fa364,166db19e268d41b8cb76eedb50c57969635bcce2218b1921df45656a24de751a
a050e9237241c02d17684df9b9039fd707fcecb2fbd9d46af95dfeb6ef1daaa3,5e3bd1a08a7418066e4231adbfa23cc969617bb67f35a5f9a4d1ebae9a196fc7,a20a81207eb5aa382759debfc3ca98d4a3cf85474c9dbb6684dbd5bae3abe58d
9f2e42881a9cd3ddd088ebc77857beb9929c42e76e3b3ab7d1928652d2b731cf,0a4353b1fe7c167d63eaa45aeb23f83d219fd31ca74a17adc84cb18bc3184833,32a9cacbb64e5679eb40dfca1192bccc3db0e19d63d1e68286fe119d7d494c8a
a46f5889983efb70e00927f5afeeb2c4042783ca36525968657e339416a6bd8d,185c697570158909298fb10019d7a3e62ed647e9a6ecd1992f3d3098a498eec9,dcd110dd05f2ef9bb46639b0abe858a545bc61f1cd0e5462f41e7003d5f68bba
8ca48464e4dd3789ec41b83827b93e840471cfce2c8e6349e4087f56c335991f,6fb96292e9a2e5480085d9b8f69bd6aa62cee3b76b090cd5d5e25f8ce253adea,b6b20ab75d2ad6e8e79fe3fdc9e28a66e2a6acecfe87a7f33cb5c3fba1d070d3

Those signatures are only fake, because there is no known transaction that can be hashed to any of this z-value. That's the only reason, but from lattice point of view, they are as good as any real signatures, there is no difference in this attack, because knowing relations between nonces or some bits of private keys or nonces is more important than having a real signature.

So, if you want to break for example puzzle 120, you don't need two real weak signatures. You need two any weak signatures, that are valid from ECDSA point of view, and that will pass lattice attack (because you cannot use for example N and N-1, they are too close and if one signature will be a tweaked version of another one, it will obviously not work). You don't need any real transaction that can be hashed to z-value, because after breaking the private key, you could make it and sign it from scratch.

How did you generate those fake signatures, though? I'm assuming you did some manipulation of an existing signature, which means the new signatures will have a linear relationship with the original and each other, making them useless for lattice attacks. Are they even weak, or does the process generate a completely random unknown nonce?

stanner.austin

member

Activity: 66

Merit: 53

@garlonicon
above example is leak known bit atlast 4 bit need, with min 90 sign else attack will not work.
so each r,s with 0 to 15 (4 bit) need to be test.
each result with 90 sign look like lot of processing power need for this.

if possible to design Matrix to test each 4 bit with each pair of r,s then may be this attack is possible.
but i don't think this possible. is it ?

COBRAS

member

Activity: 846

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: fxsniper on April 23, 2022, 01:43:53 AM

I try to learn and understand math
Did I understand correctly?
this script method use leak nonce that generates to recover private key right?
script it not use way collect data from all data from signature with?
this lattice-attack use only one signature with leak 8-bit leak nonce to calculate correctly?
just loop search from 1000 signature until found one can calculate

You have a scrypt with "loop" ? I can provide file rsz sighnatures from any bitcoin afress with outgoin trsnsactions....

litecoin_messiah

sr. member

Activity: 355

Merit: 268

https://youtu.be/RgbrpmJ49r4

garlonicon

hero member

Activity: 789

Merit: 1909

Quote

this script it is the same of lattice-attack or not

Yes, it is. You can even use the same signatures and import them to your python script to see, that it will also find the same private key.

Quote

I see it is using LLL and reduction same

Yes, because LLL is the first step in your python script.

Quote

from sample how can expand the matrix to very large enough can search number

You can find the source article for the page you mentioned in your post: https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-care/

Quote

sorry I do not yet understand clear in math of lattice algorithms

Keep reading, take your time. ECDSA, lattice attacks, hash functions, all of those things belong to advanced maths, so it is normal that it takes some time to learn.

fxsniper

member

Activity: 406

Merit: 45

this script it is the same of lattice-attack or not
https://asecuritysite.com/signatures/ecd
I see it is using LLL and reduction same
from sample how can expand the matrix to very large enough can search number
sorry I do not yet understand clear in math of lattice algorithms

garlonicon

hero member

Activity: 789

Merit: 1909

Quote

this script method use leak nonce that generates to recover private key right?

Yes.

Quote

script it not use way collect data from all data from signature with?

You only need a public key and r,s,z values. They don't have to be collected from real transactions, they only have to be correct from ECDSA point of view.

Quote

this lattice-attack use only one signature with leak 8-bit leak nonce to calculate correctly?

The number of bits is configurable, you can set it to any value you want. And based on that number of leaked bits, you need more or less signatures to run this code.

Quote

just loop search from 1000 signature until found one can calculate

No, this code doesn't work for 1000 signatures. It is focused on a small number of signatures. If you provide more of them, then some of them will be picked randomly. If you have a lot of known bits, then one signature is enough. If you have less, then maybe two, maybe three. There is a function in this code that can tell you how many signatures you need, it depends on how many bits are known. But the maximum is somewhere around 100 as far as I can tell, using more signatures will cause it to pick some of them and work on a smaller number of signatures.

fxsniper

member

Activity: 406

Merit: 45

I try to learn and understand math
Did I understand correctly?
this script method use leak nonce that generates to recover private key right?
script it not use way collect data from all data from signature with?
this lattice-attack use only one signature with leak 8-bit leak nonce to calculate correctly?
just loop search from 1000 signature until found one can calculate

garlonicon

hero member

Activity: 789

Merit: 1909

Quote

Realy ? Generate someonevfakecrsz please forvwalid bupkey, and for ex valid s...

No problem. There are fake r,s,z values for the public key from the Genesis Block:

Quote

Code:

fake_signatures.py 04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f
981c008269574d9bb73a2e781270e2163297b3d3ca9645b5e0664ffcbb19e78a,3cc2a888bae4811e75e64e19f2ce668951a3520e93e31a74b4cd4e9ce9508839,ed97aea4f9b66aca0c41ac88c2f0d90ef2ad269af0951ba2b07c70f7d1542b3c
53b9632a4250eb518426a545daa99fc6a72addfcb62714fbe81e269cd9ee39e8,62cbe3cc5eec2cbcbf61793a1d94414b43536c0e9219da703be5f141c46fa364,166db19e268d41b8cb76eedb50c57969635bcce2218b1921df45656a24de751a
a050e9237241c02d17684df9b9039fd707fcecb2fbd9d46af95dfeb6ef1daaa3,5e3bd1a08a7418066e4231adbfa23cc969617bb67f35a5f9a4d1ebae9a196fc7,a20a81207eb5aa382759debfc3ca98d4a3cf85474c9dbb6684dbd5bae3abe58d
9f2e42881a9cd3ddd088ebc77857beb9929c42e76e3b3ab7d1928652d2b731cf,0a4353b1fe7c167d63eaa45aeb23f83d219fd31ca74a17adc84cb18bc3184833,32a9cacbb64e5679eb40dfca1192bccc3db0e19d63d1e68286fe119d7d494c8a
a46f5889983efb70e00927f5afeeb2c4042783ca36525968657e339416a6bd8d,185c697570158909298fb10019d7a3e62ed647e9a6ecd1992f3d3098a498eec9,dcd110dd05f2ef9bb46639b0abe858a545bc61f1cd0e5462f41e7003d5f68bba
8ca48464e4dd3789ec41b83827b93e840471cfce2c8e6349e4087f56c335991f,6fb96292e9a2e5480085d9b8f69bd6aa62cee3b76b090cd5d5e25f8ce253adea,b6b20ab75d2ad6e8e79fe3fdc9e28a66e2a6acecfe87a7f33cb5c3fba1d070d3

Those signatures are only fake, because there is no known transaction that can be hashed to any of this z-value. That's the only reason, but from lattice point of view, they are as good as any real signatures, there is no difference in this attack, because knowing relations between nonces or some bits of private keys or nonces is more important than having a real signature.

So, if you want to break for example puzzle 120, you don't need two real weak signatures. You need two any weak signatures, that are valid from ECDSA point of view, and that will pass lattice attack (because you cannot use for example N and N-1, they are too close and if one signature will be a tweaked version of another one, it will obviously not work). You don't need any real transaction that can be hashed to z-value, because after breaking the private key, you could make it and sign it from scratch.

COBRAS

member

Activity: 846

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: garlonicon on April 21, 2022, 11:51:52 PM

Quote

R,s,z is only for outgoing transaction !!!

Yes. But you can always use fake outgoing transaction and choose some z-value, where you don't know any matching transaction. For some attacks, this approach is also useful, even if you don't know any transaction that can use your signature. In lattice attacks, you can use any z-value, you don't care about transactions, because restoring keys is the only thing you can do in such attack, so fake z-value is also useful.

Realy ? Generate someonevfakecrsz please forvwalid bupkey, and for ex valid s... For crack aftervthis sighnatures ? Original rsz is 99% imposible to crack because different lenght if r,s,z - from x...to ..y for 1 pubkey etc...

litecoin_messiah

sr. member

Activity: 355

Merit: 268

don't we use secp256k1 this is r1

garlonicon

hero member

Activity: 789

Merit: 1909

Quote

R,s,z is only for outgoing transaction !!!

Yes. But you can always use fake outgoing transaction and choose some z-value, where you don't know any matching transaction. For some attacks, this approach is also useful, even if you don't know any transaction that can use your signature. In lattice attacks, you can use any z-value, you don't care about transactions, because restoring keys is the only thing you can do in such attack, so fake z-value is also useful.

COBRAS

member

Activity: 846

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: fxsniper on April 21, 2022, 01:43:22 AM

Quote from: garlonicon on April 20, 2022, 01:50:23 PM

So, let's see:

First signature:

Second signature:

Thank you garlonicon
I try to understand math (still stuck with calculate by manual step by step)

R,s,z is only for outgoing transaction !!!

fxsniper

member

Activity: 406

Merit: 45

Quote from: garlonicon on April 20, 2022, 01:50:23 PM

So, let's see:

First signature:

Second signature:

Thank you garlonicon
I try to understand math (still stuck with calculate by manual step by step)

garlonicon

hero member

Activity: 789

Merit: 1909

Quote

Can you help to samplecalculate puzzle #115

So, let's see:

Code:

address=1NLbHuJebVwUZ1XqDjsAyfTRUPwDQbemfv
pubkey=0248d313b0398d4923cdca73b8cfa6532b91b96703902fc8b32fd438a3b7cd7f55
sig1=3045022100c3f5243089c5fc55cb215bb54d6e94f1fb09820a3e917cf52633ab9a5cea20af02207efcf46cbcad512b19d0b72788f21e63d4ccffb2c21f98638176f7816c87ebd301
der1a=3045022100
r1=c3f5243089c5fc55cb215bb54d6e94f1fb09820a3e917cf52633ab9a5cea20af
der1b=0220
s1=7efcf46cbcad512b19d0b72788f21e63d4ccffb2c21f98638176f7816c87ebd3
sighash1=01
sig2=30440220228e890f24db246b0220b0491c78a6f186dcdcb5a927a3b86ffd3b0b03fe6e2602203b4f5ae90419881143e4185820e63616b92d1f394e9414a89d79bc7b90a1c5d001
der2a=30440220
r2=228e890f24db246b0220b0491c78a6f186dcdcb5a927a3b86ffd3b0b03fe6e26
der2b=0220
s2=3b4f5ae90419881143e4185820e63616b92d1f394e9414a89d79bc7b90a1c5d0
sighash2=01

First signature:

Code:

Q=0248d313b0398d4923cdca73b8cfa6532b91b96703902fc8b32fd438a3b7cd7f55
d=0000000000000000000000000000000000060f4d11574f5deee49961d9609ac6
transaction1=020000000215cda65f1e46982fc082b15c8dbb60985d12a7e60b0c742263608cc9349f3808720000001976a914ea0f2b7576bd098921fce9bfebe37f6383e639a488acfdffffff6441384445a0f426ee689e2532e41fc6947dda41558026b80f5b1dfd7c58455d3f00000000fdffffff01f792da0600000000160014d66c2e960c57e689ffa24142bc94636a54eb2ea669b0090001000000
z1=SHA-256(SHA-256(transaction1))=2294cb823a880052d1513223d3c078f8518e277373d40b43ada4a07afa045159
r1=c3f5243089c5fc55cb215bb54d6e94f1fb09820a3e917cf52633ab9a5cea20af
s1=7efcf46cbcad512b19d0b72788f21e63d4ccffb2c21f98638176f7816c87ebd3
k1=(z1+r1d)/s1
n=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
r1d=534d2b5e5932693b7dd30266d83afdd17ef2433f4498395c8f95b959fa4ad0ae
z1+r1d=75e1f6e093ba698e4f24348aabfb76c9d0806ab2b86c44a03d3a59d4f44f2207
1/s1=582ac1bddcecd0488fb1cdded830126ef1246df1888b6495c564604613618179
k1=3a974e9b3b1015f5bf711dc34e53fe95dc1ee2183e938e32f3bd34ce7e4b9fad
k1*G=02C3F5243089C5FC55CB215BB54D6E94F1FB09820A3E917CF52633AB9A5CEA20AF
r1=c3f5243089c5fc55cb215bb54d6e94f1fb09820a3e917cf52633ab9a5cea20af
r1=(k1*G).x (valid)

Second signature:

Code:

Q=0248d313b0398d4923cdca73b8cfa6532b91b96703902fc8b32fd438a3b7cd7f55
d=0000000000000000000000000000000000060f4d11574f5deee49961d9609ac6
transaction2=020000000215cda65f1e46982fc082b15c8dbb60985d12a7e60b0c742263608cc9349f38087200000000fdffffff6441384445a0f426ee689e2532e41fc6947dda41558026b80f5b1dfd7c58455d3f0000001976a914ea0f2b7576bd098921fce9bfebe37f6383e639a488acfdffffff01f792da0600000000160014d66c2e960c57e689ffa24142bc94636a54eb2ea669b0090001000000
z2=SHA-256(SHA-256(transaction2))=98399882da0936868e7d21e7c971d8896d0897b99d8c141e6bf679ee829e9835
r2=228e890f24db246b0220b0491c78a6f186dcdcb5a927a3b86ffd3b0b03fe6e26
s2=3b4f5ae90419881143e4185820e63616b92d1f394e9414a89d79bc7b90a1c5d0
k2=(z2+r2d)/s2
n=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
r2d=bb719705669b86f216fdef762715302bd7afa1e4985b206f5e06ed09121757be
z2+r2d=53ab2f8840a4bd78a57b115df08708b68a095cb7869e94520a2b086ac47faeb2
1/s2=c1c01cfeefcba2cc824751307b5964e292f602cc05dfa8f6bc359850dd726a6d
k2=0656c9a7c7bb58c5b632cb88ac6a42d7e224f3595077e100f10c0d72622612fc
k2*G=02228E890F24DB246B0220B0491C78A6F186DCDCB5A927A3B86FFD3B0B03FE6E26
r2=228e890f24db246b0220b0491c78a6f186dcdcb5a927a3b86ffd3b0b03fe6e26
r2=(k2*G).x (valid)

Topic: lattice-attack || how to run without error - page 6. (Read 2848 times)