Four theories on the cryptography of Star Trek

frameofmind
“I’m sorry Captain. They rotated by fourteen.”

Over on ZDNet they’re asking why cybersecurity is like Star Trek. I think this is the wrong question. A better one is: why is the cybersecurity so bad on Star Trek?

Please don’t take this the wrong way. I’m a huge Trek fan. I’ve watched every episode ever made, and I’d do it again if I had time. Even the Holodeck ones.

But I also teach computer security, and specifically, cryptography. Which is ruining the show for me! How can I buy into a universe where the protagonists have starships, transporters and dorky positronic robots, but still can’t encrypt an email to save their livesThe Trek crew has never encountered an encryption scheme that didn’t crack like an egg when faced with an ‘adaptive algorithm’ (whatever that is), or — worse — just a dude doing math in his head.

But there’s no reason to take my word for this. Thanks to the miracle of searchable Star Trek, you can see for yourself.

Cryptographers deserve better. Viewers deserve better. And while I can’t fix bad screenwriting, I can try to retcon us an explanation. And that will be the subject of this post: four scientifically credible explanations why 24th century crypto could legitimately be so awful.

Theory #1: A quantum leap

One answer to the mystery of Trek’s bad crypto is so obvious it’s mundane. It’s the 24th century, and of course all the computers are quantum. Everyone knows that quantum computers are super-duper-powerful, and would blow through traditional encryption like a knife through butter.

But not so fast! As I’ve written before on this blog, quantum computers are actually quite limited in what (we think) they can do. This even goes for quantum computers enhanced with bio-neural gel packs, whatever the hell those are.

Specifically: while QCs are very good at solving certain number-theoretic problems — including the ones that power RSA and most public-key encryption schemes — theorists don’t believe that they can efficiently solve NP-complete problems, which should still leave an opening for complexity-theoretic crypto to thrive in the 24th century. And yet we never hear about this in Trek.

Of course it’s always possible that the theorists are wrong. But quantum computers still don’t explain why Spock can apparently crack encryption codes in his head. (And no, ‘Vulcans are really good at math’ is not a theory.)

Theory #2: It’s the warp drive, stupid  

If there’s a single technology that makes the Star Trek universe different from ours, it’s the Warp drive. And this tees up our next theory:

Could it be that there’s a conflict between faster-than-light travel and secure cryptography? Could Zephram Cochrane have done in crypto?

Shockingly, there might actually be something to this. Exhibit A is this paper by Scott Aaronson and John Watrous — two honest-to-god complexity theorists — on the implications of a physical structure called a closed timelike curve‘ (CTC) and what would happen if you used one to go back in time and kill your grandfather.

Aaronson and Watrous aren’t really interested in killing anyone. What they’re interested in is paradoxes, and particularly, what it means if the Universe resolves paradoxes. It turns out that this resolution power has huge implications for computing.

It seems that computers with access to paradox-resolving time travel would be dramatically more powerful than any of the computers we can envision today, regardless of whether they’re quantum or classical. In fact, CTC-enhanced computers would be powerful enough to efficiently solve problems in the complexity class PSPACE. This would utterly doom the type of complexity-theoretic crypto we rely on today.

But this still leaves a question: does the Warp drive necessarily imply the existence of CTCs?

One clue comes from Einstein’s special theory of relativity, which implies that faster-than-light travel would imply violation of causality. For those without the physics background: Star Trek IV. 

Theory #3: Complexity theory is dead

Do you remember the episode in Deep Space Nine where O’Brien and Bashir discussed the latest developments in Ferengi computer science? How about the episode that took place at a Vulcan complexity theory conference? No, I don’t either. These things never happened.

This all by itself is suspicious. Trek characters could waste hours blabbering about subspace fields or trying to convince Data he’s a real boy. But something as central as the computers that run their ship and keep them alive? Not a peep, not even in a “TECH” scene.

It’s almost as though by the end of the 24th century, complexity theory has fallen off of the list of things people care about. Which brings me to my next theory:

In the Star Trek Universe, P = NP.

In one sense this would be huge and mostly great news for computer scientists. But it would be a disaster for the efficient (complexity-theoretic) encryption we use on a daily basis. For things like RSA and AES to be truly secure, we require the existence of ‘one-way functions‘. And those can only exist if P does not equal NP (P != NP).

Fortunately for cryptography, most computer scientists are convinced that P != NP. They just haven’t been able to to prove it. The most recent attempt was made by Vinay Deolalikar of HP Labs, and his proof foundered on subtleties just like every one before it. This means the problem is still open, and technically could go either way.

If P did turn out to be equal to NP, it’s conceivable that result would look exactly like Star Trek! A few algorithms could still be quite difficult to break (i.e., the attacks would have huge polynomial runtimes). But maybe not. People might instead fall back on obscurity to overcome the mathematical impossibility of building strong complexity-theoretic encryption. One-time pads would still work, of course, and quantum key distribution might allow for point-to-point transmission. Everything else would become a massive joke.

Now, this theory still doesn’t explain the ‘breaking crypto in your head’ thing, or why it takes like six hours to change the Enterprise’s command codes. But it would go a long way to repairing the damage wrought by years of bad scriptwriting.

Theory #4: The Stallman effect

Live long and publish your source.

This last theory is the most mindbending. It’s also not mine (I ripped it off from Chris Long).

To get a fix on it, you first have to think about this Federation we hold so dear. Here we have a society where the cost of making something is simply the marginal cost of replicating a copy. Money isn’t necessary, and people are free to devote themselves to activities that are fun, after spending the necessary ten hours a week on required tasks such as legislation, family counseling, robot repair and asteroid prospecting.

Does any of this sound familiar to you? Yes. The Federation was founded on the teachings of Richard M. Stallman.

A society based on the teachings of RMS can’t possibly get security right. To such a society, security is simply a tool that prevents you you from accessing the full capabilities of your computer replicator. How could we expect serious crypto in a society that worships the legacy of RMS?

A minor problem with this theory is that it doesn’t explain why bad cryptography crosses species lines: even the Romulans have terrible encryption. Of course, the Romulans have frigging cloaking devices and still haven’t managed to wipe us out. So maybe we can just chalk that one up to incompetence.

In conclusion

I admit that there’s only so far you can go with all of this. At a certain point you have to give in and admit that the Trek screenwriters don’t know encryption from a Chronoton field. And honestly, what they’ve done with cryptography is nothing compared to what they’ve done to physics, electronics, and historical drama.

And please don’t get me started on the Holodeck. Can’t they just fit that thing with an OFF switch?

Still, if nothing else, this post has given me another forum to bitch about my favorite grievance: bad cryptography in movies and TV. And a chance to remind Hollywood (should any representatives be reading) that I am ready and willing to help you with your cryptographic script writing problems for a very reasonable fee. Just don’t expect anyone to do crypto in their head.

9 thoughts on “Four theories on the cryptography of Star Trek

  1. Awesome article! There is one additional possibility that applies when the characters have direct access to the machine that contains the message. This is not always the case but it is the case in some scripts. Star Trek folks have astonishing sensing and probing technology that could be used to find side-channels in computation and generally figure out how the machine is working.

    This would also solve the problem of taking six hours to break the encryption because it would account for some time to reverse engineer the system.

  2. Point 4 is just the dangerous myth that open source = insecure. Its false. An open source replicator couldn't stop somebody from making something dangerous, but open source encryption is highly secure. Attackers know algorithm and the implementation, but they dont know the key. Thats the only part which needs to be kept secret.

    See truecrypt and GnuPG for example.

  3. 3 seems a reasonable explanation, but 0: They didn't think of it is the real one. The original star trek first came out in 1966, but the existence of a system to break the enigma machine remained classified until the 1970s. The last experience with cryptography known would have been people breaking first world war codes by doing maths in their heads.

  4. Whereas I love your article and kind of agree completely, you have also triggered my snarky reflex, so I am compelled to come to the defense of Star Trek.

    1. Adaptive algorithms are very powerful because they figure out your strategy (using magic) and adapt to it. What would the Borg be without adaptive algorithms? So, adaptive algorithms are a totally plausible way to both break any cryptographic mechanism and form a post-singularity all-powerful supercyborg race.

    2. The Star Trek universe still suffers from security problems stemming from the limitations of its users. For example, the most common Vulcan passwords are “pon farr” and “fascinating!” Additionally, as a race, Klingons have the easiest to guess passwords based on their rather militant reactions to prompts such as “passwords much have at least 8 characters and use at least one non-alphanumeric character.”

    In conclusion, Star Trek is totally believable and we should recreate it hear on Earth.

    Thank you,
    lydia

  5. I thought you might appreciate this. So in a science fiction universe pivot, moving to the Halo universe, I was recently re-playing the first game. While on the Covenant Ship, Truth and Reconciliation, the AI that interfaces with the Master Chief's suit says the following about opening an alien door,

    “I'd like to see you crack a 128,000-bit modulating encryption key.”

    I wish she would have cracked it faster while playing on Legendary. That said, can we get an AI for the lab?

  6. 1. Cryptographers tend to frown on magic as an explanative tool, though we make an exception for lattice-based-crypto — which even the experts don't really understand. Also don't get me started on the Borg. Why don't they just shoot people who come nosing around their collective?

    2. In defense of the Klingons, I don't think they actually have non-alphanumeric characters.

    Amen to the rest of it.

  7. No, you fool! No one just unplugs a Holodeck! If it's malfunctioning, errors in the matter conversion subsystem could wipe out all the crew trapped inside!

    (Seriously, who wants to hang out inside a buggy meat grinder like a holodeck? 🙂 )

  8. it seems like cryptography in hollywood movies are about as bad as the idiot DRM schemes (HDCP included) that they attempt to dawn on us all to protect their extorsion-based failed business schemes

Comments are closed.