Re: [Cfrg] Schnorr just as vulnerable to bad RNG

Bringing in the results of a discussion from the curves list.  I think when generating signatures of short messages, the most conservative strategy is to use a PRF with a secret key, a random number, and the message.

That way if your RNG breaks, unless it’s malicious and omniscient*, at worst it will leak that a message has been repeated.  If your RNG doesn’t break and your PRF isn’t terrible, it will ensure that the nonce is unbiased and that repeated messages aren’t evident.

Some people on the curves list favor PRF(message) xor random(), but it’s more vulnerable to a broken RNG.

Schnorr doesn’t add anything to this or take anything away.  It’s just easier to implement securely because it doesn’t have that pesky inversion mod the group order, and it has a slightly better security argument.

— Mike

* Some people care about a model where a malicious RNG is trying to leak your key by influencing the ultimate output of the algorithm.  It’s more of a concern with nonces.

On Jul 25, 2014, at 6:17 AM, Dan Brown <dbrown@certicom.com> wrote:

> ‎In the SAAG meeting yesterday, it was suggested that Schnorr signatures better resist bad RNG than ECDSA, citing a flawed ECDSA implementation. 
> 
> Just like (EC)DSA, if the ephemeral key is exposed or repeated, then the Schnorr static key is exposed, which then can lead to forgery.
> 
> So this one implementation failure is not a reason to prefer Schnorr signatures, as an algorithm. 
> 
> The importance of proper ephemeral key generation is why ANSI‎ X9.62-2005 for ECDSA added a requirement (not in the1998 version) that the ephemeral key be generated using HMAC DRBG and that it be properly seeded, or else use another ANSI approved RNG. The 1998 version instead said something like unique and unpredictable. 
> 
> Some people propose using deriving the ephemerals from the message and a long term key. This does not seem any better as an algorithm than the DRBG approach, provided the X9.62 algorithm is adhered to.
> 
> There's an RFC melding both these ideas, but that is trying fix something that is not broken, at the algorithm level.
> 
> If a flawed implementation uses a DRBG in compliance with X9.62-2005, but fails to update DRBG state fails between signed messages‎, then the signing key is leaked. If a flawed implementation opts to also use deterministic ephemeral keys for encryption, then repeated messages leak info via repeated ciphertexts.  So, standards should amply warn implementers if these pitfalls. 
> 
> So I think there are issues with ease of implementation, clarity of standards, and making standards  error resistant, but the algorithm security is not significant.
> 
> In theory, some security proofs, may give different assurances, depending on the determinism, but I'll defer that issue to future discussion. 
> 
> ‎Procedurally, I think signature algorithm choice, and method to generate ephemerals is a CFRG issue, not a SAAG issue.
> 
> Best regards, 
> 
> -- Dan
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg