Question about coefficient of ECDSA in lattice attack

Question

Update: I made my lattice attack worked finally. As the actual reason is quite complicated I decide to write an answer below to describe how it worked so anyone with similar question might get inspiration from my work. The Question is not modified.

I was studying lattice attack recently. I tried to use data from TPM-FAIL to help me understand this attack and try to implement an attack using "textbook method" (there are some optimization in TPM-FAIL attack scripts). I had some questions reading the materials that I could not figured out myself. Please help me if you have any idea.

1. The DSA signature formula can finally be transformed to following equation:

   $k_i-s_i^{-1}r_id-s_i^{-1}H(m)\equiv 0 \pmod{n}$

   where k is the ephemeral key, (r,s,) is the signature pair, d is private key, H(m) is message digest as usual... you know the drill.
   Then it can be transformed in to lattice form. Something like following equation:

   $k_i+A_id+B_i\equiv 0\pmod n$, where $A_i=-s_i^{-1}r_i$ and $B_i=-s_i^{-1}H(m)$

   What I don't understand is that, why does it have to be negative? actually tried to modify the attack script provided in TPM-FAIL dataset and found that removing -1 in A_i and B_i will make the attack failed. But we can rewrite the first equation as:

   $s_i^{-1}r_id+s_i^{-1}H(m)\equiv k_i\pmod{n}$

   The concept of lattice attack should still hold: If the lattice vector is small, basis reduction algorithm should generate the answer. What have I got wrong?

2. The second thing is that I tried using the un-optimized approach, the SVP lattice is built like below:

$\begin{bmatrix}n&&&&&\\&n&&&&\\&&\ddots&&&\\&&&n&&\\A_1&A_2&\dots&A_t&K/n&\\ B_1&B_2&\dots&B_t&&K\\\end{bmatrix}$

But we can clearly see that K/n will be a fractional number which cannot use BKZ() or LLL() method in sagemath. What I understand is that we can multiply every thing in this matrix by n so everything in this matrix is integer. After apply BKZ() we divide everything by n to recover the original result: the private key should be in the second last column of the first row. However I failed to recover the private key. Even if I used 100 signatures with 8-bit leakages. Is my approach correct?

Thank you for your help in advance!

Answer 1

1. The short answer is: There is nothing wrong with the idea. The main reason I did not attack successfully after changing sign is because there was an optimization in TPM-FAIL paper. It eliminates the first signature by some transformation. This could decrease the dimension of lattice by 1, which increase the calculation speed slightly. The result of transformation is that for $B_i$ there are two terms instead of one. I only changed the sign for one term therefore the attack did not succeed.

   By the way I want to further point out that in some paper this equation is converted into CVP (closest vector problem), which has form $|\alpha \mathbf{t}-\mathbf{u}|_q < K$. Therefore in this case $A_i=\mathbf{t}=s_i^{-1}r_i$ and $B_i=\mathbf{u}=-s_i^{-1}H(m)$

   Secondly there was a concern that the sign may affect recentering. I actually failed to see how it was applied in TPM-FAIL method. In the end I used a different lattice construction so I stopped my research there.

2. The final lattice I chose is a little bit different than this. It is based on this equation:

   $ |ds_i^{-1}r_i - (-s_i^{-1}H(m))|_n = k_i < n/2^l$

   We can build the lattice after getting rid of the mod operation:

   $ d|s_i^{-1}r_i|_n - |(-s_i^{-1}H(m))|_n + C_i n=k_i < n/2^l$

   For lattice attack to work, we only need $|k|$ to be small and as $k$ is always positive we can apply recentering:

   $ d|s_i^{-1}r_i|_n - |(-s_i^{-1}H(m))|_n + C_i n - n/2^{l+1} =k_i - n/2^{l+1}$ where $ -n/2^{l+1} < k_i - n/2^{l+1} < n/2^{l+1}$

   To ensure that every element in the lattice is integer so that we could apply LLL or BKZ, the usual things we would do is to multiply both sides by $2^{l+1}$

   $ d[2^{l+1}\times |s_i^{-1}r_i|_n] - [2^{l+1}\times |(-s_i^{-1}H(m))|_n + n] + C_i\times 2^{l+1}n =k_i - n/2^{l+1}$

   The first square bracket will be $A_i$ and the second will be $B_i$. Note that the recentering term is merged into $B_i$ so there is a change in sign.

   There are several things that needs to be pointed out:

   • We need to be careful that multiplication of $2^{l+1}$ and $|s_i^{-1}r_i|_n$ is a normal multiplication, not modular. In sagemath if you write

     a = Mod(s_inv * r, n)  
     c = a * b
     

     The second line will also become modular multiplication. To make it normal we need to write

     a = Mod(s_inv * r, n)  
     c = a.lift() * b
     

   • The correct answer does not necessarily appear in the first row. Depending the number and algorithm, the answer might appear in the second row or the second last row. Therefore the best way is to check the corresponding column in every row to see if there is a correct answer.

   • As the result of recentering, the result might not be positive. Sometimes it could be $n-d \pmod n$. So for every row, we need to check both Mod(answer , n) and n- Mod(answer ,n)

     for row in range(lattice.nrows()):
         # the column number depends on how you construct the lattice, in a normal SVP with kanaan embedding technique, the corresponding column is the second last one
         solution = Mod(lattice[row, -2], modulo).lift() 
         if check_answer(solution):
             return solution
         if check_answer(modulo - solution):
             return modulo - solution
     

   If all these are handled correctly, you should have a successful attack.

Answer 2

About yhe fist interrogative sentence of the question:

why does it have to be negative?

read literally and with "it" relative to the quantities $A_i$ and $B_i$.

The second set of equations really is (or can be changed to) $k_i+{A_i}\,d+B_i\equiv0\pmod n$ where $A_i=-s_i^{-1}\,r_i\bmod n$ and $B_i=-s_i^{-1}\,H(m)\bmod n$. The $\bmod n$ are implied. Therefore, in this $A_i$ and $B_i$ are non-negative.

That's by definition of the $\bmod$ operator:

• $x\bmod n$ is the $z$ in range $[0,n)$ with $x\equiv z\pmod n$.
• $x^{-1}\bmod n$ is the $z$ in range $[0,n)$ with $x\,z\equiv1\pmod n$
• $-x^{-1}\,y\bmod n$ is the $z$ in range $[0,n)$ with $x\,z\equiv-y\pmod n$

Recall that $x\equiv z\pmod n$ is defined to mean that $x-z$ is a multiple of $n$.

---

We can rewrite the first equation as $s_i^{-1}\,r_i+s_i^{-1}\,H(m)\equiv k_i\pmod n$. The concept of lattice attack should still hold: If the lattice vector is small, basis reduction algorithm should generate the answer. What have I got wrong?

I vaguely conjecture the problem is that the lattice reduction code used wants an input in matrix form. We can match this by rewriting the equation as $s_i^{-1}\,r_i+s_i^{-1}\,H(m)+k'_i\equiv 0\pmod n$ with $k'_i=n-k_i$. But recall that the attack revolves around the feasibility of selecting, by a timing attack, the $i$ such that $k_i$ is small. The same selection method won't yield small $k'_i$; and I'm not sure a suitable method is even possible.