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

[Dan Brown <[e-mail]>]

> -----Original Message-----
> From: Alexey Melnikov
> 
>  1. CFRG should stick to randomised signature schemes only.
> 
>  2. CFRG should adopt deterministic signature scheme only.
> 
>  3. De-randomisation should be an optional feature for implementers to
>  decide upon (i.e. both choices 1 and 2 allowed).
> 

I prefer #3, but with more specific nuance:

CFRG should recommend that signers make signature ephemerals depend on
the message being signed.

Abstractly: signer has some secret s and computes ephemeral as k =
F(s,m) for some secure function F (able to avoid any bias), whose 
details are to be determined.

The secret s SHOULD be new, but MAY be old.  It MUST be secret, and
MUST be guarded to the same degree as the static signing key.  It
SHOULD be erased after use (i.e., instead of guarded for eternity).

Only ever deviate from this if ephemeral public (kG) needs to
pre-computed for low-latency signing.  (Is this what some call a
coupon?)  In this case, the message value SHOULD be replaced by a
nonce (e.g. date). 


Reasons (and some counter-reasons in #5)
=======================================


The reasons are many, so I've added headings.


1. Actual cause of catastrophic failures
----------------------------------------

The main relevant catastrophic failure I've heard of is due to re-use
of signature ephemerals across different messages.  I don't know the
details of why these happened (even what specifications the
implementers were using), but plausible explanations of why this
failure happened is:

1a. Unclear specifications and a general lack of education.

1b. Implementers trying to save a scalar multiplication.

Perhaps others know another third reason 1c.  

Note well: point 1a is somewhat self-critical in that I've
edited/commented on a few ECDSA standards, as well as written papers
on ECDSA.

Reason 1a can be fixed by clarifying standards and publicizing
potential pitfalls.  If the implementers in question had been properly
informed, they would have adhered to the specifications by using
proper randomization, thereby avoiding this catastrophic failure.

Altering technique does not address reason 1a: if the new technique is
poorly enough explained, an implementer may sidestep it too.  In other
words, no crypto can be foolproof.  See topic #3 below.

Reason 1b is not fixed by making the ephemeral key a deterministic
function of the message: the implementer still has an incentive to
re-use the ephemeral.



2. Hindsight patching
---------------------

De-randomization is a hindsight patch, even assuming we've determined
a correct cause.  Although it looks like a clear fix, we should also
take care and apply foresight to fix similar problems.  I try to do so
in the next section.



3. De-randomization is an overcorrection
----------------------------------------

De-randomization might introduce new pitfalls for an implementer to
trip into:

3a.... More side channels?

Suppose attacker asks a target to repeatedly re-use an ephemeral by
repeatedly asking for signature on the same message.  If the signer
does not cache the scalar multiplication result, and the attacks has
some kind of side channel acces, does the repeated exposure ampifly
the risk, as in a differential side channel attack?

3b... Re-use keys more often, why not always?

A naive implementer updating an existing secure signature
implementation from randomized to de-randomization might observe that
the de-randomized version re-uses ephemeral keys more often.  They
might reason that the CFRG says this is an improvement, then maybe
even more re-use is better.  Why not re-use all keys.

Sure, we will try to explain not to such a thing!  But we could also
add an equivalent explanation for randomized signatures.  In other
words, it's not the technical differences that's more foolproof, but
rather the level of instruction.


3c....  De-randomized signing key?

If the CFRG recommendation is unclear to the implementers under
consideration, the implementer may reason as follows: if randomization
is bad for signatures, maybe I should make the long-term signing key
deterministic too.  Randomization is bad for signatures, right?
Again, a well-intentioned, but misinformed, implementer may swing the
pendulum too far in the other direction.


3d.... Increased failure to erase ephemerals?

Given a deteministic signature specification, an implementer might
reason that the ephemerals are derived from the long-term secret using
a one-way function, and therefore (!) that is no (or less) need to
erase them, or keep them within some security boundary.


3e.... Replay attacks on encryption?

We want to minimize re-use ephemeral keys (and nonces) for producing
ciphertexts.  De-randomization of signatures (for equal messages)
seems to suggest that re-use of ephemerals improves security.  If the
implementers carry this logic from signatures to key exchange or
encryption, then they might compromise semantic security because
repeated plaintexts could be rendered detectable as repeated
ciphertexts.


3f.... Loss of forward secrecy?

In ECDH, we want to maintain forward secrecy by not deriving from
ephemerals from the static secrets.  If an implementer carries over
the ephemeral generation from a deterministic signing implementation,
then forward secrecy will be undermined.


3g.... Decreased Schnorr message-hiding ability?

Some protocols may rely on non-advertised properties of signatures.

For example, consider the following definition of a message-hiding
property of signatures: the only way that a signature and a public key
can be used to learn anything about a message signed is to test the
message under the verification algorithm.

ECDSA lacks this message-hiding property: 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.

Randomized Schnorr signatures seem to have better message-hiding
capability: unless I am missing something. But de-randomized Schnorr
signatures lose this non-standard property of signatures.

This issue is similar to how we now expect collision-resistant hash
functions to be like random oracles, which far exceeds their original
purpose.


3h.... Provable security: more assumptions to prove unforgeability

What is the effect of de-randomization on the security proofs of
unforgeability? 

For example, the recent work of Koblitz and Menezes

http://eprint.iacr.org/2015/140

in Section 7.2, touches upon this issue.  In particular, they treat
the case of ECDSA, and describe two de-randomized variants ECDSA* and
ECDSA**, which differ in that ECDSA** does not use the static signing
key to derive the ephemeral, but rather a separate indpendent
alternative key.

Curiously, they argue ECDSA** is at least as good as ECDSA, but they
find an obstacle to making a similar argument for ECDSA*.

My worry with their ECDSA**, however, is that not quite foolproof: an
implementer who is likely to reuse an ephemeral may be just as likely
to choose the alternative key poorly.

Coron has some results about the limitations of provably security in
"unique" signatures.  I need to review to the details to see whether
making DL signature schemes deterministic renders them "unique", or it
Coron's result, or later generalizations, already extend to most
DL-based signature schemes.   

For what little it's worth, I can think of many silly but very weak
ways to deteministically derive ephemerals, which merely shows that
the some basic assumptions must be made for the mechanism.  Do the
current proposals even have proofs?

Intuitively, we know from lattice attacks on the signatures that
rather slighly biases in epehemerals are risky.  Furthermore, even
correlations between ephemerals are risky.  So, we need to be sure
that a determinstically-derived ephemerals does not grant the
adversary a means to induce this bias by choice of message.  If you
review the Kobtliz--Menezes proof for ECDSA**, then prove this using a
PRF.

In my limited understanding, this requires deterministic signature to
rely on a stronger assumption: a PRF.  By contrast, traditionally
signatures only needed a very mild form of PRG, which seems like less
harsh threat model than PRF because it does not permit the adversary
to query any message.

What about collisions?  If the attacker can cause the a collision in
the deterministic algorithm for generating ephemerals, then the game
is over for the signer.  Of this function has a key, so it is harder
to find collisions than in SHA1.  But if one goes to the trouble of
avoiding dependence on collision-resistant hash functions like SHA1,
then one may want some kind of argument that things do not rely on
collision resistance.  (This critique is subsumed by the earlier PRF
critique: an adversary who can find a collision in a PRF wins, so it
can be viewed as a more concrete example of the PRF issue.)

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.



4. What about verification?
---------------------------

Signers may ignore the CFRG recommendation, but such ignorance can be
detected (and tested for) if the signer generates distinct signatures
on the same message.

If a verifier sees two different signatures of the same method, then
the verifier can deduce CFRG non-compliance.  Should the verifier go a
step further and reject the signatures, on the grounds of
non-compliance?

The only wrinkle here is that the issue of secure key generation is
not very visible to other parties: it is a non-interop issue; it is
purely a security issue.



5. Maybe deterministic signatures help in other ways
----------------------------------------------------

In addition to the heavily advertised property of reducing the risk of
the implementaiton fault of an ephemeral re-used across different
messages, deterministic signatures may help in other ways, as listed
below.

Note well, these arguments favor of deterministic signatures, but I do
not feel they outweigh the arguments against.


5a.... Information-theoretically each signature, being derived from
the private key, potentially leaks some information about the
long-term static key.  In deterministic signatures, the amount of
leakage is potentially reduced, because no new information is
available to the attacker.


5b.... As I now recall, some of the provable security arguments
[Advances in ECC, Chapter 2] that I found for the security of ECDSA
did require a presumption that the signature was a deterministic
function of the message.