Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not (ends on May 13th)

["D. J. Bernstein" <[e-mail]>]

Dan Brown writes:
> 2. Hindsight patching
> ---------------------
> De-randomization is a hindsight patch, even assuming we've determined
> a correct cause.

Let's go back to the videotape.

1991: NIST proposes DSA. Later, after a CPSR lawsuit, NIST admits NSA
authorship of DSA: https://epic.org/crypto/dss/new_nist_nsa_revelations.html

1992: Rivest criticizes several aspects of DSA, including DSA's use of
randomness generation during signing: "Signing with DSS requires the
generation and use of random numbers (the k values). ... The poor user
is given enough rope with which to hang himself---something a standard
should not do." https://people.csail.mit.edu/rivest/pubs/RHAL92.pdf

1994: NIST standardizes DSA.

1997: Barwood echoes the randomness criticism and, as a solution,
proposes deterministic generation of k: "The normal (i.e. IEEE P1363)
way of implementing digital signatures using an elliptic curve seems to
call (at least implicitly) for the generation of true random integers.
Generating true random integers is difficult to do in a safe portable
way, so I propose a method that does not require any true random input.
... What I suggest is that a prng is used to generate k, keyed with d
(the private key), and seeded with e (the message digest)."
https://groups.google.com/forum/#!original/sci.crypt/SalLSLBBTe4/xtYNGDe6irIJ

1997: Wigley independently proposes the same solution in more
generality: "I was thinking last night about an implementation of
digital signatures - re: the requirement for a truly random number in
DSA / NR / most other algo's. Why not derive the random number from the
message to be signed therefore removing the need for a hardware rng
(smartcards) or a complex and potentially fallible software attempt."
https://groups.google.com/forum/#!original/sci.crypt/3g8DnnEkv5A/iZqTyLxF2qYJ

1997: Naccache, M'Raihi, and Levy-dit-Vehel independently file a patent
application on the same idea. (They abandon the application in 2003.)

1998: M'Raihi, Naccache, Pointcheval, and Vaudenay manage to stretch the
idea into an entire SAC paper: "In this paper, we present a simple
method for generating random-based signatures when random number
generators are either unavailable or of suspected quality (malicious or
accidental). ... Suffice it to say that one should replace each
session's random number by a digest of the keys (secret and public) and
the signed message."
https://www.di.ens.fr/users/pointche/Documents/Papers/1998_sac.pdf

2010: Bushing, Marcan, Segher, and Sven ("failOverflow") announce that
they have recovered the Sony PlayStation 3 signing key, thanks to Sony's
reuse of a single k for many signatures.
https://www.youtube.com/watch?v=PR9tFXz4Quc

Of course, the 1997 proposals from Barwood, Wigley, Naccache, M'Raihi,
Levy-dit-Vehel, Pointcheval, and Vaudenay would have stopped this 2010
attack. Can you please explain why you call this "hindsight patching"?

> The secret s SHOULD be new, but MAY be old.

With your proposal, the "poor user is given enough rope with which to
hang himself---something a standard should not do". What stops the user
from choosing a constant s, producing a predictable k and revealing the
signing key?

It's not enough to _tell_ people that k has security consequences---
something that has been said again and again since the original ElGamal
paper in 1985. What actually works is having standard _test vectors_
that eliminate the bad implementations. By agreeing on a deterministic
way to generate k, with no additional inputs, we allow every common
mistake in k generation to be caught by test vectors.

I don't mean to suggest that _every_ k-generation function is safe. On
the contrary: generating a constant k, as Sony did, is of course very
bad; generating k biased mod the group order is bad; etc. The designer
needs to specify a k-generation function that's secure _and_ that
actually ends up being tested in implementations. Failure to do this is
tantamount to allowing _every_ function that implementors come up with;
instead of having _one_ function to carefully review for security
problems, we're faced with a neverending list of implementation-specific
functions.

The same principles apply to "entropy pools". Having each library make
up its own mechanism to combine multiple entropy sources is a recipe for
disaster. What we need is a specified, security-reviewed, deterministic,
tested mechanism to combine multiple entropy sources---centralized in
the operating system (even better, the hypervisor, when there is one) to
maximize the chance that good entropy sources are actually used and to
minimize the number of lines of code to review.

Obviously the system does ultimately rely on having some good entropy
source, and testing entropy sources is a quite different problem with a
long history of failures, even in cryptographic products "certified" by
the U.S., Canadian, and German governments:

   http://smartfacts.cr.yp.to

But the fact that there's a hard problem in one corner of the crypto
ecosystem doesn't mean that we should give up on solving the problem.
Our best chance of solving this problem starts by isolating it---
eliminating it from every other part of the ecosystem.

> 3a.... More side channels?

No. Unprotected implementations of standard _randomized_ DSA are well
known to be broken by side-channel attacks. It's important to protect
all secrets---including k, which is used for scalar multiplication, and
the long-term secret, which is used for arithmetic mod the group order.
Standard defenses include blinding of each secret bit (splitting b into
r and r+b), blinding mod the group order (replacing k with k+rp), etc.;
these defenses work for deterministic signing systems too.

The bigger picture is that crypto is constantly mixing secret data with
public data. Side-channel defenses take responsibility for protecting
this. We know how to defend, e.g., computing an authenticator of a
potentially forged message---even if the same message is repeated any
number of times. This is also what we're doing in computing k.

A carefully managed internal PRNG _can_ be cheaper to protect than this
computation, but this cost improvement is quite small compared to the
overall cost of a signature unit. An implementor desperate to take this
approach will find that the resulting signatures, despite violating the
deterministic standard (and failing standard signing tests), are fully
interoperable---CFRG is not proposing that _verifiers_ track signatures
of the same message and enforce repetition constraints.

> 3b... Re-use keys more often, why not always?
> 3c....  De-randomized signing key?
> 3d.... Increased failure to erase ephemerals?
> 3e.... Replay attacks on encryption?
> 3f.... Loss of forward secrecy?

Here you're speculating that an implementor might draw dumb conclusions
from the k definition and, as a result, misimplement something else.

Sure, anything is possible, but intelligent risk management requires
sensibly evaluating the _likelihood_ and _impact_ of bad events. The
chance of an implementor reusing k as Sony did, or generating k that's
slightly too short, is obviously much higher than the chance of all of
the scenarios that you postulate, and the impact---forgery of arbitrary
messages under this public key---is no less disastrous than the impact
of any of your scenarios.

> given a sequence of signatures under a public key, one can detect
> repeated messages, even if the repeated message are secret and
> unguessable, and therefore impossible to verify.

Sure. Standard signature caching (e.g., DNSSEC saves signatures) also
has this effect. Many RSA signature systems are also deterministic. You
speculate that there are some protocols that need non-deterministic
signatures for some vague reason; those protocols will already have to
be quite careful in their selection of signature systems.

This is obviously far less important than the disastrous consequences of
poor k generation for typical real-world applications of signatures.

> 3h.... Provable security: more assumptions to prove unforgeability
> What is the effect of de-randomization on the security proofs of
> unforgeability?

First of all, to give proper credit, this purely theoretical issue was
adequately analyzed by Olson in 1997:

   https://groups.google.com/forum/#!original/sci.crypt/3g8DnnEkv5A/TXTyOg9jgvUJ

The solution to all of the theoretical problems, as mentioned by Olson,
is to have one discrete-log key and one message-hash key. Ed25519 uses a
KDF (normally SHA-512) to derive these two separate keys from a master
signing key.

You say that "an implementer who is likely to reuse an ephemeral may be
just as likely to choose the alternative key poorly". But these objects
have totally different levels of fragility from a security perspective.
Choosing a slightly biased k is a disaster; choosing a slightly biased
message-hash key (or discrete-log key) is irrelevant. Repeating k is a
disaster; I have no idea what "poor" choice of message-hash key you
think would be analogous to this. Sure, a _guessable_ message-hash key
is as disastrous as a guessable k, but the equal problems in this
extreme case don't imply equal problems in other cases.

> Of course, we may well already need PRFs for privacy, but I wouldn't
> want to some fault in a PRF, e.g. AES, carry over into authentication.

The modern trend is to rely on the security of ciphers, notably AES, not
just for _encrypting_ every message but also for _authenticating_ every
message. Do you think this is a problem?

The community has been subjecting ciphers to massive scrutiny for many
years. The security standard is very high: we imagine that the attackers
can freely choose all inputs and see all outputs, and that the attackers
automatically win if they can find _any_ pattern, even though this isn't
enough to break typical applications. The best possible security, within
various real-world performance constraints, is systematically analyzed.
Worrisome cipher structures are identified and avoided.

Is it still possible that an attacker will find some shocking break of
AES? Yes, it's possible. Is it conceivable that generating k's with a
modern cipher will produce k's so biased as to allow forged signatures?
Yes, it's conceivable. But is it reasonable to say that this wildly
speculative horror story has the same probability as another equally
disastrous Sony-style implementation screwup? No, it isn't.

---Dan