Relationship of password strength and key strength

Question

I have just started educating myself about cryptography, and while it is mostly making sense, a few things are still eluding me. One being:

In systems that take a user's pass-word/-phrase in order to derive the encryption key, what is the relationship between that password's strength and the key's strength? I know password strength matters in authentication; is it a moot point in encryption?

From my understanding, human-created passwords tend to have very low entropy, and that's why keys are derived from them. Assuming then that both the key and algorithm are (relatively) secure, the encryption is (relatively) secure.

But while that 128-bit (or whatever) key may be all fine and dandy, what's to prevent an attacker from running lists of weak passwords through the key derivation function and then attempting to use the produced key to decrypt the message?

My hunch is it has something to do with the computational cost.... but I AM curious if it's just as secure to use the letter "a" as the password as it is to use a super strong password -- i.e. if the derived key will be just as strong regardless of input, does the password's composition matter at all?

Answer 1

Overview

1. Some examples for review/discussion.
2. Alternative: local password generated key for internal use in encryption-key access control API.
3. Entropy and increasing it.

---

1. Some examples for review/discussion

In systems that take a user's pass-word/-phrase in order to derive the encryption key, what is the relationship between that password's strength and the key's strength?

This depends entirely on how you use the password to derive the key. If you're just hashing, or even hashing and salting your password, your function might look like this:

generateKey(password, salt) := cryptoHash(password, salt)

If I took a table of the weakest passwords I could probably calculate the potential hashes, and from there I would have the possible encryption keys. Then given a message I could crack it with this function:

crack(message, saltLen, weakPassList):=
    for salt in 0..saltLen:
        for weak in weakPassList:
            let k := generateKey(weak, salt)
            if decrypt(message, k) looks okay:
                return k

This might take a really long time to run based on how big saltLen and weakPassList are; however you could cache the k generated above in a table and just try them out one at a time, to eliminate the factor of experimental key generation.

There are definitely better ways to generate a password, but without a more detailed specification or use case it's difficult to analyze or recommend which method is best.

2. Alternative: local password generated key for internal use in encryption-key access control API.

I know password strength matters in authentication; is it a moot point in encryption?

I feel like there's no difference unless you are talking about a particular method of key generation or some other specific use case. A key is a key.

Personally I'd go with using the password to generate a local encryption key kLocal, used to obscure a properly generated cryptographic key kMessage that can be used to encrypt messages for sending over non-secure channels.

This way the password is just an access control mechanism to filter users who can type commands into the system, and prevent them from using each other's encryption keys (if they can't get the right kLocal they can't discover the contents of kMessage). This is apt because you can use a secure API with, for example, a leaky bucket, to prevent people from doing password guessing attacks on the local machine.

It's not as straightforward to prevent password-guessing attacks against a ciphertext message that's already been sent out in the open! By making the password-generated kLocal for internal, API-restricted usage only, you bound the attacker's effective computation power, which is a really good thing in software security.

3. Entropy and increasing it.

From my understanding, human-created passwords tend to have very low entropy, and that's why keys are derived from them.

Be careful! Entropy is just the measure of how unpredictable something is. If I take some values with X amount of entropy, and run them each through some adversary-known function, the results can have no more than X entropy. That is, if the adversary could guess the original values and also knows the function for manipulating/extending them, he'll have just as easy of a time guessing the manipulated/extended values as he would the originals.

You're not increasing the size of the domain unless you add more information; and you're not increasing the entropy unless the information you add has some entropy itself (is somehow unpredictable/secret).

Answer 2

In systems that take a user's pass-word/-phrase in order to derive the encryption key, what is the relationship between that password's strength and the key's strength? I know password strength matters in authentication; is it a moot point in encryption?

From wikipedia: Password strength is a measure of the effectiveness of a password in resisting guessing and brute-force attacks. In its usual form, it estimates how many trials an attacker who does not have direct access to the password would need, on average, to guess it correctly. The strength of a password is a function of length, complexity, and unpredictability.

So you correctly surmised that password strength is relevant to authentication. If we're expanding our password to match the key size using a cryptographic hash function such as SHA-1, then the strength of the password isn't relevant to encryption.

But while that 128-bit (or whatever) key may be all fine and dandy, what's to prevent an attacker from running lists of weak passwords through the key derivation function and then attempting to use the produced key to decrypt the message?

Time cost is the main opponent to this sort of brute-force attack.

Per wikipedia, The resources required for a brute-force attack grow exponentially with increasing key size, not linearly. Although US export regulations historically restricted key lengths to 56-bit symmetric keys (e.g. Data Encryption Standard), these restrictions are no longer in place, so modern symmetric algorithms typically use computationally stronger 128- to 256-bit keys.

The same page postulates that breaking a 128-bit symmetric key (such as AES) would require about 10^18 joules of energy, or around 30 gigawatts of power for a period of one year. This is more than one hundredth of the world energy production.

Of course, the only way to guarantee the safety of the encoded data is simply to prevent it from falling in to malicious hands.

My hunch is it has something to do with the computational cost.... but I AM curious if it's just as secure to use the letter "a" as the "password" as it is to use a super strong password.

If the attacker can correctly guess that your encryption key is derived from a plain string, and correctly guess that the originating string was "a" (or some equally foolish password), then you're in trouble. Choosing good passwords is important.

You can also employ a tactic called "salting" where you add some random entropy to the password. The salt string is typically stored in the same location as the password and doesn't get encrypted, so it won't save you if, say, you lose a database of encrypted customer data; however it will obscure the key derivation process if the attacker is accessing your data through authentication and it will eliminate any pre-computed rainbow tables which were generated with a different salt, or no salt.

Answer 3

A few things can be put in place to frustrate attackers. Best practice in using key derivation functions is making the derivation function deliberately slow to prevent brute force attacks to reveal the input value. The use of a salt (e.g. 64bit in modern implementations) together with the input value would be used to complicate dictionary attacks. This approach is referred to as "key stretching".

Going further, "key strengthening" uses the same technique but in addition securely deletes the salt forcing attackers as well as users to do a brute force search for the salt further complicating brute force attacks. A possible implementation in this case would be to to divide the salt into a public part and a private part where the private salt would need to be brute forced. Given the correct password input and the public salt brute forcing the private salt is feasible. However, if brute forcing without the original password having to also calculate the private salt creates an additional obstacle.

Of course, the strength of the chosen input value (commonly the password) is an important factor in security.

Answer 4

What I understand you to mean is, could someone use a brute-strength attack on the key directly (without using using password-guessing to generate different keys) any easier if it were generated with a weak password than with a strong one? If that is your question, then the answer in the vast majority of cases (and certainly with any recently implemented cryptosystem) no. Keys are generated (as other answers have indicated) with hashes done on a combination of your password and (in most cases) some random "salt", which is just some random garbage generated at the time and stored in plain view. The only reason for the salt is to make it so people can't pre-guess keys based on common passwords. Even without it, though, the key generated by even a 1-bit password will produce a key that is still truly random looking. This is because modern hash algorithms are very effective at producing random garbage from even very small inputs. They are designed so changing even one bit results in a completely different hash. No person would be able to look at such a key and think, oh, that one was produced with a weak password.

Passwords are still, as others have indicated, very important. Key stretching, the act of taking a password and running it through a hash many (possibly thousands) of times to make it computationally hard to guess lots of passwords, can help you, but is subject to reduced value by Moore's law just like everything else. By that I mean what takes a lot of time to do today, doesn't necessarily take a lot of time tomorrow. But you don't really have to worry, with any modern cryptosystem, that the key will be directly attackable. Just pick a good password.