Length of a stretched gnupg passphrase that is comparable in strength to an unstretched string of 256 random bits

Question

Assume that we want to encrypt a file with gnupg using AES-256 as the encryption algorithm. (Hence, symmetric encryption.)

In this mode, gnupg requires a passphrase from the user. I understand that gnupg then derives from this passphrase a 256-bit key, which it uses for encryption.

This question is about choosing a passphrase that is at least as difficult to crack as the rest of the encryption scheme.

Now, passphrases are typically strings of printable characters, but if we used a random 256-bit string as the "passphrase", then such a "passphrase" would be at least as secure as the rest of this encryption scheme.

In contrast, a passphrase consisting of a single ASCII character (8 bits) would probably not be deemed secure, since it would be too easy to guess through a brute-force search.

The comparison between the strentgth of the passphrase and the strength of a random 256-bit key is not straightforward, however, for at least two reasons.

First, in order to derive the key from the passphrase, gnupg uses "passphrase stretching", which increases the computational cost of performing a brute-force search for the passphrase.

Second, passphrases are made of printable ASCII characters, so a 32-character (== 256-bit) passphrase, even if it were a random string of printable ASCII characters, would still have less entropy than a random 256-bit key, despite having the same number of bits.

So my question is, if we take into account both gnupg's passphrase stretching as well as the fact that passphrases consist of printable ASCII characters, what would be the length of the shortest random passphrase that would be equally hard to guess as a random 256-bit string without passphrase stretching?

Answer 1

Find a space of 2²⁵⁶ distinct possibilities, and choose your password uniformly at random from that space. For example:

• Pick 40 characters independently uniformly at random from the graphic US-ASCII set, like with tr -cd '[:graph:]' < /dev/urandom | head -c 40. There are 94 such characters, and so 94⁴⁰ > 2²⁵⁶ possible passwords this way. (You can include space too if you want to allow space; then you only need 39 to exceed 2²⁵⁶ possibilities.)
• Pick 20 words independently uniformly at random from a 7776-word list, like with diceware. There are 7776²⁰ > 2²⁵⁶ possible passwords this way. You can choose a word list you like to make things more memorable; there are many options available.

Once you do this, the stretching isn't important any more! The stretching is only a crutch to lean on if you insist on human-chosen passwords, which are a bad idea anyway.

If you use the password only for GnuPG, and you always use it with salted s2k (which, obviously!), then you can safely turn this down to 2¹²⁸, e.g. a mere 20 characters or a mere 10 words. But if there's any danger you might reuse it in an unsalted context you should stay at 2²⁵⁶.