Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id C4A80C14F6B5 for ; Thu, 29 Aug 2024 10:54:19 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -6.654 X-Spam-Level: X-Spam-Status: No, score=-6.654 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.001, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.25, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01] autolearn=unavailable autolearn_force=no Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Jc0MK8914dQk for ; Thu, 29 Aug 2024 10:54:18 -0700 (PDT) Received: from mail-pj1-f41.google.com (mail-pj1-f41.google.com [209.85.216.41]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature ECDSA (P-256) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 721CEC14F5E7 for ; Thu, 29 Aug 2024 10:54:18 -0700 (PDT) Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-2d46f2816c0so718929a91.2 for ; Thu, 29 Aug 2024 10:54:18 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1724954058; x=1725558858; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=pgOHn8b5rsNOO9bwqlHOWG4AAADaJq4fnw8RFeN7MIE=; b=f4vY0eN3fhaaz0yCyKMZnd7at6Yqi90B4cbGwhuTGJrRCFyjjKUvYFI9J12Xg9oKUK ilUIouolKANLXSyC2ozxB9LiD28ifBlq+FcMUGfIVXjjGVAaqsHuCRzEk+4soPdOohjr ADlvHm2fsOxpw1g2BVxy11rXjhanIkSnhWCrznk+xjFv+5JJMih75/7LxCjOxjmls8eY uXRkBg60TxXSkKnoSgDUCL5nGgUOq6MtpdAEUCiyGg7InHvOJPlnFiw285anMRoo411a seE7ggB1iS1BOl9QtjYAPq1IG/J+Kj/xj+wfSp1egFO7nfSK26sAALTlMnt0lhmkDS2m VG1Q== X-Forwarded-Encrypted: i=1; AJvYcCVF3zm/PNflH2XpKMm6yhr0SLpNNdt/J7G9rdsa/Za4bKJU8jR4AV6PIOnjQgvLXSkZhWSv@irtf.org X-Gm-Message-State: AOJu0YxlRtwa4nnZXNPZ1GsNoVB6STV2ldazjwjekFKDo22u4TvU9UnO RAl66TCPSfVRnbi6tfxxFFUfHcs82/ewX21L9uxR056gyFPNCS0z2KCiIfjs2XLNFv9E62NTLHA T+UC/2E9XJi5FP1IWygu9JEeyot4= X-Google-Smtp-Source: AGHT+IHpFvzG5Yc1jI9uHsTz4OdLObNN2DftOsR+5WxPT+MSgupL9XTZk9xBhcMG0KmapsoubOWSHFDagIsqFxjrin8= X-Received: by 2002:a17:90b:705:b0:2d8:53f8:77c0 with SMTP id 98e67ed59e1d1-2d85617beb2mr4006849a91.7.1724954057691; Thu, 29 Aug 2024 10:54:17 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Phillip Hallam-Baker Date: Thu, 29 Aug 2024 13:54:05 -0400 Message-ID: To: Deirdre Connolly Content-Type: multipart/alternative; boundary="000000000000dcda0e0620d62970" Message-ID-Hash: 25B4RALX4NPFIQQHZL7G7PRTY7GCQ2OF X-Message-ID-Hash: 25B4RALX4NPFIQQHZL7G7PRTY7GCQ2OF X-MailFrom: hallam@gmail.com X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; header-match-cfrg.irtf.org-0; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: IETF SAAG , IRTF CFRG X-Mailman-Version: 3.3.9rc4 Precedence: list Subject: =?utf-8?q?=5BCFRG=5D_Re=3A_Prehashing_in_EdDSA_vs_ML-KEM?= List-Id: Crypto Forum Research Group Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --000000000000dcda0e0620d62970 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Oh cripes. yup. That is what you get writing messages on ML-DSA while trying to wrestle ML-KEM into your code. On Thu, Aug 29, 2024 at 1:00=E2=80=AFPM Deirdre Connolly wrote: > I think all instances of 'ML-KEM' here are intended to be 'ML-DSA' > > On Thu, Aug 29, 2024, 12:56=E2=80=AFPM Phillip Hallam-Baker > wrote: > >> There is a lot of confusion among implementers of ML-KEM and the >> difference between the 'pure' and 'prehash' versions. While working on m= y >> implementation, I am now convinced we just got it wrong in Ed25519 and >> Ed448 which do things differently. >> >> The protocol concern here is binding the message digest to the signature= . >> This is an issue that Butler Lampson and Ron Rivest have told me is >> essential and I consider essential and why would we even have an argumen= t >> over whether a digest substitution attack is a concern. It just is. >> >> As a side bar, let me also point out that semantic substitution is also = a >> legitimate concern and that might well mean that we end up making some >> different choices in protocol designs. >> >> As a protocol designer, there are two use cases of interest. One is wher= e >> I get to pick the content digest without restriction and the other is wh= ere >> the choice is made for me because the content is already digested at the >> point I am generating the signature. Often this is because it is being >> digested for multiple purposes, in the DARE construction I use in the Me= sh, >> I digest the content of every envelope with SHA-2-512 or SHA-3-512 and I >> use that digest to construct the Merkle tree over the message sequence a= nd >> as an input to the signature. >> >> >> The objective of ML-KEM is to prevent a digest substitution attack by >> binding the digest algorithm to the message digest. What it is doing in >> effect is to create a manifest, prefixing a flag saying 'manifest' and >> signing that with ML-DSA-Internal. >> >> The objective of ML-DSA PURE is to allow direct access to ML-DSA-Interna= l >> to sign messages when the content hasn't been prehashed already. People >> have suggested quite a few purposes for this but the only purpose I see = a >> good argument for is to create *more expressive* manifest formats. >> >> >> For example, let us say we are signing a JPG, we probably want to say we >> are signing a JPG and the principled way to do that in JOSE or COSE woul= d >> be to build a manifest with the content digest, content digest algorithm >> and content type. >> >> [Yes, I am aware that you could use context for this but a much better >> use for that is to declare your manifest format] >> >> In the DARE construction, I am just updating the code so the signature i= s >> over the envelope content digest AND the Merkle tree head. So one signat= ure >> does both. >> >> >> OK so what went wrong in Ed25519 and Ed448? Problem was we were focused >> on the security of the signature and NOT how it fits into other protocol= s. >> And as a result we don't actually have a functional scheme for signing >> content that was already digested with a specific hash. >> >> What seems to have happened in practice is that instead of accepting the >> hash choices picked by EdDSA, the implementers have done hash-then-sign = in >> the exact same manner as for RSA and passed the result in to be signed b= y a >> random choice of Pre or pure. >> >> So it appears that we probably have protocols that have effectively >> broken uses of EdDSA. There is no viable attack right now but this is >> something we should fix. >> >> Certificates are probably the exception because we care enough about >> those to make sure we get them right. >> >> >> One approach is to update the RFC so that it matches the functionality o= f >> ML-DSA. I think we should do that regardless simply to ease deployment o= f >> both. We are going to be having this issue come up again and again. >> >> A new rev to the RFC gives us an opportunity to tell people the correct >> and safe way to deal with content that has already been hashed with a >> specific digest. But the problem there is EdDSA has already made its way >> into a lot of crypto APIs and it will take years for any update to make = its >> way out. >> >> So we need to look at using manifests for all content signatures. And >> that is actually the better way to go because we can address multiple >> substitution attacks, not just the one least likely to be attempted. And= we >> can do things like binding in notary and encryption witness values and >> doing all sorts of other useful stuff. >> >> _______________________________________________ >> CFRG mailing list -- cfrg@irtf.org >> To unsubscribe send an email to cfrg-leave@irtf.org >> > --000000000000dcda0e0620d62970 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Oh = cripes. yup. That is what you get writing messages on ML-DSA while trying t= o wrestle ML-KEM into your code.


On Thu, Aug 29, 2024 at 1:00=E2=80=AFPM Deird= re Connolly <durumcrustulum@= gmail.com> wrote:

I think all instances of 'ML-KEM' here ar= e intended to be 'ML-DSA'


On Thu= , Aug 29, 2024, 12:56=E2=80=AFPM Phillip Hallam-Baker <phill@hallambaker.com> wro= te:
There is a lot = of confusion among implementers of ML-KEM and the difference between the &#= 39;pure' and 'prehash' versions. While working on my implementa= tion, I am now convinced we just got it wrong in Ed25519 and Ed448 which do= things differently.

The = protocol concern here is binding the message digest to the signature. This = is an issue that Butler Lampson and Ron Rivest have told me is essential an= d I consider essential and why would we even have an argument over whether = a digest substitution attack is a concern. It just is.=C2=A0

As a side bar, let me also point out th= at semantic substitution is also a legitimate concern and that might well m= ean that we end up making some different choices in protocol designs.
=

As a protocol designer, there = are two use cases of interest. One is where I get to pick the content diges= t without restriction and the other is where the choice is made for me beca= use the content is already digested at the point I am generating the signat= ure. Often this is because it is being digested for multiple purposes, in t= he DARE construction I use in the Mesh, I digest the content of every envel= ope with SHA-2-512 or SHA-3-512 and I use that digest to construct the Merk= le tree over the message sequence and as an input to the signature.


The objective of ML-KEM is to prevent a = digest substitution attack by binding the digest algorithm to the message d= igest. What it is doing in effect is to create a manifest, prefixing a flag= saying 'manifest' and signing that with ML-DSA-Internal.

The objective of ML-DSA PURE is to= allow direct access to ML-DSA-Internal to sign messages when the content h= asn't been prehashed=C2=A0already. People have suggested quite a few pu= rposes for this but the only purpose I see a good argument for is to create= *more expressive* manifest formats.


For example, let us say we are signing a JPG, we probably want to say we = are signing a JPG and the principled way to do that in JOSE or COSE would b= e to build a manifest with the content digest, content digest algorithm and= content type.
=
[Yes, I am= aware that you could use context for this but a much better use for that i= s to declare your manifest format]

In the DARE construction, I am just updating the code so the sig= nature is over the envelope content digest AND the Merkle tree head. So one= signature does both.

OK so what we= nt wrong in Ed25519 and Ed448? Problem was we were focused on the security = of the signature and NOT how it fits into other protocols. And as a result = we don't actually have a functional scheme for signing content that was= already digested with a specific hash.

What seems to have happened in practice is that instead of a= ccepting the hash choices picked by EdDSA, the implementers have done hash-= then-sign in the exact same manner as for RSA and passed the result in to b= e signed by a random choice of Pre or pure.

So it appears that we probably have protocols that hav= e effectively broken uses of EdDSA. There is no viable attack right now but= this is something we should fix.

Certificates are probably the exception because we care enough a= bout those to make sure we get them right.


One approach is to update the RFC so that it matches the functional= ity of ML-DSA. I think we should do that regardless simply to ease deployme= nt of both. We are going to be having this issue come up again and again.= =C2=A0

A new rev to the R= FC gives us an opportunity to tell people the correct and safe way to deal = with content that has already been hashed with a specific digest. But the p= roblem there is EdDSA has already made its way into a lot of crypto APIs an= d it will take years for any update to make its way out.

So we need to look at using manifests for a= ll content signatures. And that is actually the better way to go because we= can address multiple substitution attacks, not just the one least likely t= o be attempted. And we can do things like binding in notary and encryption = witness values and doing all sorts of other useful stuff.

_______________________________________________
CFRG mailing list -- cfrg@irtf.org
To unsubscribe send an email to cfrg-leave@irtf.org
--000000000000dcda0e0620d62970--