35
$\begingroup$

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 that 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?

Improve this question
$\endgroup$
4
  • $\begingroup$ I don't see why you want to include the private key in the generation of $k$. $\endgroup$
    – Paŭlo Ebermann
    Sep 29, 2011 at 10:33
  • 10
    $\begingroup$ @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. $\endgroup$
    – Thomas Pornin
    Sep 29, 2011 at 12:28
  • $\begingroup$ @ThomasPornin Ah, thanks. Looks like I mixed $k$ and $r$. $\endgroup$
    – Paŭlo Ebermann
    Sep 29, 2011 at 12:38
  • $\begingroup$ Related blog entry: Surviving a bad RNG Scroll down to ECDSA signatures $\endgroup$
    – CodesInChaos
    Jul 22, 2012 at 15:56

4 Answers 4

Reset to default
34
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • 2
    $\begingroup$ 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. $\endgroup$
    – ByteCoin
    Sep 29, 2011 at 22:53
  • 2
    $\begingroup$ @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. $\endgroup$
    – Thomas Pornin
    Sep 30, 2011 at 0:44
  • 4
    $\begingroup$ 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. $\endgroup$
    – Gerald Davis
    Apr 15, 2014 at 16:02
  • 2
    $\begingroup$ RFC are immutable; once published they never change. $\endgroup$
    – Thomas Pornin
    Apr 15, 2014 at 16:40
  • 3
    $\begingroup$ @Jus12: you cannot verify from the outside whether the signature was done deterministically or not -- except by asking twice for the same signature. If you have a black box that computes signatures, make it sign twice the same data; if you get twice the same output, then chances are that the signature algorithm is deterministic. On a single signature, by design, you should not be able to tell how the internal k value was generated. $\endgroup$
    – Thomas Pornin
    Aug 12, 2015 at 13:45
13
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – ByteCoin
    Sep 29, 2011 at 12:52
1
$\begingroup$

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.

The private key can be calculated when there are any two different legitimate signatures.

  • msg_hash: $z_i$
  • signature: $(r_i, s_i)$
  • private key: $sk$
  • deterministic k: $k_i = [z_i \cdot P].x \cdot sk$, and point $P$ is on the same curve. and $P$ is public. let $px_i = [z_i \cdot P].x$, so $k_i = px_i \cdot sk$

$$ \begin{align*} s_1 &= \frac{m_1 + r_1 \cdot sk}{px_1 \cdot sk} \\ s_2 &= \frac{m_2 + r_2 \cdot sk}{px_2 \cdot sk} \\ \Rightarrow s_1 \cdot px_1 \cdot (m_2 + r_2 \cdot sk) &= s_2 \cdot px_2 \cdot (m_1 + r_1\cdot sk) \end{align*} $$

So the private key $sk$ can be calculated as the $px_i$ is public.

How about the $k_i = [z_i \cdot P_1].x + [sk \cdot P_2].x$, and point $P_1, P_2$ is on the same curve. You can still calculate the private key by referring to here

Improve this answer
$\endgroup$
-3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 4
    $\begingroup$ 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. $\endgroup$
    – ByteCoin
    Jan 23, 2012 at 14:45
  • $\begingroup$ 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. $\endgroup$
    – ByteCoin
    Jan 23, 2012 at 19:53
  • $\begingroup$ 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. $\endgroup$
    – Michael Anders
    Jan 24, 2012 at 7:20
  • $\begingroup$ @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. $\endgroup$
    – Michael Anders
    Jan 24, 2012 at 7:20
  • $\begingroup$ @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. $\endgroup$
    – Gerald Davis
    Apr 15, 2014 at 16:11

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.