# Importance of salt when deriving an encryption key

I'm very curious to know this and a bit confuses too:

1. Suppose, I have two files encrypted using AES-128bit with keys PBKDF2-derived from the same password and the same salt. If an attacker does brute force attack (imagining that he finishes this) to crack the keys, I'm guessing he needs to run the attack once to get those 2 keys.

2. Now, if I encrypt the files using AES-128bit with keys PBKDF2-derived from the same password and a different salt, will it make the attacker run brute force twice? If the answer is yes, then why? Changing the salt doesn't change the number of possible keys $2^{128}$.

If the answer is no then, in both cases the number of possible keys are $2^{128}$. So, what difference does it make if the salt is different?

-
the brute force attack is against the password, not the key. The purpose of the salt is so the key is not the same if the password is the same. Password recovery on one can allow key recovery of the other. –  Richie Frame Jul 19 at 9:46
@otus, not at all. You just gave my question a smart look. Thanks. –  Giliweed Jul 19 at 10:24

There are two ways to attack encryption that uses a derived key:

1. You can attack the encryption algorithm. In the case of correctly used* 128-bit AES, that essentially amounts to a brute force attack on the 128-bit keyspace.

This would succeed after on average $2^{127}$ tries (if it were practical). If you knew that two files had used the same password salt, you could brute force the key of one, then check if it also decrypts the other, meaning you'd find both with about $2^{127}$ tries when they share a password. If they had a different salt, there would be nothing special about the first key with respect to the other file – you would need a total of $2 \cdot 2^{127}$ tries.

The difference here is fairly meaningless, since both are impossible to break if AES is secure.

2. You can try to derive the same key. This means guessing the original password, deriving your own key, then trying whether it's the correct key by using it to decrypt.

The time the latter takes depends on the chosen password. Most ways humans generate passwords have much less than 128 bits of entropy, so a dictionary type attack could be faster than breaking the encryption. RFC 2898, i.e. PBKDF2 adds computational complexity to each password guess, by default making you use 1000 HMAC (2000 hash function) iterations in addition to the AES decryption. Call it $2^{b+11}$, where b is the entropy of the password.

Here, if you could find one password, you could try the same password with other files regardless of the salt. So if you knew the the same password was used for all files, salts would add ~no extra protection (just one extra key derivation per file at the end).

The situation where salts do matter is where each key is derived from a separate password. Finding one password (2. above) doesn't give you significantly more information to break others in that case. The best attack is to try the most common password for each, then the next most common password, etc. However, you need to only derive a key-guess once for any number of files that share a salt, meaning the complexity is related to the number of files with unique salts rather than all files.

* Per file AES keys do make correct implementation a bit simpler, since you don't have to worry about IV collisions or e.g. running into a per key data cap, but the fact that you then have to worry about salt collisions may outweigh any benefit.

-
what's a "per key data cap"? –  Giliweed Jul 19 at 10:45
@Giliweed, that was my fairly ambiguous way to refer to the amount of data you can safely encrypt with one key. I'll add a link to a relevant question. –  otus Jul 19 at 11:08
interesting link but I did not understand the maths. Anyway, "you would need a total of (2⋅2)^127 tries." --- how did you calculated the extra .2? can it increase to .4 or .8? Or is it fix when the password and salt being same? –  Giliweed Jul 19 at 11:31
@Giliweed, it is not $(2\cdot 2)^{127} = 2^{254}$, but $2 \cdot 2^{127} = 2^{128}$. The multiplying 2 is the number of files (with different keys) to break. –  otus Jul 19 at 11:38
now its clear to me, its the two files that you multiplied. Anyway, how do you manage to write 127 in small and in the left corner of 2, what is command to do that? I see no option to do that here. I can't even copy paste it. And strangely your name gets removed even if I write @otus in the beginning. Any idea why is it happening? –  Giliweed Jul 19 at 11:52