3
$\begingroup$

The key size for AES is chosen as 256 because that's considered the minimum keysize which can protect against a brute force attack - i.e. $2^{256}$ tries.

However, in practice, for a lot of applications, a user chosen password is used to derive the 256 size key using a KDF. Let's say the application mandates a 8 character password - that's a 64 bit password - so the brute force reduces to $2^{64}$ tries. And it probably reduces even more because a byte from a common password has much lesser entropy than a byte from a key. The brute force can be tried byte wise rather than bit wise thereby reducing the brute force to even lesser than $2^{64}$ tries. So this means that AES256 with even a 32 character password will be weaker than AES256 with a randomly generated key.

So why isn't this a concern? Or am I missing something?

Using slow KDFs will mitigate some of the security lost by using a human chosen password instead of randomly generate AES-256 - however is there any analysis on this?

$\endgroup$
3
  • 2
    $\begingroup$ It's a concern. But you seem to have missed the issue is mitigated to some degree with special, purposely slow KDFs for password, like Argon2, and before that the obsolete PBKDF2. You should study this line of defense. Still a nice question, especially if you add: how many extra bits of entropy can these mitigating measures realistically give? How does technical progress affect security of password-based cryptography, for short-term and long-term secrecy? $\endgroup$
    – fgrieu
    Sep 22 '21 at 6:51
  • 1
    $\begingroup$ @fgrieu - I do know about slow KDFs are always used (or rather always to be used). However, is there any analysis about how much mitigation they do actually provide - i.e. the comparison of a brute force attack on a randomly generated 256 bit key against a 256 key generated from a n-character password using a slow KDF. Which would give guidelines as to how many character password should be chosen & also how many rounds of which KDF will bring back the security against a brute force attack back to the same as a 256 bit key $\endgroup$
    – user93353
    Sep 22 '21 at 8:16
  • $\begingroup$ The above clarifies password-hashing is relevant to the question. I added this tag, and recommend 1) review of how the question is different from Password entropy much lower than entropy of encryption keys. Why is this acceptable? and others tagged password-hashing. 2) Then either change of at least the last paragraph to make what's asked more precise (like by incorporating some of the above comment), or deletion of the question if duplicate. $\endgroup$
    – fgrieu
    Sep 22 '21 at 9:44
5
$\begingroup$

The key size for AES is chosen as 256 because that's considered the minimum keysize which can protect against a brute force attack - i.e. $2^{256}$ tries.

That's not right, $2^{128}$ or - more accurately - a key size of 128 bits for $2^{127}$ tries on average is considered plenty, certainly against any practical attack.

However, in practice, for a lot of applications, a user chosen password is used to derive the 256 size key using a KDF. Let's say the application mandates a 8 character password - that's a 64 bit password - so the brute force reduces to $2^{64}$ tries. And it probably reduces even more because a byte from a common password has much lesser entropy than a byte from a key.

64 bits is a vain hope, human generated passwords average to about 40 bits. Of course, even well chosen passwords of 8 characters will generally use a subset of ASCII, which itself is a subset of all possible byte values. With all 24 special that are generally used I get to 86 values out of 256, i.e. $log_2(86) \approx 6.43$ bits of entropy per byte, or $\approx 51.41$ bits for 8 such characters. But that's only when perfect distribution is assumed, and humans are terrible at generating random values.

The brute force can be tried byte wise rather than bit wise thereby reducing the brute force to even lesser than $2^{64}$ tries.

Normally you would try against previously known passwords from broken databases or dictionary attacks. You would not try willy-nilly. Other attacks are possible if the implementation is broken, for instance if no salt is used within the key derivation.

So this means that AES256 with even a 32 character password will be weaker than AES256 with a randomly generated key.

Yes. A back-of-napkin will show you that you're missing $16 \times 1.5 = 24$ bits at the very least.

So why isn't this a concern? Or am I missing something?

It is a huge concern, generally you'd try and avoid using passwords at all. Otherwise you'd use a Password Based Key Derivation Function that applies key stretching such as one of the Argon2 variants (PBKDF2, scrypt and bcrypt are probably better known). But these only provide a small protection for each key derivation. It's about 20 bit for a million iterations (as $log_2(1,000,000)$ is close to 20). It certainly won't lift you to $2^{128}$ for generic passwords; $40 + 20 = 60$ bits, so breaking encryption would be expensive, but far from infeasible.

Where passwords cannot be avoided it is recommended you'd use a password manager, use e.g. 12 character passwords that are randomly generated (possibly require some symbols to be present, in case you get unlucky). That won't get you close to 128 bits, but it would be enough deterrent for anybody trying brute force or similar techniques. It is of course also possible to use 32 random hex characters and simply store a key, assuming that there are no limits to password size.

A simple trick shows that you can use $$l_p = \bigg\lceil {l_k - \log_2(i) \over log_2(N)} \bigg\rceil$$ as way of knowing the number of characters for each password, so say we use the values above: $$\bigg\lceil {128 - \log_2(1,000,000) \over \log_2(86)} \bigg\rceil = \bigg\lceil {{128 - 20} \over 6.43} \bigg\rceil = 17$$ extended character password to reach 128 bits using a KDF with 1,000,000 iterations, assuming it is perfectly random.

One way of avoiding this is to use public key encryption, and keep the private key secure. One step of protecting the private key used for decryption may be password based encryption, but you can start by keeping it on a memory stick, for instance, so that an attacker simply doesn't have access to it when it is not needed. There are of course many other ways of secure key storage.

Note that this is less of a problem when counter measures can be taken. E.g. a PIN is generally only 4-6 digits, but the fact that you can try only three times protects it against attacks (PUK codes are generally much larger, as they don't usually block, as that could lead to denial-of-service attacks). However, for e.g. file encryption offline attacks can generally be assumed.

$\endgroup$
2
$\begingroup$

Maarten's answer is good, but doesn't mention that it's possible to have human-memorable typeable passphrases with >128 bits of entropy rather easily. The Diceware system uses a good RNG (high-quality dice or a CSPRNG) to pick "characters" from an enormous "alphabet": instead of using single English letters (or ASCII characters) the "characters" are entire words, and the "alphabet" is a list of 7776 words (or 1296 words for their "short" lists).

With 7776 words you get 12.9 bits of entropy per word, with 1296 words you get 10.3 bits of entropy per word. So a 10 word phrase using the 7776-word dictionary like "ChompBuggyOkayPlatonicGrafted.KiltDecreeRecessOpacityUnedited" has 129 bits of entropy, and is a good choice to secure a password manager's database. The "." in the middle is just an easy-to-remember easy-to-type symbol to help break the passphrase into two 5-word passphrases, which makes memorizing the whole thing easier.

I use several such phrases. One for each of my computer logins, and one for my password manager. I wouldn't want to memorize too many of them (it's still a decent amount of effort), but having enough to keep logins and the password manager secure is fine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.