Comment by skmurphy
1 day ago
We are truly living in a science fiction future where quantum code cracking is not a remote possibility but a near term risk we are planning for.
In Vernor Vinge's novel "A Fire Upon the Deep" one of the most valuable commodities were one time pads that are physically transported to communication nodes to enable unbreakable communication. The pads are split into three pieces that are XORed to create the actual pad to reduce risk of compromise.
But that's a miss, it's like one of those Neal Stephenson moments where the creator is using the right language (so it's not like reading William Gibson who clearly has no idea and knows it - he's going for the emotional feel not the technology) but they don't understand what's actually going on.
OTP is in theory the correct choice if you don't have working symmetric cryptography but in fact the "Quantum computer" approach barely dents our symmetric cryptography.
I've written about this before, DES was standardized in 1977, almost 50 years ago and you might think "Well but DES is broken". Yes, DES broke exactly the way it was designed to. Literally nothing went wrong, when it was standardized we knew the keys are too small (yup, you can break it by trying all the keys) and the blocks are too small (yup, you can "just" make duplicate blocks) and it was broken by leaning on these weaknesses with huge fast modern computers.
AES is an entirely different cryptosystem, but the two most important choices were that the keys are big enough (128-bit or 256-bit commonly) and the blocks are too (128 bits). And those may seem like a small upgrade, only 2-4x as big, who cares? Well those are bit lengths so that's an exponential increase, and your quantum computer barely helps (assuming it magically is the same price rather than incredibly expensive). It is not physically practical for the necessary computation to be done, AES is broken only if there's some mathematical backdoor we didn't know about.
"We'll crack AES with a quantum computer" is a Hollywood movie plot, it's not a thing that makes any actual sense.
[Edited: I wrote "Bruce Sterling" but I meant "William Gibson", I apologise to both people for muddling them, though not for my opinion]
> But that's a miss, it's like one of those Neal Stephenson moments where the creator is using the right language (so it's not like reading William Gibson who clearly has no idea and knows it - he's going for the emotional feel not the technology) but they don't understand what's actually going on.
That feels a bit harsh when reading a book written in 1992. Shor's algorithm was only invented in 1994. There was no indication about our quantum future at the time that novel was written
A Fire upon the deep is set in the far future. Its easy to imagine all non information-theoretic secure cryptosystems failing thousands of years from now. I think that prediction is more reasonable than most far-future scifi predictions.
If i remember right, i think that is the novel that predicts we'd still be using usenet when talking between planets (i read a long time ago), so i think the crypto prediction aged a lot better than that.
The communication is clearly inflected by Usenet conventions, but I think that's as forgiveable as the choice to have Banks' Culture starships named using our cultural references like "Just read the Instructions" or "Don't Try This At Home". I don't think we're told it actually is Usenet -- it's just that necessarily light speed comms is very slow compared to the pace of life at this scale so it will feel much like Usenet. So I actually thought this made lots of sense.
It's true that we have no apriori justification for the existence of symmetric cryptography and so in principle somebody might have a constructive proof that you can't do this at all and we're boned. There was no evidence for this when the book was written and there's no evidence for it now, but it's nowhere close to as crazy as the Zones of Thought physics so, sure.
1 reply →
[Vinge](https://en.wikipedia.org/wiki/Vernor_Vinge) was a professor of mathematics and computer science. I'd expect him to get things right. Funny enough I don't remember that bit at all from fire upon the deep.
From Chapter 8, available online at https://deepness.trmm.net/c08b/
"Our main cargo is a one-time cryptographic pad. The source is Commercial Security at Sjandra Kei; the destination is the certificants' High colony. It was the usual arrangement: We're carrying a one-third xor of the pad. Independent shippers are carrying the others. At the destination, the three parts would be xor'd together. The result could supply a dozen worlds' crypto needs on the Net for --"
7 replies →
it's worth noting that the zones of thought universe literally had different physics; things like superintelligence and ftl travel were physically impossible closer to the galactic centre but commonplace further out. so the notion of "not physically practical" doesn't apply here.
The "Zones of Thought" is a fun premise for a story but I'm not sure it actually holds up. It is at least an excuse (unlike in say Iain M Banks which just has Star-Trek style "la la la I can't hear you" FTL travel that's basically magic) but I think the abandoned Eschaton series by Stross had a better excuse and even then Stross accidentally blew it up.
Maybe since our universe doesn't have FTL any author trying to make this work will almost inevitably screw it up? Like how the only novel I've read with the "Protagonist is much, much smarter than everybody else" that works does it by cheating - it's "Tatja Grimm's World" and [spoiler] Tatja isn't actually smarter than us everybody else on her world is stupid by our standards for reasons the plot justifies eventually.
Greg Egan, like some of the newer Stross novels, mostly says no FTL, you can go a long way but it takes a long time, for everybody else if not for you - suck it up. Which isn't a bad excuse, but also isn't FTL at all.
4 replies →
It's worth noting that the above assumes that grover's is optimal for symmetric crypto. There are not that many quantum attacks against symmetric crypto that are better than grover's, so in some sense this is justified. But there are some attacks for particular constructions
https://arxiv.org/pdf/2110.02836
So there is a risk that there are even more improved attacks that people aren't looking for due to the conventional wisdom that grover's is the best you can do for symmetric crypto. Hopefully this risk doesn't end up materializing.
I agree.. Consider Math symbols and physical constants themselves are signs in a humans (or machines) interpretive system. They aren’t the actual thing, and treating them as precise blinds us to alternative interpretations. Conventional wisdom about Grover’s algorithm might be blinding cryptographers. I highly recommend semiotics as a lens peaking through this veil.
In the High Beyond and the Lower Transcend, Horatio, there are more quantum algorithms than dreamt of in your philosophies.
I have come to the conclusion that it doesn't matter. What matters is that people believe quantum computers will break encryption. And pulling that lever on their seeded fears, via subterfuge, backdoors, surveillance, and maybe a _little math, is too valuable for it not to be pulled.
But how do you do the key exchange?
Concern about that makes lots more sense. If your trusted couriers are moving some bits as part of a ratchet mechanism or something I'm onboard. But the volumes involved then are tiny, whereas the story beat is about a large volume of data.
It's the difference between stealing Bearer Bonds which you can notionally insist are arbitrarily valuable despite the modest amount in Die Hard†, and stealing literal Gold Bars in Die Hard with a Vengeance which is silly because we know how valuable each bar is and they're much too heavy for the heist to actually work as depicted.
† Die Hard is set after bearer bonds don't make sense for non-crooks and thus didn't exist for crooks to steal because their tax treatment changed, however the novel Die Hard is based on was set before these tax changes so it did make sense when it was written.
> a near term risk we are planning for
I'd argue it's closer to a cheap insurance, just in case.
Take the encryption of a TLS connection itself, for example: you want to protect against a possible "store now, decrypt later" attack on your connection, 60 years from now, by an attacker with an NSA-level budget. Even if you judge the probability of it happening as "exceedingly unlikely", migrating to a hybrid scheme is a no-loss scenario, so it would be silly not to. In a way it's almost a Pascal's Wager.
And then there's of course the NSA itself, who are heavily pushing for post-quantum-only schemes and trying to suppress the hybrid schemes as they almost certainly have weaknesses for some of those new PQ schemes already lying around.
> as they almost certainly have weaknesses for some of those new PQ schemes already lying around
why believe this about PQ schemes vs about pre-existing schemes? Or any other schemes?
It's also worth mentioning that it appears that other countries (in particular China) will adopt fundamentally similar schemes. The NSA loves vulnerabilities, but generally only vulnerabilities of a certain type. These are generally referred to as "NOBUS"
https://en.wikipedia.org/wiki/NOBUS
It includes things like backdoors (say DUAL_EC_DRBG), as well as historically things like reducing the key size of DES, where the US thought they'd be able to brute force it (but other countries would lack the compute). Historically the NSA has actually assisted in removing non-NOBUS vulnerabilities (at least they did this with the SBOX design of DES, which was vulnerable to differential/linear cryptanalysis --- I forget which).
The NSA hasn't publicly assisted/disclosed any vulnerabilities with currently suggested schemes, though a close US ally (Isreal, through an IDF group known by Matzov) has. If America was hoarding vulnerabilities, one might imagine America would have pressured Isreal to keep this secret.
A final point is that it's not clear where the NSA would source the vulnerabilities. By a peculiar chain of coincidences, nearly all of the most successful lattice cryptanalysts are European. None have "gone dark" in a way that would be concerning (say how Don Coppersmith did, when he moved to a NSA affiliate in the mid 2000s). This isn't to say that it would be impossible for the NSA to have better-than-public vulnerabilities, but more to say that they can't just take some of the most successful people who have publicly attacked the problem, and throw more money at them. Their "talent-pipeline" for this particular problem is not as available (and many cryptographers soured on working with them post-Snowden anyway).
> If America was hoarding vulnerabilities, one might imagine America would have pressured Isreal to keep this secret.
just say no
I don't know about signatures, but wouldn't a hybrid encryption scheme just involve nesting? Why would that have weaknesses from the hybridization?
First, it doesn't, because we don't use public-key encryption. Instead, we use key-encapsulation mechanisms, which you have to hybridize in another way.
Second, hybridization can add weaknesses in several ways
1. Hybridization may preserve some, but not all, security properties of the constituent parts. This is the case for hybrid signatures. In particular, ML-DSA signatures have a better than SUF-CMA type of security typically called "BUFF" security. Known hybridization techniques lose this security.
2. Hybridization is also more code (and more complex code) to write. Historically, the vast majority of cryptographic issues come from implementation issues, not fundamental weaknesses in the underlying hard problems. So suggesting to obtain security by doing more complex things may not always achieve the desired goal.
This is the second time in my life I’ve heard of this book. It was a wickedly weird book. I think I was 1/3rd through it before I figured out the plurality of the characters.
If we take near term to mean “while any of the participants in this thread are still alive”, I think we’re going to be safe for a while.
https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf
it's worth mentioning opinions have started to shift away from this. Quantum computing has made quite concrete progress in the last ~2 years. No guarantee this continues, but among people I know it has changed their perspectives from (roughly) similar things as that essay, to thinking we really must transition now.
It’s also because harvest now decrypt later is the main concern.
This means even if you think viable quantum computers are 20 years away, in contexts where HNDL is an issue that means really you should be thinking about this now.
In contexts where that isn’t an issue you can debate whether we have 5 years, 10 years, 20 years or 50 years but in the case of the SSL key exchange we need to think about it now regardless
1 reply →
That was very unconvincing.
Like if you want to go from history - yes the make a giant artillery piece thing didn't work.
You know what did work? A surprising application of quantum physics known as nuclear bombs.
I'm not neccesarily saying quantum computers will work out the same way, but if you follow the logic of the presentation, nuclear bombs fit it so much better than the example they use. It was a step-change. People went from saying it was theoretically interesting without practical application to actually having a bomb very quickly. Basically replace everything in that presentation using nukes as the running example and suddenly the argument sounds really stupid.
I've always thought creating an ssh-otp should be easy to implement.
(meaning xor the packets themselves with a huge bundle of random data duplicated at each side, and never re-used)
But I think it would probably still qualify as a munition and have export restrictions.
One time pads are absurdly easy to implement. They're just impossible to use. What would be the benefit of ssh-otp?
note that OTP is only "perfectly secure" for a rather limited notion of security, namely IND-CPA. This is (roughly) an "honest but curious" adversary who looks at data on the wire (or wherever), but never tampers with it.
This is not a particularly realistic attack model. People typically instead want security against an "active" adversary who does whatever they can (say IND-CCA2 security). You can achieve this information-theoretically, given enough pre-shared randomness, by (roughly) taking some standard Authenticated Encryption with Associated Data (AEAD) construction, and swapping out whatever primitives that are used with information-theoretically secure components. A OTP for the block cipher and a Wegmen-Carter MAC for the MAC should work.
Note that this gives you a scheme with roughly the same practical security as standard ones (unless you think someone can break AES), but it still can be subject to non-trivial attacks that AES cannot. In particular
1. randomness used on both sides MUST never be repeated, and MUST stay in sync throughout, so
2. both sides MUSt stay in sync as to where 1. they are in terms of the randomness they're using, and where 2. the other half of the communication is. Realistically these should be two completely different randomness streams to guard against race conditions where otherwise each side may accidentally reuse a block of randomness
3. having to stay in sync adds several difficulties. In particular, network issues become much more annoying to deal with. This is true for e.g. environmental network disruptions, but also (plausibly) an adversary can disrupt the network temporarily. If this causes you to lose synchronization, then best case this temporary network disruption becomes a permanent network disruption. Worst case it manages to get randomness re-used on one side, which then breaks everything.
The above is likely not an exhaustive list of the problems you have to deal with. But still, you can see how it quickly becomes unclear if things are easy to implement.
Most of the ways of making the “duplicated at each end” thing practical are just figuring out where to hide the stream cipher. Like, if you just use /dev/*random to generate the random bitstream, what you have is a convoluted output-feedback-mode cipher with a key of whatever was fed into the os's prng, not a one-time-pad.
In terms of actually doing it, it's still very remote, but not as remote as it would have to be for us to completely ignore it. And the NSA has massive data centers full of hard drives storing our encrypted internet traffic.
> We are truly living in a science fiction future where quantum code cracking is not a remote possibility but a near term risk we are planning for.
Almost. Quantum is neither a remote risk nor a near-term possibility. Woof, woof, woof! https://eprint.iacr.org/2025/1237
That sounds a lot like Shamir Secret Sharing Algorithm similar to unsealing / sealing HashiCorp Vault.
I did read the books 20 years ago and forgot this aspect of the story
> The pads are split into three pieces that are XORed to create the actual pad to reduce risk of compromise.
Thus creating a two-time pad, which is completely insecure…
No, the idea is that the actual key is the XOR of 3 completely independent keys. I think you were thinking of XORing a key with itself 3 times, which would just return the original key.
In the book, there is a cargo ship carrying 1/3 of a OTP. Other two other ships from two other companies are carrying the other thirds. This actually is a fairly decent method of transporting a OTP (I'm assuming there's some kind of physical security preventing tampering).
The book even talks later on about how only using the pad isn't enough, since it provides no proof of authorship or tampering. Vinge did a pretty good job w/compsci in the book.