5 ms·

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 Vin

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.

firesteelrain 4mo ago
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
tialaramex 4mo ago
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]
- mswphd 4mo ago
  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 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.
  - spacebacon 4mo ago
    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.
  - deleted 4mo ago
    [deleted]
- zetsurin 4mo ago
  [Vinge](https://en.wikipedia.org/wiki/Vernor_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.
  - skmurphy 4mo ago
    From Chapter 8, available online at https://deepness.trmm.net/c08b/ 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 --"
nmadden 4mo ago
> 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…
- pbohun 4mo ago
  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.
tardedmeme 4mo ago
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.
bigfatkitten 4mo ago
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 https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf
- mswphd 4mo ago
  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.
  - ifwinterco 4mo ago
    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
    - mswphd 4mo ago
      these have always been an issue, and were the motivation for starting the NIST standardization in ~2016. My point is more that recent developments in quantum computing have caused many cryptographers to go from "we should do this so people are secure if progress happens in the decades from now" to "this may be a near-term issue, and we should prioritize transition for user safety issues". You can read some about this in a cloudflare article from 2 months ago, which mentions some recent developments that have people concerned about possible "Q-day" being in ~2029-2030". This is much earlier than what was the consensus 5 years ago. https://blog.cloudflare.com/post-quantum-roadmap/ https://blog.cloudflare.com/post-quantum-roadmap/ Part of this is because of a 3rd reason to transition early, which is the "long tail" of deployments which will switch over (potentially very) slowly. Think embedded/iot devices that are either difficult to patch, or have vendors who are not as security-focused.
m463 4mo ago
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.
- tptacek 4mo ago
  One time pads are absurdly easy to implement. They're just impossible to use. What would be the benefit of ssh-otp?
- cwillu 4mo ago
  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.
- mswphd 4mo ago
  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.
dundercoder 4mo ago
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.
crote 4mo ago
> 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.
- fluoridation 4mo ago
  I don't know about signatures, but wouldn't a hybrid encryption scheme just involve nesting? Why would that have weaknesses from the hybridization?
  - mswphd 4mo ago
    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.
- mswphd 4mo ago
  > 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 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).
pseudohadamard 4mo 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. Almost. Quantum is neither a remote risk nor a near-term possibility. Woof, woof, woof! https://eprint.iacr.org/2025/1237 https://eprint.iacr.org/2025/1237
misterinfo 4mo ago
All your Bitcoin are belong to Us?
- qingcharles 4mo ago
  all my apes gone

firesteelrain 4mo ago

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

tialaramex 4mo ago

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]

mswphd 4mo ago
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 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.
- spacebacon 4mo ago
  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.
- deleted 4mo ago
  [deleted]
zetsurin 4mo ago
[Vinge](https://en.wikipedia.org/wiki/Vernor_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.
- skmurphy 4mo ago
  From Chapter 8, available online at https://deepness.trmm.net/c08b/ 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 --"

nmadden 4mo ago

> 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…

pbohun 4mo ago
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.

tardedmeme 4mo ago

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.

bigfatkitten 4mo ago

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 https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf

mswphd 4mo ago
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.
- ifwinterco 4mo ago
  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
  - mswphd 4mo ago
    these have always been an issue, and were the motivation for starting the NIST standardization in ~2016. My point is more that recent developments in quantum computing have caused many cryptographers to go from "we should do this so people are secure if progress happens in the decades from now" to "this may be a near-term issue, and we should prioritize transition for user safety issues". You can read some about this in a cloudflare article from 2 months ago, which mentions some recent developments that have people concerned about possible "Q-day" being in ~2029-2030". This is much earlier than what was the consensus 5 years ago. https://blog.cloudflare.com/post-quantum-roadmap/ https://blog.cloudflare.com/post-quantum-roadmap/ Part of this is because of a 3rd reason to transition early, which is the "long tail" of deployments which will switch over (potentially very) slowly. Think embedded/iot devices that are either difficult to patch, or have vendors who are not as security-focused.

m463 4mo ago

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.

tptacek 4mo ago
One time pads are absurdly easy to implement. They're just impossible to use. What would be the benefit of ssh-otp?
cwillu 4mo ago
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.
mswphd 4mo ago
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.

dundercoder 4mo ago

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.

crote 4mo ago

> 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.

fluoridation 4mo ago
I don't know about signatures, but wouldn't a hybrid encryption scheme just involve nesting? Why would that have weaknesses from the hybridization?
- mswphd 4mo ago
  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.
mswphd 4mo ago
> 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 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).

pseudohadamard 4mo 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. Almost. Quantum is neither a remote risk nor a near-term possibility. Woof, woof, woof! https://eprint.iacr.org/2025/1237 https://eprint.iacr.org/2025/1237

misterinfo 4mo ago

All your Bitcoin are belong to Us?

qingcharles 4mo ago
all my apes gone