Subject: [Cfrg] MakingEdDSA non-collision-resistant

From: Simon Josefsson <[email-masked]>
Date: Wed, 10 Jun 2015 16:28:28 +0200

Hi.

I've been thinking about how to construct a non-collision-resiliant
signature scheme based on the collision-resiliant EdDSA, in order to
comply with how I interpret the newly imposed CFRG requirement to
support streamed IUF-modes.

A simple approach would be to specify a process like this:

  Non-CR-Ed25519-SHA256(K, M) := Ed25519(K, "SHA-256" || SHA-256(M))

The hash function to use would then be parametrizable by modifying the
constant string "SHA-256" to the name of some other function, and use
that function instead of SHA-256 to compute the hash of the message to
sign.  The string could be replaced with any string that is unique for
each hash.

Thoughts on this construct?

Having someone do proper theoretical security proofs of it would be
useful.  You would reduce the security assumptions to that of the EdDSA
signature algorithm and the collision-resistance property of the hash
function.

This construct will have the same unwanted security properties as RSA
and ECDSA have wrt having streamed untrusted data around.  I'm sure
implementers will shoot themselves in the foot with the approach -- just
like they do with RSA/ECDSA -- so a security consideration on this
aspect is warranted.  An "The Init-Update-Finish API is Considered
Harmful" text if you want.

Another approach would be to sign continously like Bernstein suggested,
by splitting up m into many packets p0, p1, ... pn:

   * packet p0 plus a signature s0 of ("start",p0);
   * packet p1 plus a signature s1 of ("middle",s0,p1);
   * packet p2 plus a signature s2 of ("middle",s1,p2);
   * ...;
   * last packet pn plus a signature of ("end",previous s,pn).

This has the advantage that it keeps the collision-resiliance property
at the expense of the cost of doing many signatures.  This approach
would need to discuss how packets are split up, which you can do in many
ways.

Both approaches would be add-on's to EdDSA itself, so they would be
optional modes.

/Simon

---

From: Taylor R Campbell <[email-masked]>
Date: Wed, 10 Jun 2015 18:01:22 +0000

Date: Wed, 10 Jun 2015 16:28:28 +0200
   From: Simon Josefsson <[email-masked]>

If you randomize this with an unpredictable 128-bit nonce r, yielding

r || Ed25519(K, "SHA-256" || r || SHA-256(r || M)),

then all you need is *either* an entropy source at signing time *or*
collision resistance of SHA-256.

Note that in this case, picking r = 0 deterministically doesn't
destroy the security of the scheme, unless collisions are found in the
function M |---> SHA-256(0 || M).  But randomization provides some
defence against cryptanalysis of the hash function like we saw with
MD5 leading to certificate forgery, thanks to RSA, Inc.'s change to
RSASSA-PSS to use H(r || H(M)) instead of H(r || M).

(This scheme still requires (r, M) |---> SHA-256(r || M) to be target-
collision-resistant -- but Ed25519 requires the same of SHA-512, and
there's been no evidence that either function is likely to flunk that
property.)