Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

migrated from stackoverflow.com Aug 9 '12 at 13:51

This question came from our site for professional and enthusiast programmers.

    
possible duplicate of stackoverflow.com/q/1219899/639891 –  dungeon Hunter Aug 8 '12 at 18:11
    
My questions are: 1)the salt must be stored in clear or encrypted? 2) The key derived from the PBKDF2 is stored somewhere ? 3) How do we know that the password we gave is the right one in order to perform the PBKDF2 function? –  thrylos_7 Aug 8 '12 at 19:02
add comment

4 Answers

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.

share|improve this answer
    
Do you any email account to discuss some issues? or something similar for a better conversation? –  thrylos_7 Aug 9 '12 at 12:03
    
given a password the PBKDF2 will derive a key from the hash of salt and password, right? This key is going to encrypt some data that i want to be protected. You are answer in the second question is that, the key must be stored somewhere. My question is : If that key is stored somewhere without any protection, then if an attacker get access to place i stored then he has the actual key, right? –  thrylos_7 Aug 9 '12 at 12:16
    
@thrylos_7 - that's not really what PBKDF2 is for. If you want to protect and encrypt/decrypt data you need a public-private key pair. PBKDF2 is designed for use with passwords - it creates one-way hashes that are very hard to brute force attach, but that can be checked when a user puts their password in. As PBKDF2 can't reverse its algorithm there's no need to store a decryption key. If you want to decrypt data then you need to hold the decryption key somewhere, but that can be the public key. –  Keith Aug 9 '12 at 13:09
    
@thrylos_7 - also, as PBKDF2 is designed for use with passwords it's very slow (which doesn't cost much on a password check but makes brute force attacks much tougher). If you want to create lots of hashes (for instance in secure communications) you want a quicker algorithm like SHA256. –  Keith Aug 9 '12 at 13:17
1  
Actually, while PBKDF2 can be used for simple password hashing (and is actually quite good for it), what it's actually designed for is deriving encryption keys from passwords. That's what the acronym "PBKDF2" stands for: "Password-Based Key Derivation Function, version 2". –  Ilmari Karonen Aug 14 '12 at 21:34
show 2 more comments

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.

share|improve this answer
    
Would it be inappropriate to use PBKDF2 for both authentication and password stretching (assuming different salts)? –  Eyal Aug 16 '12 at 10:12
    
@Eyal - could you ask this as another question? Based on this memo (section 3), I believe you can just use PBKDF2 to produces a (let's say) 256-bit key, and split that into 2 keys of 128-bits one used for MAC & the other encryption. But I'd like to know what others think. Or do you mean use it generate a key and also a hash for password storage? In any case, I think this is worth a new question. –  Stephen Harris Aug 16 '12 at 10:32
add comment

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.

share|improve this answer
    
I think the "random number of iterations" stuff does not really add any security, and adds more complication to the code. –  Paŭlo Ebermann Aug 10 '12 at 8:24
    
@paulo-ebermann Why do you think "random number of iterations" doesn't add any security? Could you please elaborate? –  Franklin Nov 5 '12 at 19:53
    
@Franklin This just makes the cracking time vary between the individual password entries, so an attacker would first attack the ones with a lower number (if it is significantly lower). Instead of this "just a little bit harder" one could just use the maximum number for all passwords, making it harder for all attackers. –  Paŭlo Ebermann Nov 5 '12 at 20:29
    
@paulo-ebermann Interesting. But what if (hypothetically speaking), the password was a FIVE digit PIN and the EXTRA "random number of iterations" (apart from the 64,000 iterations) to be done was the absolute value of the middle 3 digits? –  Franklin Nov 5 '12 at 20:50
    
@Franklin: As the attacker is just trying to guess the password, for each try this additional number is known. Yes, it needs a bit of additional code (both for attacker and legitimate verifier), but no significant additional computation. –  Paŭlo Ebermann Nov 12 '12 at 20:54
add comment

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.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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