Join Log in
Score:2
avatar Crypto

Question about coefficient of ECDSA in lattice attack

in flag
jin

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!

249
2 + 5
dsa
fgrieu avatar
ng flag
fgrieu
When you write "why does it have to be negative?", are you asking wht
0
Reply
cn flag
j.p.
Could it be that flipping the signs of A and B makes the attack fail, as the centering optimization assumes the negative signs and makes the attack worse for your choice of signs? By the way, a good tutorial to learn lattice attacks you find [here](https://ia.cr/2020/1506).
0
Reply
in flag
jin
@j.p. It is possible but at the first glance I didn't see any difference. I will try to do the calculation myself and update on the question.
0
Reply
cn flag
j.p.
@jin: Could you please post your update as answer and accept it, so that your question gets marked "solved" by the system? Thanks in advance!
0
Reply
Maarten Bodewes avatar
in flag
Maarten Bodewes
Awaiting your answer with anticipation, jin!
1
Reply
Score:2
avatar Crypto
in flag
jin

  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.

0 + 0
Score:0
fgrieu avatar Crypto
ng flag
fgrieu

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.

0 + 3
in flag
jin
Thank you for your answer. I think maybe I misunderstood the law of mod operation? We cannot transform 1st set of equation directly to 3rd set of equation like a normal equation. Is that the mistake I made?
0
Reply
fgrieu avatar
ng flag
fgrieu
@jin: when you ask "why does it have to be negative?" are you asking why $A_i$ and $B_i$ have to be negative, which is what my answer attempts to address; or why the minus sign?
0
Reply
in flag
jin
I think I did not make this question clear enough. I am really sorry about that. My actual question is that the first equation could also be transformed into the third equation, which we don't have to multiply -1 in building lattice. I should modify my question
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.