3
$\begingroup$

I know the theory of lattice attacks against ECDSA from Minerva. So, as far as I can understand, the lattice that they build is

$$ L_M = \begin{bmatrix} 2^ln & 0 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 2^ln & 0 & \cdots & 0 & 0 & 0 \\ 0 & 0 & 2^ln & \cdots & 0 & 0 & 0 \\ & \vdots & & \vdots & & \vdots \\ 0 & 0 & 0 & \cdots & 2^ln & 0 & 0 \\ 2^l t_1 & 2^l t_2 & 2^l t_3 & \cdots & 2^lt_d & 1 & 0 \\ 2^l u_1 & 2^l u_2 & 2^l u_3 & \cdots & 2^lu_d & 0 & n \end{bmatrix} $$

where $t_i = s_i^{-1}r_i \mod n$, $u_i = -s^{-1}H(m_i) \mod n$, $l$ is the nonce leakage in number of null most significant bits (for all signatures -- I'm aware that Minerva uses $l_1, \dots l_d$, but let's simplify and consider $l_1 = \dots = l_d = l$) and $n$ is the order of the group built over the elliptic curve used for ECDSA.

I found this repository online that uses a slightly different lattice:

$$ L_R = \begin{bmatrix} 2^{l+1}n & 0 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 2^{l+1}n & 0 & \cdots & 0 & 0 & 0 \\ 0 & 0 & 2^{l+1}n & \cdots & 0 & 0 & 0 \\ & \vdots & & \vdots & & \vdots \\ 0 & 0 & 0 & \cdots & 2^{l+1}n & 0 & 0 \\ 2^{l+1} t_1 & 2^{l+1} t_2 & 2^{l+1} t_3 & \cdots & 2^{l+1}t_d & 1 & 0 \\ 2^{l+1} u_1 & 2^{l+1} u_2 & 2^{l+1} u_3 & \cdots & 2^{l+1}u_d & 0 & n \end{bmatrix} $$

where all the quantities are defined like before, except for $u_i = -(s_i^{-1} \mod n) \cdot H(m_i) + n$. If I'm not mistaken, the $l+1$ and the $+n$ at the end of $u_i$ in this case are due to recentering. What I completely fail to understand is why $u_i = -(s_i^{-1} \mod n) \cdot H(m_i) + n$ and not $u_i = -(s_i^{-1} \cdot H(m_i) \mod n) + n$. If I change the relevant line of code from

2 * kbi * (- hash_i * inv(sigs[i].s, n_order) )  + n_order

to:

2 * kbi * (- hash_i * inv(sigs[i].s, n_order) ) % n_order  + n_order

(where kbi = 2**l) the code does not work anymore and it does not find any secret key where it worked perfectly before the change.

Any hints on a reason for this peculiar behavior?

$\endgroup$
1
  • $\begingroup$ First of all, welcome to Cryptography. Sometimes we are all stupid. Please revert back to your question and answer this question yourself. This is better since if one searches this question may skip since there is no answer. If one can see there is an accepted answer, then they can consider that the problem is resolved. $\endgroup$
    – kelalaka
    Commented Oct 31, 2023 at 16:06

1 Answer 1

1
$\begingroup$

This

2 * kbi * (- hash_i * inv(sigs[i].s, n_order) ) % n_order  + n_order

reduces modulo n_order even 2*kbi. The actual line of code should be

2 * kbi * (- hash_i * inv(sigs[i].s, n_order) % n_order)  + n_order

The mistake is so stupid that I would have avoided posting it as an answer, but kelalaka's comment made me change my mind, so here is the answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.