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 E28BDC14F689 for ; Thu, 29 Aug 2024 10:00:37 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.857 X-Spam-Level: X-Spam-Status: No, score=-1.857 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, HTML_MESSAGE=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=ham autolearn_force=no Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com 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 RgKvzYQVNn6a for ; Thu, 29 Aug 2024 10:00:37 -0700 (PDT) Received: from mail-ed1-x52a.google.com (mail-ed1-x52a.google.com [IPv6:2a00:1450:4864:20::52a]) (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 3610CC14F5E9 for ; Thu, 29 Aug 2024 10:00:37 -0700 (PDT) Received: by mail-ed1-x52a.google.com with SMTP id 4fb4d7f45d1cf-5bede548f7cso970673a12.2 for ; Thu, 29 Aug 2024 10:00:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1724950836; x=1725555636; darn=irtf.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=eyrdYNLvs/PlZbBukCmp97hNJlxav+R4MagUSKLHZOQ=; b=fsFTqK/T0qOGS1glhcsf51CMH2Qy+bMYk7qsvmJ63TgMFPxkCU3yofRCS31tlmhtj+ ySIx+FRDdlX7CrsW82CCTXU6kc2u0i2Bqx0zXaCH5P03zk75rdt8Wy9SFXRMqd9hqBY1 PUPqE0TXyfs7IIfTRRMDE4033AE4nFDdAUOr1jwz0p2Xi01z1nPllrSp9Rg5CRUuvEID B7cSLeF80czM3SJLySCy4MYU4lK8xcBusBHgudcWz9DWVZ/H/zgQkaqMJmDAbDHCT3tN OIQMuG9MdkkjS310LAVjk9tu0+spcdRChuzTbRPtPYO/RdvfdB/S9JEc+bNbTtb/fnqK TqsQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1724950836; x=1725555636; 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=eyrdYNLvs/PlZbBukCmp97hNJlxav+R4MagUSKLHZOQ=; b=lQwbXlZfJAfLYpve3uOlt8/JT16KJz4R09hAgL7mDkiLvrfwA3PTw4V1Cy8CesyeVh 11vDVFFJS50BorpT3l1CQmjrAp7IsbT42D+AnG3Bz11BrBJWv0G1u6ZjFxbexLG/GPbX hCD4BiQUnS+p4anE3vaRWYJbkymkKRe1HbFZC0T3Hsksj7ULACVpONArb3J0F/hzwrwA J8pu4a3PDecdWrctueOLz8A/165AvyyIs9YAsk1l2V4E7F/GVVrMoX9HZF8Ih+zGp1x4 Pn0fGh4oDycVuE73xq3K/c6943Yu4szg5uqpjJDrjBBKBmtX29XrQs+Dcre5w2LOoBsk rCmQ== X-Forwarded-Encrypted: i=1; AJvYcCVI/b5wJ/1iUQs/xGf/SoVXUC9urUaiYi5qXs+DkHxIW0G9/mvFbzBORm4zuSTymku2NW4S@irtf.org X-Gm-Message-State: AOJu0YzE0wFJ5049cCwWm2vsTqsqWkLP+gXmBSBfPW87MmGoTBv0II7R WNm9WkrisObFH2K48b9pU8jrmmy0PFB28q/HnpTdUhu9ZbAA4HA2u5Y9Iszjt7rj0DSZ7oISNu5 Co3k03ykh3syOxprcl1seKZJtG1JFOA== X-Google-Smtp-Source: AGHT+IG/6W/eO/AU+1KPY5I5NX8Yy1SSAIErtiwnoct1zTgUn6txMohvcECATexfAlcppFR+TuixQaU2Jy3rHipbaME= X-Received: by 2002:a05:6402:3493:b0:5c2:2b1f:f757 with SMTP id 4fb4d7f45d1cf-5c22b1ff81dmr1341064a12.17.1724950835041; Thu, 29 Aug 2024 10:00:35 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Deirdre Connolly Date: Thu, 29 Aug 2024 13:00:06 -0400 Message-ID: To: Phillip Hallam-Baker Content-Type: multipart/alternative; boundary="000000000000c71cdf0620d56928" Message-ID-Hash: X2YCQXDZN7X4OEXLFAKAGMYLX6MYCTQR X-Message-ID-Hash: X2YCQXDZN7X4OEXLFAKAGMYLX6MYCTQR X-MailFrom: neried7@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: --000000000000c71cdf0620d56928 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 my > 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 argument > 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 where > I get to pick the content digest without restriction and the other is whe= re > 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 Mes= h, > 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 an= d > 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-Internal > 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 would > 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 us= e > for that is to declare your manifest format] > > In the DARE construction, I am just updating the code so the signature is > over the envelope content digest AND the Merkle tree head. So one signatu= re > does both. > > > OK so what went wrong in Ed25519 and Ed448? Problem was we were focused o= n > the security of the signature and NOT how it fits into other protocols. A= nd > as a result we don't actually have a functional scheme for signing conten= t > 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 i= n > the exact same manner as for RSA and passed the result in to be signed by= a > random choice of Pre or pure. > > So it appears that we probably have protocols that have effectively broke= n > 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 thos= e > to make sure we get them right. > > > One approach is to update the RFC so that it matches the functionality of > ML-DSA. I think we should do that regardless simply to ease deployment of > 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 i= ts > way out. > > So we need to look at using manifests for all content signatures. And tha= t > 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 > --000000000000c71cdf0620d56928 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

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 <phill@hallambaker.com> wrote:
There is a lot of confusion among implementers of ML= -KEM and the difference between the 'pure' and 'prehash' ve= rsions. While working on my 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 argument over whether a digest substitution attack is a co= ncern. It just is.=C2=A0

= As a side bar, let me also point out that semantic substitution is also a l= egitimate concern and that might well mean that we end up making some diffe= rent choices in protocol designs.

As a protocol designer, there are two use cases of interest. One= is where I get to pick the content digest without restriction and the othe= r is where the choice is made for me because the content is already digeste= d at the point I am generating the signature. Often this is because it is b= eing digested for multiple purposes, in the DARE construction I use in the = Mesh, I digest the content of every envelope with SHA-2-512 or SHA-3-512 an= d I use that digest to construct the Merkle 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 bind= ing the digest algorithm to the message digest. What it is doing in effect = is to create a manifest, prefixing a flag saying 'manifest' and sig= ning that with ML-DSA-Internal.

The objective of ML-DSA PURE is to allow direct access to ML-DSA-Int= ernal to sign messages when the content hasn't been prehashed=C2=A0alre= ady. People have suggested quite a few purposes for this but the only purpo= se I see a good argument for is to create *more expressive* manifest format= s.


For example, let us say we are= signing a JPG, we probably want to say we are signing a JPG and the princi= pled way to do that in JOSE or COSE would be to build a manifest with the c= ontent digest, content digest algorithm and content type.

[Yes, I am aware that you could use cont= ext for this but a much better use for that is to declare your manifest for= mat]

=
In the DARE construc= tion, I am just updating the code so the signature is over the envelope con= tent digest AND the Merkle tree head. So one signature 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 protocols. And as a result we don't actually have a fu= nctional scheme for signing content that was already digested with a specif= ic hash.

What seems to ha= ve happened in practice is that instead of accepting the hash choices picke= d by EdDSA, the implementers have done hash-then-sign in the exact same man= ner as for RSA and passed the result in to be signed by a random choice of = Pre or pure.
So it appear= s that we probably have protocols that have effectively broken uses of EdDS= A. There is no viable attack right now but this is something we should fix.=

Certificates are probabl= y the exception because we care enough about those to make sure we get them= right.


One approach is to update t= he RFC so that it matches the functionality of ML-DSA. I think we should do= that regardless simply to ease deployment of both. We are going to be havi= ng this issue come up again and again.=C2=A0

A new rev to the RFC gives us an opportunity to tell p= eople the correct and safe way to deal with content that has already been h= ashed with a specific digest. But the problem there is EdDSA has already ma= de its way into a lot of crypto APIs and it will take years for any update = to make its way out.

So w= e need to look at using manifests for all content signatures. And that is a= ctually the better way to go because we can address multiple substitution a= ttacks, 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 o= f other useful stuff.

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