# 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.

• Ah. Why do you think that a key is non deterministic, when it pops out of a key derivation function? Consider - how could it possibly be non deterministic yet repeatable? – Paul Uszak May 5 '18 at 23:36
• The main thing is to consume substantial CPU time and memory to slow down a brute force attack. Generally an iteration count is chosen such that it takes around 100ms, that is a substantial increase in the level of difficult , in time, of a brute force attack. – zaph May 5 '18 at 23:47
• WRT "random nature of the derived encryption key" the salt which is the random component, is not secret and can be passed with the encrypted data. – zaph May 5 '18 at 23:49
• @zaph So, if an attacker whould use brute-force, it will have to iterate over all passphrases computing the encryption key in each iteration. Can't lookup tables be used to derive the passphrase for a specific KDF? That is, if a weak salt is used. – Mussé Redi May 6 '18 at 6:40
• The point it is that creating a lookup table for every possible input times every salt times many iteration counts times 100ms per calculation is not possible. – zaph May 6 '18 at 10:44

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 & 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.

• The function of a salt, is to protect against dictionary attacks, and, more broadly, to increase the entropy of the passphrase, right? I mean, in a sense, the concatenated string consisting of the passphrase and the salt could be interpreted as the new/improved passphrase. Notwithstanding that the use of a salt also distinguishes cases were the same passphrase is used, with different keys for the same passphrase. – Mussé Redi May 6 '18 at 20:14
• No, because the salt is considered public to the adversary. So from the view of the adversary, the salt cannot increase the entropy. The salt is just there so the hash is unique for the given password, even if the password is repeated given a different salt. – Maarten Bodewes May 6 '18 at 20:30
• As an example, OpenSSL uses password based encryption where the ciphertext consists of a magic value: "Salted__" in ASCII, followed by an 8 byte salt and then the actual ciphertext. So the salt is communicated together with the ciphertext; without it the receiver cannot decrypt the data. – Maarten Bodewes May 6 '18 at 21:04
• How does one then distinguish the salt from the cyphertext when using OpenSSL, given that immediately follows the other? – Mussé Redi May 6 '18 at 21:08
• It's 8 bytes, just after the 8 byte magic value. That's all there is too it, it isn't marked otherwise as it is simply always in the same place, using the same (relatively bad) password derivation mechanism. And the choice of using password or key encryption is performed by the user, not the ciphertext. It's not a particularly good scheme but it is the one that is easy to explain and the first one to pop into my head. – Maarten Bodewes May 6 '18 at 21:17

When you derive an encryption key from a password, and perhaps a salt, the encryption key is indeed a deterministic function of the password and salt, $$k = H(\mathit{password}, \mathit{salt})$$.

Presumably the adversary does not know the password, so although the derivation is deterministic, the adversary is about as uncertain about what the key is as they are uncertain about what the password is: at best, they know a probability distribution on possible keys, determined by the salt and the probability distribution on possible passwords.

As you noted, the use of a salt per encryption key prevents the adversary from sharing effort when attacking many targets at once, e.g. with Oechslin's rainbow tables, which traditionally trade memory and communication to reduce hash evaluations at about the same net cost, but which can be parallelized to get an answer faster at substantially lower net cost.

The cost of an attack is measured in storage, computation, communication, number of times we must evaluate $$H$$, and cost of each evaluation of $$H$$.

One definition for the ‘security level’ of a cryptosystem in bits is the exponent of 2 in the expected cost of an attack on a single key, by which metric AES-128 has about a 128-bit security level because it costs an expected $$2^{127}$$ evaluations of AES-128 to break a single key. Another more realistic definition is the exponent of 2 in the expected cost of an attack on all plausible numbers of target keys, by which metric AES-128 should not be considered to have a 128-bit security level.

For a password hashing scheme, the expected cost of an attack depends on the probability distribution on passwords. If they are chosen uniformly at random from $$2^t$$ possibilities, and each one has a unique salt so that Oechslin's rainbow tables don't help to save work, then breaking the first of $$n$$ keys with probability $$p$$ costs about $$2^t p$$ evaluations of $$H$$ along with negligible storage, communication, and other computation costs.

If you picked passwords uniformly at random from $$2^{128}$$ possibilities, then this would be the end of the story, and any old preimage-resistant hash function like MD5 would work just fine: the number of MD5 evaluations is so high that any attack on any number of targets is infeasible. But humans don't pick passwords like that, unless they ask for computer assistance like they should but invariably don't, in addition to their various other basic flaws like inability to fly.

So password-based key derivation functions also raise the cost of evaluating $$H$$, such as by iterating a fast hash function such as SHA-256 with no shortcuts, and by using as much memory as you're willing to devote to it, as scrypt and argon2 do. If the cost of evaluating $$H$$ is $$2^c$$ times the cost of evaluating some basic hash function $$H_0$$, then in estimates of attack cost with factor $$2^t 2^c p$$ for probability $$p$$, using $$H$$ is as if the passwords were chosen uniformly at random from $$2^{t + c}$$ possibilities and hashed with $$H_0$$.

• By probability distribution of possible passwords, are you referring to that, for instance, the letter e is the most used in the English lanuage, giving its use in a password a higher probability? How could one infer a probability distribution on possible passwords, short of choosing its length and base/characterset? – Mussé Redi May 6 '18 at 21:57
• What do you mean with communication, as a measure for attack cost? – Mussé Redi May 6 '18 at 21:59
• @MusséRedi Quantifying probabilities for passwords is difficult if you don't know the procedure (e.g., pick a sequence of 10 words independently and uniformly at random from the diceware dictionary), but if a human generated the password without assistance from a computer, probably ‘password’ is more likely than ‘silverfish’ which in turn is more likely than ‘hcjmlutvrt’. Whatever the distribution on passwords, the expected cost to attack a salted password-based key derivation function $H$ is greater by a factor of $2^c$ than the cost to attack the underlying salted hash function $H_0$. – Squeamish Ossifrage May 6 '18 at 22:53
• @MusséRedi It takes time for information to propagate across distances. If you have a cluster of computers that are not working completely independently, so they have to communicate, you have to power whatever apparatus they use to communicate for whatever time it takes for the information to propagate. That's in addition to the CPUs you have to power for computation, the RAM you have to power for storage, etc. All this is to estimate proxies for cost in euros or joules. Usually we model costs in the area*time metric. – Squeamish Ossifrage May 6 '18 at 22:58