| I’m very confused by this whole crusade of yours. What does “defense in depth” mean formally? I can’t help but read it as “arbitrary extra steps of questionable value”. There are likely many such steps that could be added to any cryptographic protocol. It’s unclear to me the value of any of them.
Does hashing yield a tighter advantage bound anywhere? Or can we quantify the benefit of additional computation here in any way? If not, then why should we consider adding in arbitrary steps of questionable value?
I’m also deeply confused by your references to the approx SIVP reduction. Has this been used for ML-KEM? Note that by this I mean the concrete question of whether
1. Approx SIVP has been worst-case cryptanalyzed, and then 2. The estimates from that worst-case cryptanalysis have been shoved through such a reduction, and then 3. The resulting parameters were used for ML-KEM.
If this happened, and the reduction was highly non-tight, the resulting ML-KEM instance could be easily attacked. That would be concerning.
Fortunately, it never happened. So I do not see why we should care. Even if we had a tight reduction, it’s not clear what the worst case hard instances of approx SIVP look like outside of the NP hard regime. So we probably would need to average case cryptanalyze it anyway. And then what’s the point?
Note that if for some reason you have a personal predilection for worst-case hardness, there are reductions of improved tightness by Aggarwal et al.
Again, I do not think any of this discussion is relevant to this mailing list. But to the extent to which it is being discussed, it is out of date with the current literature.
Sent from my iPhone Hi Paul,On 7/13/26 17:02, Paul Wouters wrote:On Mon, 13 Jul 2026, Jacob Appelbaum wrote:
It is not a red herring against pure ML-KEM. ML-KEM is not broken.
I'm glad to hear you think this,
Yes. My objection is not that ML-KEM's lattice problem is broken. I havenot claimed there is a backdoor but my statements were twisted in any case.I do worry about some of the provable security claims. For example,Neal Koblitz, Subhabrata Samajder, Palash Sarkar, and Subhadip Singha's2022 paper [0] says in its abstract: "We give a concrete analysis of this multi-step reduction. We find that the tightness gap in the reduction is so great as to vitiate any meaningful security guarantee, and we find reasons to doubt the feasibility in the foreseeable future of the quantum part of the reduction. In addition, when we make the reduction concrete it appears that the approximation factor in the SIVP problem is far larger than expected, a circumstance that causes the corresponding approximate-SIVP problem most likely not to be hard for proposed cryptosystem parameters. We also discuss implications for systems such as Kyber and SABER that are based on module-DLWE."I would be interested to know whether the authors have changed theirminds, or whether their analysis received a published response thataddresses the core concerns of the 2022 paper. People involved withNIST's PQC process know about this paper and I do not believe that theyhave ever addressed it. Literature about this is most welcome.Again, I am not claiming that ML-KEM lattice security is practicallybroken, and I am not making a negative lattice-security claim here. I amsaying that the proof landscape does not make me _more_ comfortable withremoving a very simple defense-in-depth strategy that survivedthree NIST PQC rounds, that was added to address this type of issue, andyet the removal was not identified as a security problem.My main issue remains the protocol consequence of NIST removing Kyber'shash over `m`. The pushback against restoring that hash does not seemproportional, especially when the TLS draft does not itself impose theapproved-RBG conditions that FIPS 203 used to justify removing it. Theabsence of both the hash and the approved-RBG requirement is unreasonable.I agree that both ML-KEM drafts should get equal treatment.
I'm glad to hear you say this.
I realize that you may perceive me as being difficult, so I am glad thatyou are glad. My goal here is straightforward and I believe that theyare compatible with our mutual cypherpunk sensibilities as I rememberthem: strong cryptography, safe defaults, and fewer avoidable footguns.The hashing change is wire-compatible with a peer that decapsulatesnormally, and no peer will know whether you are hashing it anyway unless they know something about your random bytes that you probably do not know yourself.The equal treatment should be to restore the Kyber hash in both drafts.
I don't think that is an option in MLKEM drafts. It could be an option in a Kyber draft if you submit that.
If restoring the hash is "not an option" in an ML-KEM draft, then thatis exactly one major problem that I am raising. Who decides the options?We don't have consensus, so why can't we change the options on the table?A generic warning about randomness does not restore the defense-in-depthproperty that Kyber had. It leaves the NIST change intact and leaves`m` recoverable by the decapsulating peer as raw output from whateverRBG/DRBG construction is used.If the WG cannot or will not restore Kyber's hash while still callingthe result ML-KEM, then the draft should say that clearly. Or ismentioning this entire line of thinking also not an option? Either waythe draft should not pretend that generic RNG advice addresses the sameissue. This is not an entropy issue; it is a hidden-structure issue.NIST removed a hidden-structure mitigation. That is much harder to waveaway than TLS as a protocol not having defense-in-depth everywhere. Onelooks like an oversight; the other was a deliberate change.The sentence added would be about using good strong random, not about adding a hash. If as part of good strong random, an implementer feels the need to run a hash over RDRAND() or whatever OS source you are using, implementers can decide to do so on their own. It would be generic advise and apply to all parts that need randomness.
That is not sufficient.Of course implementers should use good randomness. The specific issue isthat ML-KEM `m` is recoverable by the decapsulating peer. If `m`preserves hidden structure from the sender's random-generator output,then the peer may get an oracle on that state. Hashing `m` beforeencapsulation destroys that structure.Leaving this to each implementer is exactly how the defense-in-depthproperty gets lost and this is how users come into harm's way. Someimplementations will restore the hash, some will not, and some will notknow about the issue at all. I understand that some implementers maybelieve their entire hardware and software randomness stack is audited,correct, and safe against this threat model. Fine. There are no protocolpolice. But IETF guidance is not only for those implementers. It is alsofor everyone else, right?The lack of humility around this class of attack is not credible.Dual_EC_DRBG is not imaginary history. Bouncy Castle's Java providerships and has shipped a Dual_EC_DRBG implementation with the NISTstandardized parameters in versions I have checked, and it also shipsML-KEM. To be clear: Dual_EC_DRBG is not the default DRBG there. But itscontinued presence is a reminder that "nobody would ever do that" is nota serious security argument. It should be removed, and downstreampackages should remove it too and yet we see this:- https://downloads.bouncycastle.org/java/docs/bcprov-jdk15to18-javadoc/index.html?org/bouncycastle/jcajce/provider/asymmetric/MLKEM.html- https://downloads.bouncycastle.org/java/docs/bcprov-jdk15to18-javadoc/org/bouncycastle/crypto/prng/drbg/DualECSP800DRBG.html- https://downloads.bouncycastle.org/java/docs/bcprov-jdk15to18-javadoc/org/bouncycastle/crypto/prng/drbg/DualECPoints.htmlNotably DualEC is it not listed in their deprecated list:- https://downloads.bouncycastle.org/java/docs/bcprov-jdk15to18-javadoc/deprecated-list.htmlThis discussion also reminds me of discussions before and after MUSCULAR[1][2]. Yahoo! and Google engineers were surprised to learn that GCHQand NSA were tapping internal backbones after those companies hadalready appeared in PRISM reporting. The lesson was not that the publiccryptography was broken. The lesson was that large-scale adversariesexploit whatever gap remains or as NSA phrased it: "SSL added andremoved here :-)" The right response is to close gapswhen we see them especially when they're cheap. It does not get muchcheaper than restoring Kyber's hash.The IETF's publications gives important advice to large companiesselling FIPS-certified products to the USG, also to Free Softwareprojects running on hardware that users cannot meaningfully verify, andto many kinds of systems in between. Some systems have hadserious RNG, firmware, or hardware trust issues, including examples suchas Cavium [3]. We do not need to design for the worst possible machinein every respect. But we should not reject a cheap defense-in-depth stepwhen the failure mode is exactly historical cryptographic sabotage. TheCavium story is an important one, and it is ignored almost entirely bypeople pretending this isn't a real class of issues.Should we discuss that as a case study in detail? It is pretty much themost obvious smoking gun sitting on the table for over a decade, stillsmoking, and still relevant.So the technical question remains: what is the security reason to rejectrestoring Kyber's hash over `m`?If the answer is only "then it is no longer ML-KEM as specified byNIST", that is a naming or conformance answer, not a security answer. Weare not discussing draft-ietf-tls-fips-certified-mlkem-08, right?If you read one report with leaked NSA documents beyond PROJECT BULLRUNand the black budget reporting [7][8][9], I strongly encourage you toread about SENTRY EAGLE [4][5][6]. This is not a "conspiracy theory"frame than an NSA term of art. It is documented history about corporatepartnerships, access, and cryptographic exploitation. That history iswhy some of us insist on cheap, conservative defenses when the cost is ahash call. The term of art by the way for the "conspiracy theory" notionas shown in SENTRY EAGLE is Corporate Partnership. That is not even ajoke - that is just how the sausage is made.We should discuss hardware concerns in detail, but restoringthe hash over `m` is the immediate issue.Kind regards,Jacob AppelbaumP.S.I covered some of this topic in my PhD thesis [10], Chapter 4. Check thefootnotes carefully. Thanks again to Edward Snowden for blowing the whistle on PROJECT BULLRUN and SENTRY EAGLE [4][5][6].[0] https://eprint.iacr.org/2022/275.pdf[1] https://www.washingtonpost.com/world/national-security/nsa-infiltrates-links-to-yahoo-google-data-centers-worldwide-snowden-documents-say/2013/10/30/e51d661e-4166-11e3-8b74-d89d714ca4dd_story.html[2] https://dcssproject.net/muscular/index.html[3] https://www.computerweekly.com/news/366552520/New-revelations-from-the-Snowden-archive-surface[4] https://theintercept.com/2014/10/10/core-secrets/[5] https://snowden.xsurveillance.site/items/show/992[6] https://www.wired.com/2014/10/nsa-may-undercover-operatives-foreign-companies-new-documents-show/[7] https://www.washingtonpost.com/world/national-security/black-budget-leaked-by-edward-snowden-gives-details-of-agencies-beyond-cia-nsa/2013/08/29/a7f20890-10f0-11e3-bdf6-e4fc677d94a1_story.html[8] https://www.washingtonpost.com/news/wonk/wp/2013/08/29/your-cheat-sheet-to-americas-secret-intelligence-budget/[9] https://web.archive.org/web/20130831140612/http://www.washingtonpost.com/world/national-security/black-budget-summary-details-us-spy-networks-successes-failures-and-objectives/2013/08/29/7e57bb78-10ab-11e3-8cdd-bcdc09410972_story.html[10] https://research.tue.nl/en/publications/communication-in-a-world-of-pervasive-surveillance-sources-and-me/_______________________________________________TLS mailing list -- [email protected]To unsubscribe send an email to [email protected]
|
