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.

Using the terminology of the ECDSA wikipedia page, ECDSA (and DSA) signatures require a random k value for each signature which ensures that the signature is different each time even if the message and key are the same. For some applications a "constant" signature may be desirable.

It seems to me that there would be no harm in implementing "constant" ECDSA by setting the "random" k value to be the x-coordinate of the message hash z (converted to a curve point in some arbitrary fashion) multiplied by the private key. Obviously the method translates back to DSA.

This scheme might be useful for implementations which do not have access to a source of random numbers.

Are there any problems with this? Is there a faster way of generating a suitable k than a point multiplication?

ByteCoin

share|improve this question
    
I don't see why you want to include the private key in the generation of $k$. –  Paŭlo Ebermann Sep 29 '11 at 10:33
5  
@Paulo: if you guess $k$ then you can recompute the private key from the signature. $k$ MUST be hidden from any attacker; hence, its generation must include some secret data. The private key is some secret data. –  Thomas Pornin Sep 29 '11 at 12:28
    
@ThomasPornin Ah, thanks. Looks like I mixed $k$ and $r$. –  Paŭlo Ebermann Sep 29 '11 at 12:38
    
Related blog entry: Surviving a bad RNG Scroll down to ECDSA signatures –  CodesInChaos Jul 22 '12 at 15:56

3 Answers 3

There is a draft RFC which describes a way to implement deterministic (EC)DSA (with test vectors). In this draft, both $h(m)$ (the hash of the message) and $x$ are used as input to a deterministic PRNG which uses HMAC (that's HMAC-DRBG as specified by NIST); the PRNG output is used to yield $k$. I am not sure your simple multiplication with $x$ would be enough to guarantee security; ideally, a random oracle should be used, and HMAC-DRBG is the closest to a practical random oracle that I could find.

Note that $k$ must be generated uniformly in the $[1, q-1]$ range (where $q$ is the subgroup order). Any information on $k$, even partial (such as: values between $1$ and $2^{160}-q$ are twice as probable than values between $2^{160}-q$ and $q$), can be exploited by the attacker.

(There will be a new draft version with a few text changes in the draft -- but the same test vectors -- as soon as I find the time to do it.)

Edit: the RFC is now published as RFC 6979.

share|improve this answer
1  
What a coincidence that you're the author of the relevant RFC! It's "expired" - what happened to it? You make a good point about wanting not to have to worry about detecting bad quality random numbers. –  ByteCoin Sep 29 '11 at 22:53
1  
Can you give a reference for a technique which would exploit such weak partial information on k? I think I recall seeing an attack which required several bits fixed. –  ByteCoin Sep 29 '11 at 23:05
2  
@ByteCoin: drafts expire after 6 months -- that's why they are called drafts. I submitted it as "independent submission" (i.e. not from an IETF committee) and got a few remarks; the new draft will be up as soon as I spend a few hours on it. As for the technique with partial information on $k$, it was found by Bleichenbacher; in this article, Serge Vaudenay says that it was a "private communication", hence not really published anywhere. –  Thomas Pornin Sep 30 '11 at 0:44
    
RFC 6979 should be used for all ECDSA signatures. The weak link in most strong cryptographic systems is the reliance on PRNG with sufficient entropy. TPRNG are generally slow and expensive however key generation is significantly less common than signature generation. Depending on the number of private keys needed, offline manual sources of entropy (rolling dice or flipping coins) could be sufficient. Without RFC 6979 that would be time consuming. RFC 6979 would have prevented the theft of private keys (and Bitcoins) due to flawed PRNG in Android OS generating the same k value. –  Gerald Davis Apr 15 at 16:02
    
@Thomas Pornin Can you considered adding test vectors for the SECP256K1 curve to RFC 6979? While it is a less common curve in general it is the curve used by Bitcoin and this is one community where implementing deterministic signatures is getting significant attention. –  Gerald Davis Apr 15 at 16:05

This certainly creates the opportunity to mount a birthday attack. Oscar creates two Messages hashing to the same value - certainly doable at least with sha1 or MD5 and succeeds in making you sign both of them. He can then reconstruct your private key from the signatures.

I would certainly avoid deterministic ECDSA Signatures and regard the very act of securely creating the random number for signing as a core security feature.

In an ECDSA setting the (P)RNG is a prime target for attack. Tampering with this part is dangerous in my opinion, regardless whether it may mathematically be sound in principle.

share|improve this answer
4  
This doesn't work. If a hash collision is found then the two messages have the same hash $z$. In my scheme, this results in the same $k$ and hence the signature is identical and hence the secret key is not revealed. –  ByteCoin Jan 23 '12 at 14:45
    
As you say, the RNG is a prime target for attack. As Thomas Pornin has said, it's very difficult for an implementation to know whether their source of random numbers has been compromised. I seem to remember some devices by a Swiss firm Crypto AG being compromised in this fashion. Much better to remove the need for random numbers hence my, Pornin's and Bernstein's schemes. Note that this is the direct opposite of your conclusion. –  ByteCoin Jan 23 '12 at 19:53
    
I admit you are right ByteCoin, my suggestion wouldn't work. Thinking about it, I agree that your scheme would work. Still, it would remove one degree of freedom from the procedure and you would be using the secret key for two different purposes within the same procedure which "feels dangerous". Out of paranoia I would implement it with an independent second secret key component used for just this purpose. –  Michael Anders Jan 24 '12 at 7:20
    
@ByteCoin The security of your procedure depends on the onewayedness of the hash involved in deriving the k from message and secret key. If this is about overall security it seems to come down to the question whether this property of the hash is easier to defend (or prove) than the randomness of the (P)RNG. –  Michael Anders Jan 24 '12 at 7:20
    
@MichaelAnders ECDSA already relies on the security ("onewayedness") or a hashing function as for computational reasons the message isn't signed a hash of the message is signed. If the hashing function is compromised then so are the signatures. The attacker may not gain the private key however the attacker can preimage the message and it appear as it was signed by the victim. –  Gerald Davis Apr 15 at 16:11

In their 1998 SAC paper, M'Raihi et al showed how to use hash functions to turn Schnorr signatures (quite similar to (EC)DSA) deterministic, and proved that if the original signature scheme (with randomness) is secure, so is the deterministic one.

Bernstein et al's recent EdDSA signature scheme uses the same technique to avoid randomness.

share|improve this answer
1  
Thanks for the references. The EdDSA paper refers to setting k as the hash of the message and private key which for many applications would be faster and superior to my original proposal. –  ByteCoin Sep 29 '11 at 12:52

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.