3
$\begingroup$

I was recently asked whether a certain library supports the ECDSAwithNone Signature algorithm. Clearly this would mean ECDSA with the identity function as the hash function. I know this is a really bad idea. And I also know that there's a trivial attack if two messages have the same prefix as the "hash" gets truncated to the first q bits (q being bitlength of the order of the curve).

However I wanted to know: What are the "worst" possible attack(s) against this signature scheme?

The worst attack is hereby defined to be the attack that needs the least known or chosen signatures while being executable in reasonable amount of time.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Who would even want such a thing? $\endgroup$ – pg1989 Oct 22 '15 at 18:34
  • 2
    $\begingroup$ @pg1989 I don't know. I only saw the request on our mailing list and the immediate reaction that our library doesn't support it and that it is a bad idea. $\endgroup$ – SEJPM♦ Oct 22 '15 at 19:13
  • 1
    $\begingroup$ @SEJPM Could it be that the request is just to perform the hash separate from the signature algorithm itself? $\endgroup$ – Maarten Bodewes♦ Oct 22 '15 at 22:35
  • 1
    $\begingroup$ "...that your customer is stupid???" Request on mailing list doesn't imply customer. And then no one said stupid, which sounds quite harsh. But as a hint to the sad truth about cryptography: Most people don't understand it, and unless studying crypto extensively, they also have no clue what damage can be done by easy beginner's mistakes. There are countless self-proclaimed "experts", which come up with new schemes and basically re-invent things, which have been dismissed for 30 years, maybe from a different point of view, but with the same weaknesses. $\endgroup$ – tylo Oct 23 '15 at 14:44
  • 1
    $\begingroup$ @Cryptostasis …because the customer needs it – May be me, but when it comes to cryptography (and other things touching information security) I rather tend to gently educate “customers” to use something safer, instead of simply following the easiest path towards writing the next bill that’ll pay someone’s rent. On the long run, putting an emphasis on security instead of the feelings of “customers” always turned out to be the smarter choice – at least for those I interacted with. But maybe that’s merely rooted in the fact I have yet to meet my first (as you call it) stupid customer. $\endgroup$ – e-sushi Oct 24 '15 at 10:13
4
$\begingroup$

There is a way to generate forgeries for (EC)DSA when the hash function is not one-way:

  • Let $n$ be the order of the group, $P$ a generator, and $Q = aP$ for some secret $a$;
  • Pick arbitrary $\alpha$ and $\beta$ $\in \{0, \dotsc, n\}$;
  • $r = x \bmod n$, where $(x, y) = \alpha P + \beta Q$;
  • $s = r \beta^{-1} \bmod n$;
  • $h = s \alpha \bmod n$;
  • Invert $H(h)$ to get $m$. Since we are using the identity function here, $m = h$.

You can verify that $(h s^{-1}) P + (r s^{-1}) Q = (\alpha P + \beta Q)$, whose $x$ coordinate is precisely $r$. Therefore this is indeed a valid signature.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ah but that didn't forge a chosen m but a randomized m. $\endgroup$ – Joshua Nov 8 '16 at 20:26

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.