9 ms·

Why Quantum Cryptanalysis is Bollocks [pdf]

132 points by commandersaki 2y ago

kirrent 2y ago
Man, some real "Cynicism is the intellectual cripple's substitute for intelligence" energy here. Seems unnecessary given what I read of Gutmann's history. I get it must be annoying to be someone working in cryptography and always be hearing about QC when there are endless security issues today. It must be tiring to have all these breathless pop-science articles about the quantum future, startups claiming ridiculous timelines to raise money on hype, and business seminars where consultants claim you'll need to be prepared for the quantum revolution changing how business works. I feel the same way. But you shouldn't let that drive you so far in the opposite direction that you're extrapolating fun small quantum factoring experiments from a decade ago to factoring 1024 bit keys in the year 4000. Or say things like 'This makes the highly optimistic assumption that quantum physics experiments scale linearly... the evidence we have, shown by the lack of progress so far, is that this is not the case'. If we get fault tolerant QC of course it scales linearly and it seems embarrassing as a computer scientist to not understand the difference between constant and asymptote. "Actually, quantum computers are so new and untested that they really qualify as physics experiments"... yeah? And? None of this is to say that fault-tolerant highly scalable QC implementing Shor's algorithm is just around the corner, I truly believe it's not. But the world of QC is making really interesting advances running some of the coolest experiments around and I find this superior Hossenfelder-like cynicism in the face of real science making real progress so so tiring.
- pclmulqdq 2y ago
  One major point of the presentation here is that it's not making real progress. People are still publishing papers, but they have done nothing with an effect outside their little community. It's been in roughly the same state for the last 10 years. For a minimum of 30 years, there have been promises of amazing things coming in the next decade in QC. After how many decades should those predictions lose credibility? There is real opportunity cost to doing this stuff, and real money getting sucked up by these grifters that could be spent on real problems. There are real PhD students getting sucked down this rabbit hole instead of doing something that actually does make progress. There is a real cost to screwing around and making promises of "next decade."
  - kirrent 2y ago
    I agree! People who predicted QC soon over the last few decades should lose credibility. They were wrong and they were wrong for no good reason. There is a real opportunity cost to focusing on the wrong thing. There are definitely grifters in the space. Responsible QC researchers should call it out (e.g. Scott Aaronson). But it doesn't necessarily follow that you can dismiss the actual underlying field. Within the last five years alone we've gone from the quantum supremacy experiment to multiple groups using multiple technologies to claim QEC code implementations with improved error rates over the underlying qubits. People don't have to be interested in these results, they are rather niche (a little community as you put it), but you shouldn't be uninterested and then write a presentation titled 'Why Quantum Cryptanalysis is Bollocks'.
    - pclmulqdq 2y ago
      Well, when the little community circles the wagons around the grifters instead of excising them, the rest of us get to ask questions about that community. The cold fusion community did the same thing for several decades, too. And by the way, about 0.01% of the grifters in the QC space are getting called out right now.
  - wasabi991011 2y ago
    > One major point of the presentation here is that it's not making real progress. How are you measuring "real progress"? > People are still publishing papers, but they have done nothing with an effect outside their little community. Having an effect outside the research community is essentially a Heaviside function. Before the field is mature enough, there is no effect outside, but once the field is mature enough, there is an effect outside. Makes it hard to judge if there is any progress or not.
    - pclmulqdq 2y ago
      The field has had 40 years of maturing. Experimentation on QC started in the 1980's. At what point are we going to be factoring numbers or (more realistically) simulating chemical interactions? Real progress in this field is very easy to measure. It's based on number of effective qbits of computation. That is just a metric where QC is failing to deliver so badly that everyone in the field wants to deny its existence. Unfortunately, the level of investment in QC is very much outsized compared to the level of progress. These things should rise at the same time. More promising areas of science can get the investment that is otherwise being sucked into QC. > Having an effect outside the research community is essentially a Heaviside function. This is something that people like to say but is never true. Impact on the outside world for new technologies is almost always a sigmoid function, not a heavyside function. You should see some residual beneficial effects at the leading edge if you have something real.
- oh_my_goodness 2y ago
  It's strange to see so many negative responses that start with vague emotional language. It's almost as if a lot of critics didn't read the presentation. Or maybe they think the rest of us didn't read it.
  - fxwin 2y ago
    Is it really that strange when the slides themselves pretty emotionally charged?
    - oh_my_goodness 2y ago
      Good question. Yes it is strange, because the information on the slides is mainly numerical. For example the integers "15" and "21" and the years "2002" and "2012" don't pack much of an emotional charge for me. I suspect they wouldn't for most people.
      - fxwin 2y ago
        You missed the number 15360 on p12, which is mostly what i was referring to.
  - kirrent 2y ago
    I read the whole presentation. The physics experiment criticism Guttman makes that I referred to is at page 16/30. Nothing after that engages with QC to the extent that the first half of the presentation did, so I didn't refer to later parts.
nemo 2y ago
This smalls a lot like wishcasting masquerading as critique. I just attended a PQC conference, so I'm biased, but this paper's author makes a lot of very strong claims about the infeasibility of future attacks developing that most experts in the field would disagree with. There is a hope that this is all a fire drill and RSA/EC will survive the next decade unscathed, but there's also plenty of evidence to suggest that incremental improvements in PQ compute will eventually reach their goal. Rather than a big cannon, I see it looking more like AI/LLMs, lots and lots of small incremental improvements by researchers were needed to eventually yield some significant advancements. I pray Post Quantum computing stays in the realm of Cold Fusion, but I'm not about to believe it. Cryptanalysis has already made a few strides on breaking RSA more quickly, and I've heard from noted cryptanalysts the claim there's a significant chance RSA will be further broken in the next decade regardless of PQ. It's a scary take to double down on RSA of all things.
- baxtr 2y ago
  Out of curiosity: which conference did you attend? I find the field interesting.
  - nemo 2y ago
    PKI Consortium: https://pkic.org/events/2025/pqc-conference-austin-us/ https://pkic.org/events/2025/pqc-conference-austin-us/
- tptacek 2y ago
  Could you relate who those noted cryptanalysts are, that are predicting a significant chance that RSA-2048 is broken classically?
  - nemo 2y ago
    I don't recall their name, they were a guest on the Root Causes podcast discussing PQ topics, though your summary varies from what I was trying to express. It's not that RSA will be classically broken, but that novel attacks to reduce factoring times of RSA key like batch attacks have a statistically significant chance of being discovered, that "further" was not meant to imply "completely broken classically," but "weakened further using classical approaches". Sounded plausible to me, though that's not a thing I'm any kind of domain expert in.
tptacek 2y ago
Love me some Peter Gutmann. This is classic Gutmann. A lot of this presentation is mooted by understanding PQC as an scientific question rather than an engineering one. What are the precise natures of quantum-superior attacks on cryptosystems and what are key establishments and signatures that resist those attacks? Whatever else you think of quantum cryptanalysis those are undeniably important theoretical questions. A few more slides are mooted by the likelihood that any mainstream deployed PQC system is going to be hybridized with a classical cryptosystem. As an articulation of a threat model for modern computing, it simultaneously makes some sense and proves too much: if you think OWASP-type vulnerabilities are where everyone's head should be at (and I sort of agree), then all of cryptography is a sideshow. I'm a connoisseur of cryptographic vulnerabilities that break real systems the way SQL injection does (a bitflipping attack on an encrypted cookie, a broken load-bearing signature scheme) but even I have to admit there's 1 of those for every 10,000 conventional non-cryptographic attack. But of course, it also depends on who your adversary is. Ironically, if you're worried about state-level SIGINT, the barrier for OWASP-style attacks may be higher than that of large-scale codebreaking; passive interception and store-now-decrypt-later is the SIGINT love language. My biggest thing with all of this is a core belief about organizations like NSA: that they exist primarily to secure budget for NSA. Given that, the one thing you absolutely don't want to do is have a system that is breakable only at almost-implausible cost. (Also, his RSA-1024 analysis is off; it's missing batch attacks).
- pclmulqdq 2y ago
  Yeah, I don't think anyone told him about WindsorGreen, the RSA-cracking supercomputer that IBM built for the NSA. RSA-1024 probably should be assumed unsafe at this point.
- dadrian 2y ago
  I'm with you, but the government (at least in the US and UK) should definitely be spending more time figuring out how to patch reliably, and little less on PQC.
  - thadt 2y ago
    Perhaps the other side of the coin Peter calls "churn" is "updated software". Government, like every other old organization, has a ton of legacy systems. Even if CRQC is a pipe dream, having an excuse to tell everyone across the board they need to update their stuff sometime in the next decade might be a net win.
mik1998 2y ago
I think it is worthwhile to explore cryptography that is not based on the discrete logarithm problem. Currently, we're keeping all eggs in one conjectured basket. Even if quantum computing will never be viable, there is a non-zero chance that the discrete logarithm problem will be solved in some other way.
- layer8 2y ago
  There is a non-zero chance of pretty much anything. I don't think Gutmann is opposed to exploration.
  - bawolff 2y ago
    I think the parent's point is that if there is a non-zero chance of anything then it is good to have a backup plan
    - layer8 2y ago
      There is a non-zero chance of a black hole forming in the LHC and swallowing the Earth, yet we don’t have a backup plan for that. There are an infinite more examples like that. A non-zero chance is not an argument for anything, unless you have a good basis on actually quantifying it.
- als0 2y ago
  What are you talking about? PQC is based on learning-with-errors and lattice problems https://en.wikipedia.org/wiki/Learning_with_errors https://en.wikipedia.org/wiki/Learning_with_errors
hujun 2y ago
one thing I agree that software/standard people like to churn, churn is a source of new income regardless if QC could break RSA or not in the future, people could make profit now
Strilanc 2y ago
Using the largest number factored as a benchmark for progress in quantum computing is like evaluating floor(f(0)) = 0 and floor(f(1)) = 0 and concluding f(x) = 0. You can't distinguish f(x) = 0 from f(x) = x/2 from f(x) = e^x/3 when your test is too coarse. If you want to see the progress in quantum computing today, pay attention to component reliability. For example, in 2014, the best rep code run on a quantum computer had a 1% error rate per round [1]. In 2024, it was 0.00000001% and it had become possible to run full quantum codes with a 0.2% error rate per round [2]. If it takes another decade for that 0.2% to go down by a factor of a thousand, then you've got lots of time. Maybe you'll be dead before progress exceeds the coarseness of factoring. If it takes a year instead of decade (because the cost of error correction is frontloaded) then, well, pay appropriate attention to that. [1]: https://arxiv.org/abs/1411.7403 https://arxiv.org/abs/1411.7403 [2]: https://arxiv.org/abs/2408.13687 https://arxiv.org/abs/2408.13687
- upofadown 2y ago
  I think the author was just poking fun at the idea that the 15 and 21 factoring results can be used to indicate some sort of progress. I think the graph makes that obvious. Last I heard we were 1-2 orders of magnitude away from a physical qubit error rate low enough for error correction to have a chance of creating a threat against cryptography. So things sound pretty unlikely at the moment. We need a fundamental breakthrough.
  - dullcrisp 2y ago
    Is 1–2 orders of magnitude a lot or a little here? With exponential progress that could be a few years; with stalled progress that’s maybe never.
    - adgjlsfhk1 2y ago
      Even if that's a few years, that's the progress until we get 1 (useful) qbit. We're then another 3 orders of magnitude from being able to factor a number that can't be factored on a classical computer. I don't think it's impossible, but I do think it's very much in the ~2 decades away stage.
Retr0id 2y ago
"Are there any known cases of a real-life attacker ever using Spectre, Rowhammer, POODLE, etc?" This is a lot like the Y2K problem, in that nothing particularly bad happened because a lot of people spent a lot of time and money on fixing things. That doesn't mean we shouldn't take them seriously.
- hammock 2y ago
  Or TSA airport security
- JohnKemeny 2y ago
  You should include the context: Fancy crypto attack: You have a 0.00001% change of recovering 2 bits of plaintext from a single message Any of the OWASP top ten: You have a 100% chance of recovering the plaintext of all the messages
  - Retr0id 2y ago
    It's highly misleading context. Leaking tiny amounts of information a tiny fraction of the time can be totally disastrous in the context of cryptography. One of my favourite recent examples (2020): "LadderLeak: Breaking ECDSA With Less Than One Bit Of Nonce Leakage" https://eprint.iacr.org/2020/615.pdf https://eprint.iacr.org/2020/615.pdf
    - deleted 2y ago
      [deleted]
    - commandersaki 2y ago
      But I think the issue still stands, we keep hearing about timing attacks, spec-ex attacks, partial nonce reveal, etc. and yes you should carefully design around them, but they're pretty much overhyped and there's easier ways to attack systems. The only timing attack that's been seen in the wild is the MAC bypass in XBox 360. The reality is it is too difficult to launch these attacks and the cryptography is rarely attacked unless there's straightforward flaws. As for the partial nonce, I've seen many attacks on this kind of issue, but I've yet to see this mistake made.
cakealert 2y ago
While it's possible that CRQC (cryptographically relevant quantum computers) are vaporware that will never be made practical, now that were have some PQC algorithms might as well hybridize them. The only downside of the PQC algos is that they don't nicely fit inside packets. So just design newer protocols that don't rely on discrete packets, most of them do that already.
mcint 2y ago
p 11 (/30), makes a terrible case in handwaving. It ignores the requirement that secret data needs to stay secret for 30 years, or 100 years, or long into the future, and attacks only get better. https://www.schneier.com/blog/archives/2009/07/another_new_aes.html https://www.schneier.com/blog/archives/2009/07/another_new_a... > They also describe an attack against 11-round AES-256 that requires 2^70 time—almost practical. >> AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). >> In the case of AES-128, there is no known attack which is faster than the 2^128 complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2^176 and 2^119 time, respectively.
- bawolff 2y ago
  > It ignores the requirement that secret data needs to stay secret for 30 years, or 100 years, or long into the future, and attacks only get better. What data has to stay secret for 100 years? To extrapolate backwards, was there anything in 1925 that would be still sensitive today? Its hard to imagine.
  - ziofill 2y ago
    My genetic data will be relevant even after I'm dead because my children and grandchildren share it with me. And it's a modern kind of data that didn't exist in 1925.
    - pclmulqdq 2y ago
      I hate to tell you, but even if you have never done 23 and me or anything similar, enough of your family has that your genetic data is already very readily accessible to the parties who need it.
    - ein0p 2y ago
      Your genetic data is not secret though. It's rather easy to obtain during your lifetime, even without you knowing.
hatsunearu 2y ago
This is nonsense. - Crypto building blocks are important basic research because it underpins everything. - Good crypto (this exists btw) is impossible to beat, unless QC is available. That's why PQC is being researched. Think about what kind of crypto NSA wants to break, it's not your bank of america passwords. - IDK why this guy thinks we need to shut down Los Alamos to do crypto, does he not think the NSA has datacenters of its own? - The problem with "well, it's not a problem now, why are we preparing for it" is that nation states are storing everything that is going on in the internet, waiting for when QC becomes active. This essentially means you can assume every secret you have will not be secret in 10/20/50 years. Your password is probably fine, but if you sent secret diplomatic cable today, it might be unlocked for your adversaries some years later. These secret nation-state comms are designed to be unlocked after N years normally since keeping them secret forever is expensive; PQC is simply designed to withhold that number N. - The NSA is generally known to be several decades ahead of the academia. They infamously knew and corrected a differential cryptography vulnerability in DES long before differential cryptanalysis was known in the public community. Saying QC isn't growing fast enough doesn't mean much. - The 2008 financial crisis metaphor is the only one that seemed poignant
- boppo1 2y ago
  >Think about what kind of crypto NSA wants to break, it's not your bank of america passwords. I'm not very bright, what kind of encryption does NSA want to break?
  - deleted 2y ago
    [deleted]
  - fragmede 2y ago
    The crypto that China and Russia uses, among others.
purplezooey 2y ago
I appreciated calling out the well-known job role known as: "Fly from one exotic location to another and argue over which post-physics-experiment algorithm is the most cromulent." Every tech company maintains a select cadre of hot-air specialists whose chief responsibility is to keep the catered lunch warm with an endless cycle of self-important discourse. A vital role, truly indispensable.
DebtDeflation 2y ago
>"These are physics experiments, not computers. Claiming that it’s a computer misrepresents what we’re really working with. Every time you see “quantum computer” mentally substitute “physics experiment”, which is what’s actually being discussed." This needs to be a disclaimer on every discussion of "quantum computing."
- sesm 2y ago
  Also, I like how in those experiments they are trying to fight wave function collapse without having any physical model of wave function collapse.
- fxwin 2y ago
  This seems like a rather pedantic distinction unless you go with "Computer = von neumann architecture", in which case the category becomes rather strict (Are FPGAs/analogue computers physics experiments too?). If we assemble a physics experiment to obtain a result that exists at a meaningful level of abstraction from the physical processes themselves (like factoring a prime number using quantum processes, or adding numbers using transistors), it seems appropriate to call this experiment a computer.
  - DebtDeflation 2y ago
    Were the first point-contact transistors that were developed in the 1940s at Bell Labs and that consisted of a piece of gold foil stretched over a plastic wedge which was then cut by hand at the tip and pressed against a block of germanium stacked on a metal base, a computer or an experiment?
    - fxwin 2y ago
      What were they used for?
      - DebtDeflation 2y ago
        Experiments to show that solid-state materials were capable of amplifying or switching one electric voltage/current with another. I'm not disputing that these later became the building blocks for computers, just as the quantum gate experiments being conducted in laboratories today may become the building blocks for quantum computers in the future. But that's not where we are now.
ash-ali 2y ago
the main takeaway is complexity is the enemy of security; we could all agree with this no? ... anyone ever opened the thousands of pages bluetooth standard? this is a really cool presentation to read regardless if people agree with it or not. regarding the QC stuff ... i no idea.
nn3 2y ago
Wish openssh would take that presentation to heart instead of constantly breaking everyones setups with new keys.
AlexCoventry 2y ago
DJB made a brief critique of this argument: https://blog.cr.yp.to/20250118-flight.html#rsa https://blog.cr.yp.to/20250118-flight.html#rsa
int0x29 2y ago
The NSA may not be breaking RSA right now but I'd bet good money they are storing some traffic for later. So the whole factorization isn't worth it argument feels silly.
GTP 2y ago
Is there any recording of this being presented?
mcnichol 2y ago
This is just one big article on survivor bias. I get what they are saying: There is a difference between theoretical and applied. I think the OWASP/NIST/InfoSec has always been a bit behind because of this mentality. I think there is a progressive forward looking mindset that is often seen as "mad" or "unhinged" when it's ultimately throwing paint at a wall to see what sticks. The driver is curiosity but then someone comes along and applies CBA and ROI, and CAC...the person who was curious has left because that wasn't the goal. Eventually something will stick that meets all of those mainstream ideas. If you think of the body as a computer, it communicates through DNA, a much larger scale of information passing. Binary is just arbitrarily selected because it was there. Should we stop exploring binary computational systems? No but we also don't need all our eggs in one basket.

132 points by commandersaki 2y ago

Man, some real "Cynicism is the intellectual cripple's substitute for intelligence" energy here. Seems unnecessary given what I read of Gutmann's history. I get it must be annoying to be someone working in cryptography and always be hearing about QC when there are endless security issues today. It must be tiring to have all these breathless pop-science articles about the quantum future, startups claiming ridiculous timelines to raise money on hype, and business seminars where consultants claim you'll need to be prepared for the quantum revolution changing how business works. I feel the same way. But you shouldn't let that drive you so far in the opposite direction that you're extrapolating fun small quantum factoring experiments from a decade ago to factoring 1024 bit keys in the year 4000. Or say things like 'This makes the highly optimistic assumption that quantum physics experiments scale linearly... the evidence we have, shown by the lack of progress so far, is that this is not the case'. If we get fault tolerant QC of course it scales linearly and it seems embarrassing as a computer scientist to not understand the difference between constant and asymptote. "Actually, quantum computers are so new and untested that they really qualify as physics experiments"... yeah? And? None of this is to say that fault-tolerant highly scalable QC implementing Shor's algorithm is just around the corner, I truly believe it's not. But the world of QC is making really interesting advances running some of the coolest experiments around and I find this superior Hossenfelder-like cynicism in the face of real science making real progress so so tiring.

pclmulqdq 2y ago
One major point of the presentation here is that it's not making real progress. People are still publishing papers, but they have done nothing with an effect outside their little community. It's been in roughly the same state for the last 10 years. For a minimum of 30 years, there have been promises of amazing things coming in the next decade in QC. After how many decades should those predictions lose credibility? There is real opportunity cost to doing this stuff, and real money getting sucked up by these grifters that could be spent on real problems. There are real PhD students getting sucked down this rabbit hole instead of doing something that actually does make progress. There is a real cost to screwing around and making promises of "next decade."
- kirrent 2y ago
  I agree! People who predicted QC soon over the last few decades should lose credibility. They were wrong and they were wrong for no good reason. There is a real opportunity cost to focusing on the wrong thing. There are definitely grifters in the space. Responsible QC researchers should call it out (e.g. Scott Aaronson). But it doesn't necessarily follow that you can dismiss the actual underlying field. Within the last five years alone we've gone from the quantum supremacy experiment to multiple groups using multiple technologies to claim QEC code implementations with improved error rates over the underlying qubits. People don't have to be interested in these results, they are rather niche (a little community as you put it), but you shouldn't be uninterested and then write a presentation titled 'Why Quantum Cryptanalysis is Bollocks'.
  - pclmulqdq 2y ago
    Well, when the little community circles the wagons around the grifters instead of excising them, the rest of us get to ask questions about that community. The cold fusion community did the same thing for several decades, too. And by the way, about 0.01% of the grifters in the QC space are getting called out right now.
- wasabi991011 2y ago
  > One major point of the presentation here is that it's not making real progress. How are you measuring "real progress"? > People are still publishing papers, but they have done nothing with an effect outside their little community. Having an effect outside the research community is essentially a Heaviside function. Before the field is mature enough, there is no effect outside, but once the field is mature enough, there is an effect outside. Makes it hard to judge if there is any progress or not.
  - pclmulqdq 2y ago
    The field has had 40 years of maturing. Experimentation on QC started in the 1980's. At what point are we going to be factoring numbers or (more realistically) simulating chemical interactions? Real progress in this field is very easy to measure. It's based on number of effective qbits of computation. That is just a metric where QC is failing to deliver so badly that everyone in the field wants to deny its existence. Unfortunately, the level of investment in QC is very much outsized compared to the level of progress. These things should rise at the same time. More promising areas of science can get the investment that is otherwise being sucked into QC. > Having an effect outside the research community is essentially a Heaviside function. This is something that people like to say but is never true. Impact on the outside world for new technologies is almost always a sigmoid function, not a heavyside function. You should see some residual beneficial effects at the leading edge if you have something real.
oh_my_goodness 2y ago
It's strange to see so many negative responses that start with vague emotional language. It's almost as if a lot of critics didn't read the presentation. Or maybe they think the rest of us didn't read it.
- fxwin 2y ago
  Is it really that strange when the slides themselves pretty emotionally charged?
  - oh_my_goodness 2y ago
    Good question. Yes it is strange, because the information on the slides is mainly numerical. For example the integers "15" and "21" and the years "2002" and "2012" don't pack much of an emotional charge for me. I suspect they wouldn't for most people.
    - fxwin 2y ago
      You missed the number 15360 on p12, which is mostly what i was referring to.
- kirrent 2y ago
  I read the whole presentation. The physics experiment criticism Guttman makes that I referred to is at page 16/30. Nothing after that engages with QC to the extent that the first half of the presentation did, so I didn't refer to later parts.

nemo 2y ago

This smalls a lot like wishcasting masquerading as critique. I just attended a PQC conference, so I'm biased, but this paper's author makes a lot of very strong claims about the infeasibility of future attacks developing that most experts in the field would disagree with. There is a hope that this is all a fire drill and RSA/EC will survive the next decade unscathed, but there's also plenty of evidence to suggest that incremental improvements in PQ compute will eventually reach their goal. Rather than a big cannon, I see it looking more like AI/LLMs, lots and lots of small incremental improvements by researchers were needed to eventually yield some significant advancements. I pray Post Quantum computing stays in the realm of Cold Fusion, but I'm not about to believe it. Cryptanalysis has already made a few strides on breaking RSA more quickly, and I've heard from noted cryptanalysts the claim there's a significant chance RSA will be further broken in the next decade regardless of PQ. It's a scary take to double down on RSA of all things.

baxtr 2y ago
Out of curiosity: which conference did you attend? I find the field interesting.
- nemo 2y ago
  PKI Consortium: https://pkic.org/events/2025/pqc-conference-austin-us/ https://pkic.org/events/2025/pqc-conference-austin-us/
tptacek 2y ago
Could you relate who those noted cryptanalysts are, that are predicting a significant chance that RSA-2048 is broken classically?
- nemo 2y ago
  I don't recall their name, they were a guest on the Root Causes podcast discussing PQ topics, though your summary varies from what I was trying to express. It's not that RSA will be classically broken, but that novel attacks to reduce factoring times of RSA key like batch attacks have a statistically significant chance of being discovered, that "further" was not meant to imply "completely broken classically," but "weakened further using classical approaches". Sounded plausible to me, though that's not a thing I'm any kind of domain expert in.

tptacek 2y ago

Love me some Peter Gutmann. This is classic Gutmann. A lot of this presentation is mooted by understanding PQC as an scientific question rather than an engineering one. What are the precise natures of quantum-superior attacks on cryptosystems and what are key establishments and signatures that resist those attacks? Whatever else you think of quantum cryptanalysis those are undeniably important theoretical questions. A few more slides are mooted by the likelihood that any mainstream deployed PQC system is going to be hybridized with a classical cryptosystem. As an articulation of a threat model for modern computing, it simultaneously makes some sense and proves too much: if you think OWASP-type vulnerabilities are where everyone's head should be at (and I sort of agree), then all of cryptography is a sideshow. I'm a connoisseur of cryptographic vulnerabilities that break real systems the way SQL injection does (a bitflipping attack on an encrypted cookie, a broken load-bearing signature scheme) but even I have to admit there's 1 of those for every 10,000 conventional non-cryptographic attack. But of course, it also depends on who your adversary is. Ironically, if you're worried about state-level SIGINT, the barrier for OWASP-style attacks may be higher than that of large-scale codebreaking; passive interception and store-now-decrypt-later is the SIGINT love language. My biggest thing with all of this is a core belief about organizations like NSA: that they exist primarily to secure budget for NSA. Given that, the one thing you absolutely don't want to do is have a system that is breakable only at almost-implausible cost. (Also, his RSA-1024 analysis is off; it's missing batch attacks).

pclmulqdq 2y ago
Yeah, I don't think anyone told him about WindsorGreen, the RSA-cracking supercomputer that IBM built for the NSA. RSA-1024 probably should be assumed unsafe at this point.
dadrian 2y ago
I'm with you, but the government (at least in the US and UK) should definitely be spending more time figuring out how to patch reliably, and little less on PQC.
- thadt 2y ago
  Perhaps the other side of the coin Peter calls "churn" is "updated software". Government, like every other old organization, has a ton of legacy systems. Even if CRQC is a pipe dream, having an excuse to tell everyone across the board they need to update their stuff sometime in the next decade might be a net win.

mik1998 2y ago

I think it is worthwhile to explore cryptography that is not based on the discrete logarithm problem. Currently, we're keeping all eggs in one conjectured basket. Even if quantum computing will never be viable, there is a non-zero chance that the discrete logarithm problem will be solved in some other way.

layer8 2y ago
There is a non-zero chance of pretty much anything. I don't think Gutmann is opposed to exploration.
- bawolff 2y ago
  I think the parent's point is that if there is a non-zero chance of anything then it is good to have a backup plan
  - layer8 2y ago
    There is a non-zero chance of a black hole forming in the LHC and swallowing the Earth, yet we don’t have a backup plan for that. There are an infinite more examples like that. A non-zero chance is not an argument for anything, unless you have a good basis on actually quantifying it.
als0 2y ago
What are you talking about? PQC is based on learning-with-errors and lattice problems https://en.wikipedia.org/wiki/Learning_with_errors https://en.wikipedia.org/wiki/Learning_with_errors

hujun 2y ago

one thing I agree that software/standard people like to churn, churn is a source of new income regardless if QC could break RSA or not in the future, people could make profit now

Strilanc 2y ago

Using the largest number factored as a benchmark for progress in quantum computing is like evaluating floor(f(0)) = 0 and floor(f(1)) = 0 and concluding f(x) = 0. You can't distinguish f(x) = 0 from f(x) = x/2 from f(x) = e^x/3 when your test is too coarse. If you want to see the progress in quantum computing today, pay attention to component reliability. For example, in 2014, the best rep code run on a quantum computer had a 1% error rate per round [1]. In 2024, it was 0.00000001% and it had become possible to run full quantum codes with a 0.2% error rate per round [2]. If it takes another decade for that 0.2% to go down by a factor of a thousand, then you've got lots of time. Maybe you'll be dead before progress exceeds the coarseness of factoring. If it takes a year instead of decade (because the cost of error correction is frontloaded) then, well, pay appropriate attention to that. [1]: https://arxiv.org/abs/1411.7403 https://arxiv.org/abs/1411.7403 [2]: https://arxiv.org/abs/2408.13687 https://arxiv.org/abs/2408.13687

upofadown 2y ago
I think the author was just poking fun at the idea that the 15 and 21 factoring results can be used to indicate some sort of progress. I think the graph makes that obvious. Last I heard we were 1-2 orders of magnitude away from a physical qubit error rate low enough for error correction to have a chance of creating a threat against cryptography. So things sound pretty unlikely at the moment. We need a fundamental breakthrough.
- dullcrisp 2y ago
  Is 1–2 orders of magnitude a lot or a little here? With exponential progress that could be a few years; with stalled progress that’s maybe never.
  - adgjlsfhk1 2y ago
    Even if that's a few years, that's the progress until we get 1 (useful) qbit. We're then another 3 orders of magnitude from being able to factor a number that can't be factored on a classical computer. I don't think it's impossible, but I do think it's very much in the ~2 decades away stage.

Retr0id 2y ago

"Are there any known cases of a real-life attacker ever using Spectre, Rowhammer, POODLE, etc?" This is a lot like the Y2K problem, in that nothing particularly bad happened because a lot of people spent a lot of time and money on fixing things. That doesn't mean we shouldn't take them seriously.

hammock 2y ago
Or TSA airport security
JohnKemeny 2y ago
You should include the context: Fancy crypto attack: You have a 0.00001% change of recovering 2 bits of plaintext from a single message Any of the OWASP top ten: You have a 100% chance of recovering the plaintext of all the messages
- Retr0id 2y ago
  It's highly misleading context. Leaking tiny amounts of information a tiny fraction of the time can be totally disastrous in the context of cryptography. One of my favourite recent examples (2020): "LadderLeak: Breaking ECDSA With Less Than One Bit Of Nonce Leakage" https://eprint.iacr.org/2020/615.pdf https://eprint.iacr.org/2020/615.pdf
  - deleted 2y ago
    [deleted]
  - commandersaki 2y ago
    But I think the issue still stands, we keep hearing about timing attacks, spec-ex attacks, partial nonce reveal, etc. and yes you should carefully design around them, but they're pretty much overhyped and there's easier ways to attack systems. The only timing attack that's been seen in the wild is the MAC bypass in XBox 360. The reality is it is too difficult to launch these attacks and the cryptography is rarely attacked unless there's straightforward flaws. As for the partial nonce, I've seen many attacks on this kind of issue, but I've yet to see this mistake made.

cakealert 2y ago

While it's possible that CRQC (cryptographically relevant quantum computers) are vaporware that will never be made practical, now that were have some PQC algorithms might as well hybridize them. The only downside of the PQC algos is that they don't nicely fit inside packets. So just design newer protocols that don't rely on discrete packets, most of them do that already.

mcint 2y ago

p 11 (/30), makes a terrible case in handwaving. It ignores the requirement that secret data needs to stay secret for 30 years, or 100 years, or long into the future, and attacks only get better. https://www.schneier.com/blog/archives/2009/07/another_new_aes.html https://www.schneier.com/blog/archives/2009/07/another_new_a... > They also describe an attack against 11-round AES-256 that requires 2^70 time—almost practical. >> AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). >> In the case of AES-128, there is no known attack which is faster than the 2^128 complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2^176 and 2^119 time, respectively.

bawolff 2y ago
> It ignores the requirement that secret data needs to stay secret for 30 years, or 100 years, or long into the future, and attacks only get better. What data has to stay secret for 100 years? To extrapolate backwards, was there anything in 1925 that would be still sensitive today? Its hard to imagine.
- ziofill 2y ago
  My genetic data will be relevant even after I'm dead because my children and grandchildren share it with me. And it's a modern kind of data that didn't exist in 1925.
  - pclmulqdq 2y ago
    I hate to tell you, but even if you have never done 23 and me or anything similar, enough of your family has that your genetic data is already very readily accessible to the parties who need it.
  - ein0p 2y ago
    Your genetic data is not secret though. It's rather easy to obtain during your lifetime, even without you knowing.

hatsunearu 2y ago

This is nonsense. - Crypto building blocks are important basic research because it underpins everything. - Good crypto (this exists btw) is impossible to beat, unless QC is available. That's why PQC is being researched. Think about what kind of crypto NSA wants to break, it's not your bank of america passwords. - IDK why this guy thinks we need to shut down Los Alamos to do crypto, does he not think the NSA has datacenters of its own? - The problem with "well, it's not a problem now, why are we preparing for it" is that nation states are storing everything that is going on in the internet, waiting for when QC becomes active. This essentially means you can assume every secret you have will not be secret in 10/20/50 years. Your password is probably fine, but if you sent secret diplomatic cable today, it might be unlocked for your adversaries some years later. These secret nation-state comms are designed to be unlocked after N years normally since keeping them secret forever is expensive; PQC is simply designed to withhold that number N. - The NSA is generally known to be several decades ahead of the academia. They infamously knew and corrected a differential cryptography vulnerability in DES long before differential cryptanalysis was known in the public community. Saying QC isn't growing fast enough doesn't mean much. - The 2008 financial crisis metaphor is the only one that seemed poignant

boppo1 2y ago
>Think about what kind of crypto NSA wants to break, it's not your bank of america passwords. I'm not very bright, what kind of encryption does NSA want to break?
- deleted 2y ago
  [deleted]
- fragmede 2y ago
  The crypto that China and Russia uses, among others.

purplezooey 2y ago

I appreciated calling out the well-known job role known as: "Fly from one exotic location to another and argue over which post-physics-experiment algorithm is the most cromulent." Every tech company maintains a select cadre of hot-air specialists whose chief responsibility is to keep the catered lunch warm with an endless cycle of self-important discourse. A vital role, truly indispensable.

DebtDeflation 2y ago

>"These are physics experiments, not computers. Claiming that it’s a computer misrepresents what we’re really working with. Every time you see “quantum computer” mentally substitute “physics experiment”, which is what’s actually being discussed." This needs to be a disclaimer on every discussion of "quantum computing."

sesm 2y ago
Also, I like how in those experiments they are trying to fight wave function collapse without having any physical model of wave function collapse.
fxwin 2y ago
This seems like a rather pedantic distinction unless you go with "Computer = von neumann architecture", in which case the category becomes rather strict (Are FPGAs/analogue computers physics experiments too?). If we assemble a physics experiment to obtain a result that exists at a meaningful level of abstraction from the physical processes themselves (like factoring a prime number using quantum processes, or adding numbers using transistors), it seems appropriate to call this experiment a computer.
- DebtDeflation 2y ago
  Were the first point-contact transistors that were developed in the 1940s at Bell Labs and that consisted of a piece of gold foil stretched over a plastic wedge which was then cut by hand at the tip and pressed against a block of germanium stacked on a metal base, a computer or an experiment?
  - fxwin 2y ago
    What were they used for?
    - DebtDeflation 2y ago
      Experiments to show that solid-state materials were capable of amplifying or switching one electric voltage/current with another. I'm not disputing that these later became the building blocks for computers, just as the quantum gate experiments being conducted in laboratories today may become the building blocks for quantum computers in the future. But that's not where we are now.

ash-ali 2y ago

the main takeaway is complexity is the enemy of security; we could all agree with this no? ... anyone ever opened the thousands of pages bluetooth standard? this is a really cool presentation to read regardless if people agree with it or not. regarding the QC stuff ... i no idea.

nn3 2y ago

Wish openssh would take that presentation to heart instead of constantly breaking everyones setups with new keys.

AlexCoventry 2y ago

DJB made a brief critique of this argument: https://blog.cr.yp.to/20250118-flight.html#rsa https://blog.cr.yp.to/20250118-flight.html#rsa

int0x29 2y ago

The NSA may not be breaking RSA right now but I'd bet good money they are storing some traffic for later. So the whole factorization isn't worth it argument feels silly.

GTP 2y ago

Is there any recording of this being presented?

mcnichol 2y ago

This is just one big article on survivor bias. I get what they are saying: There is a difference between theoretical and applied. I think the OWASP/NIST/InfoSec has always been a bit behind because of this mentality. I think there is a progressive forward looking mindset that is often seen as "mad" or "unhinged" when it's ultimately throwing paint at a wall to see what sticks. The driver is curiosity but then someone comes along and applies CBA and ROI, and CAC...the person who was curious has left because that wasn't the goal. Eventually something will stick that meets all of those mainstream ideas. If you think of the body as a computer, it communicates through DNA, a much larger scale of information passing. Binary is just arbitrarily selected because it was there. Should we stop exploring binary computational systems? No but we also don't need all our eggs in one basket.