PBKDF2 and salt

Question

I want to ask some questions about the PBKDF2 function and generally about the password-based derivation functions.

Actually we use the derivation function together with the salt to provide resistance against the dictionary attacks, right? One example is the UNIX encryption scheme.

My first question:
For example, if want to encrypt a piece of data in a card and I use the password to derive a new key using the PBKDF2 function, usually the salt is stored unencrypted, right?

But if an attacker get access to the card and find the salt then the only security we have is the password again, isnt it? So, why do we store the salt in the clear? I know that it makes it harder for dictionary attacks, but if someone gets access to the card, then we are in the first where the only precaution is the length of the password, right?

Also, we have the same scenario:
We have the password and we want to generate a new key and we use the PBKDF2 or any other function(I know it has the HMAC as generator). Until now, I didn't find anywhere explaining whether the result of the function, the actual key is stored or not?

Also, given the password, how do we know whether the password is the right one, in order to derive the actual key?

Answer 1

First, realize that PBKDF2 is PKCS #5 is RFC 2898, i.e. http://www.ietf.org/rfc/rfc2898.txt

It's essentially an algorithm to securely hash a password as many times as you want, with whatever hash you want. OWASP recommends hashing the password at least 64,000 times in 2012, and doubling that every two years, per https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet

Note that storing (also in cleartext) a variable number of iterations per user also helps. Instead of always running PBKDF2 64,000 time, instead generate a random salt, and a random number I between 1 and 20,000. Run PBKDF2 64,000 + I times for that particular username. This makes cracking it just a little more difficult, and may prevent certain optimizations in cracking code from being useful.

Actually we use the derivation function together with the salt to provide resistance against the dictionary attacks, RIGHT?

Essentially - we salt the cleartext passphrase prior to hashing it.

My first question : ... usually the salt is stored un-encrypted, right?

In simpler implementations, a long (8 bytes or more), cryptographically random salt is stored unencrypted and regenerated with every password change. OWASP (link above) recommends additional precautions including having an additional salt stored in a config file somewhere (i.e. not stored in the database), another portion hardcoded in the source code, and storing the per-user salt in a different location than the password, perhaps a flat file vs. a database (or vice versa). Note this ideally also requires passwords and salts be backed up to different locations as well - the goal is to make it harder to steal both salts and passwords with one theft.

Also, we have the same scenario : we have the password and we want to generate a new key ... Until now, I didnt find anywhere explaining if the result of the function (the actual key( it is stored or not?

That depends. If you're using PBKDF2 to generate a key for realtime encryption during this session only, then no, it should stay in memory only, and be discarded at the end. If you're using PBKDF2 to generate a hash (after N iterations) to authenticate a user later, then you must save that hash.

I know is make it harder for dictionary attacks but if someone get access to the card i store it then we are in the first where the only precaution is the length of the password right

No, the only precaution is the strength of the password. "P@ssw0rdP@ssw0rdP@ssw0rd" is a bad password, even if it is 24 characters long and "complex". If you're going to be "registering" users, or letting them choose passwords, you need to reject any password in the most common cracking dictionaries. Further, when you're testing for rejection, you need to apply the same kind of rules that rules based dictionary crackers like Elcomsoft or Hashcat use - translate to 1337 speak, add 1 to 1000 after it, add random characters to the front and back, double it, etc. This is thankfully easier on the front end, since you can simply reverse-translate 1337 speak and lowercase it, so both P@ssw0rd and Passw0rd end up as "password", which should be filtered out as horrible. Melinda2006 is always a bad password, as is 12345.

Also, given the password how do we know if the password is the right password in order to derive the actual key?

You don't know beforehand; you just try it. If it works, it was right. If it doesn't work, it was wrong. Now, by "works", again, it depends. For realtime decryption, you'd attempt to decrypt the message; you would then compare the HMAC you saved with the message (prior to encryption) with the values; if the HMAC doesn't match, it's a forgery, part of the message was altered, you have a bug, or the password was wrong. For authentication, you collect the salt value that should have been used, and then re-hash the password the same number of times. If you get the same hashed result, the input must have been the same, and so it was right.

Answer 2

Password based key derivation functions generate a key suitable for ciphers from a given password. It relies only on the original password being kept secret.

The purpose of the salt is simply to prevent the use of rainbow tables. A rainbow table would have to be made for each salt, and if (as is common practise), each user has their own salt, a rainbow table would have to be constructed for that particular user. In general it is not assumed to be secret.

Salts are used in conjunction with a higher number of iterations inside the PBKDF function to hinder any attempt to create a rainbow table.

The key derived from the PBKDF2 is stored somewhere

I think maybe you've confused a cryptographic hash of a password that is stored for authentication and PBKDF (which can use an underlying cryptographic hash) to 'stretch a password' for use in encryption.

The generated key should not be stored anywhere (unless itself suitably encrypted). The generated key is used for encryption. When the data is to be decrypted, the user should be prompted for the password, and the key is generated again. This generated key is then used to decrypt the data.

How do we know that the password we gave is the right one in order to perform the PBKDF2 function?

When encrypting data you should also be including message authentication (MAC). This generally means encrypting message || MAC. You would decrypt the data using a (potentially false) key. And then check to see if the MAC and message correspond. If they don't, either the key was false or otherwise the ciphertext has been tampered with.

Alternatively you could hash the password. Though a PBKDF can be used for this, it should be clear that a different salt must be used (even if you don't use the same algorithm).This hash is stored. When the user enters their password you hash it, and check it with the stored hash, if they match you proceed to generate the encryption key, and decrypt the data.

Answer 3

I found responses provided by Stephen Harris and PBKDF2 Answers very useful. I just wanted to add my two cents on authenticated encryption and verification of the ciphertext without actually decrypting it.

In PBKDF2 Answers' response computing HMAC prior to encryption was suggested:

For realtime decryption, you'd attempt to decrypt the message; you would then compare the HMAC you saved with the message (prior to encryption) with the values; if the HMAC doesn't match, it's a forgery, part of the message was altered, you have a bug, or the password was wrong.

However, in my search I found that encrypt-then-authenticate is better than authenticate-then-encrypt:

Abstract... We show that any secure channels protocol designed to work with any combination of secure encryption (against chosen plaintext attacks) and secure MAC must use the encrypt-then-authenticate method.

Hugo Krawczyk - The Order of Encryption and Authentication for Protecting Communications (Or: How Secure is SSL?)

Recently, I wrote a wrapper class for using the AesCryptoServiceProvider .NET class to encrypt and decrypt files. In my implementation, three salts saltAuth, saltHMAC and saltEncrypt are generated with a cryptographic random number generator, and then:

1. PBKDF2(password, saltAuth, iterations1) gives hashAuth
2. PBKDF2(password, saltHMAC, iterations2) gives keyHMAC
3. PBKDF2(password, saltEncrypt, iterations2) gives keyEncrypt

If encrypted data is stored in the following order:

1. saltAuth
2. hashAuth
3. HMAC(saltHMAC | saltEncrypt | ciphertext, keyHMAC), '|' implies concatenation
4. saltHMAC
5. saltEncrypt
6. ciphertext

Then, upon a request to decrypt data:

1. hashAuth can be generated and compared to verify the authority to decrypt.
2. Upon verification of authority, keyHMAC can be generated to compute HMAC which is then compared with the stored value to detect tampering.
3. If no tampering is detected, then keyEncrypt can be generated and decryption can be performed.

Answer 4

Quoting NIST 800-132:

The purpose of the salt is to allow the generation of a large set of keys corresponding to each password, for a fixed iteration count.

To put it another way, if two people happen to use the same password on implementations using the same iteration count, they're highly likely to get different keys - and that's a very good thing.

Answer 5

1) the salt must be stored in clear or encrypted?

Either, the salt is only part of the protection, it helps if hackers don't know what it is, but even if they do they can't use rainbow tables. If you encrypt it then you also have to decrypt it, which means that only add defence if the hackers compromise your [user] table but don't compromise your code-base.

Most PBKDF2 implementations store a random salt with the password hash (so you end up with a format like salt + salted hash) - this is enough to force regeneration of every password and stop any rainbow tables from being used.

2) The key derived from the PBKDF2 is stored somewhere

Nope, the PBKDF2 can't be decrypted, that's the point. Do you mean the result hash? Store it where you like, but if it's likely to easily compromised use more iterations.

3) How do we know that the password we gave is the right one in order to perform the PBKDF2 function?

By re-hashing it.

An example PBKDF2 implementation goes something like this:

User sets password:

• Random fixed length salt is generated (most often 128 bit)
• Salt added to password
• Salt and password run through hashing algorithm (usually an SHA variant) at least 1,000 times but often lots more.
• Unencrypted salt and hash added together and encoded to a string for storage.

You check a password against a user:

• Get the saved hash.
• Read the first 128 bits (or whatever) as the stored salt.
• Add the salt to the new potential password and run through the same hashing algorithm.
• Check it matches the saved hash, if it does the passwords match.

Note that the salt isn't encrypted, it's stored with the hashed result. You don't have a key anywhere that can decrypt the hashes - the only way a hacker can get in is to brute force the passwords and PBKDF2 is designed to be slow to make that hard.

Answer 6

The salt that is used with a PBKDF is not a confidential information, it only needs to be different (with very high probability) for each encryption key that is generated from the password. The actual password is the confidential information that needs to be protected! Therefore, it is perfectly "safe" to store the salt together with the encrypted data. The actual key is never stored anywhere. It is only kept in memory for a very short time. The key will be re-computed, from the user-provided password and the stored salt value, whenever it is needed.

---

One important reason why an individual salt shall be incorporated into your PBKDF-generated encryption key is this: For an attacker, "breaking" the encryption key (of sufficient size, e.g. 128 bits or more) directly via brute-force method, is practically impossible – there simply are way too many combinations. However, instead of trying out all possible keys (which would be way to slow!), the attacker can try out many possible passwords and hope that a "weak" password was used.

Testing all possible passwords up to a certain length, or performing a dictionary attack, is very possible! But, if the attacker is testing many passwords, then each password must be "translated" into the corresponding encryption key, by applying the PBKDF, before it can actually be tried on the encrypted data. That is why this kind of "password cracking" attack is easily thwarted by deliberately making your PBKDF very slow, e.g. by using a large number of iterations, so that the attacker can only test a tiny number of passwords in reasonable time. Meanwhile, if you are the legitimate owner of the file and you do know the correct password, then the PBKDF only needs to be applied once, so that the slowness of the PBKDF is not an issue for you.

Still, the attacker may generate a huge table containing pre-computed keys for a large number of possible passwords. This table only needs to be computed once - at least if no salt was involved in the generation of the keys! The pre-computed keys then could be tested quickly on a large number of encrypted files. This is a bit similar to "rainbow tables", even though rainbow tables are a special data structure specifically for "reversing" password hashes, so it is not exactly the same. Anyway, by incorporating an individual salt into the PBKDF-generated key, the "table-based" attack is easily thwarted: Now the generated keys depend on the password and on the individual salt, making any pre-computed keys useless for the attacker – as long as the salt does not repeat.

---

Another important reasons why an individual salt should be used in the PBKDF process is because this way we can generated an individual (different, with very high probability) encryption key for each file to be encrypted - even when the same password is re-used many times! Be aware: There are certain attacks that apply, iff multiple (different) files were encrypted with the same key.

---

Also, given the password, how do we know whether the password is the right one, in order to derive the actual key?

You derive the key from the given password and the stored salt value, then try to decrypt the data with that key. If the "decrypted" data comes out as random garbage, then the password (and thus the derived key) was probably wrong. Often there is a "checksum", e.g. a MAC, included with the encrypted data, so that you can actually verify whether the data was decrypted correctly.

As an aside: In TrueCrypt, the plaintext header literally contains the ASCII string "TRUE", which can be used to check whether the header was decrypted correctly or not.