Re: [Cfrg] Elliptic Curves - signature scheme: friendliness to low memory implementations (ends on June 3rd)

[Taylor R Campbell <[e-mail]>]

   Date: Wed, 03 Jun 2015 17:14:57 -0400
   From: Rene Struik <[e-mail]>

   Isn't the double signing merely an artifact of running the Schnorr 
   signature scheme in a mode where the ephemeral private key is 
   deterministically derived from message and private info?
   I don't see how this would apply with the original Schnorr scheme, since 
   there one simply has s:= k - e d (mod n), where e=h(m,R), where R:=kG, 
   where n size of prime-order subgroup, and where k is randomly picked. 

Requiring signers to have a source of entropy at signing time to
randomly choose a distinct k for each signature has historically been
a source of high-profile cryptography disasters[1][2].

The NIST was warned about this in 1991 when standardizing the DSA, and
ignored the warning[3], claiming that entropy at signing time is no
more likely to be bad than entropy at key generation time.  Debian
showed them wrong.

There are three security concerns in Alexey's poll and your question:

(a) secret key recovery if k is reused or even slightly predictable,

(b) signature forgery if the attacker can find collisions in the hash
function, and

(c) denial of service or processing of unauthenticated data if a
protocol requires the verifier to consume arbitrarily large messages
before verifying the signature.

Randomized DSA- or Schnorr-type schemes that use an entropy source at
signing time are vulnerable to (a).  You can defend against this (and
EdDSA does) by hashing the secret key together with the message to
derive k deterministically: the secret key is unpredictable to the
attacker, so standard PRF assumptions imply k is unpredictable too.
(Bonus: easy test vectors for the real signing code.)

Schemes defined in terms of H(m) for a fixed H are vulnerable to (b).
You can defend against this (and EdDSA does) by using a keyed hash
H_k(m) and relying only on target collision resistance instead of
collision resistance.

You could defend against both (a) and (b) by hashing the message under
a different key, say h, and signing H_h(m) -- that is, choose h
randomly, compute H_h(m), and derive k from the secret key and H_h(m)
to sign the message h || H_h(m).  But this leaves (c).

Protocols designed under the assumption of streaming I/U/F are likely
to be vulnerable to (c).  You can defend against this (and EdDSA does)
by encouraging protocol designers to sign and verify short messages
rather than long ones, and to split long messages into independently
verifiable parts, e.g. by signing each part separately or signing the
root of a Merkle tree of parts.


[1] Debian broke OpenSSL's PRNG seeding so that it had only 2^15
possible seeds, enabling recovery of (EC)DSA secret keys used on
affected systems with predictable k even if the secret key was
otherwise secure.  https://wiki.debian.org/SSLkeys

[2] Sony reused k verbatim for PlayStation 3 firmware updates signed
with ECDSA, enabling recovery of the firmware signing key.

fail0verflow, `Console Hacking 2010: PS3 Epic Fail', 27c3, 2010.
http://events.ccc.de/congress/2010/Fahrplan/attachments/1780_27c3_console_hacking_2010.pdf

[3] Miles E. Smid and Dennis K. Branstad (NIST), `Response to Comments
on the NIST Proposed Digital Signature Standard', CRYPTO'92, LNCS 740,
pp. 76--88, Springer, 1993.  (See Sec. 4.9 about k.)