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

From: Dan Brown <[email-masked]>
Date: Fri, 25 Jul 2014 13:17:38 +0000

‎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

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 25 Jul 2014 10:09:20 -0400

Dan Brown <[email-masked]>:

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.
>

It's certainly not broken, but more fragile than necessary. If you use an
appropriate PRNG with proper seeding, there's no problem, but in practice,
sometimes you *think* you have proper seeding when you actually don't.
 That's usually bad in any case, but it can be less bad with the hash-based
approach.  Since the additional cost of hashing is minor, I think hashing
is a good idea for implementations.

(What document are you referring to?  Really an RFC?)

Bodo

---

From: Rene Struik <[email-masked]>
Date: Fri, 25 Jul 2014 10:15:49 -0400

RFC 6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) 
and Elliptic Curve Digital Signature Algorithm (ECDSA) (August 2013)

On 7/25/2014 10:09 AM, Bodo Moeller wrote:
> Dan Brown <[email-masked] <mailto:[email-masked]>>:
>
>     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.
>
>
> It's certainly not broken, but more fragile than necessary. If you use 
> an appropriate PRNG with proper seeding, there's no problem, but in 
> practice, sometimes you *think* you have proper seeding when you 
> actually don't.  That's usually bad in any case, but it can be less 
> bad with the hash-based approach.  Since the additional cost of 
> hashing is minor, I think hashing is a good idea for implementations.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: Bodo Moeller <[email-masked]>
Date: Fri, 25 Jul 2014 10:22:33 -0400

> and Elliptic Curve Digital Signature Algorithm (ECDSA) (August 2013)

Thanks!

That's not what I thought "melding both these ideas" meant; I thought it's
about mixing (presumed) randomness *with* deterministic inputs (such that
you end up with deterministic usage if and only if the "PRNG" is actually
constant).

Bodo

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 25 Jul 2014 10:49:28 -0700

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.

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 25 Jul 2014 22:16:41 +0100

Hiya,

On 25/07/14 14:17, Dan Brown wrote:
> ‎Procedurally, I think signature algorithm choice, and method to
> generate ephemerals is a CFRG issue, not a SAAG issue.

No. IETF WGs can choose to ask CFRG for advice and, when given,
that's very welcome and seriously considered. CFRG, nor the IRTF
more generally, don't get to determine IETF consensus.

S.

---

From: David Jacobson <[email-masked]>
Date: Fri, 25 Jul 2014 19:33:58 -0700

On 7/25/14 7:09 AM, Bodo Moeller wrote:
> ... in practice, sometimes you *think* you have proper seeding when 
> you actually don't.
This is wandering off topic, but I'm going to mention it anyway. Entropy 
generation is a very tricky thing.  Unfortunately, there is far too much 
emphasis on estimating the entropy of a source based on long term 
averages of something.  The problem is that many sources have entropy 
dropouts.  In one system I'm aware of, entropy was collected from noise 
in a radio.  I got a pile of the raw entropy, and noticed that every so 
often there were long runs of zeros. My guess is that there were 
occasional powerful RF "clicks" that overloaded the front end RF 
circuitry, and until the system recovered from the overload, zeros were 
reported.  These dropouts were tiny compared to the overall data, maybe 
0.01%, so they would have negligible effect on any metric that does long 
averages.  But had a seed been grabbed right during a dropout, it would 
have been a cryptographic disaster. And 0.01% corresponds to about 13 
bits of security.

      --David Jacobson

---

From: Sandy Harris <[email-masked]>
Date: Sat, 26 Jul 2014 10:16:54 -0400

David Jacobson <[email-masked]> wrote:

> This is wandering off topic, but I'm going to mention it anyway.

One place where it is on-topic and often discussed is Perry's
crypto list:
http://www.metzdowd.com/mailman/listinfo/cryptography

There is also a list specifically for RNG discussion:
http://lists.bitrot.info/mailman/listinfo/rng

> Entropy
> emphasis on estimating the entropy of a source based on long term averages
> of something.

It is possible to build an RNG without having to estimate average
entropy. Instead you can get a provable minimum on Nyquist
noise in a circuit from well-understood physics:
http://www.av8n.com/turbid/paper/turbid.htm

>  The problem is that many sources have entropy dropouts.  In
> one system I'm aware of, ... had a seed been grabbed right
> during a dropout, it would have been a cryptographic disaster.

"Doctor, it hurts when I do this." "Well, don't do that, then."

Do not grab seeds straight from the source; use an entropy
pool, stir in the source data, and generate output with a
cryptographically strong mixer. This is not foolproof, i.e.
not remarkably easy to get right, but there is hope. It is
safe if the total input entropy is adequate and the crypto
anywhere even close to its design goals.