6
$\begingroup$

Suppose ECDSA is used without hashing the message, but directly using a short message (say 10-bytes long) as the value z (using the definitions at http://en.wikipedia.org/wiki/Elliptic_Curve_DSA) because we need extremely fast signing with ECDSA in a specific embedded platform. We also pre-compute kG and k^-1 values.

Are there any weak z values such that the signature can be forged ?

Improve this question
$\endgroup$
2
  • $\begingroup$ I suppose the overhead of hashing is not that large compared to the time for the signature, but you should measure this. $\endgroup$
    – Paŭlo Ebermann
    Jul 23, 2013 at 6:44
  • $\begingroup$ @PaŭloEbermann DSA is very fast if you don't consider the (per-signature) pre-computation cost. You only need one multiplication and one addition after you learn the message. $\endgroup$
    – CodesInChaos
    Jul 23, 2013 at 8:05

2 Answers 2

Reset to default
3
$\begingroup$

[Partial answer] In Generic Groups, Collision Resistance, and ECDSA by D. Brown (see http://cacr.uwaterloo.ca/techreports/2002/corr2002-06.ps or http://eprint.iacr.org/2002/026) on page 17, you have a lot of information about the kind of hash functions that can be used with ECDSA. In your case, taking the identity function as hash and looking at the results you find that two of the proposed weaknesses are particularly relevant to your case:

  1. $z=0$ is a weak value (see Zero-Finder-Resistant Hash)
  2. If the probability that a random number modulo the curve order belongs to your acceptable range of $z$ values is not too low, there also is an attack (see One-Way Hash Function). With 10 bytes long values as suggested, the probability is sufficiently low and you can probably ignore this attack.
Improve this answer
$\endgroup$
3
$\begingroup$

I don't think the designers of DSA expected the attacker to have control over the value of $z$.

What about the following (using the notations of wikipedia):

  1. Pick random $x,y \in [0,n-1]$

  2. Set $P:=xG+yQ$ with $P=(P_x,P_y)$

  3. Set $r:=P_x \mod n$ and $s:=ry^{-1} \mod n$

Now if $rxy^{-1} \mod n$ is a valid message then $(r,s)$ is a valid forgery for it. If not just start again with a new pair $x$, $y$

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is the attack mentioned by Brown under the heading One-Way Hash Function. With messages on 10-bytes (and an elliptic curve modulo a prime of at least 160 bits), the average number of trials to find a valid message is going to be very high ($\geq 2^{80}$). $\endgroup$
    – minar
    Jul 23, 2013 at 10:41
  • $\begingroup$ You're right, I didn't read the question well enough. That being said I think the point is still valid since there was no technical reasons for keeping the messages short and that limitation could well have been lifted in the future $\endgroup$
    – Alexandre Yamajako
    Jul 23, 2013 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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