Consistently implement `DigestSigner/Verifier` as non-pre-hash signatures

[daxpedda]

Following up on #2003 we want to figure out how to implement DigestSigner/Verifier for PureEdDSA.

With dalek-cryptography/curve25519-dalek#828, we will add DigestSigner/Verifier implementations directly on SigningKey/VerifiyingKey/Context, which end up creating a HashEdDSA (ed25519ph) signature.

The initial idea was thrown around to add a hazmat ZST that would implement DigestSigner/Verifier for PureEdDSA, using the already available raw_sign_byupdate(). The reasoning for adding it in hazmat, is that we can't ensure on a type level that users are really updating the hash function with the same message. I'm not sure how strong that reasoning really holds.

---

However, thinking about this again, I'm not sure we are going down the right path. Currently DigestSigner/Verifier is able to offer a trait over various signatures, including ML-DSA, that uses the pre-hash mode of that signature. Even if ML-DSA's pre-hash mode produces the same signature as the regular one.

Re-using that same trait for the regular mode of a signature, would only be applicable for curve25519-dalek and ed448-goldilocks, in addition to being behind hazmat modules (ergo separate types). I'm not sure how valuable a common trait, for different modes, that is only selectively available, is in a real-life scenario.

I'm thinking it might be better if we had a separate trait for regular mode signatures that can really be applied for all signatures. So instead I propose the following:

• Rename PreHashSigner to RawPreHashSigner.
• Rename DigestSigner to PreHashSigner, making it clear that this is using the pre-hash mode of the signature.
• Add a new DigestSigner which uses the regular mode of the signature.

The signature would be the same as the current DigestSigner, which I believe works fine as all signature algorithms I know of use a hash internally.
I should probably point out that the transition might be problematic for users because we are re-using the DigestSigner name for a different signature mode.

(I decided to post this here instead of curve25519-dalek because my concerns about the signature API, instead of questions about the implementation)

[tarcieri]

However, thinking about this again, I'm not sure we are going down the right path. Currently DigestSigner/Verifier is able to offer a trait over various signatures, including ML-DSA, that uses the pre-hash mode of that signature. Even if ML-DSA's pre-hash mode produces the same signature as the regular one.

External mu isn't a "prehash" mode, it requires key-specific inputs to the hash function prior to the message. The changes #2003 proposed make that possible, and we can't similarly impl the PrehashSigner/PrehashVerifier traits for the same algorithm. That was the whole impetus for #2003: now the DigestSigner/DigestVerifier traits fit a shape which can't always be fit by PrehashSigner/PrehashVerifier and are no longer redundant in that regard.

There is an alternate prehash API for ML-DSA called HashML-DSA, which is effectively a different algorithm, ala Ed25519ph. One observation is Ed25519ph largely failed in practice and doesn't get used, because it's a hassle to use an algorithmic variant that can't be verified by standard implementations.

The prehash modes completely sacrifice avoidance of collisions, whereas the external mu approach can help mitigate chosen prefix collisions. I would expect future signature algorithms to adopt a similar approach, where as the two-pass approach Ed25519 uses to address the same problem may be overkill and makes it difficult to build these sort of update-oriented APIs, so I don't think we'll see it repeated.

[daxpedda]

I was aware of HashML-DSA, but thought that external µ is also considered a pre-hash mode. But yeah, it makes sense that the point of "pre-hash mode" is to not take any key-specific inputs.

That was the whole impetus for #2003: now the DigestSigner/DigestVerifier traits fit a shape which can't always be fit by PrehashSigner/PrehashVerifier and are no longer redundant in that regard.

Actually I'm proposing to change it the other way around. ecdsa, curve25519-dalek and ed448-goldilocks currently use DigestSigner/Verifier for pre-hash mode signatures. My proposal is to change them to regular mode signatures.

Basically, the goal is to settle on a single trait that can be implemented universally, which exposes the non pre-hash mode signature with a streaming interface. We already have that with a non-streaming interface: Signer/Verifier. We also have that for pre-hash modes, PreHashSigner/Verifier (which doesn't need a streaming interface anyway).

I believe that DigestSigner/Verifier fits that bill. We don't necessarily have to add new traits for pre-hash modes.

So to lay out my proposal in more detail:

• Change ecdsa DigestSigner/Verifier implementations to regular mode signatures.
• Change curve25519-dalek and ed448-goldilocks DigestSigner/Verifier implementation to regular mode signatures.
• PreHashSigner/Verifier remains for pre-hash mode signatures.
• Optionally rename PreHashSigner/Verifier to RawPreHashSigner/Verifier and introduce a new PreHashSigner/Verifier with the old fn(digest: D) interface to expose pre-hash mode signatures outside of hazmat.

This way we would have a single streaming interface for non pre-hash mode signatures for all our curves.

I would expect future signature algorithms to adopt a similar approach, where as the two-pass approach Ed25519 uses to address the same problem may be overkill and makes it difficult to build these sort of update-oriented APIs, so I don't think we'll see it repeated.

AFAIK SLH-DSA faces the same problem already. I would like DigestSigner/Verifier there to also use the non pre-hash mode signature instead of HashSLH-DSA (which we don't implement right now anyway).

[tarcieri]

I was aware of HashML-DSA, but thought that external µ is also considered a pre-hash mode. But yeah, it makes sense that the point of "pre-hash mode" is to not take any key-specific inputs.

It used to be defined here: https://docs.rs/signature/2.2.0/signature/trait.PrehashSignature.html

Though that trait has sense been removed. Perhaps the associated documentation can be moved to PrehashSigner.

Change ecdsa DigestSigner/Verifier implementations to regular mode signatures.

ECDSA doesn't have a special prehash mode: hashing the raw message is a normal part of the operation of the signature algorithm. I don't know what change you would even have in mind.

curve25519-dalek and ed448-goldilocks DigestSigner/Verifier implementation to regular mode signatures.
PreHashSigner/Verifier remains for pre-hash mode signatures.

I thought the prehash mode was implemented on a special context object to capture that particular parameter of Ed25519ph, though I guess I'll need to re-review.

I would agree it would be better not to mix the algorithms supported by a given key type, e.g. Ed25519ph could use its own keys (which can also capture the context).

I'll also add that generally I'm not a fan of the prehash modes and I'm not alone. I'm not sure if HashML-DSA is worth supporting for example, and certainly would deprioritize it until we're happy with our external mu implementation.

[daxpedda]

Change ecdsa DigestSigner/Verifier implementations to regular mode signatures.

ECDSA doesn't have a special prehash mode: hashing the raw message is a normal part of the operation of the signature algorithm. I don't know what change you would even have in mind.

There isn't, my bad.

curve25519-dalek and ed448-goldilocks DigestSigner/Verifier implementation to regular mode signatures.
PreHashSigner/Verifier remains for pre-hash mode signatures.

I thought the prehash mode was implemented on a special context object to capture that particular parameter of Ed25519ph, though I guess I'll need to re-review.

It is, but DigestSigner does Ed25519ph as well and just uses an empty context.

I would agree it would be better not to mix the algorithms supported by a given key type, e.g. Ed25519ph could use its own keys (which can also capture the context).

I guess that's the ideal scenario: a complete type separation of regular and pre-hash signatures.

I'll also add that generally I'm not a fan of the prehash modes and I'm not alone. I'm not sure if HashML-DSA is worth supporting for example, and certainly would deprioritize it until we're happy with our external mu implementation.

Personally: I've absolutely no stake or interest in pre-hash mode signatures.

---

I guess then my proposal boils down to just changing curve25519-daleks DigestSigner/Verifier to use PureEdDSA.
Apologies for my obvious oversights!

[tarcieri]

The reasoning for adding it in hazmat, is that we can't ensure on a type level that users are really updating the hash function with the same message. I'm not sure how strong that reasoning really holds. [...] I guess then my proposal boils down to just changing curve25519-daleks DigestSigner/Verifier to use PureEdDSA.

Before exposing it outside a hazmat context, we should probably ensure that misuses don't leak the private key

[daxpedda]

I thought that this attack relies on passing the wrong public key? Not on two different messages being used during the two hashing passes.

I have no idea how to ensure on a type-level that Fn(&mut Digest) uses the same message. While Fn should signal non-mutability to the user, there's definitely ways to get around that. I'm also afraid that users will request we change it to FnMut to be able to use Reader APIs inside the closure.

Alternatively, we can still move DigestSigner/Verifier to some ZST in hazmat.
Worst case scenario we just don't implement it at all. Which at least fulfills the goal of consistency between which traits use which signature modes.

[tarcieri]

I thought that this attack relies on passing the wrong public key? Not on two different messages being used during the two hashing passes.

I think there's the potential for a similarly catastrophic vulnerability. The aforementioned vulnerability occurs because two signatures are produced for the same message but with different public keys. And I think there's similar possibility for something like that to go wrong in the event the same message is used for two signing operations for the first/second pass but one of the four doesn't match, which would produce two signatures e.g. for different messages under the same "nonce", or for the same message but under different nonces. The latter would be similar vulnerability to what's seen with fault injection attacks.

EdDSA's security as a deterministic signature algorithm relies on all of those inputs actually being deterministic, and it fails catastrophically if there's a way to produce duplicate signatures with "tweaked" inputs that don't meet the requirements.

[daxpedda]

I see, kinda makes sense to me.

So I think whats left to do is:

• Open an issue in curve25519-dalek to figure out how to proceed.
• Open a new issue for my RawPreHashSigner/Verifier idea.
• Figure out if we are hitting the same issue in slh-dsa: implement DigestSigner/Verifier signatures#1075.