[Cfrg] 8032(PureEdDSA) question

[Dan Brown <[e-mail]>]

Hi CFRG,

A pedantic question about RFC 8032 claim (and any similar claims about 
PureEdDSA):

"The collision resilience property means EdDSA is secure even if it is 
feasible to compute collisions for the hash function."

This claim fairly advertises a defense in depth against a security collapse in 
the hash.  Fine!  But shouldn't it also very clearly delimit this defense?  As 
it stands now, it seems like slight exaggeration, because "even if it is 
feasible to compute collisions" is rather open-ended.

My suggestion would be *either* to amend the main claims as

"The collision resilience property means EdDSA is secure even if it is 
feasible to compute collisions for the hash function, provided the hash 
remains at least  <XYZ-secure> ",

for some value of <XYZ-secure>.

As I recall, <XYZ-secure> should include things like prefix 2nd preimage 
resistance (to prevent some forgeries, and maybe to make security proofs work 
...) and pseudorandom (to protect r generation).  I forget the details, but I 
think that there is also a loose consensus on what <XYZ-secure> would be.

Either the amendment above, *or* just point out the well-known hash-collision 
attack on HashEdDSA, but then not promise anything about PureEdDSA, letting 
silence (on the latter) speak louder than words (imprecise promises).  This 
might entail more changes to the document.

An amendment could be an erratum (though I am unfamiliar with the 
process/purpose of errata).  Moreover, any future RFCs on PureEdDSA might 
address also try to this issue.  Academically, could I be reminded what the 
consensus on <XYZ-secure> is (if any)?

Of course, perhaps, contrary to my opinion, there is also consensus that 
adding a proviso is unnecessary (due to limitation of "collision" being 
self-sufficient and implicit as a delimiter)?

Best regards,

Dan

PS  More details:

There are some security proofs for Schnorr signatures, which surely apply to 
EdDSA (whether one likes provable security or not).  I once looked at this 
issue, but now I mostly forgot those details, but they probably provide some 
help on stating part of what should go into <XYZ-secure>.  I can probably 
review this to find some phrasing.

Usually there is gap between proofs and reasonable intuition: so <XYZ-secure> 
might reasonably include less stringent hash security than what the security 
proofs offers.

***

Next I elaborate on my concern about delimiting collision attacks, with a 
speculative example.  The phrase

"... feasible to compute collisions for the hash function"

conditionally hypothesizes some unknown collision algorithm.  Since it enters 
into hypothetical territory and persuasion of the reader of security in this 
territory, the reader might be forgiven for thinking it claims that PureEdDSA 
is safe against a very strong hash collision attack like the following:

An adversary might know a set of L (say 2^50) message extensions M1,...ML, 
such that H(X,M1),...,H(X,ML) is likely to contain to contain a collision, for 
any choice of X and without M1,..,ML depending on X (though which messages 
collide may somehow depend on X).

I don't know enough about collision attacks (e.g., on MD5 and SHA1) to say how 
unlikely such an attack is, though I can see that it is very strong attack.

Of course, this attack is *also* a (weak) attack on H(X,-) as pseudorandom 
function (with secret X).

For PureECDSA, with its deterministic signature generation, this hash attacker 
could then ask a signer to sign each of M1,...,ML.  One of these is likely to 
collide giving the same r value in the signature.  The r collision enables the 
adversary to recover the signing key s, and then forge arbitrarily many 
messages.

Of course, this is very high-cost forgery, since 2^50 signatures is excessive. 
So, it may be rated as a low impact on security.

Also, I don't think that this strong hash collision attack would imply an 
attack on random r version of EdDSA signing.  To be clear, I am *not at all* 
saying that this hypothetical attack is more likely than a fumbled 
implementation of random r, or that it justifies random r.  The point here 
concerns only a reader's state of mind.  Some reader might contemplate the 
security of PureEdDSA by focusing at attacking the verifier, ignoring the 
issue of how signatures are generated.  This reader then mistakenly concludes 
that PureEdDSA is safe in the presence of this strong hash collision attack, 
because this hash attack does not lead to a forgery (if one ignores how the 
signer generates r).

Anyway, this remote risk seems easily and well-resolved by adding some kind of 
"pseudorandom" property for the hash into <XYZ-secure>.  This delimitation 
would clearly rule out such a strong collision attack (without relying on, for 
example, the fuzziness of the meaning of feasible).

I think that the pseudorandom qualities of H have been put forward in various 
places (including CFRG) as very reasonable defense to PureEdDSA's method of 
generating r.   So, I don't think there is any controversy that pseudorandom H 
defeats such an attack.  There may be some question on how to formulate the 
pseudorandom property - the example above shows a weak pseudorandom attack 
leads to a weak forgery.

(Again: I expect the main the controversy might be whether it is necessary to 
spell out the adversarial limitations in a proviso, or whether everything I am 
saying is made 100% implicit by use of the work "collision".)

***

8032 also says

"One of the parameters of the EdDSA algorithm is the "prehash" function.  This 
may be the identity function, ..."

Which might be worth amending as  "... The prehash (but not the hash) may be 
the identity function, ...".

Because, if the prehash were (absurdly) replaced by an identity function, 
things go quite awry.

As with the <XYZ-secure> amendment , an alternative amendment might also be 
possible by saying much less, not mentioning the identity function at all. 
(Replacing a hash function by identity function is playing with fire: great 
for exposition to dramatically make a point, but not so cool for a standard.)