Mechanism of PBKDF in encryption key generation with passphrase I want to roughly understand how the mechanism works of generating an encryption key from a passphrase, by which we encrypt a volume or file.

I'm familiar with public key encryption, the concept of a salt and the password hashing approach to password verification. A salt prevents attackers from precomputing a dictionary of derived keys.

I don't understand the main merits of deriving an encryption key from a passphrase, by which we then encrypt the data. From what I've read, it's key stretching- and strengthening that accounts for the main merit; a longer- or higher entropy key is more secure that the supposedly weak passphrase.

My first confusion arises from the random nature of the derived encryption key. Shouldn't this be a deterministic process? A passphrase should correspond to a certain unique hash, in order to verify it?

As a whole, I find this mechanism quite vague at the moment, and would love some elaboration on it. :)

Update

The salt is the only random component, which is passed with the encryption key. Hence, the key derivation key is deterministic, indeed.
The salt is indeed randomly generated. If the salt is random then it becomes impossible to pre-calculate the hash, thus making it impossible to build a lookup table hash -> password called a rainbow table. The salt only has to be unpredictable and unique, so the amount of security relying on the salt to be unique is relatively small.

Once the salt is known it is stored so that the password derivation is otherwise deterministic. This lets you regenerate the same hash for the same salt &amp; password combination (and the same work factor or iteration count).



Key stretching (or rather, key strengthening) may need to be used within PBKDF's because the input key material is generally not strong enough to be used as a key. A password commonly has only around 50 bits of security or so. Key strengthening can add a few bits of security if the password isn't strong enough. This adds an amount of of work to an adversary per password tested.

Key strengthening makes it infeasible to perform a dictionary attack against a large amount of hashes in a database, as each password / salt combination should be tested, and each test would be a relatively large amount of work. This comes at a cost of course: each time the password hash is generated the work factor is also incurred on the user.

Note that the output size of the resulting key doesn't increase the amount of randomness of the input keying material. So just outputting a larger amount of bits won't increase the security. Outputting a 128 or 256 bit AES key won't increase the security if the input keying material has a lot less entropy than the input key.



A password should not correspond to a unique hash. A password / salt combination should, for a given password hash and work factor, correspond to a certain hash.

Otherwise you or anybody else could be using the same password for different purposes, and the calculated hash would be identical at the different locations. This leaks information about the password, possibly even leading to compromise of the hash, for instance if somebody would use the same password and finds out that the hash is repeated elsewhere.