2
$\begingroup$

The aim is to check if it is possible to break the ECDSA cryptosystem under the following criteria.

  • Suppose that each ECDSA signature is generated by using the GLV method for point multiplication (the random nonce $k$ used in each signature is decomposed into $k_1$and $k_2$).
  • For every ECDSA signature, I can obtain few bits (least significant bits, most significant bits, ...) of the respective $k_1$ and $k_2$.

Is it possible to carry out a lattice attack to gain the value of the underlying secret key ($\alpha$)? If yes, then can you explain the attack in detail?

PS: I have a beginner level understanding of ECDSA and lattices.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It is a theoretical question. I tried searching if it is possible to do that, and more information on the topic. I searched various research papers and the internet. For example, I have confirmed that a lattice attack can be applied when I have few bits of $k$ for every signature (this is generally the case when GLV method is not used). But in my case I have few bits of $k_1$ and $k_2$. $\endgroup$ – progammer Jun 26 '15 at 21:54
  • $\begingroup$ Yes, this paper is exactly for your question. iacr.org/conferences/asiacrypt2014/… $\endgroup$ – user31633 Feb 18 '16 at 20:25
4
$\begingroup$

Sure you can do. There are many lattice attacks, using your second assumption, to ECDSA (which also applied to DSA). For instance see Smart and Howgrave-Graham and Shparlinski and Nguyen. All the lattice attacks base on finding small solutions (for the ephemeral key $k$ and the private key $a$) to the signing equation $sk-ra\equiv H(m)\pmod q.$ If you have enough signatures (i.e. enough $k_i$) then you construct a linear system $\bmod q$ and then a suitable lattice and if you have enough bits from every $k_i$ and $a$ and enough messages you can solve the CVP problem. Also you can apply Coppersmith method to the signing equation.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I've quickly edited your answer to improve your signing equation and I've also improved your style a bit. If you don't like my edits you can either edit again or roll my edits back by clicking on the "edited...ago". $\endgroup$ – SEJPM♦ Jul 19 '15 at 18:44
  • $\begingroup$ Thank you for the answer. But $k_1$ and $k_2$ in my question do not mean random nonces of different signature instances. Please read my comment below the question. $\endgroup$ – progammer Jul 22 '15 at 10:59
  • 1
    $\begingroup$ As far as I know, If you have few bits ( $\ll \sqrt{q})$ from two ephemeral keys there is not any attack. $\endgroup$ – 111 Jul 22 '15 at 11:41
  • $\begingroup$ it seems like you misunderstood my question/comment. $k_1$ and $k_2$ are not two ephemeral keys. They are related to a single ephemeral key ($k$) by the relation: $k \equiv (k_1 + k_2 \lambda) \mod n $. Here, $\lambda$ is the endomorphism of the curve. $\endgroup$ – progammer Jul 23 '15 at 16:41
  • $\begingroup$ Ok, you have two blocks of contiguous bits of one ephemeral key. You can apply the attacks given by the references I wrote in my answer. But you need enough bits. Almost bits(k1)+bits(k2)$\approx bits(n)/2$ (of course with $n$ here, you mean the prime order of the subgroup generated by a point of your curve, usually in ECDSA is written $q$). $\endgroup$ – 111 Jul 23 '15 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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