RFC8032 (section 8.7) states that IUF (Init, Update, Finish) should not be used in Ed25519 API:

Avoid signing large amounts of data at once (where "large" depends on the expected verifier). In particular, unless the underlying protocol does not require it, the receiver MUST buffer the entire message (or enough information to reconstruct it, e.g., compressed or encrypted version) to be verified.

This is needed because most of the time, it is unsafe to process unverified data, and verifying the signature makes a pass through the whole message, causing ultimately at least two passes through.

As an API consideration, this means that any Initialize Update Finalize (IFU) verification interface is prone to misuse.

It is a bad idea to modify Ed25519 or Ed448 signing to be able to create valid Ed25519/Ed448 signatures using an IUF interface with only constant buffering. Pretty much any error in such would cause catastrophic security failure.

Why? What implications does it have?

  • $\begingroup$ The same requirement makes JCE providers not stream AES/GCM decryption since the authentication can only be verified after processing all data. If you release some before you might be exploited by unverified data. This is actually a NIST requirement, One reason for processing streams or large files only in segments. $\endgroup$ – eckes Nov 28 '17 at 23:00
  • $\begingroup$ ObJava: Oracle JCE buffers AES/GCM to be compliant/safe, BouncyCastle chooses to stream for performance. $\endgroup$ – eckes Nov 28 '17 at 23:02

What implications does it have?

That's because, as designed, Ed25519 does two passes over the message that is being signed:

  • It first hashes the message (and secret data) to construct the internal value $r$ (which is used to compute the public value $R$)

  • It then hashes the message (and the public value $R$) to construct the public value $S$.

Because of the ordering of the hashes in the second pass, the first pass must be completed before starting the second pass [1]

Now, the verifier cannot check that $r$ was constructed correctly, and so you could (say) select a random value in its place, which would allow you to create a signature with a single pass. However, if you did that, and got it wrong (say, using the same $r$ to sign two different messages), you just leaked the private key; Ed25519 was designed to avoid such possibilities.

[1]: Random musing: if you modify Ed25519 by changing the ordering of the hashes $H(R, A, M)$ to, say, $H(A, M, R)$, you could perform it in a single pass (performing both hashes in parallel). Of course, the verifier would need to know about the modified hash ordering. I speculate Dan did it the way he did because that change would require a stronger security assumption on the hash function; as it is, Ed25519 assumes second preimage resistance, rather than collision resistance.

  • $\begingroup$ Thank you for such a good answer. It looks like not exposing IUF outside the sign/verify function, but using it internally is okay. $\endgroup$ – warchantua Nov 28 '17 at 17:27
  • $\begingroup$ @warchantua: if it was such a good answer, why don't you show some love and upvote it... $\endgroup$ – poncho Nov 28 '17 at 18:45
  • $\begingroup$ Unfortunately I have less than 15 reputation :( $\endgroup$ – warchantua Nov 28 '17 at 18:46
  • $\begingroup$ Update: Now I have enough. +1 $\endgroup$ – warchantua Nov 28 '17 at 19:27
  • $\begingroup$ About the random musing: The Ed25519 paper on p. 9 et seq. notes the collision resistance of $H(R, M)$ over $H(M, R)$, which djb explained in detail on the cfrg mailing list. $\endgroup$ – xorhash Apr 25 '20 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.