Fictional Encryption Code
April 13, 2011 11:46 AM   Subscribe

Can you give me an example of what this ridiculously-hard-to-decrypt code might have been?

I came across this article from 2006 that describes a criminal who encrypted a database in such a way that it would have taken police 400 computers and 12 years to crack the code. I'm working on a writing project now where I want to include a scenario like this, but I have no idea what the parameters of the set-up would be (my background in CS is minimal at best).

I don't need to know how it's done per se (I probably wouldn't understand anyway), but I would like to know what a good example of the code (or codes) might be (are we talking hundred of characters? Millions? Is it randomly generated? ASCII characters? Unicode? Something totally different?

Also, could this sort of thing be done with a flash drive? Any input you can offer would be great.
posted by baronessa to Technology (34 answers total) 4 users marked this as a favorite
You most likely want to read up on public key cryptography, or cryptography in general.

When you talk about the "code" do you mean the programing code used to encrypt the data, or the sized of the encoded data itself? Really, the size of the encoded data doesn't matter, unless it's encrypted in such a way that a larger data set will let you see patterns, and this doesn't really hold true.

What you're talking about is what encryption algorithm is used, and the key size.
posted by mikeh at 11:53 AM on April 13, 2011

Trucrypt with a sufficently long passphrase (64-256 characters) and and randomly generated keyfile would offer roughly this level of protection. It's free and can run off a flash drive.

Specifically it uses algorithms called AES, Twofish and Serpent.
posted by T.D. Strange at 11:53 AM on April 13, 2011

A lot of common public key encryption formats take forever to figure out. As long as it's a published and peer-reviewed cypher it's going to be nearly impossible to crack unless someone finds a 'weakness' in it
posted by the mad poster! at 11:56 AM on April 13, 2011

Encryption is not my forte, but this kind of thing pretty much comes down to the length of the key.

When you encrypt something, you first select a key length (a certain number of bits) for scrambling the text. If you have a 128-bit key, that's 2^128 possible combinations required to unlock the text. if you have a 512-bit key, 2^512. Obviously that's a very large number, which is why it would take many computers many years to run through all of them.

Then, of course, you generate the key itself, which is used to encrypt the text.
posted by adamrice at 11:57 AM on April 13, 2011 [1 favorite]

Response by poster: I don't entirely know what I'm talking about here (hence my plea for answers!) but I believe I'm referring to the passphrase that is encrypted the data. Basically, I want to have a cypher/code/passphrase/whatever that can't be cracked by my fictional police, but ends up being solved by another character based on some sort of clue they find or what have you. But I need to know what it would look like in order to have the character solve it...
posted by baronessa at 11:59 AM on April 13, 2011

I very much doubt the 4800-computer-years-to-break figure.

Modern algorithms (if 2006 can be considered "modern" in encryption terms) take thousands or millions of computer-years to break.

The most modern encryption algorithm is probably the Advanced Encryption Standard (AES). A file encrypted with AES-256 would take a billion computers, each checking a billion keys per second about 3669308260170000000000000000000000000000000000000000 years to decrypt. It will also take, at the very least, 700000 million million million million million times the energy used per year in the world.
posted by alby at 12:01 PM on April 13, 2011 [1 favorite]

The idea behind public key encryption is that you already know how it was encoded, you just don't know with what. And the search space for the what (you probably already know the size of it) is so large and there's no way but trial and error to find it. So you can estimate how long it takes to try each one and thus estimate, say, 40 years.
posted by Obscure Reference at 12:02 PM on April 13, 2011

The length of the passphrase is immaterial, as whatever passphrase you use will be hashed to form a key. It is the size (length) of the key that is important. A 256-bit key will be a number about 78 characters long.
posted by alby at 12:02 PM on April 13, 2011

Others more knowledgeable will chime in with more up-to-date info, but in the meantime:

Encryption is an arms race. The encrypter invents a bigger wall (better encryption code), and it holds... for a while. The attackers either develop a crack (as in the case of the Allies breaking the Enigma Machine's encryption), or get a bigger battering ram (more CPU power to brute-force attack the code).

In general, since Moore's Law is exponential, the code that took 8,000 years to break in 2005 technology would only take a mere 1,000 years to break today... if that were the only part of brute-force attacks. However, malware can be used to hijack remote computers from unsuspecting users across the globe, providing tens of thousands of CPUs to work in parallel on problems... yet barely costing the attacker anything but a little programming time, and a few months of patience.

Additionally, there are other weaknesses: most encryption is only as good as the encryption key, which is akin to a password. First step for an attacker: try the key "password"! Seriously, as long as human beings are allowed to pick keys, the keys will often be guessable.

AES encryption is the current US gov't standard for encryption. Blowfish was previously the hottest thing on the block in encryption.

There is a way out of this arms race. Quantum entanglement may be able to produced encryption sequences that are really, truly random (and therefore not decipherable by math at all). One of the two identical paired sets (of physical quantum-entangled entities - a set of protons, for argument's sake) could be given to the encoder, another to the desired decoder. Without the second key, the encrypted message would be forever indecipherable, even given a kajillion computers and ninety-bazillion years.

Don't lose the damned key.
posted by IAmBroom at 12:05 PM on April 13, 2011 [1 favorite]

Coded messages and the "codes" which determine how information is stored on a computer are very different.

HTML is a "code" in the latter sense - you can see what it looks like by going to the View->Source menu in your browser. This kind code is supposed to be a perspicuous as possible, a happy intermediary between what makes sense to people (an expression of their intentions regarding display) and unambiguous enough to be processed algorithmically ("I want it to have a really clean look, lots of white space" expresses your intentions, one might say, but good like writing a computer program to act on that).

"Codes" in the former sense, as in cryptographic codes (rarely referred to as such by CS people), are ways of re-expressing data in such a way as to make it very, very, difficult for an interloper to work backward to it's original form by dint of requiring some additional piece of information (the "cryptographic key") and a knowledge of the algorithm (a series of steps a computer can carry out) used. A well designed cryptographic algorithm requires only that the key be kept secret, not the necessarily algorithm used, to be effective.

I mention all this because you don't seem to be distinguishing between these two senses of the word in your question.

The size of the key (how many bits are needed to express it) is only one factor in how difficult it will be to decrypt a message without foreknowledge of the key. A very poor algorithm won't be secure no matter how long the key is, unless it's effectively a one time pad, meaning the key is as long as the data to be encrypted. A perfectly random (note: hard to do) key that's as long as the plaintext will result in an unbreakable message. Encryption algorithms exist only so that you don't need to use such long keys (which are inconvienent) and so that keys need not be exchanged between parties ahead of time (public key, mentioned above, allows you to exchange keys over an untrusted channel).
posted by phrontist at 12:06 PM on April 13, 2011

References to public key / private key cryptography are off here. Why would a lone criminal use public key cryptography? It's strictly worse than a shared-secret encryption for their purposes. If you're a criminal and you need to keep a secret from everyone else, you use symmetric encryption. The police are far more likely to find the file you kept your private key in than to crack your password.

A simple cipher like 256-bit AES used with a 30-character alphanumeric password would yield 10^53 possible keys, which even at a rate of trying a trillion keys per second would take longer than the universe has existed to crack.
posted by 0xFCAF at 12:06 PM on April 13, 2011

In a modern computer-based encryption scheme, the time to find the key by brute force (i.e., by checking every possible key until the key is found) is proportional to two raised to the number of bits in the key. That is, each bit doubles the amount of time it will take to brute-force the key.

The amount of time it actually takes depends on how quickly each key can be tried and what the key is. If the key is 0 or 1, or even 1000, it will obviously be found very quickly. For this reason, all keys are quite large numbers.

Assuming you had a computer that could try a trillion keys per second, a 128-bit key, common for Web security these days, would take about 2 million million million years to try every key. (There are not currently any computers that can try a trillion keys per second.)

Another issue is how to tell whether you have in fact found the correct key. If the key is wrong, you don't get an error; you get gibberish. Often there is a fingerprint (checksum) of the data, so that the program that decrypts it can know when it's correct. In this case it is easy (though time-consuming, since you must re-generate the fingerprint for each candidate decryption and see if it matches the known fingerprint).

Absent a fingerprint, you are in real trouble. If you know the encrypted data is English text, it is straightforward to run a letter frequency analysis on every decryption result and save off results that look like they might be English. But this too adds to the time it takes to check each key. And if the file is compressed binary data, it can be very difficult to tell when you've got it right.

Since you are looking for the passphrase for encrypting the data, you should know that the passphrase is generally used to encrypt the real key that's used to encrypt the data. The fingerprint of the real key is generally known, so you can tell when you have got the passphrase right. However, there are techniques to "fortify" the fingerprint so that it takes a long time to validate it (say, a tenth of a second, which would be unnoticeable to a user but would allow you to validate only ten passphrases a second).

Modern cryptography, in fact, is rather bulletproof if implemented well. You are on the right track with your idea to have some other character solve it based on a clue; it's pretty much the only way you would ever get in.
posted by kindall at 12:09 PM on April 13, 2011 [1 favorite]

So yeah, I'd say AES with a 128-bit or 64-bit key.
posted by phrontist at 12:09 PM on April 13, 2011

OP: Basically, I want to have a cypher/code/passphrase/whatever that can't be cracked by my fictional police, but ends up being solved by another character based on some sort of clue they find or what have you. But I need to know what it would look like in order to have the character solve it...

baronessa, a passphrase is something typable, so an actual phrase is appropriate: "Four score and 7 years ago, our forefathers set forth upon this continent", for instance.

The hero might deduce this because the suspected criminal is a big Lincoln buff. OK, that's cheesy, but not dumber than real life.

Why would a lone criminal use public key cryptography?

Because we live in a world where criminals make mistakes, 0xFCAF.
posted by IAmBroom at 12:10 PM on April 13, 2011

Response by poster: So are people saying that the passphrase could be something as "simple" as 30-78 alphanumeric characters?

For example:
posted by baronessa at 12:15 PM on April 13, 2011

One way that your hero can crack the code is by a known plaintext attack. This is where you have a piece of data that you know that has been encrypted with the same key. This knowledge can be used to deduce the key (or part of it) and then you are home free.

Or, the bad guy generated the key with a random number generator that happened to be faulty.
posted by It's Never Lurgi at 12:15 PM on April 13, 2011

Response by poster: Sorry, I mean Password. I warned you, my knowledge of this sort of thing is minimal...
posted by baronessa at 12:16 PM on April 13, 2011

Sure, it absolutely could be.
posted by phrontist at 12:18 PM on April 13, 2011

Here is a password generator that adheres to the widely held best practices for selection. It's what I use, except with a printed word list and a box of dice, though my life is not nearly exciting enough to warrant that.
posted by phrontist at 12:20 PM on April 13, 2011 [2 favorites]

You don't know that much about this. I think my advice would be to get a rough understanding (which I think most of the explanations in this thread are adequate for), and then don't write about the specific technical details, but write stuff that makes sense with them.

The non-techy reader won't care whether it's AES or blowfish or 128 or 256 bit keys. The techny reader may spot errors in your explanation.

So yeah, the high level functional summary is: This stuff is clearly encrypted, and it would take a computer forever to guess the password.

FWIW, passphrases and passwords are the same thing. The security community prefers the term passphrase, because password implies a single word. While there's gazillions of possible keys to try, there's few enough English words that it would be quite fast to just try them all (a "dictionary attack"). So a single word is discouraged and a phrase (or nonsense like 416wb5uz9651) is necessary for strong protection. It's pretty common for people to abbreviate song lyrics or book quotes; IAmABroom's suggestion might be reasonably shorted to 4s&7yra which is short and easy to type and remember, but not something one is likely to stumble upon with random guesses.

It's not uncommon for people to write passwords down, especially if they're good strong passwords (like 416wb5uz9651) which are often hard to remember. That gives you lots of plausible ways to detective it up.
posted by aubilenon at 12:36 PM on April 13, 2011

What is it you want to accomplish in your story? Just accurately name-drop what encryption scheme someone used? Have the cops decrypt it?

If it's the latter, then the criminal's an idiot and is using some known-broken or known-weak approach, or is an idiot and is using a simple dictionary word as the passphrase, or isn't an idiot and actual brute-force decryption is implausible. Some things that are plausible: someone installed a keylogger on the criminal's computer (or in the keyboard) and got their password. Someone rigged a camera to record the criminal entering the password. The criminal wrote it down somewhere, and the cops found it -- this could be arbitrarily complex if the criminal broke it into two or more parts and the cops had to track down all of them.

There are other alternatives involving information leak. The criminal may have unlocked the encrypted volume and then used a word processor that helpfully cached an enencrypted copy of a file on the hard drive.
posted by Zed at 1:00 PM on April 13, 2011

then the criminal's an idiot and is using some known-broken or known-weak approach, or is an idiot and is using a simple dictionary word as the passphrase

This is not implausible.

I suppose the bad guy in the story could be restricting his encryption technology because of religious or ideological reasons, and the hero realizes that.
posted by chengjih at 1:06 PM on April 13, 2011

I really like cryptography and study it as a hobby. I found CrypTool Online to be useful in learning about all the various ciphers and analysis methods. Also, Cryptonomicon (wiki) (Amazon) is a great fiction book introducing basic (and in-depth) cryptography concepts. It is a lengthy read, at >1000 pages, but its worth it if you're interested in this stuff. Hppe Mvdl!
posted by wayofthedodo at 1:12 PM on April 13, 2011 [1 favorite]

Response by poster: Thanks everybody! Just to be clear, I'm not planning to go into detail about the type of technology used. I just wanted to know what the password would look like so that I could create something my character could crack using a more old fashioned brand of cryptography.
posted by baronessa at 1:15 PM on April 13, 2011

as "simple" as 30-78 alphanumeric characters?

If it's a random string of them, much simpler. Wikipedia's password strength article has a good breakdown of this.

As the article notes, human-chosen passwords are typically much, much weaker than randomly generated ones.
posted by Zed at 1:33 PM on April 13, 2011

A common approach to password hacking is to begin with information gathered about the person like their kids' names, birthdate, address, etc. This tends to work because people, as mentioned above, are really, really bad at password generation. We're also prone to forgetting things like (seemingly) nonsensical strings of letters and numbers so unless forced to, we like to base our passwords on familiar things. Convenient, but not secure!

A good bad guy will also try to examine the target's home or office for clues. Often a password is found scribbled on note paper and shoved into a desk drawer or on a post-it note stuck to a monitor. This is probably less likely in a corporate setting than at home, but it still happens.

You can save a lot of computer time by being observant.
posted by tommasz at 1:50 PM on April 13, 2011

When people try to argue w/ me about good passwords, I point them to this (now dated) article: Password Recovery Speeds

And that's not encrypted information, it's merely guessing password strings.
posted by TomMelee at 1:55 PM on April 13, 2011

My suggestion if you're going to use cryptography as a plot device is to read a copy of The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. It's a fun (and sometimes scary) read which highlights the basic problem that good cryptography is hard to pull off primarily due to human error, and is full of James Bond type stuff of intelligence services playing mind games with each other.

My suggestions for a plausible passphrase that your hero can discover that might baffle law enforcement:
1: something longer than 8 characters. Preferably, something longer than 12.
2: something that can be discovered by knowing the target's psychology, but not something you can pull from a dictionary.
3: a passphrase that's hidden in the character's effects in some non-obvious way: a strangely named playlist on the iPod, a deck of cards, a list of books, an oddly-written paragraph in a document.

In modern codebreaking, you're almost certainly better off hacking the people and processes of communication rather than attacking the cyphertext. Bribe or coerce an informant. At some point, that information was plaintext, perhaps there's a copy left somewhere? Who's sloppy with their security? Is the person paranoid enough to leave a plaintext backup somewhere that's difficult to find?
posted by KirkJobSluder at 2:04 PM on April 13, 2011

Here is a pretty good (and easy to read) guide to the advanced encryption standard.

Pay attention to the foot shooting prevention agreement - there's a whole list there of where your proposed encryptor can go wrong.
posted by Kid Charlemagne at 5:18 PM on April 13, 2011 [1 favorite]

A very plausible situation: private key cryptography relies on the private key being kept secret (duh). Private keys are typically stored on disk, and there are plenty of ways a disk could be thought to be disposed of but actually not. The key could also certainly be on a USB thumbdrive.

In practice, almost all attacks that succeed because people slip up somewhere in the security process. If someone's there to catch it (or they forced it), they get a break, but a single person isn't likely to do much good against a modern encryption scheme.

Of course, if you wanted a mathematically nice situation, someone could write his own public-key encryption scheme thinking it was perfect (and it was actually stupid) and publish his public key, and another character could figure out something about the public key and be able to make good guesses about the private key. If this was used for authentication to one of the bad guy's systems, this could give the good guy access.

Much more fun for fiction are something like book ciphers, since a character with insight into the criminal can guess at the book.
posted by devilsbrigade at 10:14 PM on April 13, 2011

Modern cryptographic systems encrypt exported private keys with a password. So even if you obtain the USB drive or whatever with the private key, it is still likely to be unusable without its password
posted by CautionToTheWind at 2:58 AM on April 14, 2011

Modern cryptographic systems encrypt exported private keys with a password. So even if you obtain the USB drive or whatever with the private key, it is still likely to be unusable without its password

I'd suggest this is where you want to go, as it represents the last line of defense of a private key. Your hero guesses the password encrypting the (much longer, bitwise) encrypted private key obtained by the police. This allows your hero and the police to start with the same knowledge (the encrypted private key, won from the criminal at no small expenditure of effort) and end up in different places. Refer to the previously linked discussions of "good passphrase selection" for an idea of what such passphrase might look like.
posted by axiom at 8:25 PM on April 14, 2011

You might also want to look into the notion of hidden volumes. The criminal might provide the police with the dummy passphrase (leading them to release him as the dummy volume contains nothing incriminating) while your hero successfully deduces the correct passphrase.
posted by axiom at 8:28 PM on April 14, 2011

Since I'm apparently sticking my nose into all your questions relating to this story I'd go with my answer in another one of these - modern cryptography is impossible to break without a macguffin (i.e. the device from Sneakers) or the password. Again, the weak link in any security system is human. With access to Facebook and a person's name there's a good chance you can work out their password (kid's name, dog's name, DoB etc) and once you've got that there's a good chance that password will be the same across that individual's online life - remember the gawker password issue last year?

A good proportion of average folk have extremely weak passwords. Some variation of an important name, favourite media character and a birthday. The film Wargames is probably the best fictional treatment of this sort of thing. In my experience the regional choice of password is also unsurprising - people from Newcastle Upon Tyne often use "Shearer" and at least 1 in 5 people from Liverpool choose "Liverpool"* as their password. It's staggering that people are this crap but there you have it.

*seriously - I kid you not. Scousers are that proud that they throw security to the wind in their effort to glorify their place of birth. Funnily enough, those who choose "ManchesterUnited" or "Chelsea" almost never originate from those locations. Glory supporters...
posted by longbaugh at 12:27 PM on April 25, 2011

« Older Oh and I also don't know how to store animated...   |   What should I do with this WWI scrapbook? Newer »
This thread is closed to new comments.