Good layperson analogy for password and encryption keys

Question

NOTE: QUESTION UPDATED. SEE BOTTOM OF THIS POST.

I'm writing something where I need to make someone come across as though they know cryptography. I don't know enough, but as cryptography plays only a very minor role in what I'm writing, there's very little I need to know.

As I understand it, a password is a (preferably) mnemonic string that is fed into a function that generates a much longer and complex string that nobody knows, the user included. The encryption key is what is actually used to encrypt and decrypt a file.

Again, as I understand it, if you want to break an encrypted file, you can either try to brute-force the password, or the encryption key (there may well be other ways I'm not aware of). I learned this many years ago when I had forgotten my password to a document and the recovery tool I used claimed that it wouldn't try to crack the password, but rather the encryption key (it did work, in case you're wondering). I don't know where I picked this up from, but for years I was convinced that brute-forcing the encryption key is a better option to crack an encrypted file than going after its password. Possibly, the very software I used claimed it.

Years later, I realised I'm actually not sure if it's true. Is it actually generally faster/more efficient to brute-force the encryption key rather than the password itself? Considering the definition of the password and encryption key I gave above, you'd think the opposite is true.

Also, would you say that, if brute-forcing a password is like trying a bagillion keys to see which one opens a door, finding the encryption key of a file is like removing the lock from the door? I'm looking for a good analogy but I'm not sure this one works at all—especially because doors are rarely scrambled when they're locked...

UPDATE

After reading Gilles 'SO- stop being evil' answer below, I realised I didn't ask the right question. The right question is here. Probably more about information security than cryptography per se.

Answer 1

Regarding your understanding

You mostly have things right, but not completely.

a password is a (preferably) mnemonic string that is fed into a function that generates a much longer and complex string that nobody knows, the user included. The encryption key is what is actually used to encrypt and decrypt a file.

This is true apart from “preferably mnemonic”. It isn't an advantage for a password to be mnemonic: it's a constraint. From a cryptographic point of view, it's better for the password to be written down somewhere (on paper, or in a computer file) because that way it can be less mnemonic and therefore harder to crack. But there are common circumstances where writing the password down is not desirable for non-cryptographic reasons. For example, your computer login password at work must not be written on a piece of paper that sits on your desk (because anyone who walks around could need it) and can't be written in a file in your computer (because you wouldn't be able to read it before logging in), so you have to memorize it. As a consequence, computer systems that use passwords must be able to work securely with memorizable passwords.

if you want to break an encrypted file, you can either try to brute-force the password, or the encryption key (there may well be other ways I'm not aware of)

With modern encryption methods, this is true. (Here, “modern” roughly means “computer era”. I won't go into the details.)

Note however that there is a hidden assumption here, which is that all you have is the encrypted file. The easiest way to break an encrypted file in practice is often to find someone who can decrypt it and either convince them to decrypt it (through bribery or “rubber-hose cryptanalysis”) or spy on them when they decrypt it.

Is it actually generally faster/more efficient to brute-force the encryption key rather than the password itself? Considering the definition of the password and encryption key I gave above, you'd think the opposite is true.

For almost any password that's used in practice, it's easier to brute-force the password than the encryption key. Indeed, since the password is usually mnemonic, there are far fewer plausible passwords than possible encryption keys.

If you encountered software that claimed that it was faster to brute-force keys than passwords, there are a few possibilities. The claim may have been mistaken. The encryption method may have been badly designed: it's common, but less so nowadays as robust encryption is more common. The encryption method may have been deliberately stunted for legal reasons, a topic which I'll expand on a little.

Numbers

Today, your run-of-the-mill file encryption uses 128-bit keys, perhaps even 256-bit keys. Each key bit doubles the time it takes to go through all the possible keys. There are 2¹²⁸ (2 to the power of 128) possible keys, so it takes 2¹²⁸ attempts to try them all. It takes 2¹²⁸/2 = 2¹²⁷ attempts to have an even chance of finding the right key.

What's 2¹²⁸? It's about 340 billion billion billion billion. Let's take some orders of magnitude:

• A fast computer can perform about one billion operations per second.
• If you're really rich (say with the budget of a government department), you might be able to afford one billion computers.
• The universe is around one billion billion seconds old.

So if you had a tremendous computer budget and had somehow started running them at the birth of the universe, solely to brute-force one key, you'd have covered about 1 billion billion billion billion keys by now. You'd still have less than a 1% chance of having found the key.

In practical terms, this means that brute-force on a key is simply not doable. You have to find another method.

This hasn't always been true. In the past, most governments restricted cryptography to something anyone could crack if they could afford an expensive computer. In particular, until 2000, the United States (where a lot of software originated) forbade the export of software that was capable of using keys larger than 40 bits. With only 2⁴⁰ possible keys, brute force was doable even on a budget. Other governments had similar restrictions: for example, in France, at the time, it was illegal to import or use encryption with keys larger than 48 bits.

A lot of software restricted encryption to such ridiculously small keys to avoid falling under the scope of these laws, either the US export laws or other countries' similar laws. Even after the restrictions were lifted (at least in democracies), it took a while for old software and file formats to disappear.

Now let's compare the numbers with passwords. Suppose you password is made of random letters. Not a mnemonic, pronounceable sequence of letters: just letters. Just lowercase a–z letters. How long does the password have to be to have the equivalent strength of a 128-bit keys, meaning that there are as many possible passwords as there are 128-bit keys? The answer is $\log_{26}(2^{128})$ (that's the mathematical notation for the number $x$ such that number of passwords = $26^x = 2^{128}$ = number of keys). This is between 27 and 28: it takes a 28-letter random password to be as strong as a 128-bit key. Putting special characters helps, but only a little: with the 94 characters that are accessible on a US keyboard, you need $\log_{94}(2^{128}) \approx 19.5$ characters to have the strength of a 128-bit key.

In practice, most people's passwords are not nearly that long, and most people's passwords are much more mnemonic than a random sequence of letters. Using words, pronounceable syllables, or mnemonic punctuation like l33t, greatly reduces the number of possibilities. A famous XKCD comic estimates the entropy of two common password selection methods — the “entropy” is the number of possibilities when the adversary knows how the method works (e.g. “take a dictionary word and replace some letters by punctuation”) but not the details of the specific instance (which word, which replacements), coming to a measly 28-bit strength for l33t-style passwords. That's about a quarter of a billion possibilities.

Delaying the inevitable

If someone has an encrypted file, there's no way to prevent an adversary from trying all possible passwords or all possible keys, and in principle eventually finding the right one. We've seen that with keys, there are so many that it's impossible in practice: even with a huge budget, you can only try such an infinitesimal fraction of the possible keys that it isn't worth attempting. But with passwords, the number of typical passwords is low enough that you can try them all.

The techniques that are used to turn a password into a key are designed to delay the inevitable. Literally: the main ingredient in turning a password into a key is intrinsic slowness. The basic technique is to perform a repeated calculation that there's no way to accelerate or shortcut. There are additional complications that I won't go into here; if you want more technical information, read How to securely hash passwords. The technical name for this kind of slow transformation is key stretching.

Let's take our previous examples of an expensive computer that can perform a billion operation per second, and a weak but common password selection technique that has a quarter of a billion possibilities. Suppose it takes just 10 operations to turn a password into a key: then the computer can crack the encryption in a few seconds. But suppose we're using a method that requires 100 million operations to turn the password into a key — there's a 10 million slowness factor built into the method. For the user who knows the password, the decryption will take about one tenth of a second (100 million times one billionth of a second), which is acceptable. The cost has increased by 10 million, but it's barely noticeable. For the adversary who doesn't know the password, the cost has increased by 10 million. Now it'll take months to break the password. That's still doable — showing that the l33t method of password selection is weak — but it's already getting somewhat expensive. With a good method of password selection, the cost can go out of reach.

On a side note, I wrote earlier that there's no way to prevent an immortal, infinitely patient adversary eventually finding the right key. That's not exactly true: there is a way, called the one-time pad, which consists of making all possible decryptions equally likely. The adversary can try all the keys, but they won't know when they've found the right one. This comes with some huge downsides, however. First, there has to be as many possible keys as there are possible files. So the key is as long as the file. Second, the key can only ever be used once: using the same key twice (“two-time pad”) breaks the encryption. As a consequence, one-time pad is not very useful: if you can store a key that's only for use with a single file, and that's as big as the file, you might as well store the file itself. It therefore has very little practical relevance, but it might come up in a story because laypeople often downplay the consequences of reusing the key (it's a devastating break) and underestimate the strength of modern cryptography (NSA can't break properly implemented cryptography, so what they do instead is exploit software bugs, which are a dime a dozen).

The lock analogy

The lock analogy can be a good one, but you have to accept some restrictions.

The door and the lock are made of a very sturdy material. There's no way to remove the lock or inspect it. The only thing you can do with a lock is try a key, and if it doesn't fit you can try another one. Trying a key doesn't give you any information on the right key: you might have it completely wrong, or almost right, but you can't tell the difference. Either you've got it or you haven't. There are so many different positions for the pins on the key that you can't ever hope to try them all.

People don't like carrying keys in their wallet, so instead they have “universal” keys with pins that can be moved. When they need to unlock a door, they take a universal key and move the pins. Since nobody can remember the pin positions, they carry small pieces of paper with instructions on how to set the pins. But to keep the piece of paper short, in practice, these are simple instructions like “push every third pin, except for the ones that are also a multiple of five”. If you want to pick a lock, you don't try all possible pin configurations: you try the ones derived from simple patterns.

Key stretching consists of applying a decoder ring (which everyone has, it was published in a popular science magazine) to the instructions written on a piece of paper. It's a minor hurdle when you have the instructions. But if you don't have the instructions, you have to go through the decoder ring all over again at each attempt, which is tedious.

Cost analogies

Regarding the respective roles of passwords and keys for encryption, I explained above that the important thing about the transformation of passwords into keys (the key stretching method) is that it's slow. It's about raising the cost for the legitimate user from negligible to acceptable, while raising the cost for the adversary from small to high.

You can find this principle in other aspects of security. For example, the very existence of locks applies this principle. For the owner of the house, having a lock on your door means that you have to carry the key in your wallet, and spend an extra few seconds opening your door when you get home. For a burglar, the lock means that they need to carry specialized tools, and they'll be under suspicion if they're found carrying lockpicking tools. The tools needed to break a high-end lock take some time to use, and require power, and make noise, so if there are people watching, the burglar will be conspicuous. Even if a lock is breakable (the password or the key stretching method is weak), it's a deterrent compared to having no lock.

Fraud detection is another example where scale plays a major role, although there the scale is built into the problem rather than into the solution. Most fraud detection methods won't detect if someone tries to steal a dollar once. Fraud detection works in bulk: it's about preventing someone from sealing a lot of dollars at once, or from making a lot of small thefts. Here, the adversary (the thief) wants to steal a lot of money, and the system tries to prevent stealing a lot of money, while not bothering people much if they're only withdrawing or paying a few dollars.

It's about security, not cryptography

Does your character really need to know about cryptography? Cryptography is a very specialized skill that in fact rarely comes into play. Security breaches arise for non-cryptography-related reasons far more often than for cryptography-related reasons.

Everyday computer security, such as the security of the web, does rely on cryptography. There are people who work on the cryptography in web browsers, and web servers, and other related software and systems. Every once in a while, a security researchers finds a flaw, and then those people who work on the software scramble to fix it.

But most security breaches are due to operational reasons. Someone left a database unprotected. Someone left a database unprotected, again. Someone gave their password for a bar of chocolate. Someone fell for a scam where a crook posed as a computer repairman. Did someone leave a database unprotected? And after the last big cryptography vulnerability, vendors distributed corrected versions of their product, but many people didn't apply the security fixes.

If your story depicts someone who knows cryptography and has a job related to cryptography, such as computer developer, system administrator, or spy, chances are that at any given time, they aren't actually working on cryptography or using cryptographic skills.

Answer 2

A cryptographic key is a string of bits. For example, AES-128 uses 128 bits, each one of them being either 0 or 1. To be able to encrypt or decrypt, each one of those 128 bits must be set correctly. This key is the input to the encryption algorithm. For AES-128 it has to be exactly 128 bits - not more nor less.

For humans, remembering 128 bits (= 16 bytes) is very difficult and impractical. It's much easier to remember (and type) a passphrase such as "mary had a little lamb" than an AES-128 key such as 0a fc 5d e7 43 21 9c b3 6f 1b 93 c7 70 55 24 18. Furthermore, a requirement that all passwords must be exactly 16 bytes is silly. For AES-256 you woud need twice as much. And of course, the true entropy of a 16-character password is much less than 128 bits because of language redundancy and the fact that an ASCII character takes up only 7 bits.

This is why we have key derivation functions (KDF). You input a password of any length into a KDF and tell it how many bits you need for key. The KDF takes the bits from the password, adds some magic spices (called salt) and mixes them up using some cryptographic hash function. You get out just as many bits as you wanted which have the same statistical properties as if they were random. They are based on password, so the same password will always give you the same key. As such, KDF are a perfect "converter" of passwords into cryptographic keys.

If an adversary wants to break the encryption, he/she ultimately needs the encrption key (e.g. 128 bits for AES-128). With a truly random key, this means trying 2^128 combinations, which is an awful lot. Because passwords have less entropy, it would make more sense to attack the passwords as this would reduce the needed effort by several orders of magnitude. However, good key derivation functions such as PBKDF2 are designed to counter this by requiring to do a long computation (basically applying the hash function 10000 times). This "computational cost" slows down the attack on passwords significantly and makes it unfeasible.

As an analogy:

• Cryptographic key is a key that actually opens the door.
• Password is the secret word that you tell to the locksmith (KDF) so that he can make a key for you. If you tell the same password to the locksmith, you get the same key.

Answer 3

The symmetric encryption algorithms require keys with good entropy. Usually, humans tend to have passwords with bad entropy then they are crackable There are well-known cracker programs like John the Ripper and hashcat, and rainbow tables.

Today, we have better password mechanisms like Dicewire so that the entropy of the password can be much longer. In any case, a Password-Based Key Derivation function, BPKDF is used to generate a key from the passwords. Examples are Scrypt, PBKDF2, Argon2id. We require iteration control to reduce the attacker's time, memory-hard property to eliminate the massive ASIC/FPGA/GPU farms to attack. Argon2 was the winner of the Password Hashing Competition in July 2015. Whenever available, prefer Argon2.

The generation method strength the output with the help of the salt and the usage of the salt kills the rainbow tables, which was very popular on the systems where salt is not used. The attacker gets the user's table and first looks for the well-known passwords than perform the rainbow table attack to find some working passwords.

Ironically Facebook was worst than this they stored passwords in plaintext.

Is it actually generally faster/more efficient to brute-force the encryption key rather than the password itself?

It is depending on the system and usage;

• If the entropy of the password is less than the entropy of the key attacking the password is preferred. And, that was usual in older times.
• If the entropy of the password much longer than the key, then the key should be preferred.

Hey, wait for a second, AES with 128 bit for a single target is beyond for anyone to reach [1]. In older systems, one might guess that it was DES, Still, it was out of the question for a company [2].

It might be the broken example; the PKZIP known-plaintext attack that can find the internal representation of the key in a few hours. There are tons of off-line online software for this.

There is no conclusion here without knowing the system. Some old system was not using the full key sizes, due to the export rules of USA that you cannot export an algorithm that has secured more than 40-bit encryption, so they were achievable.

or, today we should say; hell NO, you can't brute-force a 256-bit key.

I'm looking for a good analogy but I'm not sure this one works at all—especially because doors are rarely scrambled when they're locked...

An analogy

Put the key into a magical box and lock/unlock it with your magic words (your passwords). When you need for the encryption or decryption spell the words and get the key. A skilled locksmith, however, who doesn't have any knowledge of magic, try to lockpick the lock.

So, someone who can brute-force the password or someone who can brute-force the key can access the vault.