Articles / Security

907 words

  • backups
  • encryption
  • passphrases
  • key-derivation
  • security
  • entropy

A 256-Bit Backup Key Is Only as Strong as Its Passphrase

Your backup tool says "AES-256" on the box, and you typed "Summer2019!" into the prompt. The cipher is not the weak point here; you are. An attacker with a copy of your repository never attacks AES, they attack the passphrase that feeds it.

The 256 bits describe the size of the key. They say nothing about how many of those bits an attacker has to guess. If the key is derived from a passphrase, the number of possible keys is the number of possible passphrases, however long the key is.

Where the 256 bits actually come from

Backup tools such as restic and borg do not use your passphrase as the key. They run it through a key derivation function (scrypt, Argon2 or PBKDF2, depending on the tool and version) and use the output to unlock a randomly generated master key stored in the repository.

So the chain looks like this:

  1. You type a passphrase.
  2. A deliberately slow KDF turns it into a wrapping key.
  3. The wrapping key decrypts the real master key from the repository's key file.
  4. The master key encrypts your data.

The master key is strong. But the key file sits in the repository next to your data, and it is an offline target: anyone holding a copy can test passphrase guesses at their own pace, with no rate limiting and no lockout. The security of the whole backup is the cost of guessing step 1, multiplied by the cost of step 2.

The arithmetic

Entropy is measured in bits: a passphrase with N bits needs on average 2^(N-1) guesses to find. The table below assumes, purely for illustration, an attacker managing 10,000 guesses a second against your KDF settings. Your real number depends on your parameters and their hardware, so treat it as an order-of-magnitude figure.

  • About 28 bits (a dictionary word with a capital, a digit and a symbol, the sort of thing humans pick): average of a few hours.
  • About 40 bits (a longer, cleverer-feeling human passphrase): around a year and a half.
  • About 52 bits (four random words, or eight random printable characters): several thousand years.
  • About 77 bits (six random words): not a meaningful number.

Those first two rows are why "I used a symbol and a number" does not help much. Cracking tools do not try random strings; they try what people actually type, in order of likelihood, with the usual substitutions built in. Your passphrase has the entropy of the process that produced it, not of the string it happens to be.

Quick detour: why 256 bits is untouchable

Hang on, why is a 256-bit key considered unbreakable at all? Because 2^256 is roughly 10^77, and no plausible amount of hardware gets anywhere near that, even with absurd assumptions about speed and energy. Brute-forcing the master key directly is not the attack.

That is the daft part. The cipher is so far beyond reach that attackers ignore it entirely, and go for the thing a human typed at a prompt. Rest assured they are not wasting time on the hard door when the window is open.

What the KDF buys you, and what it does not

A slow KDF multiplies the attacker's cost per guess. Moving from a fast hash (billions of guesses a second on a GPU) to a memory-hard function tuned to 100 ms or more per attempt is worth several orders of magnitude. That is genuinely useful.

But it is a constant factor. Each factor of 10,000 in slowdown is about 13 bits. A 28-bit passphrase behind a very slow KDF is still a 28-bit passphrase plus roughly 13 bits of help. A random six-word passphrase needs no help at all.

Check what your tool is configured with before leaning on it. Older borg repositories used PBKDF2, which is much cheaper to attack on GPUs than a memory-hard function. Upgrading the KDF is possible in some tools, but check the documentation for your version rather than assuming.

Picking one that holds up

Let a machine choose. A random selection from a published word list gives you a known number of bits per word: the EFF large list has 7,776 words, so about 12.9 bits each. Six words is about 77 bits, which is comfortable, and typing it is far less painful than eight characters of line noise.

cut -f2 eff_large_wordlist.txt | shuf -n 6 --random-source=/dev/urandom | paste -sd- -

Run it, memorise or store the result, and do not regenerate until you like the look of it; choosing among outputs quietly throws away entropy. Dice work just as well if you do not trust the machine.

Things that still bite

  • Reuse. A passphrase that also protects a website login is only as strong as that site's breach history.
  • Keeping it only in your head. A forgotten passphrase is a destroyed backup. Store a copy somewhere separate from the repository, such as a password manager or a sealed paper copy.
  • Passphrase in a script. If it sits in an environment variable or a world-readable file on the machine being backed up, the attacker who owns that machine owns the backups too.
  • Old key files. Changing the passphrase on a repository does not help if someone already copied the old key file; they can keep guessing the old one.

The cipher was never the interesting part of encrypted backups. Spend the effort on the passphrase and where it lives, and the 256 bits start to mean something.

← All articles