LSB 0 bit bias

[eychei]

Hello Martin,

after some work with WSL and Debian I was able to get sage and g6k working.
Some of your instructions did not work for me. I had to try different routes but succeeded at the end.
Your scripts works great. Thank you for that. (Docker image does not work for me).

Reading through the paper of de Micheli and Heniger et al. I expected that the LSB bias HNP would be as easy as the MSB bias.
They state that a bitshift is everything that is needed to use the LSB bias in the MSB bias matrix. I tested every possible way to try this but I did not succeed in getting this to work.

Maybe you have a hint for me.

Danke dir.

Best wishes

-e

[factorable]

If you know your nonce k = 2^z k' where z is the number of zero least significant bits and k' which is small, then you can multiply your signature relation (sk = h+xr mod n) by 2^{-z} on both sides, and obtain a new relation written in terms of k'. I don't think you'll be able to use our code as a black box to solve this without going into the internals of the code. You can probably get the lattice basis to contain the desired solution by multiplying the r and h in the signature input data by 2^{-z}. But then this will cause the check for the correct solution (which verifies that the x coordinate of kG on the curve for the candidate k coming from the lattice vector is r) to fail. So you will need to write a new predicate function that inputs a candidate k' from the lattice, multiplies it by 2^z to get a candidate k, and checks whether the x coordinate of the value kG on the curve matches the original r.

[eychei]

Wow that was fast.
Thanks for the response and the work you have put into this research.

Checking the formula and trying to calculate the new relation k' I get:
t' = -inv_s1 s2 r1 inv_r2
u' = inv_s1 r1 inv_r2 h2 2^(-z) - inv_s1 h1 2^(-z)

putting this into my matrix for 8bit shift like so:

t=-(modular_inv(sigs[i][1], order)*sigs[i][0]snrn_inv)
u=((modular_inv(sigs[i][1], order)sigs[i][0]mnrn_inv2(-8)) - (modular_inv(sigs[i][1], order)*msgs[i]2(-8)))

then reversing the shift like this:

potential_nonce = row[0]
potential_nonce = potential_nonce*2**8

This should work right? It does not for me. Maybe I am just missing something else...

Also in your code checking the predicate function I see the check:

        if (kG + G_powers[w]).xy()[0] == r:
            return True
        elif (-kG + G_powers[w]).xy()[0] == r:
            return True
        else:
            return False

But where is the output of the lattice where the first row should be my k' values? I would then just shift k' back and the check should work again right?

Thanks again for the help.

-e

[factorable]

The predicate function takes in a vector v and in this case is checking the value of the first coordinate to see if it matches the r value from the first signature. The multiplication and unshifting in the code are a bit confusing because we precompute the scalar multiplications on the curve to speed up the predicate check.

I'm not going to be able to debug your code for you. Your best bet is to go through and verify your values on a known test example at every step.

[eychei]

Hello,

thank you for the help so far. I was able to implement the LSB Shift into my own code and it is working.

Looking at the matrix generation in your code I can see that it is not as easy to implement. But I will try to see if I can get it to work and post an update.

Best Wishes
-e