Don’t Sweat Quantum Crypto


This is another example of credulous/bad reporting about my field. Whenever I see the press utterly fail to “get” something to do with computer security, I assume they’re equally lazy and wrong about every other field that requires more understanding than “who made Kim Kardashian’s shoes?” (because they are labelled)

BBC leads: [bbc]

As malicious hackers mount ever more sophisticated attacks, China is about to launch a new, “unhackable” communications network – at least in the sense that any attack on it would be quickly detected.

That’s not “unhackable.” That’s “can’t be hacked without being detected” and there’s a great big difference.

The pioneering project is also part of a bigger story: China is taking the lead in a technology in which the West has long been hesitant to invest.

Oh, it’s part of a bigger story: we should be scared of the Chinese.

China’s push in quantum communication means the country is taking huge strides developing applications that might make the increasingly vulnerable internet more secure. Applications that other countries soon might find themselves buying from China.

I hear the sounds of some DoD research department trying to get funding to spend on quantum encryption.

There’s nothing wrong with doing research, and I hate the fact that research is almost entirely military or commercial, nowadays. Under the pressure to commercialize everything, no matter how far out it is, has to be justified with bullshit like “other countries might soon find themselves buying from China.” Funding research in theoretical physics (but, please, no more city-devouring explosions) and quantum effects is great, but it’s sad that researchers have to spin stuff this way. And it’s sad that journalists don’t know they’re being spun.

Quantum key exchange [source] (note that the article linked to is about how such a method was broken recently)

So, what’s the value of quantum encryption? It could be valuable, someday, for massive code-breaking. Carl Ellison explained it to me once, but the details flew way over my head – the idea is, basically, that we could build a quantum computer in which it was in all the states of decrypting a message, at once, and which would collapse its wave-function conveniently down to the one state where the key was the correct one. A quantum decryptor would be badass. What about a quantum encryptor? The idea is to use entanglement to transmit a message-key in such a way that anyone attempting to interfere with the transmission would announce their involvement – in other words, you give the message key to Schrodinger’s cat, who is then shipped off to the person you’re communicating with. If the cat arrives and is already either dead or alive then we know that someone else observed the cat, collapsed its wave function, and must have tried to look at the key. If the cat’s alive/dead state is still uncertain when it arrives, then we know nobody collapsed its state, and the cat was un-tampered with: we then observe the cat and it lives or dies and we can start using the message key. That’s playing a bit fast and loose with the physics but that’s close enough.

Robert Morris Sr. Former NSA Chief Scientist

Robert Morris Sr. Former NSA Chief Scientist (mjr photo, circa 1994)

The problem with all this fol-de-rol is that the end-points are going to be doing all their computing running on a PC with an Intel processor, most likely on a stock motherboard using an off-the-shelf operating system. As Robert Morris, Sr., the former NSA Chief Scientist once commented: “using high quality encryption in modern computing is like using an armored truck to take a message to a paper bag taped under a park bench.” We’ve already seen ample evidence that the NSA has techniques for embedding malware in motherboard BIOS, and there are some really scary ‘accidental’ backdoors in Intel’s remote-management protocol – anyone with the correct key (which happens to be NULL) can remotely access the memory, processor, bus, and power below the level of awareness of the operating system. [ars] So let’s imagine that our system uses fancy quantum encryption to exchange a key safely, and someone just scrapes that key out of system memory after it’s been exchanged. Now the “link-state: secure” light is on, but the key has left the building.

Back to BBC’s explanation:

Quantum communication works differently:

  • If you want to send your secure message, you first separately send a key embedded in particles of light

  • Only then do you send your encrypted message and the receiver will be able to read it with the help of the key sent beforehand

All this stuff drives me nuts because one of the hidden presuppositions of most of these systems is that there’s some kind of out of band mechanism for authenticating who you are talking to. In other words, before you start swapping messages with the other person on the other side of your perfectly secure Schrodinger-pipeline, you need to know that they’re them. How do you do that? There are two ways:

  1. You call them on the telephone.
  2. You pre-exchange some sort of credential.

If you’ve used Signal or some of the other secure communications apps, you’ll know how the first one works: it sets up an exchanged key and then you call your friend, recognize their voice (assuming it’s not a professional mimic the FBI hired!) and tell them a fragment of some information that depends on the key – usually four or five digits of a checksum of the key. The authentication is you recognizing their voice. The second one works where you give them a key, and you have a copy of the key, and you use the pre-exchanged key to authenticate all of the temporary keys. Since the temporary keys are (presumably) random, you can encrypt them with the pre-exchanged key and announce 5 digits of that to authenticate the temporary session key.

This is an endpoint; it has keying data and a computer in it.

But since you’ve already exchanged a key (or are talking to your friend) (or, per BBC “exchange a key embedded in particles of light”) why not just exchange a great big wad of random data (aka, a “one time pad”) on a hard drive and be done with it? If I’m going to set up a quantum encryption system that’s secure against someone jacking the endpoint, that means I’m giving them the endpoint. If I’m giving them the endpoint, I may as well just give them an endpoint that has an 8tb hard drive of random data that’s an exact copy of my 8tb of random data and we can XOR blissful messages back and forth for a very long time. Doing that also solves the authentication problem: I handed them the endpoint; we’re good, we’re done.

[source] (this is a pretty cool article if you’re interested in one time pads)

Like I said, I love fundamental research and I’m a big fan, but please, journalists, if you’re going to talk about how scary a threat some new thingie is, it’s got to be significantly better than something that was invented in 1888.

------ divider ------

Carl Ellison and the decryption machine: if I recall correctly, Carl said that one of the neat features of the “bombe” decryption machines used to attack German codes in WWII is that they exploited symmetries in how the rotor-wiring was done so that it would check multiple rotor-positions at a time, since all it was doing was looking for electricity to flow through a circuit, any circuit would do. I’m tempted to track Carl down and annoy him by asking him to re-explain it to me, but I know it won’t take any better than it did the last time.

If you used 8tb hard drives to hold your data, and used them to exchange message keys, instead of using them for ciphertext, it would be weaker – the strength of that system would be equal to the strength of the bulk encryption algorithm that you used – but you could encrypt a lot of stuff for a long time. By the way, such a system requires no fancy math, minimal power, and can be implemented in a few hours. If implemented correctly, it would also have to maintain state between the two devices – remember the current offset into the bit-pile on the hard drive – so if someone deleted, injected, or altered a message, you’d know. You still wouldn’t know if the NSA exploited a BIOS backdoor on the motherboard, which is why you wouldn’t want the thing to be easily reachable; that problem applies equally to the quantum encryption system: if you haven’t got physical control of your endpoints, it’s all over.

To really piss off a cryptographer, ask them the difference between a digital certificate that is used for authentication and a pre-exchanged secret. If they answer honestly, and think about the question, they’ll realize that most of public key cryptography as it is generally employed is bunk. If you build public key systems like Whit Diffie originally proposed – in which the public key exchange is just used to set up perfect forward secrecy to carry an otherwise-authenticated message – then you’ve got something. All this SSL stuff and certificates is largely security theater intended to monetize key and identity infrastructure. Remember, the certificates have to be stored safely on the endpoint without their being replaced by an attacker – where do the certificates that are used to sign certificates come from? (They are distributed with the browser and the operating system and we blindly trust them)

Comments

  1. Dunc says

    To quote the inimitable James Mickens:

    When you read a security paper, there’s often a sentence near the beginning that says “assume that a public key cryptosystem exists.” The authors intend for you to read this sentence in a breezy, carefree way, as if establishing a scalable key infrastructure is a weekend project, akin to organizing a walk-in closet or taming a chinchilla.

    […]

    [C]onstructing a public key infrastructure is incredibly difficult in practice. When someone says “assume that a public key cryptosystem exists,” this is roughly equivalent to saying “assume that you could clone dinosaurs, and that you could fill a park with these dinosaurs, and that you could get a ticket to this ‘Jurassic Park,’ and that you could stroll throughout this park without getting eaten, clawed, or otherwise quantum entangled with a macroscopic dinosaur particle.”

    And furthermore:

    In summary, https:// and two dollars will get you a bus ticket to nowhere. Also, SANTA CLAUS ISN’T REAL.

    Read the whole thing, it’s funny.

  2. says

    Dunc@#1:
    Read the whole thing, it’s funny.

    You’re not kidding!! It’s hysterical!

    And, I hadn’t realized ;Login: was still a going concern. USENIX was a very important formative part of my life, back in the day.

  3. Dunc says

    He did a series of columns for them, all of which are at least as hilarious as that one. He’s also recorded a few videos of various presentations, which are also hilarious. All linked from The Wisdom of James Mickens… There’s a reason they call him “the funniest man in Microsoft Research”. (When they’re not using his preferred job title, which is “Intergalactic Viceroy of Research Excellence”.)

    He also plays in 3 bands, none of which have any other members.

    James Mickens is a god.

  4. consciousness razor says

    Carl Ellison explained it to me once, but the details flew way over my head – the idea is, basically, that we could build a quantum computer in which it was in all the states of decrypting a message, at once, and which would collapse its wave-function conveniently down to the one state where the key was the correct one.

    Heh… not that it makes a big difference, but it’ll be fun to quote the top banner of Scott Aaronson’s blog:

    If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.

    But he occasionally says some nutty things too, so take from that what you will.

  5. says

    consciousness razor@#4:
    If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.

    I’ll check that article out, though I only ever got through undergraduate physics in the 80s, which means I’m completely ignorant for all intents and purposes. The instantaneous quantum cryptocracker always seemed to me to be a bit of silliness (not that NSA wouldn’t and isn’t investing in the research) when the obvious point of attack is the endpoint.

  6. says

    Dunc@#3:
    From his page:
    Abstract: Young people often come up to me and say that “the cloud is the future.” This is proof that young people are idiots. In this talk, I also describe why the middle aged people who built the cloud are idiots. I don’t say anything bad about old people, mainly because I love their charming stories and their delightful insistence that ATM machines were created by the Devil.

    (choking with laughter)
    OK, I am behind on two deadlines already, don’t do this to me!

  7. consciousness razor says

    I’ll check that article out,

    Don’t worry. It doesn’t link to any particular article, just his home page…. And he very rarely does a decent job of explaining things for non-experts.

    The instantaneous quantum cryptocracker always seemed to me to be a bit of silliness (not that NSA wouldn’t and isn’t investing in the research) when the obvious point of attack is the endpoint.

    Sure. I do have sort of vague worries that I can’t afford a quantum computer (or a classical supercomputer, teams of engineers and cryptographers, etc.), while the NSA and assorted baddies can. But of course this just magnifies the imbalances that are already problematic now.

  8. says

    Marcus:

    All this stuff drives me nuts because

    Drives me nuts because: “Jesus Fuck, who has time for such idiocy? Whatever you have to say isn’t that bloody important.” I know anything I have to say isn’t important enough to waste my time on such nonsense. I don’t think there will ever be a way to secure communications over the ‘net. For every new thing, there will be a million people trying to unravel it, and so humanity goes.

  9. says

    Caine@#8:
    Jesus Fuck, who has time for such idiocy?

    They’re worried about stuff like the military GPS constellations’ crypto. Stuff like that. I’m also pretty sure that a lot of very important communications are being done over networks that are fairly open: power grid control systems, which means nuclear reactors, air traffic control systems, etc. We’re right not to care about our email and whatnot; unfortunately a lot of really important stuff is getting more and more exposed all the time.

  10. says

    Marcus:

    We’re right not to care about our email and whatnot; unfortunately a lot of really important stuff is getting more and more exposed all the time.

    Oh, I have no doubt. What does that really matter in the never-ending games of war, though? The more people try to make things secret, the more people will be trying to break it. It just seem futile to me.

  11. timberwoof says

    Caine, the war against burglars is lost. The more I try to make my front door secure, the more people will be trying to break it. It just seems futile to me. Well, no. If I put a lock on my door that is more troublesome to break than the value of the things in it, the fewer sane burglars will try to break in.

    Stderr, I’m not sure I agree with your conclusion about ssl certificates: the ones I use didn’t come with the browser; I made them. However, I’m in the midst of trying to get a test of a cloud-based system that uses such things all over the place to work and I can’t give your article the kind of attention it deserves. I’ll look at it in a few hours. That said, cloud computing pays my mortgage … and I keep my important data on computers not connected to the net. Too much stuff is done in half-assed ways.