known_bits and kp

[fitzjalen]

Hello!
I cannot understand how to fill data.json with my parameters.
First of all I can't understand how can I find known_type, known_bits and kp?
And hash in data.json is transaction hash or z?

 R: 02cf4753908805e913dee644e19fd43d40c69d28f321e3cf832b8908d99f07c4
 S: 5cd318ea86c93b955501d57c6228c0ef5b411a72ceccd8f5c4e751f4e7a486cb
 Z: f6bed3403ab21d8054b7c266a552eadbb2d5a73d3240c74f4bdb46a489ecaa99

PubKey: 0445952f99b777cbd57a9d03eb5196dd97622668f5bb6f4190d882a6a3987b0a4474109a96cd8949056267f928994d2c36a4f239d2e0b54e87667a37fe19244020

Transaction info:
hash: 08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f

So, can you please clarify me how to fill data.json with parameters I have?

[bitlogik]

The use case of LatticeAttack is to compute the private key from a set of EC digital signatures, knowing some part of the internal signature nonce (ephemeral "k").
So you know partial information about the internal nonces, and you know all signatures and their message (plus the public key).
For LatticeAttack, one has to provide for each signature the "kp" integer, the known part of kp, in the format explained. In practice, this is often 0, when the read detected bits are all zeros.
To recap, this software can work with any system where you have / you know :

• ECDSA (with "SECP224R1", "SECP256K1", "SECP256R1", "SECP384R1" or "SECP521R1" curve)
• A public key
• A set of signatures done by this key pair
• The partial information about the ephemeral random internal secret nonce (from a side channel, or "internal" info) for each of these signatures.

As soon as you get a set of signature (for a given public key), and with their corresponding ephemeral random internal secret ECDSA number partial info (MSB or LSB), you can use lattice-attack to recover the private key.

In practice. You input the "partial k info" as follow :
"known_type": known bits type : MSB or LSB, default to "LSB". Do you know the final end or the bits at the start?
"known_bits": is an integer, number of know bits in each "k" (ephemeral internal nonce)
"kp": an integer in the range is [ 0 : 2**KnownBits - 1 ], representing the known value of the ephemeral nonce.

Example if the LSB known for "k" are 0b00101 for a given signature:
-> { "hash": xyz, "r": xxx, "s": xxx, "kp": 5 }
So basically, for LSB, there is no shift at all, and you provide the known bits for each signature as an integer. You can even write the 0bxxx in the code so they're binary provided.
To get the LSB from the full nonce, the best option is to use a simple mask as the maximum value, for example with 5 bits, your mask the full nonce with 0b11111, which is 31 : nonce & 31.
Also you can get the LSB from the full nonce with modulo 2**known_bits, in the example of 5 bits : nonce % 32.
For MSB, you need to provide the known "upper" bits. Means you shift them to reduce as only to provide these bits. Ex : 0b00101..... -> kp: 5.

About the hash :
There are 2 ways to provide the message or hash in the input data for LatticeAttack.
Single common message
In the case the message is the same for all the signature, this needs to be provided as a binary string message (not the hash, before hashing). The format is an integer list/tuple or bytes/bytesarray. The key is top-level "message".
The hash used is SHA2-256 for the hash. Hence it works only for ECDSA using SHA2-256 hash.
Per signature message
In the case the message is unique per signature. The data to provide is an integer. The hash value is provided in the "hash" key in each signature object. The integer is the value of the binary bytes in big endian : from_bytes(h, "big").

About the public key
You need to input the key as a 2-integers array representing the coordinates of the point : [x, y]
In your case, you need to decode the X9.62 uncompressed format into x and y integers. This encoding format is basically 04 x y.

I don't fully understand what is Z, how it relates to the known nonce. I bet this is related to Z being a cube root or similar, so you can figure out some information about "k". Anyway, you need to figure that out yourself and proceed to compute the recovered information in term of the ECDSA nonce. Then you can use this software. Else, if you know nothing about the internal nonce, LatticeAttack might not be the right tool.

For further details, you can look at the this file source, it can help into decoding into the target input. Because this file generates dummy data for an example, so it does the work to convert into the LatticeAttack expected format.
Also this real example code provided can give details and practical clues on how to generate data in the right format for this software.

As always, we can provide further help on all this matter. This is out of scope of the free support on how to use it, fixing bug, installation support, etc... You can reach us at [email protected], and we'll provide a quotation and a schedule for the work.

[bitlogik]

In case your Z is the full secret nonce, the Lattice ECDSA Attack software is not designed for that. In this case, all you have to do is to compute d = ( s.Z - H ) . r^-1 where (r,s) is the signature duet, Z the secret nonce, H the hash, and you get the private key (d). See more details here. This software is designed to recover the private key from a hundred of signatures when only a part of the nonce is known (first bits, or last bits) for each signature.

[kpot87]

@bitlogik how you retrieved H(m) from transaction? Tnx

PS what does it mean xyz “ "hash": xyz”, mult pubX,PubY and Z?

[bitlogik]

Usually, from a blockchain transaction, the hash H(m) is recomputed from the transaction message. The data signed is built from the transaction data, then hashed to get the hash value of the transaction. Sometimes also the tx hash is directly the H (in case the tx hash doesn't include the signature).

what does it mean xyz “ "hash": xyz”, mult pubX,PubY and Z?

No, in our example { "hash": xyz, "r": xxx, "s": xxx, "kp": 5 }, "xyz" is just a single integer value, like xxx. Nothing related with Z nor Y.

[kpot87]

Usually, from a blockchain transaction, the hash H(m) is recomputed from the transaction message. The data signed is built from the transaction data, then hashed to get the hash value of the transaction. Sometimes also the tx hash is directly the H (in case the tx hash doesn't include the signature).

what does it mean xyz “ "hash": xyz”, mult pubX,PubY and Z?

No, in our example { "hash": xyz, "r": xxx, "s": xxx, "kp": 5 }, "xyz" is just a single integer value, like xxx. Nothing related with Z nor Y.

Thank you for your answer! Ok just for education purpose, you know that in standart settings 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, if i gen_data 1500 sigs and changed in json file all kp to 2 ('kp':2), lattice attack didnt work. can you explain why? if you know, it interesting for me. Thank you!

[bitlogik]

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).