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. 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.
Presumably 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.
This 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.
> 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.
It'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.
There isn’t any going back until they have a version that supports different crypto (a hard fork). It’s not clear how you could possibly allow exits unless you literally ban all transactions on the chain after a certain date.
At that point though, why would anyone be on the buy side of the sell to USD?
I addition to the incentive to hide it and not stir up any obvious evidence, anyone with enough money to throw at the problem probably doesn't want to wreck the current financial system
You'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-...)
> […] 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.
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.
Many of the bigger inventions in history were popularized by someone other than the original inventor, because everything is a remix: https://www.youtube.com/watch?v=nJPERZDfyWc
Turing also just comes off like a bit of an antisocial asshole, and those around him are kind of dimwitted fools. Neither of those seem accurate based on anything else I've read of that time.
He's a movie trope instead of a character or a person.
> 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.
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.
> 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.
That 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?
"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]
NIST'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.
He 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.
CRYSTALS-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?
> The developers of OpenSSH agree enough to use this scheme in OpenSSH.
Or simply because it was the most convenient algorithm at the time (2022).
There may also be regulated industries where Officially Approved™ algorithms need to be used, and if you're not on the list you're not going to be enabled, so if the developers of OpenSSH want to protect their users in those situations, then they're going to have to offer something on the list (even if it's not enable by default, or further down the preference ranking in the default settings).
> 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.
So in my opinion, NTRU Prime is a good cryptosystem. But it's not particularly better than Kyber: each has small advantages and disadvantages, and both got a ton of expert review (Kyber even more than NTRU Prime), and they will probably stand or fall together depending on improvements in lattice cryptanalysis.
I also don't think Kyber suffers from design-by-committee. There are a zillion small choices to make in these lattice schemes, and while some choices are definitely wrong, both the NTRU Prime and Kyber teams made reasonable ones. The same goes for SABER and regular NTRU.
DJB's signature proposal is SPHINCS+, which is standardized in FIPS 205 as SLH-DSA. NTRUPrime is a KEM, so it doesn't really compete with FALCON.
Personally I think that FALCON is brilliant, but it is very difficult to securely implement or even precisely define, due to heavy use of floating-point arithmetic in the signing routine. I don't want to put words in DJB's mouth, but if you share his concern for ease of secure implementation, ease of auditing and side-channel protection, then you may prefer SPHINCS+ or, if the performance of SPHINCS+ is not acceptable in your workload, possibly Dilithium.
Of course, if signature size is make-or-break, then of the choices currently slated for standardization, FALCON has the smallest signatures. But it is possible that the new signature onramp will change that in a few years -- if you can be confident in the security of whatever is chosen within so short a time.
I find this particular NIST process confusing. ML-KEM 1024 for key encapsulation is FIPS 203 certified, so I take it that it is the right choice for key encapsulation? But there are FIPS 204 and 205 standards for digital signatures, apparently soon to be complemented by FIPS 206 based on FALCON. Which one should be used?
Has NIST stopped to recommend one winner and opted for several. Or, do these have different purposes?
SLH-DSA aka SPHINCS+ is the most conservative choice (i.e. they are all secure against currently-known attacks, but SLH-DSA is less likely to be broken later), but it is slow (at least several milliseconds to sign) and produces large sigs (>= 7.8kB). This means that it may not be suitable for all applications.
Dilithium is faster but less conservative, harder to implement securely, and produces medium sigs.
FALCON is even harder to implement securely, faster to verify and produces smaller sigs, though still much larger than classical systems. IMHO this choice was questionable, in that its advantages overlap too heavily with Dilithium to be worth another standard, but NIST apparently felt otherwise.
Thank you! That clarifies it. The length of the signatures indeed seems to be a problem. I'm currently investigating ways to implement secure group chat (like adapting MLS to use PQC).
PQC 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.
There’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.
The 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.
47 comments
[ 1.7 ms ] story [ 107 ms ] threadIt 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.
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.
At that point though, why would anyone be on the buy side of the sell to USD?
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-...)
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.
The book is much better about both.
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.
Many of the bigger inventions in history were popularized by someone other than the original inventor, because everything is a remix: https://www.youtube.com/watch?v=nJPERZDfyWc
He's a movie trope instead of a character or a person.
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-...
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/
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.
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/
"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://libntruprime.cr.yp.to/
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.
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?
https://csrc.nist.gov/Projects/post-quantum-cryptography/sel...
Some previous discussion on this from 2022 and 2023:
* https://news.ycombinator.com/item?id=32360533
* https://news.ycombinator.com/item?id=37756656
Or simply because it was the most convenient algorithm at the time (2022).
There may also be regulated industries where Officially Approved™ algorithms need to be used, and if you're not on the list you're not going to be enabled, so if the developers of OpenSSH want to protect their users in those situations, then they're going to have to offer something on the list (even if it's not enable by default, or further down the preference ranking in the default settings).
* https://ubuntu.com/blog/ubuntu-22-04-fips-140-3-modules-avai...
* https://www.stigviewer.com/stig/canonical_ubuntu_22.04_lts/2...
* https://www.stigviewer.com/stig/red_hat_enterprise_linux_9/2...
* https://support.apple.com/en-ca/guide/certifications/apc35eb...
So in my opinion, NTRU Prime is a good cryptosystem. But it's not particularly better than Kyber: each has small advantages and disadvantages, and both got a ton of expert review (Kyber even more than NTRU Prime), and they will probably stand or fall together depending on improvements in lattice cryptanalysis.
I also don't think Kyber suffers from design-by-committee. There are a zillion small choices to make in these lattice schemes, and while some choices are definitely wrong, both the NTRU Prime and Kyber teams made reasonable ones. The same goes for SABER and regular NTRU.
But really, there are very few "trustworthy" PQCrypto algorithms/implementations and he is the author of more than one of those.
Personally I think that FALCON is brilliant, but it is very difficult to securely implement or even precisely define, due to heavy use of floating-point arithmetic in the signing routine. I don't want to put words in DJB's mouth, but if you share his concern for ease of secure implementation, ease of auditing and side-channel protection, then you may prefer SPHINCS+ or, if the performance of SPHINCS+ is not acceptable in your workload, possibly Dilithium.
Of course, if signature size is make-or-break, then of the choices currently slated for standardization, FALCON has the smallest signatures. But it is possible that the new signature onramp will change that in a few years -- if you can be confident in the security of whatever is chosen within so short a time.
Has NIST stopped to recommend one winner and opted for several. Or, do these have different purposes?
Dilithium is faster but less conservative, harder to implement securely, and produces medium sigs.
FALCON is even harder to implement securely, faster to verify and produces smaller sigs, though still much larger than classical systems. IMHO this choice was questionable, in that its advantages overlap too heavily with Dilithium to be worth another standard, but NIST apparently felt otherwise.
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.
Do you have a project webpage?