Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
When using the PBKDF2, is one taking on significant risk if one chooses to lower the number of iterations and choose to have very long keys?
Can I XOR my message with a a very long key (plain-text sized) generated using PBKDF2? Will this make XOR encryption as strong as a one-time pad?
When using the PBKDF2, is one taking on significant risk if one chooses to lower the number of iterations and choose to have very long keys?
Yes. PBKDF2's method of generating keys longer than the length of PRF output is... a really bad idea. I'll use the same notation that the Wikipedia article on PBKDF2 currently uses to explain why.
The derived key is defined to be $$DK = T_1 \| T_2 \| ... \| T_{dklen/hlen}$$ where $\|$ means concatenation.
The way each $T$ is derived is very important to this question.
Each one of these $T$ are calculated by iterative hashing. $U_1, U_2, U_3, ...$ each need to be computed sequentially for each block of output $T$. $U_2$ needs the result of $U_1$. $U_3$ needs the result of $U_2$. And so on. But each $T$ block does not have any dependency on the sequential hash computed by other blocks.
$T_2$ can be computed without calculating $T_1$. Each block is solely a function of the password, salt, cost parameter, and the output block number (subscript $i$ of $T_i$). Denoted in the article as $$T_i = F(Password, Salt, c, i)$$
If you use PBKDF2 in applications like password authentication or for deriving a stream cipher's key-stream then this is a problem. The password storage example is easier to demonstrate as a problem.
Each block of output can be computed independently of the other. In that sense using PBKDF2 with $dklen = hlen * k$ is basically the same as publishing $k$ hashes for a single password. To test if a candidate password is correct, a password cracker does not need to compute all $k$ blocks of $T$. It suffices to compute only one of them.
If any one block doesn't match the hash you are trying to crack then you know the password is wrong. A hash based PRF with output length $m$ will only produce false positives with a probability of $2^{-m}$, low enough that we don't need to consider it in estimating the password cracker's cost-per-password-test.
As the legitimate party trying to hash a password by telling PBKDF2 to output $k$ times the PRF output length you are forcing yourself to do $c * k$ work. The password cracker on the other hand only needs to test one block and thus only needs to use $c$ work per guess.
The same logic applies to a PBKDF2 style stream cipher. To encrypt every block of plaintext you have to do $c$ work per block. Someone that wants to brute-force decrypt a single block of ciphertext, on the other hand, only needs to do work proportional to $c$ once per guess. You make the eavesdropper's job $k$ times easier than yours if you need to encrypt $k$ blocks. Not only that, once someone correctly decrypts one block they will know what password was used to compute every other block.
The bad guy never needs to do more than $c$ work to recover the password used to derive EVERY $T$ block. If you decide you want $k$ blocks of output and you compensate by decreasing $c$ by a factor of $k$ you are just making the hacker's job easier. This is a huge flaw in PBKDF2's design.
If you really needed to use PBKDF2 for key derivation (as opposed to Argon2 or scrypt), or something like it, then what you should instead do is use the CPU-time you've budgeted to password hashing to deriving one key with a length no greater than $hlen$. Call this the master key. Take all the resources in your budget and put them into computing just one block of output that's as strong as you can afford to make it. Your passwords will be $k$ times more difficult to brute force this way.
If you need more key-bits than $hlen$ then use your master key to derive child keys. You derive the master key from a password using a password-based KDF. Then you derive each child key using a key-based KDF.
A password-based KDF is designed to be expensive to compensate for passwords being weaker than keys. A key-based KDF lets you derive new keys from a single strong secret key very efficiently. (Or just use one key with an authenticated encryption algorithm. Which is what one normally would do.)
Always be wary of password hashing scenarios where you're incurring unnecessary (including redundant) expense for yourself. If you were planning to spend that much time hashing you should have spent it with a single stronger hash.
And speaking of stronger hashes you should be using Argon2 for now, both for password-database user authentication and for key derivation. Argon2, along with scrypt and "balloon hashing", is what's called a "memory-hard" algorithm. It is designed to make heavy use of RAM, in addition to CPU time (which is all PBKDF2 and bcrypt do for you). Memory-hard functions are thought to be more resistant to CPU-based, GPU-based, and ASIC-based password cracking.
Edit: Clarification in response to a comment
Suppose the absolute maximum amount of compute time (work) you can dedicate to password-stretching is some number denoted $W$. Consider $C_D$, the cost a defender pays to generate their entire derived key (per password entry), and $C_A$ the cost an attacker pays to test a candidate password.
We'll ignore the PRF parameter because the question is only about trading off number of iterations (c in the wiki article) and the key length (dklen in the article). Instead of worrying about dklen, hlen, and the number of blocks $T$ and doing the arithmetic to convert between each variable let's simplify things by measuring hlen in terms of PRF's output length.
Instead of dklen bytes and hlen bytes per block T, let's just say dklen and hlen are in units of $T$'s block size. This is easier because hlen is automatically 1 by definition. We can use $k = \lceil dklen / hlen \rceil$, the number of T in
DK = T1 || T2 || ... || Tdklen/hlen
The cost of generating one block T is however much work is needed to compute $c$ iterations of the PRF function. The cost to generate the entirity of DK is $k$ times the cost to generate one $T$. So we get $C_D = k \times c$.
For the defender to maximize the strength of their password-hash they will want to set $C_D = k \times c = W$. This is the trade-off between iteration count and key length. If you want to double your key length ($k = 2$) then you need to half $c$.
On the other hand the attacker doesn't need to generate all of DK. It suffices to generate any one $T$ and check that block to see if their password guess was correct. Therefore no matter what value $k$ is, $C_A$ always equals c.
The ratio $\frac{C_D}{C_A} = \frac{k \times c}{c} = k$. So if you double $k$ then you force the good guys to do twice as much work as the password crackers. If you triple $k$ then the defender does three times as much work per password tried as the bad guys. You want to minimize the ratio to give the attacker the smallest advantage. Therefore you are always better off using $k = 1$. That's why I said use a key-based KDF if you need more than hlen bytes of output.
Joke answer: Or you could set $k = 0$ and use Argon2 instead. It's stronger and it has the advantage that you don't need to think about this kind of stuff... as long as you follow the recommended procedure for choosing parameters.
hlen sized master key. This would make my k=1. I am confused. I would make sense with c - number of iterations.
$\endgroup$
Sep 23, 2018 at 18:30
A PBKDF2 is a specifically designed "key derivation function with a sliding computational cost, aimed to reduce the vulnerability of encrypted keys to brute force attacks." That means it securely converts a user's password into a uniformly distributed pseudo random key (of some size) for use with another cryptographic function. The another bit is crucial. It is not designed to generate a cipher stream itself, and I'm unaware of a security assessment for such usage, especially for huge outputs.
And if indeed you followed this method and produced a key for direct XOR with plain text, it could not be as secure as a one time pad. It might not be very secure at all bearing in mind the comments above regarding it's use. The algebraic creation of one time pads pops up fairly often here, and all are proved to not be one time pads. They are forms of stream ciphers. A one time pad is generated with hardware, be that a typewriter, laser beams or a handful of Zener diodes. A pad cannot (by it's definition) be generated solely by an algorithm. Have a browse though the one time pad tag, especially https://crypto.stackexchange.com/a/53035/23115 and Why is OTP not vulnerable to brute-force attacks?.
