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

[Rene Struik <[e-mail]>]

Hi Taylor:

I  think that lots of assertions and claims in the email poll are 
somewhat (or, perhaps, a lot) "off" and put people (at least me) on the 
wrong footing. Hence, my email.

Thanks for your anecdotal pointers, which are well-documented factoids 
of in-expert implementations (aka stupidity).

Rene

On 6/3/2015 6:47 PM, Taylor R Campbell wrote:
>     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.)


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]