4 ms·

because the NSA has never surreptitiously pushed bad standards they used to exploit before /s

by cassonmars 1mo ago

tptacek 1mo ago
Which PQC standard are you suggesting they pushed, and how did they push it? Flesh the argument out.
- vlovich123 1mo ago
  That’s a very unfair position to take when dealing with secret agencies who try very hard to obfuscate this stuff - it is hard to provide evidence for in the moment. The government has intentionally acted to weaken DES, standardized Dual_EC_DRBG, performed subtle subterfuge through interfering how NIST operates to inject weaknesses and vulnerabilities, trying to weaken SSL and IPSec, 4G smartphone encryption. These are all documented examples of the NSA engaging in bad faith. So whether or not it is happening in this particular case, there’s now just zero trust in the institutions acting in good faith. And given it took decades for the actions to come out after they were taken, how do you expect someone to answer your request to present evidence there’s anything nefarious happening now? Anyway, that’s what I think a fleshed out argument would look like
  - tptacek 1mo ago
    It's a simple question. I'm not asking anybody to prove anything. I'm literally asking: propose the PQC standard IETF could have subverted, and give a sketch of how they could have done it. The bar is merely "plausibility". I'm not asking whether NSA has subverted standards before; obviously they have. NSA, by the way, rescued DES from differential cryptography, the core mechanism by which block ciphers and hash functions have been attacked ever since.
    - Vecr 1mo ago
      > NSA, by the way, rescued DES from differential cryptography, the core mechanism by which block ciphers and hash functions have been attacked ever since That's why you use ML-KEM 1024 at all... As part of a hybrid.
      - tptacek 1mo ago
        I don't know what this is, but it isn't an answer to the question. I'm starting to notice that nobody is able to come up with an answer.
        Vecr 1mo ago
        There is no public reason to think that 1024 is better than 768, or DJB's S-NTRU-P 761. The NSA might know something, but we can't trust them. So, use a hybrid, in case they are really just trying to protect us.
        tptacek 1mo ago
        That can't be the argument --- it can't be that NSA simply knows a vulnerability that impacts one very specific lattice scheme and not the others. The reason for that is a cryptographic concept known as the Vizzini Conjecture: the argument you just put forward can be applied to literally any cryptographic standard NIST authors. Since NSA knows that, and knows you know it, you can clearly not choose the wine in front of you. It must be that the standard NIST picks is the only secure one, so that NSA can see it tainted by NIST association. But yes, this is the useful conversation to have. There are other scenarios! You can get into more detail on where MLKEM came from, for instance.
        Vecr 1mo ago
        Yes, they trick me and I pick the poisoned wine... But wait, no, I used a hybrid. Imagine the code can't be backdoored (it's proven not to crash/be slow/be exploitable) so at worst it can make the security no better. At best, the NSA knows a whole new subfield of cryptography (from history: differential cryptanalysis) and it really is more secure. They laugh at us while we try to think of how 1024 is better than 768: "bigger is better, right?" "does 1024 refer to the number of years it takes Nightmare Moon to break the code?"
    - vlovich123 1mo ago
      They did both - they strengthened it from differential integrity but weakened it by picking a known-to-be-too-short key length. Meaning they had the compute power to crack it but others couldn’t do the same through pure algorithmic means. As for your post below > it can't be that NSA simply knows a vulnerability that impacts one very specific lattice scheme and not the others Ok. My argument is they know all lattice schemes are weak and the push to use a lattice-only scheme is precisely to have a cryptographic mechanism they can easily bypass without a classical known-secure backstop.
      - tptacek 1mo ago
        See, here's another argument that doesn't work here, because Bernstein very publicly backs a different lattice cryptography scheme. In addition to the previously-stated reason why that argument is inoperative (besides being unfalsifiable, it admits a strategy where NSA "poisons the well" to get people to avoid a particular construction or family of algorithms, so that we all move to weaker ones --- a counterfactual that should be much more vivid after what was released this week!)
        vlovich123 1mo ago
        Does Bernstein back using the alternate scheme exclusively or combined as a hybrid? You’re arguing in bad faith throughout the thread, taking the weakest possible interpretation of anything said and extrapolating to nonsensical positions to paint the people who disagree with you as idiots. Please do better.
        tptacek 1mo ago
        We'll never know, because he only started advocating for hybrids after MLKEM happened. When he did 25519, he did not advocate for 25519/RSA or 25519/FFDH or 25519/P256 hybrids. Agree or disagree with my arguments on substance; it's fine, we're all coming to this with different priors, levels of experience, familiarity with the drama and with the underlying issues, etc. But this "do better, you're in bad faith" stuff is just chaff, and you'd do well to leave it out of your comments. (It's hard sometimes for me to do that, too. Disagreement is tough!)
    - DonHopkins 1mo ago
      Re "NSA rescued DES from differential cryptography": I coined the name Deep Crack for the EFF machine that brute-forced DES in 56 hours on a $250K budget. Ostensibly a play on Deep Blue and Deep Thought. The official hidden message, per my email in 1998: there's a Deep Crack in the government's export control policies. Unofficial hidden message: they strengthened DES against every attack except the one their budget could afford. Not responsible for allusions to the Liberty Bell, Marion Barry's favorite nose candy, Mark Felt's alias, Linda Lovelace's famous movie, or Douglas Adams's computer that answered forty-two. Responsible for the observation that when someone says NSA "rescued" a standard, it's worth asking what crack they left in it for themselves. The first key's free! Deep Crack origin story (Denise Caruso + Gilmore + Hopkins, 1998): https://www.donhopkins.com/home/archive/humor/deep-crack.txt https://www.donhopkins.com/home/archive/humor/deep-crack.txt EFF DES cracker: https://en.wikipedia.org/wiki/EFF_DES_cracker https://en.wikipedia.org/wiki/EFF_DES_cracker Deep Crack Chip: https://en.wikipedia.org/wiki/EFF_DES_cracker#/media/File:Chip300.jpg https://en.wikipedia.org/wiki/EFF_DES_cracker#/media/File:Ch... EFF's Cracking DES Page: https://w2.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/ https://w2.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/ Sun DES chip socket (export control) and boot ROM easter egg: https://news.ycombinator.com/item?id=34125377 https://news.ycombinator.com/item?id=34125377
- cassonmars 1mo ago
  Let's opt for the simplest possible way to describe this. A good number of the proposals (in particular, the proposals that actually got close to being chosen), are based on lattice constructions. NTRU's underlying construction has been available to scrutinize for 30 years, whereas the Module-LWE proposals (Kyber being one) has had 11 years. Keep in mind, the largest employer (and under very tight classified controls) of number theorists _is_ the NSA. In terms of overall intellectual power, if there _is_ a problem in the MLWE constructions, they'd very likely be the first to find it, all while not saying a single word. Then, despite clear objections laid out by people with explicit expertise on the distinctions between RLWE and MLWE, especially w/r/t parameter choice, Kyber, under weaker parameters, was chosen anyway. We can't rely on the obvious tells anymore – they've already played that hand (EC-DRBG) and were caught. If a bad standard is being pushed, it has to be done in a way that is so subtle, that it literally comes up to, "yeah, maybe this is weaker, but we haven't found a way to prove that". DJB already lost the selection process, so now the goal is to at the very least, avoid recommendations that push an unshielded, far less historically tested option, with no helpful antidote if it were to be broken. I get that generally assuming conspiracies is a bad starting place for debate (after all, how do you disprove a hypothesis that is expected to be so surreptitiously constructed that it evades all ability to be scrutinized?), and I'd similarly think this is an unreasonable assumption, except for the fact _it has already happened and been exposed, multiple times_.
  - tptacek 1mo ago
    Wait, first off, I want to note here that you're suggesting that 1990s NTRU is a more trustworthy design than Module-LWE. But the bigger problem is with your logic. It applies to literally any other choice NIST could have made. If they had selected Classical McEliece, another Bernstein submission, people like you would be on threads pointing and saying "see, the security of McEliece is collapsing before our eyes, of course NSA forced NIST to choose it".

because the NSA has never surreptitiously pushed bad standards they used to exploit before /s

tptacek 1mo ago

Which PQC standard are you suggesting they pushed, and how did they push it? Flesh the argument out.

vlovich123 1mo ago
That’s a very unfair position to take when dealing with secret agencies who try very hard to obfuscate this stuff - it is hard to provide evidence for in the moment. The government has intentionally acted to weaken DES, standardized Dual_EC_DRBG, performed subtle subterfuge through interfering how NIST operates to inject weaknesses and vulnerabilities, trying to weaken SSL and IPSec, 4G smartphone encryption. These are all documented examples of the NSA engaging in bad faith. So whether or not it is happening in this particular case, there’s now just zero trust in the institutions acting in good faith. And given it took decades for the actions to come out after they were taken, how do you expect someone to answer your request to present evidence there’s anything nefarious happening now? Anyway, that’s what I think a fleshed out argument would look like
- tptacek 1mo ago
  It's a simple question. I'm not asking anybody to prove anything. I'm literally asking: propose the PQC standard IETF could have subverted, and give a sketch of how they could have done it. The bar is merely "plausibility". I'm not asking whether NSA has subverted standards before; obviously they have. NSA, by the way, rescued DES from differential cryptography, the core mechanism by which block ciphers and hash functions have been attacked ever since.
  - Vecr 1mo ago
    > NSA, by the way, rescued DES from differential cryptography, the core mechanism by which block ciphers and hash functions have been attacked ever since That's why you use ML-KEM 1024 at all... As part of a hybrid.
    - tptacek 1mo ago
      I don't know what this is, but it isn't an answer to the question. I'm starting to notice that nobody is able to come up with an answer.
      - Vecr 1mo ago
        There is no public reason to think that 1024 is better than 768, or DJB's S-NTRU-P 761. The NSA might know something, but we can't trust them. So, use a hybrid, in case they are really just trying to protect us.
        tptacek 1mo ago
        That can't be the argument --- it can't be that NSA simply knows a vulnerability that impacts one very specific lattice scheme and not the others. The reason for that is a cryptographic concept known as the Vizzini Conjecture: the argument you just put forward can be applied to literally any cryptographic standard NIST authors. Since NSA knows that, and knows you know it, you can clearly not choose the wine in front of you. It must be that the standard NIST picks is the only secure one, so that NSA can see it tainted by NIST association. But yes, this is the useful conversation to have. There are other scenarios! You can get into more detail on where MLKEM came from, for instance.
        Vecr 1mo ago
        Yes, they trick me and I pick the poisoned wine... But wait, no, I used a hybrid. Imagine the code can't be backdoored (it's proven not to crash/be slow/be exploitable) so at worst it can make the security no better. At best, the NSA knows a whole new subfield of cryptography (from history: differential cryptanalysis) and it really is more secure. They laugh at us while we try to think of how 1024 is better than 768: "bigger is better, right?" "does 1024 refer to the number of years it takes Nightmare Moon to break the code?"
  - vlovich123 1mo ago
    They did both - they strengthened it from differential integrity but weakened it by picking a known-to-be-too-short key length. Meaning they had the compute power to crack it but others couldn’t do the same through pure algorithmic means. As for your post below > it can't be that NSA simply knows a vulnerability that impacts one very specific lattice scheme and not the others Ok. My argument is they know all lattice schemes are weak and the push to use a lattice-only scheme is precisely to have a cryptographic mechanism they can easily bypass without a classical known-secure backstop.
    - tptacek 1mo ago
      See, here's another argument that doesn't work here, because Bernstein very publicly backs a different lattice cryptography scheme. In addition to the previously-stated reason why that argument is inoperative (besides being unfalsifiable, it admits a strategy where NSA "poisons the well" to get people to avoid a particular construction or family of algorithms, so that we all move to weaker ones --- a counterfactual that should be much more vivid after what was released this week!)
      - vlovich123 1mo ago
        Does Bernstein back using the alternate scheme exclusively or combined as a hybrid? You’re arguing in bad faith throughout the thread, taking the weakest possible interpretation of anything said and extrapolating to nonsensical positions to paint the people who disagree with you as idiots. Please do better.
        tptacek 1mo ago
        We'll never know, because he only started advocating for hybrids after MLKEM happened. When he did 25519, he did not advocate for 25519/RSA or 25519/FFDH or 25519/P256 hybrids. Agree or disagree with my arguments on substance; it's fine, we're all coming to this with different priors, levels of experience, familiarity with the drama and with the underlying issues, etc. But this "do better, you're in bad faith" stuff is just chaff, and you'd do well to leave it out of your comments. (It's hard sometimes for me to do that, too. Disagreement is tough!)
  - DonHopkins 1mo ago
    Re "NSA rescued DES from differential cryptography": I coined the name Deep Crack for the EFF machine that brute-forced DES in 56 hours on a $250K budget. Ostensibly a play on Deep Blue and Deep Thought. The official hidden message, per my email in 1998: there's a Deep Crack in the government's export control policies. Unofficial hidden message: they strengthened DES against every attack except the one their budget could afford. Not responsible for allusions to the Liberty Bell, Marion Barry's favorite nose candy, Mark Felt's alias, Linda Lovelace's famous movie, or Douglas Adams's computer that answered forty-two. Responsible for the observation that when someone says NSA "rescued" a standard, it's worth asking what crack they left in it for themselves. The first key's free! Deep Crack origin story (Denise Caruso + Gilmore + Hopkins, 1998): https://www.donhopkins.com/home/archive/humor/deep-crack.txt https://www.donhopkins.com/home/archive/humor/deep-crack.txt EFF DES cracker: https://en.wikipedia.org/wiki/EFF_DES_cracker https://en.wikipedia.org/wiki/EFF_DES_cracker Deep Crack Chip: https://en.wikipedia.org/wiki/EFF_DES_cracker#/media/File:Chip300.jpg https://en.wikipedia.org/wiki/EFF_DES_cracker#/media/File:Ch... EFF's Cracking DES Page: https://w2.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/ https://w2.eff.org/Privacy/Crypto/Crypto_misc/DESCracker/ Sun DES chip socket (export control) and boot ROM easter egg: https://news.ycombinator.com/item?id=34125377 https://news.ycombinator.com/item?id=34125377
cassonmars 1mo ago
Let's opt for the simplest possible way to describe this. A good number of the proposals (in particular, the proposals that actually got close to being chosen), are based on lattice constructions. NTRU's underlying construction has been available to scrutinize for 30 years, whereas the Module-LWE proposals (Kyber being one) has had 11 years. Keep in mind, the largest employer (and under very tight classified controls) of number theorists _is_ the NSA. In terms of overall intellectual power, if there _is_ a problem in the MLWE constructions, they'd very likely be the first to find it, all while not saying a single word. Then, despite clear objections laid out by people with explicit expertise on the distinctions between RLWE and MLWE, especially w/r/t parameter choice, Kyber, under weaker parameters, was chosen anyway. We can't rely on the obvious tells anymore – they've already played that hand (EC-DRBG) and were caught. If a bad standard is being pushed, it has to be done in a way that is so subtle, that it literally comes up to, "yeah, maybe this is weaker, but we haven't found a way to prove that". DJB already lost the selection process, so now the goal is to at the very least, avoid recommendations that push an unshielded, far less historically tested option, with no helpful antidote if it were to be broken. I get that generally assuming conspiracies is a bad starting place for debate (after all, how do you disprove a hypothesis that is expected to be so surreptitiously constructed that it evades all ability to be scrutinized?), and I'd similarly think this is an unreasonable assumption, except for the fact _it has already happened and been exposed, multiple times_.
- tptacek 1mo ago
  Wait, first off, I want to note here that you're suggesting that 1990s NTRU is a more trustworthy design than Module-LWE. But the bigger problem is with your logic. It applies to literally any other choice NIST could have made. If they had selected Classical McEliece, another Bernstein submission, people like you would be on threads pointing and saying "see, the security of McEliece is collapsing before our eyes, of course NSA forced NIST to choose it".