Hi Jacob, I appreciate your response, though am still confused by many parts. I’ve tried to reduce my point of confusion to some basic/succinct arguments. In the following message I will repeat them quite a lot, because I am very confused by them, and you have written many words which make me confused on these same basic points.
> On Jul 14, 2026, at 6:02 PM, Jacob Appelbaum <[email protected]> wrote: > > Hi Mark, > > This replies to your three messages of 7/14/26 00:15, 14:41, and > 15:23. > > On 7/14/26 00:15, [email protected] wrote: >> 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. > > It is reasonable to be confused; this discussion crosses standards > process, lattice proofs, RNG engineering, protocol design, and > declassified history. I do not accept the "crusade" framing. I am > raising a specific issue in ML-KEM as used by IETF protocols, especially > TLS. Is this issue specific to ML-KEM? Are you claiming that using a backdoored RNG, but where ML-KEM specifically pre-hashes, yields a secure system? Very specifically, would you be comfortable switching your system random over to DUAL_EC_DRBG, provided that ML-KEM is pre-hashing? I would not be comfortable personally. So I do not understand why we are pretending that pre-hashing meaningfully guards against someone setting system.random to DUAL_EC_DRBG. >> 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? > > The benefit is not a tighter lattice reduction. I did not say a tighter lattice reduction bound. I said a tighter advantage bound. The concept is independent of lattices, and ML-KEM itself has many bound terms that are completely independent of lattice-reduction. > The benefit is > destroying hidden algebraic structure in `m` before `m` is encrypted and > then recovered by the decapsulating peer. This leads to the same query about replacing your system random with DUAL_EC_DRBG. > NIST itself wrote: > > "As others have pointed out before, hashing m in the ML-KEM's spec > only protects the KEM, the whole system is still considered > compromised when other crypto functions rely on the security of the > broken or attacker-controlled RBG." [2] This appears to be NIST making exactly the same point RE the efficacy of pre-hashing when your system is DUAL_EC_DRBG. > That is exactly the point: hashing `m` protects the KEM from this class > of failure. It does not solve every RNG problem. It does close this > peer-recoverable `m` oracle. Ok, would you be comfortable replacing your system random with DUAL_EC_DRBG if we pre-hash? > The cost tradeoff is simple: > > - Kyber with the hash; > - ML-KEM without the hash; > - ML-KEM with the hash restored. Do any of these choices make you comfortable with replacing your system random with DUAL_EC_DRBG? Or do none of them really matter. > The 2023 pqc-forum discussion put the hash overhead on the order of > hundreds to low thousands of cycles, depending on platform and parameter > set [14]. That is small compared with performing the whole ML-KEM > computation while also exposing a useful oracle on structured RNG > output and achieving no security against the relevant Adversary. It is only small if it helps in some measurable way. In particular, would pre-hashing make you comfortable with replacing your system random with DUAL_EC_DRBG? > Incredibly the basic concept that a peer with the secret key can recover > `m` was the subject of a multi-day discussion on this list! Note that this discussion did not solely suggest pre-hashing. It also suggested whitening, etc. So even if some sort of “RNG fixing” makes someone comfortable with replacing their system random with DUAL_EC_DRBG, it’s not clear if that “RNG fixing” is solely pre-hashing. >> I'm also deeply confused by your references to the approx SIVP reduction. >> Has this been used for ML-KEM? ... > > I think I see the disconnect when I cite [8] and so [9] appears > responsive. My point with [8] is not that either citation proves ML-KEM > is broken. No, the disconnect is that [8] is an irrelevant reference to the security of ML-KEM. An alternative universe where [8] found that Regev’s reduction is highly tight does not make ML-KEM more secure. > The 2022 pqc-forum MATZOV thread is relevant as context, not as proof > that ML-KEM is broken. No, it is not relevant. MATZOV is a topic that is relevant to the security of ML-KEM. [8] is not relevant to the security of ML-KEM. This is how they are different. The fact that even now you are comparing [8] to things that are relevant to the security of ML-KEM does not inspire confidence in your understanding of the security of ML-KEM. > The thread shows how security estimates depend on > modeling assumptions, memory-cost models, and concrete attack-cost > quantification [26]. Yes, none of this is contentious. The only thing you mentioned that I contend with is that [8] is relevant to the security of ML-KEM. It is not. Discussing things that are relevant does not change that fact. > Standards should make such assumptions visible > instead of letting implementers infer more than the proofs or estimates > say. Standards should also not mention things that are irrelevant to the security of the system under consideration, such as [8]. > This is the other part of the point of mentioning [8] about "provable > security": what exactly does the proof cover, what assumptions does it > require, and where are the gaps between theory, standards, and > deployment? Again, [8] is irrelevant to the security of ML-KEM. Nothing you write here changes that fact. Concretely, an alternative world where [8] is highly tight does not impact the security of ML-KEM. > Standards sit between the mathematics and the engineering. > This is where mathematical assumptions should become implementer > guidance, and where engineering failure modes should feed back into > conservative protocol advice. It is also where we should be honest with implementors, and in particular not pretend [8] is relevant to the security of ML-KEM. > A key practical question is: when the hash was present in Kyber, were > you satisfied with the proofs offered for Kyber? I am not comfortable with replacing my system random with DUAL_EC_DRBG. This remains to be true if we pre-hash for Kyber, or we pre-hash + whiten. Given that this is the case, the hash appears to be useless. In its stated goal (security in the context of a subverted RNG) it does not appear to suffice. > If so, restoring the > hash does not create a speculative new cryptographic object. It restores > a conservative step already reviewed during the NIST process. Would restoring the hash make you comfortable using ML-KEM with system random set to DUAL_EC_DRBG? If it does not, then restoring the hash seems to cost another hash invocation for no benefit. > A second key practical question is: do you find NIST's motivation to > remove it to be sufficiently well motivated if you are meanwhile asking > for a game based proof? The game-based proof would be useful for probing whether pre-hashing solely or pre-hashing + whitening is required. Both were discussed on this mailing list. It is not clear to me which is the proper thing to do. Regardless, neither would make me comfortable with having my system random set to DUAL_EC_DRBG. So I personally do not see how they would make my system more secure if my RNG was subverted. > > FIPS 203 says ML-KEM.KeyGen and ML-KEM.Encaps require fresh random bytes > from an approved RBG, as prescribed in SP 800-90A, SP 800-90B, and > SP 800-90C, with security strength at least 128 bits for ML-KEM-512, > 192 bits for ML-KEM-768, and 256 bits for ML-KEM-1024 [0][15][16][17]. > > As shorthand examples, the SP 800-90A DRBG cases are: > > - ML-KEM-512-Hash_DRBG > - ML-KEM-512-HMAC_DRBG > - ML-KEM-512-CTR_DRBG > - ML-KEM-768-Hash_DRBG > - ML-KEM-768-HMAC_DRBG > - ML-KEM-768-CTR_DRBG > - ML-KEM-1024-Hash_DRBG > - ML-KEM-1024-HMAC_DRBG > - ML-KEM-1024-CTR_DRBG > > These are shorthand and not new algorithm names. They illustrate what > FIPS 203 relies on: ML-KEM at the relevant security level with a > NIST-approved RBG of sufficient strength, plus the relevant SP 800-90B > entropy-source and SP 800-90C construction requirements. There may be > other approved RBG constructions, including validated designs ultimately > backed by hardware devices. But a raw platform interface or device is > not automatically the same thing as a NIST-approved RBG. > > The TLS drafts under discussion do not specify ML-KEM-768-Hash_DRBG, > ML-KEM-768-HMAC_DRBG, ML-KEM-768-CTR_DRBG, or any equivalent approved > RBG construction with the required emphasis. Real software may use > getentropy(), getrandom(), /dev/random, /dev/urandom, /dev/hwrng, OS > get-random-bytes API calls, wrappers around them, or library policy [20] > [21][22][23]. Some of these choices may be excellent. Some software > correctly uses the operating system CSPRNG interface. Some software has > historically used hardware RNG devices more directly. Some software > mixes these paths or delegates the choice to a crypto library. These > choices are still not the same as carrying over the approved-RBG > condition NIST used to justify removing the hash. > > If an implementation does not meet the FIPS 203 randomness requirements, > NIST's rationale for removing the hash no longer applies. If an > approved RBG ever has hidden structure, the removed hash is also no > longer present as internal defense in depth. Those are the two gaps the > TLS drafts should explain. Again, this all makes sense if pre-hashing yields meaningful security benefits. Concretely, would you be comfortable with using a system with system random instantiated with DUAL_EC_DRBG if we added pre-hashing to ML-KEM? > This matters beyond these two TLS drafts. Many current and future IETF > documents will use ML-KEM directly or indirectly. RFC 9794 gives hybrid > terminology, and RFC 9958 gives PQC engineering guidance, but neither > replaces putting the relevant ML-KEM security assumptions into the > documents that instantiate ML-KEM [24][25]. Is this a ML-KEM security assumption? Perhaps I’m naive, and a system with system random set to DUAL_EC_DRBG (and ML-KEM pre-hashes) is perfectly secure. If it is not, I suspect this is not a ML-KEM security assumption, and is rather a security assumption for every cryptographic system. > > My requested text is modest: > > - cite the third-round Kyber submission [1]; > - cite FIPS 203 Appendix C, where NIST documents removing `m <- H(m)` > [0]; > - state the FIPS 203 approved-RBG requirement [0][15][16][17]; > - state that `m` is recovered by the decapsulating peer; > - recommend restoring Kyber's hashing of `m`, as defense in depth > against hidden-structure RBG failures; > - cite Dual_EC_DRBG as the public standardized example [3][4]. If this was done, would you be comfortable using your system with system random set to DUAL_EC_DRBG? > This does not turn the TLS draft into a FIPS certification scheme and it > is appropriate because the TLS draft is _not_ a FIPS certification draft > but the IETF's _consensus_ on deploying pure ML-KEM in TLS. It should at > least tell implementers what NIST's security rationale assumes, it must > tell it what is _required_ and what Kyber originally did to reduce risk > is literally in FIPS 203, so quoting it doesn't even require a new > reference! > > It probably also makes sense to edit the text to make clear that these > are the combinations that NIST says would meet the requirements where a > hash isn't needed: > > - ML-KEM-512-Hash_DRBG > - ML-KEM-512-HMAC_DRBG > - ML-KEM-512-CTR_DRBG > - ML-KEM-768-Hash_DRBG > - ML-KEM-768-HMAC_DRBG > - ML-KEM-768-CTR_DRBG > - ML-KEM-1024-Hash_DRBG > - ML-KEM-1024-HMAC_DRBG > - ML-KEM-1024-CTR_DRBG > > > On 7/14/26 14:41, [email protected] wrote: >> That webpage does not answer my question. I am currently interpreting >> "defense in depth" as a synonym for "arbitrary modifications to a >> cryptographic scheme of unquantifiable value". > ... >> For example, if pre-hashing m yielded tighter advantage bounds in the >> IND-NSA-TOOK-MY-RNG game, that would be a modification of quantifiable value. > > Recovering the internal RNG state is quantifiable and the literature is > fairly clear. I am happy to send you a Sage script or a Python script if > it will help. Usually, about 30 bytes of output is enough to recover the > state but not if those 30 bytes are hashed first. > > Here is a sketch of some simplistic game-based reasoning. This is not a > finished proof or final definition; the oracle structure and state > lineage would need more work. But it captures the engineering failure mode. > > Call it ASH-KEM/HYB: Algebraic-Structure-Hiding robustness for > peer-recoverable KEM inputs, including hybrid KEX use. > > Let RBG_t be an RBG family whose raw output contains trapdoor- > recoverable which is to say, you have some secret keys that allow you to > exploit the algebraic structure, with Dual_EC_DRBG as the NIST public > standardized example. Let W be either identity or a whitening function > such as H. > > Stage 0: passive TLS-visible state recovery. TLS-visible randomness, > such as ClientHello.random, ServerHello.random, GREASE values, random > padding, randomized ordering, or related fields, is derived from the > same RBG lineage. The adversary observes the wire and wins if these > values let it recover or synchronize future RBG state. > > Stage 1: active ML-KEM state recovery. For an adversary-chosen ML-KEM > public key, the sender draws (x, s') <- RBG_t(s), sets m = W(x), runs > Encaps_internal(ek, m), and sends the ciphertext. Because the adversary > knows the decapsulation key, it recovers m. The adversary wins if m lets > it recover or synchronize future RBG state. > > Stage 2: passive ML-KEM compromise. Later, the same RBG lineage is used > for an honest ML-KEM encapsulation. The adversary only observes the > public key and ciphertext, but wins if Stage 0 or Stage 1 lets it > predict the future m or compute the ML-KEM shared secret without solving > the KEM's hardness problem. > > Stage 3: passive hybrid compromise. In X25519MLKEM, if the same > compromised RBG lineage also feeds the future X25519 scalar, the > adversary can compute both the ML-KEM and X25519 inputs without solving > any of ML-KEM's lattice hardness assumptions or X25519's ECDLP hardness > assumptions. Note that this does not require a quantum computer. > > For W(x) = x, Dual_EC_DRBG-shaped output can fail at all these points. > For W(x) = H(x), the Stage 1 ML-KEM m-oracle no longer gives the raw > structured object needed for Dual_EC_DRBG-style state recovery. That > does not solve every TLS covert channel, but it removes this one which > is extremely reliable and also surprising. > > So hopefully this clarifies that the issue is not a tighter lattice > reduction. It is a practical bypass of the lattice assumption through > state recovery in the randomness path. NIST presented no such game when > it removed the hash, and did not require such a game to keep the hash. I appreciate you attempting to spell out a game. My hope for the game was that it would answer whether 1. pre-hashing by itself is better, or 2. pre-hashing and whitening is better, or 3. neither particularly matter Does your game answer this? I personally don’t think so, but this is the first real cryptographic argument you’ve made, so I’d like to spend more time here. For example, an important part of cryptographic games is that they place realistic limitations on adversaries. For example, I live in a world where 1. IND-CPA, and 2. IND-CCA2 adversaries are realistic. I must be comfortable using my system despite these adversaries existing. If you give me a machine, and tell me I can use it, but there is an IND-CCA2 adversary attacking me, I’ll shrug and go about my way. Your game is not like this. If you gave me a machine and told me that an attacker has loaded a backdoored PRNG onto it, I would not use the machine. Concretely, I would not be comfortable with setting my system random to be DUAL_EC_DRBG. Pre-hashing ML-KEM does not change this. Your game does something more limited than this, but the same fundamental issue remains. Patching one consumer of an RNG broken in a particular way appears to be much worse than 1. patching every consumer, or 2. using a non-broken RNG. So I appreciate your attempt to formalize your attack into a game, and believe there is a moderate amount of value that was attained by this. The attack scenario is wildly implausible. Patching ML-KEM would not make me believe the overall system in this game would be secure. It is also unfortunate that the game does not make clear whether pre-hashing or pre-hashing + whitening is superior. As far as the “pro-pre-hashing” side goes, it appeared they had some internal disagreement on the superior strategy. >> But perhaps this is some new field (I might jokingly call it "post- modern >> cryptography") that I do not have sufficient technical experience with to >> follow. > > No new field is needed. You want the proof joke? I am sure you can > handle the proof joke: Oded Goldreich already beat you to the name in > his paper "On Post-Modern Cryptography" in 2006 in an opinion paper > responding to... the Another Look series by Koblitz and Menezes, the > same Koblitz from the paper I cited. I will remind you that paper you cited is irrelevant to the security of ML-KEM. The fact that Kobilitz and Menezes have done good work with that series is separate from the basic fact that the non-tightness of Regev’s reduction is not relevant to the security of ML-KEM. > I am sympathetic to the approach of proving things. The point lost > between us here is that the proofs are sometimes confusing or > misleading. I do not have a lot of confidence in proofs that for example > excluded `m` as being relevant. This as the toy game above demonstrates > is enough to guess future ML-KEM keypairs. Yes, but it is also likely enough to break the system in many other ways. As I have repeated many times above, replacing system random with DUAL_EC_DRBG does not appear to be a problem that is fixable by pre-hashing `m`. > The historical context is also not speculative. NIST's own material on > Dual_EC_DRBG documents the NSA role and NIST's failure to reject or > modify the design [3]. The Don Johnson and John Kelsey email about > Dual_EC_DRBG's design shows how NSA gagged NIST [4] and NIST again is > mum when pressed on key issues. Juniper ScreenOS then showed how a > Dual_EC_DRBG-style mechanism deployed in real products can become a > NOBUS-except-when-someone-else-changes-the-parameters failure [5]. I agree. I would not be comfortable with using a system where system random is set to DUAL_EC_DRBG. Though I remain uncomfortable with this even if we pre-hash `m`. > Current software context also matters. Bouncy Castle Java still > documents DualECSP800DRBG and also documents ML-KEM support [10][11] > [12]. Its deprecated list is relevant here too as neither of those are > on it [13]. That is a popular library too. Ok, well more concretely, if Bouncy Castle Java uses DUAL_EC_DRBG, I would not be comfortable using it. If we pre-hash `m`, it is not clear to me that plugs all the “leaks” that DUAL_EC_DRGB (or more generally bad cryptographic RNGs) would introduce. Would you be comfortable using Bouncy Castle Java with DUAL_EC_DRBG as its PRNG if we pre-hash `m`? > Again, I am not claiming this proves the TLS ML-KEM draft is backdoored > but the removal of the hash over `m` from NIST is beyond fishy. > Why is it fishy? The standardized backdoor history, the continued > availability of (historical, backdoored) DRBG code also mirrors hardware > backdoors in real devices, and the deployment of ML-KEM in the same > broad software ecosystem make the Security Considerations text worth > getting right. NIST does not meet their own definition for defense in > depth by making that change. Again, it is not clear to me this is defense in depth. If you would use a system with system random set to DUAL_EC_DRBG provided we pre-hash the `m` in ML-KEM, I would view this as you thinking this is defense-in-depth (whatever that means). I suspect you would not use such a system though. > In some sense, I worry that by focusing on > this change, we do not give enough scrunity to the lattice security > issues. What does the lattice security matter if one does not even need > to resolve the lattice security assumptions to break the security? > > Cavium/Marvell is very stark reminder that hardware and RBG assumptions > matter, even though Marvell issued a carefully worded denial and then > refused to answer key aspects of the reporting [6]. This connects > directly to platform randomness: hardware RNG output, /dev/hwrng, kernel > RNG interfaces, getrandom(), getentropy(), /dev/random, and /dev/urandom > are not interchangeable with a validated NIST-approved RBG just because > they are available [20][21][22][23]. > > The attack strategy is real, the historical precedent is real, the > removed Kyber protection addressed this class of failure, and the cost > to document and mitigate it is tiny. Again, concretely, if it was mitigated, would you be comfortable using a system where 1. the system random is DUAL_EC_DRBG? or 2. say you’re using Bouncy Castle Java, with its RNG set to DUAL_EC_DRBG. I’ll even say you can use hybrid PQC If the answer is “no”, it is not clear to me what the pre-hashing is accomplishing. > On 7/14/26 15:23, [email protected] wrote: >> I just wanted to point out the irony of directing Eliot to view an off-list >> email regarding the importance of keeping the emails on- list. ... > > Substantive technical decisions and consensus formation should remain on > the public list where the community can inspect the reasoning. > > That is why I am putting these technical points on the record here. > > Kind regards, > Jacob Appelbaum > > [0] https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.pdf > > [1] https://pq-crystals.org/kyber/data/kyber-specification- > round3-20210804.pdf > > [2] https://mailarchive.ietf.org/arch/msg/tls/PMjmt78qRreJh2RHD5eLH9nhmNQ/ > > [3] https://csrc.nist.gov/csrc/media/projects/crypto-standards- > development-process/documents/dualec_in_x982_and_sp800-90.pdf > > [4] https://csrc.nist.gov/CSRC/media/Projects/Crypto-Standards- > Development-Process/documents/ > Email_Oct%2027%202004%20Don%20Johnson%20to%20John%20Kelsey.pdf > > [5] https://hovav.net/ucsd/dist/juniper.pdf > > [6] https://www.theregister.com/security/2023/09/19/marvell-disputes- > claim-cavium-backdoored-its-chips/763270 > > [7] https://datatracker.ietf.org/doc/html/rfc7258 > > [8] https://eprint.iacr.org/2022/275.pdf > > [9] https://eprint.iacr.org/2026/1364 > > [10] https://www.bouncycastle.org/download/bouncy-castle-java/ > > [11] https://downloads.bouncycastle.org/java/docs/bcprov-jdk15to18- > javadoc/org/bouncycastle/crypto/prng/drbg/DualECSP800DRBG.html > > [12] https://downloads.bouncycastle.org/java/docs/bcprov-jdk15to18- > javadoc/org/bouncycastle/jcajce/provider/asymmetric/MLKEM.html > > [13] https://downloads.bouncycastle.org/java/docs/bcprov-jdk15to18- > javadoc/deprecated-list.html > > [14] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/ > WFRDl8DqYQ4/m/MRa5O0CvAAAJ > > [15] https://nvlpubs.nist.gov/nistpubs/SpecialPublications/ > NIST.SP.800-90Ar1.pdf > > [16] https://nvlpubs.nist.gov/nistpubs/SpecialPublications/ > NIST.SP.800-90B.pdf > > [17] https://nvlpubs.nist.gov/nistpubs/SpecialPublications/ > NIST.SP.800-90C.pdf > > [18] https://csrc.nist.gov/glossary/term/defense_in_depth > > [19] https://www.cs.utexas.edu/~hovav/dist/hedge.pdf > > [20] https://man7.org/linux/man-pages/man2/getrandom.2.html > > [21] https://man.openbsd.org/getentropy.2 > > [22] https://man7.org/linux/man-pages/man4/random.4.html > > [23] https://docs.kernel.org/admin-guide/hw_random.html > > [24] https://datatracker.ietf.org/doc/html/rfc9794 > > [25] https://datatracker.ietf.org/doc/html/rfc9958 > > [26] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s > > > On 7/14/26 00:15, [email protected] wrote: >> 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. >> iacrlogo.png Time vs Success Probability Tradeoff for SVP and BDD with >> Implications to LWE and SIS <https:// eprint.iacr.org/2026/1364> >> eprint.iacr.org <https:// eprint.iacr.org/2026/1364> >> <https://eprint.iacr.org/2026/1364> >> 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 >>> On Jul 13, 2026, at 4:16 PM, Jacob Appelbaum <[email protected]> wrote: >>> 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 have >>> not 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's 2022 >>> 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 their minds, >>> or whether their analysis received a published response that addresses the >>> core concerns of the 2022 paper. People involved with NIST's PQC process >>> know about this paper and I do not believe that they have ever addressed >>> it. Literature about this is most welcome. >>> Again, I am not claiming that ML-KEM lattice security is practically >>> broken, and I am not making a negative lattice- security claim here. I am >>> saying that the proof landscape does not make me _more_ comfortable with >>> removing a very simple defense- in- depth strategy that survived three NIST >>> PQC rounds, that was added to address this type of issue, and yet the >>> removal was not identified as a security problem. >>> My main issue remains the protocol consequence of NIST removing Kyber's >>> hash over `m`. The pushback against restoring that hash does not seem >>> proportional, especially when the TLS draft does not itself impose the >>> approved-RBG conditions that FIPS 203 used to justify removing it. The >>> absence 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 that >>> you are glad. My goal here is straightforward and I believe that they are >>> compatible with our mutual cypherpunk sensibilities as I remember them: >>> strong cryptography, safe defaults, and fewer avoidable footguns. The >>> hashing change is wire- compatible with a peer that decapsulates normally, >>> 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 that is >>> 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- depth >>> property that Kyber had. It leaves the NIST change intact and leaves `m` >>> recoverable by the decapsulating peer as raw >>> output from whatever RBG/DRBG construction is used. >>> If the WG cannot or will not restore Kyber's hash while still calling the >>> result ML-KEM, then the draft should say that clearly. Or is mentioning >>> this entire line of thinking also not an option? Either way the draft >>> should not pretend that generic RNG advice addresses the same issue. This >>> is not an entropy issue; it is a hidden-structure issue. NIST removed a >>> hidden-structure mitigation. That is much harder to wave away than TLS as a >>> protocol not having defense-in-depth everywhere. One looks 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 is >>> that 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` before encapsulation destroys >>> that structure. >>> Leaving this to each implementer is exactly how the defense-in- depth >>> property gets lost and this is how users come into harm's way. Some >>> implementations will restore the hash, some will not, and some will not >>> know about the issue at all. I understand that some implementers may >>> believe their entire hardware and software randomness stack is audited, >>> correct, and safe against this threat model. Fine. There are no protocol >>> police. But IETF guidance is not only for those implementers. It is also >>> for 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 provider ships >>> and has shipped a Dual_EC_DRBG implementation with the NIST standardized >>> parameters in versions I have checked, and it also ships ML-KEM. To be >>> clear: Dual_EC_DRBG is not the default DRBG there. But its continued >>> presence is a reminder that "nobody would ever do that" is not a serious >>> security argument. It should be removed, and downstream packages 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.html >>> Notably DualEC is it not listed in their deprecated list: - >>> https://downloads.bouncycastle.org/java/docs/bcprov-jdk15to18- javadoc/ >>> deprecated-list.html >>> This discussion also reminds me of discussions before and after MUSCULAR >>> [1][2]. Yahoo! and Google engineers were surprised to learn that GCHQ and >>> NSA were tapping internal backbones after those companies had already >>> appeared in PRISM reporting. The lesson was not that the public >>> cryptography was broken. The lesson was that large-scale adversaries >>> exploit whatever gap remains or as NSA phrased it: "SSL added and removed >>> here :-)" The right response is to close gaps when we see them especially >>> when they're cheap. It does not get much cheaper than restoring Kyber's >>> hash. >>> The IETF's publications gives important advice to large companies selling >>> FIPS-certified products to the USG, also to Free Software projects running >>> on hardware that users cannot meaningfully verify, and to many kinds of >>> systems in between. Some systems have had serious RNG, firmware, or >>> hardware trust issues, including examples such as Cavium [3]. We do not >>> need to design for the worst possible machine in every respect. But we >>> should not reject a cheap defense-in-depth step when the failure mode is >>> exactly historical cryptographic sabotage. The Cavium story is an important >>> one, and it is ignored almost entirely by people pretending this isn't a >>> real class of issues. >>> Should we discuss that as a case study in detail? It is pretty much the >>> most obvious smoking gun sitting on the table for over a decade, still >>> smoking, and still relevant. >>> So the technical question remains: what is the security reason to reject >>> restoring Kyber's hash over `m`? >>> If the answer is only "then it is no longer ML-KEM as specified >>> by NIST", that is a naming or conformance answer, not a security answer. We >>> are not discussing draft-ietf-tls-fips-certified- mlkem-08, right? >>> If you read one report with leaked NSA documents beyond PROJECT BULLRUN and >>> the black budget reporting [7][8][9], I strongly encourage you to read >>> about SENTRY EAGLE [4][5][6]. This is not a "conspiracy theory" frame than >>> an NSA term of art. It is documented history about corporate partnerships, >>> access, and cryptographic exploitation. That history is why some of us >>> insist on cheap, conservative defenses when the cost is a hash call. The >>> term of art by the way for the "conspiracy theory" notion as shown in >>> SENTRY EAGLE is Corporate Partnership. That is not even a joke - that is >>> just how the sausage is made. >>> We should discuss hardware concerns in detail, but restoring the hash over >>> `m` is the immediate issue. >>> Kind regards, Jacob Appelbaum >>> P.S. >>> I covered some of this topic in my PhD thesis [10], Chapter 4. Check the >>> footnotes 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] > I’m glad you’ve put them here. I think this discussion makes my (and I would anticipate others’) disagreements with pre-hashing plain. It appears to be of questionable value. In particular, 1. I would not feel comfortable using a system with system random set to DUAL_EC_DRBG if ML-KEM was switched to pre-hash, and 2. I would not feel comfortable using a system that relies on Bouncy Castle Java for its crypto, if it was using DUAL_EC_DRBG as its RNG, if ML-KEM was switched to pre-hash. In both situations, pre-hashing would be (for me) an arbitrary (why pre-hashing vs pre-hashing + whitening) modification of questionable cryptographic value. If you would be comfortable using such systems, perhaps that is our point of disagreement. Would you be? Mark _______________________________________________ TLS mailing list -- [email protected] To unsubscribe send an email to [email protected]
