LSB 2bit bias

[eychei]

Me again.

I am working on changing some code at: https://github.com/malb/bdd-predicate/

This is code from Heninger et al. and it can solve the HNP down to 2 bit bias. Maybe you want to look into that?

Can not get the LSB function to work with that code. Would be great if you could join the discussion. Your code does have the LSB function integrated and I would appreciate your help. I can not figure out how to shift the data so the LLL matrix gets the right nonce vector.

Best Wishes -e

[bitlogik]

Before digging down to help you on a third-party topic, here's some info about LSB with LatticeAttack : Each "kp" is an integer in the range is [ 0 : 2**KnownBits - 1 ] 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 the topic "down to 2 bits", note that we never found a private key using our LatticeAttack software below 4 know bits, hence the restriction put in place that prevent the user to run it with lower than 4 bits. But we never performed long running time. Using higher RECOVERY_SEQUENCE "effort" block size, combined with a loop "-l" can be a way to recover key with 3 or even 2 bits. That would just require long running times (several hours), and no guarantee of result.

[eychei]

Thanks for the clarification. I will adapt the code and see what happens. If I understand this correctly I just have to mask the input signatures (not the msgs) and the resulting vector of the LLL Matrix should be the nonce? I am using the LLL Matrix suggested by Heninger et al. . According to her comment on github, I would need to shift the signatures and at the end shift back the calculated nonce. This is not the case in your solution right?

-e

[eychei]

Looking at your code and implementing the LLL Matrix in my own code I am now able to calculate with LSB bias. Thank you for the help. Why is it that the matrix is returning the priv_key and not the nonce in row[-2]?

-e

[bitlogik]

I just have to mask the input signatures (not the msgs) and the resulting vector of the LLL Matrix should be the nonce?

No, the HNP for ECDSA, you know partial information about the nonces, and you know all signatures and their message (plus the public key). The masks only apply to the nonce, but usually, as we know partial data, there's no need to mask anything. Read the scientific material we provide in the Readme bibliography. They provide lots of details on the HNP method.

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.

Why is it that the matrix is returning the priv_key and not the nonce in row[-2] ?

See Minerva paper §4.4, LatticeAttack is using SVP method with the "recentering" optimisation, and random subset.

Some HNP lattice are built with one variable less. That is sometimes referred as the "Eliminating One Variable" optimization, a way to reduce the lattice dimension, with the elimination of a variable from the system : the private key is discarded, for "equation relatives". That gives a little boost to the lattice reduction solving, as the dimension is decreased by 1. This slightly decrease the matrix reduction time, at the expense of very complex and iterative computations to build the matrix, and then to recover the private key. So LatticeAttack is not using this optimization, we estimate it brings more complexity for a very small speedup. Even the matrix speed up can be lost by the "outer" computations added. Still, this optimization can be effective when doing EHNP, because this involves very large matrix, and it gains one dimension for every hole/parts. LatticeAttack is not doing EHNP for now. You can read further details about EHNP and optimizations in this publication §3.3. Side Journey to Titan is also using this "one less variable" optimization, as they have to use EHNP.