Question about coefficient of ECDSA in lattice attack - Cryptography Stack Exchange most recent 30 from crypto.stackexchange.com 2022-01-26T18:31:10Z https://crypto.stackexchange.com/feeds/question/93478 https://creativecommons.org/licenses/by-sa/4.0/rdf https://crypto.stackexchange.com/q/93478 2 Question about coefficient of ECDSA in lattice attack jin https://crypto.stackexchange.com/users/94176 2021-08-09T10:47:47Z 2021-08-17T03:29:56Z <p><strong>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.</strong></p> <p>I was studying lattice attack recently. I tried to use data from <a href="https://github.com/vernamlab/TPM-FAIL" rel="nofollow noreferrer">TPM-FAIL</a> to help me understand this attack and try to implement an attack using &quot;textbook method&quot; (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.</p> <ol> <li><p>The DSA signature formula can finally be transformed to following equation:</p> <p><span class="math-container">$k_i-s_i^{-1}r_id-s_i^{-1}H(m)\equiv 0 \pmod{n}$</span></p> <p>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.<br /> Then it can be transformed in to lattice form. Something like following equation:</p> <p><span class="math-container">$k_i+A_id+B_i\equiv 0\pmod n$</span>, where <span class="math-container">$A_i=-s_i^{-1}r_i$</span> and <span class="math-container">$B_i=-s_i^{-1}H(m)$</span></p> <p>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:</p> <p><span class="math-container">$s_i^{-1}r_id+s_i^{-1}H(m)\equiv k_i\pmod{n}$</span></p> <p>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?</p> </li> <li><p>The second thing is that I tried using the un-optimized approach, the SVP lattice is built like below:</p> </li> </ol> <p><span class="math-container">$\begin{bmatrix}n&amp;&amp;&amp;&amp;&amp;\\&amp;n&amp;&amp;&amp;&amp;\\&amp;&amp;\ddots&amp;&amp;&amp;\\&amp;&amp;&amp;n&amp;&amp;\\A_1&amp;A_2&amp;\dots&amp;A_t&amp;K/n&amp;\\ B_1&amp;B_2&amp;\dots&amp;B_t&amp;&amp;K\\\end{bmatrix}$</span></p> <p>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?</p> <p>Thank you for your help in advance!</p> https://crypto.stackexchange.com/questions/93478/-/93483#93483 0 Answer by fgrieu for Question about coefficient of ECDSA in lattice attack fgrieu https://crypto.stackexchange.com/users/555 2021-08-09T14:12:21Z 2021-08-10T21:52:44Z <p>About yhe fist interrogative sentence of the question:</p> <blockquote> <p>why does it have to be negative?</p> </blockquote> <p>read literally and with &quot;it&quot; relative to the quantities <span class="math-container">$A_i$</span> and <span class="math-container">$B_i$</span>.</p> <p>The second set of equations really is (or can be changed to) <span class="math-container">$k_i+{A_i}\,d+B_i\equiv0\pmod n$</span> where <span class="math-container">$A_i=-s_i^{-1}\,r_i\bmod n$</span> and <span class="math-container">$B_i=-s_i^{-1}\,H(m)\bmod n$</span>. The <span class="math-container">$\bmod n$</span> are implied. Therefore, in this <span class="math-container">$A_i$</span> and <span class="math-container">$B_i$</span> are non-negative.</p> <p>That's by definition of the <span class="math-container">$\bmod$</span> operator:</p> <ul> <li><span class="math-container">$x\bmod n$</span> is the <span class="math-container">$z$</span> in range <span class="math-container">$[0,n)$</span> with <span class="math-container">$x\equiv z\pmod n$</span>.</li> <li><span class="math-container">$x^{-1}\bmod n$</span> is the <span class="math-container">$z$</span> in range <span class="math-container">$[0,n)$</span> with <span class="math-container">$x\,z\equiv1\pmod n$</span></li> <li><span class="math-container">$-x^{-1}\,y\bmod n$</span> is the <span class="math-container">$z$</span> in range <span class="math-container">$[0,n)$</span> with <span class="math-container">$x\,z\equiv-y\pmod n$</span></li> </ul> <p>Recall that <span class="math-container">$x\equiv z\pmod n$</span> is defined to mean that <span class="math-container">$x-z$</span> is a multiple of <span class="math-container">$n$</span>.</p> <hr /> <blockquote> <p>We can rewrite the first equation as <span class="math-container">$s_i^{-1}\,r_i+s_i^{-1}\,H(m)\equiv k_i\pmod n$</span>. 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?</p> </blockquote> <p>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 <span class="math-container">$s_i^{-1}\,r_i+s_i^{-1}\,H(m)+k'_i\equiv 0\pmod n$</span> with <span class="math-container">$k'_i=n-k_i$</span>. But recall that the attack revolves around the feasibility of selecting, by a timing attack, the <span class="math-container">$i$</span> such that <span class="math-container">$k_i$</span> is small. The same selection method won't yield small <span class="math-container">$k'_i$</span>; and I'm not sure a suitable method is even possible.</p> https://crypto.stackexchange.com/questions/93478/-/93593#93593 2 Answer by jin for Question about coefficient of ECDSA in lattice attack jin https://crypto.stackexchange.com/users/94176 2021-08-17T03:05:47Z 2021-08-17T03:29:56Z <ol> <li><p>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 <span class="math-container">$B_i$</span> there are two terms instead of one. I only changed the sign for one term therefore the attack did not succeed.</p> <p>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 <span class="math-container">$|\alpha \mathbf{t}-\mathbf{u}|_q &lt; K$</span>. Therefore in this case <span class="math-container">$A_i=\mathbf{t}=s_i^{-1}r_i$</span> and <span class="math-container">$B_i=\mathbf{u}=-s_i^{-1}H(m)$</span></p> <p>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.</p> </li> <li><p>The final lattice I chose is a little bit different than this. It is based on this equation:</p> <p><span class="math-container">$|ds_i^{-1}r_i - (-s_i^{-1}H(m))|_n = k_i &lt; n/2^l$</span></p> <p>We can build the lattice after getting rid of the mod operation:</p> <p><span class="math-container">$d|s_i^{-1}r_i|_n - |(-s_i^{-1}H(m))|_n + C_i n=k_i &lt; n/2^l$</span></p> <p>For lattice attack to work, we only need <span class="math-container">$|k|$</span> to be small and as <span class="math-container">$k$</span> is always positive we can apply recentering:</p> <p><span class="math-container">$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}$</span> where <span class="math-container">$-n/2^{l+1} &lt; k_i - n/2^{l+1} &lt; n/2^{l+1}$</span></p> <p>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 <span class="math-container">$2^{l+1}$</span></p> <p><span class="math-container">$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}$</span></p> <p>The first square bracket will be <span class="math-container">$A_i$</span> and the second will be <span class="math-container">$B_i$</span>. Note that the recentering term is merged into <span class="math-container">$B_i$</span> so there is a change in sign.</p> <p><strong>There are several things that needs to be pointed out</strong>:</p> <ul> <li><p>We need to be careful that multiplication of <span class="math-container">$2^{l+1}$</span> and <span class="math-container">$|s_i^{-1}r_i|_n$</span> is a normal multiplication, not modular. In sagemath if you write</p> <pre><code>a = Mod(s_inv * r, n) c = a * b </code></pre> <p>The second line will also become modular multiplication. To make it normal we need to write</p> <pre><code>a = Mod(s_inv * r, n) c = a.lift() * b </code></pre> </li> <li><p>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.</p> </li> <li><p>As the result of recentering, the result might not be positive. Sometimes it could be <span class="math-container">$n-d \pmod n$</span>. So for every row, we need to check both <code>Mod(answer , n)</code> and <code>n- Mod(answer ,n)</code></p> <pre><code>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 </code></pre> </li> </ul> <p>If all these are handled correctly, you should have a successful attack.</p> </li> </ol>