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

[Andrey Jivsov <[e-mail]>]

On 06/19/2015 02:32 PM, Adam Langley wrote:
> Ponder, for a second, a world in which CFRG specified two schemes:
> Ed25519(m) and Ed25519(H(m)).
>
> Also consider a PKI system that issues certificates and CRLs.
> Certificates are a type of message and are some serialisation of {0,
> name, public-key of name}, where the zero is a single byte that serves
> as a "type" indicator. CRLs are another type of message and are {1,
> start-time, end-time, list of revoked certificate hashes}.
>
> A signed message is {message, signature-algorithm, signature}.
>
> Now, you might not think that this design is wise, but I would argue
> that it's plausible as it's similar to X.509.
>
> 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.
>
> Now I register that domain name and get a certificate for it. Then I
> construct {message = fake CRL, signature-algorithm = Ed25519(m),
> signature = signature from real certificate}. That should validate,
> no? If I can construct a valid, signed CRL that covers a wide range of
> time then I've broken revocation in this system.
>
> The key here is that the attacker can specify the signature algorithm
> and confuse the verifier. X.509 allows exactly this but, even if not,
> I suspect that people will use the same key in several different
> contexts like that.
>
> So we would need to be careful with Ed25519(H(m)).
>
We can stress that IUF is a property of the key. I think this is a 
natural thing to do.

Randomized signatures mitigate these concerns too. The attack Adam 
described assumes that the attacker controls the image of the H(m) fed 
by the CA to Ed25519.

Compare this with sig = nonce | Ed25519(H(nonce | m))), where the signer 
picks/derives the unpredictable nonce somehow. Applications that want 
IUF need it for "large" files, and they shouldn't mind expanding the 
signature with an explicit nonce.

( On Adam's particular attack, it's odd that a (small) X.509 cert is 
signed as Ed25519(H(m)), but a (large) CRL as Ed25519(m) ).