7
$\begingroup$

I'm really excited by what I've learned of advancements in elliptic-curve cryptography. Curve25519 seems to be a great choice at this point in time, but if I recall correctly, some elliptic curve algorithms can be compromised during signature generation by a bad RNG: my understanding was that by a compromised RNG, the private key could be leaked.

From the documentation:

Signatures are generated deterministically; key generation consumes new randomness but new signatures do not. This is not only a speed feature but also a security feature, directly relevant to the recent collapse of the Sony PlayStation 3 security system.

Granted that if your RNG is compromised, you're going to have a bad time in all regards, does Curve25519 suffer from this private key leak problem as well?

Improve this question
$\endgroup$
4
  • $\begingroup$ Yes, since that problem isn't affected by what group is being used. ​ ​ $\endgroup$
    – user991
    Commented Aug 28, 2015 at 18:55
  • $\begingroup$ Perhaps a better question: are any elliptic curve algorithms not vulnerable to this problem? $\endgroup$
    – Naftuli Kay
    Commented Aug 28, 2015 at 18:56
  • $\begingroup$ tools.ietf.org/html/draft-pornin-deterministic-dsa-00 $\;$ $\endgroup$
    – user991
    Commented Aug 28, 2015 at 19:01
  • $\begingroup$ All are. DSA is defined for any group and the attack on bad PRNGs hence applies to all curves using something like (default) DSA. ECDSA is completely vulnerable (as it's mostly plain DSA on EC) and (AFAICT) only EdDSA fixed it. $\endgroup$
    – SEJPM
    Commented Aug 28, 2015 at 19:03

2 Answers 2

Reset to default
8
$\begingroup$

Any key generation algorithm for any cryptosystem is going to be weak if the attacker can predict what seed was used to generate the key. They can just generate the same key. However, assuming the the random number generator is not that bad, different algorithms start to look different.

If you are just using the output of the random number generator as a private key, Curve25519 (the encryption algorithm) will use that as the secret curve point. That means any structure in the output of the RNG might be visible. So whether it's theoretically exploitable depends on how broken the RNG is.

In contrast, in Ed25519 (the signature algorithm you linked to), the actual elliptic curve point is derived from the private key using a hash function. That means as long as there's enough entropy in the key that the attacker cannot guess it, there should be no visible structure to take advantage of, unless the hash function – SHA-512 – is also broken.

With Ed25519 it's about as good as it can get. The RNG is only used in key generation, signatures require no entropy and so aren't vulnerable. Even if the RNG was slightly biased, it should be hidden by the hash.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So, having a good RNG at key generation time is the main factor, and that is acceptable and true for almost all cryptographic operations. Since ED 25519 seems to not require a RNG at signature time (right?), its implementation isn't vulnerable to what I described, right? $\endgroup$
    – Naftuli Kay
    Commented Aug 28, 2015 at 19:35
  • $\begingroup$ @NaftuliTzviKay, Ed25519 isn't vulnerable to a PS3-type key recovery attack due to bad RNG, but I think you knew that. It could be vulnerable to something like what happened with Debian weak keys where the RNG had so little entropy that many servers were generating the same keys. There's not much you can do about that. $\endgroup$
    – otus
    Commented Aug 28, 2015 at 19:39
  • $\begingroup$ Yes, I was primarily concerned about private key exposure at signing time, not bad RNG at key-generation time; if you've got bad RNG at key generation time, you're screwed eternally if you keep using that key. $\endgroup$
    – Naftuli Kay
    Commented Aug 28, 2015 at 19:44
4
$\begingroup$

No, Curve25519 signature is not vulnerable to bad RNG during signature generation; that's because Curve25519 signature needs no random number during signature generation. By contrast, in ECDSA, a fresh random number is needed for each signature, and if it gets known, that allows to recover the private key from the signature and public key; same if the same random number is used for two signatures; or even if the random number partially leaks for many signatures.

That quality of Curve25519 signature has nothing to do with the elliptic curve (named Curve25519) that it uses; that quality comes by using a deterministic procedure to generate what is random in ECDSA, from the message and the private key.

As pointed by otus in his answer, using a very bad (predictable) RNG during choice of private key will make any cryptosystem insecure.

Improve this answer
$\endgroup$

Your Answer

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

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