Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 ?

share|improve this question
    
I suppose the overhead of hashing is not that large compared to the time for the signature, but you should measure this. –  Paŭlo Ebermann Jul 23 '13 at 6:44
    
@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. –  CodesInChaos Jul 23 '13 at 8:05
add comment

2 Answers

up vote 3 down vote accepted

[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.
share|improve this answer
add comment

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$

share|improve this answer
    
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}$). –  minar Jul 23 '13 at 10:41
    
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 –  Alexandre Yamajako Jul 23 '13 at 17:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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