kp is the **known leaked part of the internal eHello!Please explain.I have generated a dummy data file.json 1500 signatures,MSB 4 bit and inserted my Pubkey x,y and r,s there. Should I leave the hash as it is?phemeral nonce** during ECDSA. As this is supposed to be an internal secret, it can be read using a side channel. As it is a protected secret, sometimes we don't get it fully, but only a part, the starting bits, or the last bits. That's the exact purpose of LatticeAttack. If you know the nonce in full, you don't need LatticeAttack, as a simple computation using one signature leads to the private key. But if you only know start (or end) of the nonce for a couple of signatures, then LatticeAttack can provide the secret key. #29
kp is the **known leaked part of the internal ephemeral nonce** during ECDSA. As this is supposed to be an internal secret, it can be read using a side channel. As it is a protected secret, sometimes we don't get it fully, but only a part, the starting bits, or the last bits. That's the exact purpose of LatticeAttack. If you know the nonce in full, you don't need LatticeAttack, as a simple computation using one signature leads to the private key. But if you only know start (or end) of the nonce for a couple of signatures, then LatticeAttack can provide the secret key.
kp represents the known value of the leaked bits of the internal secret nonce for a given signature. kp means "k partial".
Examples : LSB known (bits at the end) for "k" are 0b000101 for a given signature :
{ "hash": xxx, "r": xxx, "s": xxx, "kp": 5 }
In case you get MSB (bits at the beginning), kp shall be provided reduced like LSB, means only the known bits :
0b000101... -> "kp": 5
If the known bits are all 0 : "kp":0, because the known value is 0. Now I think you understand why changing this value doesn't' work. You need the real value of the known part.
Note : "hash" needs to be provided as integer in the signatures data when there's no "message" key. That means each signature has its own hash. Alternatively, if the exact same message was signed multiple times (all message/hash are same), then "message" can be provided once at the info top level, and the hash will be computed.
we need about 80 sigs for find PVK, as example, for received correct kp of 80 sigs (ex. 'kp':2) we need around 1500 tx, in this 1500 tx we guarantee received 80 sigs of any kp for 4 bits
How does it work usually? Lets say you only get 4 bits of nonce k, and pvkey being 256 bits. The number of signatures required is roughly the number of bits "summed" up to 256 bits = 256/4. But there are margin, like 4/3 theoretical, and LatticeAttack even adds 3% as a margin. You need apprx 4/3 256/4 1,03 = 88 signatures (for each you know partial k, 4 bits).
On top of that, usually, when listening to a side channel, we only detect when all the bits are 0 (or any particular value, among all the possible values). 0b0000 is 1 value over 16 different (2^4), so for every signature, you have 1 over 16 chances to get the value you can detect. And you need 88 signatures with a known value (kp). It is like 15 times over 16 you cant read the kp value. At the end it means you need to perform 88*16 = 1376 signatures "statistically" to get the minimum number of data to perform a recovery.
So yes, if your system you can detect only 4 bits, when 0000, so 1 over 16 signatures can extract the leading bits. You need something like 1500 signatures, then it provides approx 90 signatures with valid data (known k, kp), and this amount will lead to a private key finding. In this example kp=0, in case you can only detect kp equals to 0 (all bits are 0).
kp represents the known value of the leaked bits of the internal secret nonce for a given signature. kp means "k partial". Examples : LSB known (bits at the end) for "k" are 0b000101 for a given signature : { "hash": xxx, "r": xxx, "s": xxx, "kp": 5 }
In case you get MSB (bits at the beginning), kp shall be provided reduced like LSB, means only the known bits : 0b000101... -> "kp": 5
If the known bits are all 0 : "kp":0, because the known value is 0. Now I think you understand why changing this value doesn't' work. You need the real value of the known part.
Note : "hash" needs to be provided as integer in the signatures data when there's no "message" key. That means each signature has its own hash. Alternatively, if the exact same message was signed multiple times (all message/hash are same), then "message" can be provided once at the info top level, and the hash will be computed.
How does it work usually? Lets say you only get 4 bits of nonce k, and pvkey being 256 bits. The number of signatures required is roughly the number of bits "summed" up to 256 bits = 256/4. But there are margin, like 4/3 theoretical, and LatticeAttack even adds 3% as a margin. You need apprx 4/3 256/4 1,03 = 88 signatures (for each you know partial k, 4 bits).
On top of that, usually, when listening to a side channel, we only detect when all the bits are 0 (or any particular value, among all the possible values). 0b0000 is 1 value over 16 different (2^4), so for every signature, you have 1 over 16 chances to get the value you can detect. And you need 88 signatures with a known value (kp). It is like 15 times over 16 you cant read the kp value. At the end it means you need to perform 88*16 = 1376 signatures "statistically" to get the minimum number of data to perform a recovery.
So yes, if your system you can detect only 4 bits, when 0000, so 1 over 16 signatures can extract the leading bits. You need something like 1500 signatures, then it provides approx 90 signatures with valid data (known k, kp), and this amount will lead to a private key finding. In this example kp=0, in case you can only detect kp equals to 0 (all bits are 0).
Originally posted by @bitlogik in https://github.com/bitlogik/lattice-attack/issues/21#issuecomment-1367314274