Incremental API for pure Ed25519?

[LoupVaillant]

Unless we’re willing to risk ECDSA-like footguns, EdDSA signatures require 2 pass over the message. EdDSA verification on the other hand only requires a single pass. I believe it hints at a legitimate use case for an incremental API for verification, Ed25519ph notwithstanding: the machine who performs the signature and the machine who performs the verification are almost never the same. In some cases, the issuer may have much more RAM at their disposal than the verifier. It would be nice for the verifier to be able to use an incremental API that requires little RAM in all cases, including pure Ed25519.

One instance where this might be useful is minisign: when used to sign big messages, it issues a warning advising the user to switch to Ed25519ph with the -H option. Thing is, the only reason this warning is needed in the first place, is because libsodium currently doesn’t have an incremental API for pure Ed25519, so minisign must allocate a giant buffer to verify the message. The problem with that warning is that the threshold is somewhat arbitrary, and it’s not always clear for the issuer what the capabilities of the verifier might be. If we added an incremental verification interface for pure EdD25519, this wouldn’t be a problem: every machine could verify any Ed25519 message, and the decision to switch to Ed25519ph would only depend on how much RAM the issuer has —a known quantity in most cases.

Now one might punt on the issue and use Ed25519ph all the time. This causes two issue: first, we lose hash collision resilience. While I don’t think we’ll find any collision in SHA512 any time soon, others may be more nervous about it. Second, pure Ed25519 is just plain more popular, and this could become a compatibility issue.

Would you be willing to consider accepting a pull request that adds an incremental API to pure Ed25519 verification?

[jedisct1]

It's already very simple to compute a signature without keeping the entire message in memory. Either using ed25519ph, or by prehashing the message with any collision-resistant hash function.

This is an opportunity for applications to use faster hash functions than sha512 if necessary.

Applications may also rely on the fact that ed25519 is deterministic. Getting deterministic signatures if the input is processed as a single chunk, and non-deterministic signatures if the same input is split into multiple chunks would be very confusing.

So, I don't think we should introduce another way to do what's already possible, especially since that other way now requires a CSPRNG. The ability to sign without the need for a randomness source is a useful property of ed25519. We should keep it, especially since prehashing is a simple operation and, for large messages, can increase performance.

[jedisct1]

Oops, my bad. After a second read, I realized that you were talking about verification only 😄

A streaming verification API may indeed be useful. I'll see what I can do. Thanks for suggesting this!

[LoupVaillant]

Nice, thanks. Let me know if you'd rather have someone else do the work, I believe I can propose a PR (well, provided reviewing a PR is not more work than doing it yourself…).

[enkore]

A concern with incremental sign and authenticate APIs is that they make it easy to start using data before the signature / authtag is checked. The docs have a mild warning for the pre-hashed sign function family, I think a similar warning should be put in front of an IUF verify function in case it is added.

[ivmaykov]

While people are here discussing incremental Ed25519 APIs I'd like to once again raise the question of adding a pre-hashed API where someone else computes the SHA-512 hash of a message and provides only the hash to libsodium, and the resulting signature is the same as calling the multi-part ed25519ph API on the message.

Use case: a remote signing service which holds private keys, client wants to sign large messages (think multi-GB binaries) without having to transmit the entire message to the service. So, client computes the SHA-512 then sends it to the service and gets back a standard Ed25519ph signature that can be verified by using the multi-part ed25519ph API.

I can hack around the lack of such an API in LS (e.g. by using Ed25519pure(SOME_HASH(message)) instead of Ed25519ph(message)), but I prefer to stick to standards. My other option is to fork libsodium internally, which I don't particularly want to do either.

I think I had a pull request that implemented this at some point which was rejected, but if I can convince @jedisct1 that this is worth implementing, I'm willing to do all the implementation grunt work :)