6 ms·
What Is Post-Quantum Cryptography? – NIST
- cj 2y agoI was watching a WW2 documentary yesterday and learned Nazi Germany’s encryption had already been (mostly) cracked by the time they entered the war, which (don’t quote me) significantly influenced the outcome of the war. They thought their communications were encrypted, but that was a false belief. It got me thinking. Once someone truly does break current gen encryption via quantum or otherwise, how much time would go by before it is made known to the public that the encryption is broken? It seems the safest path forward is to assume encryption is broken and move to post-quantum crypto before we “need” to.
- throw0101d 2y ago> I was watching a WW2 documentary yesterday and learned Nazi Germany’s encryption had already been (mostly) cracked by the time they entered the war, which (don’t quote me) significantly influenced the outcome of the war. The Poles had broken Enigma before the outbreak of war (1945-09-01) with the help of intelligence from France. Bletchley Park used computers to speed up the process of going through the messages.[0] It has been remarked that 'cracking Enigma shortened the war by X years',[1] so for some people this could be considered "significantly influenced". However, after reading Engineers of Victory by Paul Kennedy: > Kennedy recounts the inside stories of the invention of the cavity magnetron, a miniature radar “as small as a soup plate,” and the Hedgehog, a multi-headed grenade launcher that allowed the Allies to overcome the threat to their convoys crossing the Atlantic; the critical decision by engineers to install a super-charged Rolls-Royce engine in the P-51 Mustang, creating a fighter plane more powerful than the Luftwaffe’s; and the innovative use of pontoon bridges (made from rafts strung together) to help Russian troops cross rivers and elude the Nazi blitzkrieg. He takes readers behind the scenes, unveiling exactly how thousands of individual Allied planes and fighting ships were choreographed to collectively pull off the invasion of Normandy, and illuminating how crew chiefs perfected the high-flying and inaccessible B-29 Superfortress that would drop the atomic bombs on Japan. * https://www.penguinrandomhouse.com/books/91616/engineers-of-victory-by-paul-kennedy/ https://www.penguinrandomhouse.com/books/91616/engineers-of-... I think there were more important developments than cracking Enigma, as influential as that could have been. If we're talking about codes, then I think the Americans breaking the Japanese ones was more important: the US would have won regardless just because of industrial output, but the intercepts allowed things like being able to predict Midway and being able to take out Yamamoto had more meaningful operational results than what was gained out of Ultra, IMHO. In the European theatre, I think the Merlin engine was much more critical to the outcome of the war (especially in the Battle of Britain), and the cavity magnetron was more important in the Battle of the Atlantic (along with re-learning to use convoys, like was done in WW1). [0] Bletchley Park broke other codes, like Lorenz; see William "Bill" Tutte. [1] https://old.reddit.com/r/AskHistorians/comments/2pq5fa/ https://old.reddit.com/r/AskHistorians/comments/2pq5fa/
- Mistletoe 2y agoPretty sure all hell would break loose financially so there would definitely be signs. Think how much value is locked up behind cryptography.
- cj 2y agoPresumably any organization/government smart enough to break cryptography would be smart enough not to do anything that would reveal their ability, unless they wanted their ability known.
- derekmhewitt 2y agoThis actually happened in WW2, after fully breaking the Enigma codes the Allies had to carefully choose which intelligence to act on and not act on, sometimes with poor results for their own side. But the alternative would have been that the Germans would have to conclude their communications were compromised and change something, rendering a lot of the effort to crack enigma in the first place moot. The Turing movie mentioned in another comment is excellent and touches on this topic.
- staunton 2y ago> Think how much value is locked up behind cryptography. It's actually "so much value" that it's not possible to take much of it if you reveal that you did. People can "fork (parts of) the financial system" even more easily (per actor) than what happens with cryptocurrencies. Sure, it's a huge hassle with huge overhead but you cannot reveal the capability and also take more than that hassle is worth. I think this means that anyone capable of doing it would not reveal the ability as as a first priority, as others here have also suggested. Especially for a state actor, the trade-off is very clear.
- notfed 2y agoIt'd be sort of a funny situation if this happened now, because a fork necessarily rolls back recent transactions. So, imagine if people are made aware of a break, and it caused a bank run (on Bitcoin for let's say). Well, tons of transactions would be reversed, including peoples' attempt to cash out. If the attack repeats the next day, the fork would happen again. It'd be utter chaos.
- refulgentis 2y agoYou'll enjoy the movie "The Imitation Game" - it's a well-made film about Alan Turing (of Turing-completeness fame) and his working group's cracking of Germany's Enigma encryption system. FWIW, secondary to that: 100%, industry and NIST are actively voicing this, there's an interesting Google blog somewhere about work on it in Chrome (tl;dr: behind flags in chrome, but you can try it today. I think this is what I'm thinking of: https://blog.chromium.org/2023/08/protecting-chrome-traffic-with-hybrid.html https://blog.chromium.org/2023/08/protecting-chrome-traffic-...)
- deleted 2y ago[deleted]
- throw0101d 2y ago> […] and his working group's cracking of Germany's Enigma encryption system. Enigma was already broken. AIUI, Turing et al helped automate the deciphering messages, which was heavy going manually because of the volumes involved. Bletchley Park did have to do cryptanalysis on Enigma when a new rotor was added though. Completely 'original' breaking did occur at Bletchley Park with (e.g.) the Lorenz cipher; see William "Bill" Tutte.
- kadoban 2y agoIt is an enjoyable movie, but I'd caution that it's _quite_ innacurate both about the history in general and about Turing in particular. The book is much better about both.
- kortilla 2y agoIs there a tldr on the inaccuracies to quickly inform people who only watched the film?
- less_less 2y agoGeez like pretty much everything. See eg https://slate.com/culture/2014/12/the-imitation-game-fact-vs-fiction-how-true-the-new-movie-is-to-alan-turings-real-life-story.html https://slate.com/culture/2014/12/the-imitation-game-fact-vs... Enigma was originally broken by a team of Polish cryptanalysts, who invented both a paper method to break it (Zygalski sheets) and the machine shown in movie (Rejewski's bomba). Turing later worked on a team to improve the bomba, which was a significant achievement but he didn't invent or spearhead the whole thing. All this "don't use a machine to do a man's job" was bullshit invented for the movie, as were like half the other conflicts. Everyone involved knew that breaking Enigma was important, and they were already using a machine to do it, but after the Nazis changed their use of Enigma, the Brits needed mathematical insights to improve the speed of their machine. The main characters in the film did exist and had some of the personality traits shown, but mostly didn't interact they way that the film showed. Turing was openly gay. Cairncross (the spy) didn't work with Turing. The codebreakers didn't choose which intercepted information to use and how, etc.
- staunton 2y ago> the safest path forward is to assume encryption is broken and move to post-quantum crypto before we “need” to. An even safer path would be to use both "classical" and post-quantum methods in combination ("hybrid"). You're protected against someone building quantum computers (and inventing new math to break classical cryptography, which is less likely) and also against yet-undiscovered weaknesses of post-quantum primitives.
- notfed 2y agoThat is exactly why the term "post-quantum crypto" was coined and why it's being pushed. [1] For confidential data, the only rational thing to do is assume asymmetric crypto is already broken, or will be broken soon. And for non-confidential data, well...come on, who wants to waste time combing through data and deciding if it's confidential or not? [1] https://postquantum.cr.yp.to/ https://postquantum.cr.yp.to/
- shoggouth 2y agoIn case anyone wants to check out NTRU. "NTRU encryption algorithm, is an NTRU lattice-based alternative to RSA and elliptic curve cryptography (ECC) and is based on the shortest vector problem in a lattice (which is not known to be breakable using quantum computers)."[0] [0]: https://en.wikipedia.org/wiki/NTRUEncrypt https://en.wikipedia.org/wiki/NTRUEncrypt
- tptacek 2y agoNIST's first PQC standard, CRYSTALS-Kyber, is also a lattice-based system (with a more complex structure and based on LWE rather than the NTRU SVP. There are now solid implementations of it all over the place, so it's much easier to check out.
- alphazard 2y agoDan Bernstein (look him up, you already use a lot of his cryptography) recommends Streamlined NTRU Prime. https://libntruprime.cr.yp.to/ https://libntruprime.cr.yp.to/
- tptacek 2y agoWhich other cryptographers agree with him about this?
- alphazard 2y agoHe has repeatedly collaborated with Tanja Lange who is also credited as working on the original NTRU Prime design. The other collaborators (all respected cryptographers) presumably think the scheme is sound as well. The developers of OpenSSH agree enough to use this scheme in OpenSSH. DJB is high profile enough that all of his stuff gets a lot of cryptanalysis from experts. This isn't a rando proposing a scheme that no one can follow, and no one can be bothered to review. He consistently designs cryptographic systems which perform better and are less error prone to implement than systems designed by committees of people.
- tptacek 2y agoCRYSTALS-Kyber had the same team structure; neither was more "designed by a committee" than the other. Can you articulate what would make Bernstein's team more credible than the Kyber team? I promise you, CRYSTALS-Kyber does not lack for expert analysis. I ask all this because there's a pretty big "Schneier Facts" vibe to anything that involves Bernstein, and because I don't think you'll find many cryptographers --- probably even including on the NTRU Prime team --- that would sign off on his critique of Kyber and the NIST process. I could be wrong, but if I am, could you tell me how?
- notfed 2y agoAlso, CRYSTALS-Kyber was a finalist in NIST's PQCrypto competition: https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022 https://csrc.nist.gov/Projects/post-quantum-cryptography/sel...
- ilove196884 2y agoPQC is a proposal based on aggressive scaling of quantum computers however looking at the manufacturing end of it (mainly IMEC and PSI) that doesn't seem to be the case. Heck the chinese government doesn't think that aes-256 will be broken by quantum computers till atleast 2100.I wonder which vendor convinced NIST to go ahead with PQC because the hype is plain fear mongering.
- lattice_epochs 2y agoI think they're talking about asymmetric crypto, not symmetric crypto, which is somewhat quantum resistant (or they can just double the length).
- orangeboats 2y agoAES is symmetric. PQC is pretty much all about asymmetric cryptography.
- kurikuri 2y agoThere’s a lot wrong with what you said. PQC is a new set of standards (FIPS 203, 204, and 205) describing digital signature schemes and key encapsulation methods that are resistant to a quantum computer’s computational advantage. These methods involve public key cryptography and are asymmetric. AES-256 is a symmetric encryption method and PQC has nothing to do with it. The article in question mentions one of the key risks of not introducing quantum-resistant methods: harvesting the encrypted data and waiting for a future date to decrypt it. This is a real risk, and breakthroughs in this field are difficult to predict. Considering the fact that NIST’s guidance applies to most of the federal government, it is prudent for their strictest forms of security standards to provide a high level of assurance against state-level threat actors.
- kidme5 2y agoThe quantum "threat" is a great excuse to get everyone to adopt new backdoors. If you use these it better be enveloped in a more trustworthy encryption.
- lokimedes 2y agoI would like to add PQE to our WebRTC E2EE system, have anyone here dine that?
- kurikuri 2y agoDepending on how modular your current implementation is, most of the interfaces of PQC-implementations are the same as those which they replace. Do you have a project webpage?