[CFRG] Re: Do we have unsafe uses of Ed448 and Ed25519? Fix, Ed448?

[Mike Hamburg <[e-mail]>]

Hi Dan,

If I skimmed Kaliski’s paper correctly, it doesn’t claim that hash function firewalls are ineffective in general, just that *some* such firewalls do not prevent certain attacks.  If a verifier only accepts strong hash functions then the schemes Kaliski studied are strong, but the attacks come into play if the verifier would accept either a strong or a weak hash.  Ideally if a signer only signs messages with strong hash functions, then it should still be infeasible to forge even if the verifier would accept a weaker one.  But the paper shows that for some hash firewalls such a forgery is possible, in that a preimage attack on the hash suffices to forge a signature.

Phillip points out that this vulnerability applies to EdDSA with prehash mode, because it doesn’t have a firewall at all, except between “yes prehash” and “no prehash".  EdDSA uses a fixed hash function internally: SHA-512 for Ed25519, or SHAKE256 for Ed448.  But the prehash mode signs the hash of a message, without indicating what hash function was used.  So if an attacker can convince a victim to use a weak hash for verification, then they could forge messages, even if SHA-512, SHAKE and any other hash the legitimate signer used remain unbroken.  For example the attacker could obtain a legitimate signature on some M using e.g. SHA512 as the prehash, but then tell the victim that it is a signature on some M’ using some weak hash as the prehash, where WeakHash(M’) = SHA512(M) — using a preimage attack to find M'.  If the verifier would accept signatures using weak hash function, then they would be fooled by this forgery.

The same attack does not apply to ML-DSA unless SHAKE is broken, because ML-DSA’s prehash mode indicates what hash was used for the message.  If a signer signs a prehashed message using a weak hash function, then this can be used to create a forgery (using e.g. a collision or second-preimage attack), but if they only sign using strong hash functions (and if SHAKE and ML-DSA itself remain strong) then such forgeries would not be possible.

Regards,
— Mike

> On Sep 11, 2024, at 11:48 AM, Dan Brown <[e-mail]> wrote:
> 
> Kaliski argued (AFAICR) that hash firewalls in signatures were ineffective:
> 
> Kaliski, B.S. (2002). On Hash Function Firewalls in Signature Schemes. In: Preneel, B. (eds) Topics in Cryptology — CT-RSA 2002. CT-RSA 2002. Lecture Notes in Computer Science, vol 2271. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45760-7_1
> 
> What has changed since 2002 to support effectiveness of a hash firewall, such as the proposal below?  Was this hash firewall in HashML-DSA deemed effective?   If the HashML-DSA hash firewall is effective, then what is the new distinction, perhaps about lattices, that made Kaliski's observations inapplicable?  (No rush: I can scan PQC-forum to find out, re-read Kaliski 2002, etc.)
> 
> Date: Tue, 10 Sep 2024 14:02:57 -0400
> From: Phillip Hallam-Baker<[e-mail]>
> ...
> The concern is a downgrade attack where the attacker substitutes a weak
> digest for a strong one. Some people seem to think this is an implausible
> attack but it really is not because there is no way for the signer to
> control the set of digests accepted by the verifier.
> 
> For example, Alice signs a PDF document and sends it to Bob who checks it
> using an application that Mallet has added his own digest verifier to. Yes,
> this assumes a degree of platform compromise but so does every
> privilege escalation attack and those are something we worry about A LOT.
> The reason we spent so much time over RSA signature modes was precisely
> because this is a critical security concern and the RSA padding matters.
> 
> So the rule is that when you have a signature over a digest value, you MUST
> always sign the data itself or a manifest that includes the digest value
> and the digest algorithm.
> ...
> So what I propose is we specify a proper prehash mode for Ed25519 and Ed448
> and any other algorithm that doesn't provide binding of a chosen digest to
> the algorithm used to produce it by specifying a manifest format that can
> be applied generically.
> 
> Does not have to be fancy, in fact I would just take the ML-DSA
> construction:
> 
> 𝑀′ ← BytesToBits(IntegerToBytes(1, 1) ∥ IntegerToBytes(|𝑐𝑡𝑥|, 1) ∥
> 𝑐𝑡𝑥 ∥ OID ∥ PH𝑀)
> 
> And the only thing I would change there is to replace the ML-DSA version
> identifier with an OID off an IETF arc to denote the manifest construction.
> 
> 
> 
> <OpenPGP_0xE712051E172D17CD.asc>_______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]