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

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

   Date: Fri, 19 Jun 2015 21:40:30 +0000
   From: "Blumenthal, Uri - 0553 - MITLL" <[e-mail]>

   On 6/19/15, 17:32 , "Adam Langley" <[e-mail]> wrote:

   >Ponder, for a second, a world in which CFRG specified two schemes:
   >Ed25519(m) and Ed25519(H(m))...

This is why I and others pointed out that you need to sign the choice
of H along with H(m) if you want to do this seriously:

Ed25519(`literal' || m)
Ed25519(`SHA3-512' || SHA3-512(m))
r || Ed25519(`BLAKE2S-PRF' || r || BLAKE2S-PRF_r(m))

   >I, the attacker, can register a domain name and get a certificate for
   >it. The CA happens to sign with Ed25519(H(m)), even though the
   >messages aren't very large. So, offline, I iterate over many domain
   >names and pick one where the hash of the certificate structure for
   >that name and my public-key looks like a valid CRL message. I need to
   >fix the first byte to be one, probably fix a few other length bytes,
   >and obviously my fake CRL has to be exactly the length of a hash, but
   >the work-factor is pretty plausible.

   Good point. But doesn't that imply the ability to create collisions in H()
   at will?

No, just the ability to find a message whose hash's first few bytes
are the same as the first few bytes of a valid CRL message.  If you
want to specify n bits exactly, it takes 2^n tries on average.