Content-Type: text/plain;
	charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3776.700.51\))
From: Mike Hamburg <mike@shiftleft.org>
In-Reply-To: <f49bcf97-1612-4252-b682-60b7a868f500@gmail.com>
Date: Wed, 11 Sep 2024 13:35:07 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <CA345BC5-C207-4212-A556-EC2DF6E304EF@shiftleft.org>
References: <f49bcf97-1612-4252-b682-60b7a868f500@gmail.com>
To: Dan Brown <dan.brown.cryptographer@gmail.com>
Message-ID-Hash: TTUGJ7BOPP2F7PKRZAG3BMFTFQ5W4C6X
CC: cfrg@irtf.org
Precedence: list
Subject: =?utf-8?q?=5BCFRG=5D_Re=3A_Do_we_have_unsafe_uses_of_Ed448_and_Ed25519=3F_Fi?=
	=?utf-8?q?x=2C_Ed448=3F?=
Archived-At: 
 <https://mailarchive.ietf.org/arch/msg/cfrg/WbIz-UyNwHG2Bm0jseSGg3GBcgQ>

Hi Dan,

If I skimmed Kaliski=E2=80=99s paper correctly, it doesn=E2=80=99t 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=E2=80=99t have a firewall at all, except between =
=E2=80=9Cyes prehash=E2=80=9D and =E2=80=9Cno 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=E2=80=99 using =
some weak hash as the prehash, where WeakHash(M=E2=80=99) =3D SHA512(M) =
=E2=80=94 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=E2=80=99s 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,
=E2=80=94 Mike

> On Sep 11, 2024, at 11:48=E2=80=AFAM, Dan Brown =
<dan.brown.cryptographer@gmail.com> wrote:
>=20
> Kaliski argued (AFAICR) that hash firewalls in signatures were =
ineffective:
>=20
> Kaliski, B.S. (2002). On Hash Function Firewalls in Signature Schemes. =
In: Preneel, B. (eds) Topics in Cryptology =E2=80=94 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
>=20
> 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.)
>=20
> Date: Tue, 10 Sep 2024 14:02:57 -0400
> From: Phillip Hallam-Baker<phill@hallambaker.com>
> ...
> 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.
>=20
> 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.
>=20
> 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.
>=20
> Does not have to be fancy, in fact I would just take the ML-DSA
> construction:
>=20
> =F0=9D=91=80=E2=80=B2 =E2=86=90 BytesToBits(IntegerToBytes(1, 1) =E2=88=A5=
 IntegerToBytes(|=F0=9D=91=90=F0=9D=91=A1=F0=9D=91=A5|, 1) =E2=88=A5
> =F0=9D=91=90=F0=9D=91=A1=F0=9D=91=A5 =E2=88=A5 OID =E2=88=A5 PH=F0=9D=91=
=80)
>=20
> 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.
>=20
>=20
>=20
> =
<OpenPGP_0xE712051E172D17CD.asc>__________________________________________=
_____
> CFRG mailing list -- cfrg@irtf.org
> To unsubscribe send an email to cfrg-leave@irtf.org