Can I use PBKDF2 as a stream cipher?

Question

Unfortunately I have to implement some naive homemade symmetric crypto, since ordinary AES CTR is not implemented in available API on target platform.

What I’m going to do is, given encryption password and plaintext bytes, generate “encryption key” from password via PBKDF2/RFC 2898 with length of plaintext, and then XOR this “gamma” against plaintext bytes.

Could you please criticize this approach and enumerate vulnerabilities and issues?

Answer 1

TL;DR: Yes, you can use PBKDF2 as a stream cipher. However, you should not use it for that and for its intended purpose (i.e. password-based key derivation) at the same time. Instead, if you need to do both, call it twice.

---

PBKDF2 is a password-based key derivation function — or, rather, a scheme for constructing such a function out of a variable-key-length PRF, which in turn is is usually implemented by taking a cryptographic hash function and wrapping it in the HMAC construction.

As a general-purpose key derivation function, PBKDF2 is designed be able to generate an arbitrarily long* string of pseudorandom bits. To make it resistant to brute force password guessing, it is also designed to take an iteration count that deliberately slows it down.

However, when used to generate more output than the underlying PRF / hash function produces, PBKDF2 has what is nowadays generally considered to be a design flaw: its runtime is roughly proportional to the product of the iteration count and the length of output requested (whereas, in many real-world scenarios, the time for an attacker to test one guessed password still only depends on the iteration count). Thus, you really don't want to call PBKDF2 with both a high iteration count and a high output length.

Instead, my general recommendation** for applications that need to generate large amounts of key material using PBKDF2 is to first use PBKDF2 with a large iteration count to generate a "master key" whose size equals the output size of the underlying hash (which should preferable be chosen to make this as large as feasible, e.g. SHA-512 for a 512-bit output), and then feed this master key into a non-iterated KDF (such as HKDF-Expand from RFC 5896, or even PBKDF2 itself with the iteration count set to 1) to expand it into the full required length.

With this scheme, the output of PBKDF2 applied to the master key, with a unique per-message salt and an iteration count of 1, should even be safe to use directly as a keystream to XOR the message with. Internally, PBKDF2 simply uses (salted and optionally iterated) HMAC in counter mode, which yields a secure stream cipher as long as the underlying hash function satisfies the conditions of the HMAC security proof (which all secure modern hashes, and even some old not-so-secure ones like SHA-1 and even MD5, are believed to do).

You do need to ensure that the salt input to PBKDF2 is unique for each message; otherwise you end up reusing the same keystream for two messages, which breaks the security of any XOR-based stream cipher.

---

Also, note that, like any XOR stream cipher, this construction does not protect message integrity, and in fact is highly malleable. To protect against active attacker, you need to combine the encryption scheme with a message authentication code. Fortunately, you already have one available, namely HMAC. So just run the XORed ciphertext through HMAC again (preferably with a separate key derived from the master key), append the result to the message, and verify it before decryption, and you're all set.

Indeed, if you really cannot access the underlying HMAC function, even PBKDF2 itself (being really just a thin wrapper around HMAC) could be used as a MAC, by passing the message to be authenticated as the salt parameter and requesting one hash block of output. While this won't quite produce the same output as raw HMAC (since, even with the iteration count set to 1, PBKDF2 still appends the block counter to the salt), the security proof carries over trivially.

If you wanted to get fancy, you could even use HMAC (or PBKDF2) in the SIV construction as both the MAC / nonce generator and as the encryption primitive. So, as perverse as it may seem, the following pseudocode should implement a secure misuse-resistant AEAD scheme using nothing but PBKDF2:

// a variable-length PRF, implemented using PBKDF2 with an iteration count of 1
function prf(key, data, len):
    return PBKDF2(key, data, 1, len)

// SIV authenticator / IV length in bytes (32 bytes = 256 bits)
constant token_size = 32

// internal MAC output length, may be larger than token_size
constant internal_mac_size = max(token_size, PBKDF2_hash_block_size)

function SIV_PBKDF2_encrypt(key, plaintext, assoc_data, nonce):
    macP = prf(key, "macP" + plaintext, internal_mac_size)
    macA = prf(key, "macA" + assoc_data, internal_mac_size)
    token = prf(key, "auth" + macP + macA + nonce, token_size)
    ciphertext = plaintext XOR prf(key, "encr" + token, length(plaintext))
    return (token, ciphertext)

function SIV_PBKDF2_decrypt(key, token, ciphertext, assoc_data, nonce):
    plaintext = ciphertext XOR prf(key, "encr" + token, length(ciphertext))
    macP = prf(key, "macP" + plaintext, internal_mac_size)
    macA = prf(key, "macA" + assoc_data, internal_mac_size)
    if token != prf(key, "auth" + macP + macA + nonce, token_size):
        return ERROR
    else:
        return plaintext

In the code above, all variables are assumed to be byte strings of arbitrary length, and may contain null bytes. The + operator always denotes string concatenation. Note that the length of the left argument to + above is always fixed, making the concatenated result unambiguous.

The ERROR constant stands for some unambiguous indication of decryption failure, possibly due to malicious input; instead of a special return value, one could also e.g. throw an exception in that case. The important things is that, however it is implemented, such a failure should not reveal anything about the invalid plaintext string to the caller, as the content of that string may be manipulated by an attacker.

If a distinct nonce is provided for every encrypted message, this code should implement (modulo any possible implementation bugs) an IND-CCA secure authenticated encryption scheme. Even if the nonce is repeated or omitted, it should still implement a "deterministic authenticated encryption" scheme, in the sense of Rogaway and Shrimpton, essentially meaning that the only information it leaks (besides message length, which all arbitrary-length encryption schemes reveal to some extent) is whether two encrypted messages are identical or not.

The length of the key input is arbitrary, but should be sufficient to resist brute-force guessing attacks (i.e. at least 128 bits, preferably more). It should not be a user-supplied password — you'll want to run those through PBKDF2 (or some other password-based KDF) with a high iteration count first.

As an optimization, the internal macA variable may be precomputed if the associated data is known in advance; other similar optimizations, as in Rogaway's original SIV scheme, are also possible.

---

^{*) Technically, the output length of PBKDF2 is limited to $2^{32}-1$ times the output length of the underlying PRF / hash.}

^{**) Assuming that one cannot or will not switch to a more modern password-based KDF, such as scrypt, Argon2, Catena or Balloon hashing. Unlike PBKDF2, all of these KDFs are designed to also consume large amounts of memory, which makes them more resistant to massively parallel brute force attacks using GPUs, FPGAs or ASICs. As a side effect, they also intrinsically support efficient generation of large amounts of output key material.}

Answer 2

Have a read of the One-time pad, as it seems identical to what you have described.

https://en.wikipedia.org/wiki/One-time_pad

Especially the section "problems" goes over the issues raised by fgrieu.

• Key Distribution : You will still require a secure means of exchanging keys. If your keys remain static you are just giving an attacker all the time in the world to work out what they are.

• Authentication : You would have no way to know if the message had been altered in transit.

An attacker, knowing the structure of the data you are sending would be able to drastically reduce the required search space.

DON'T DO THIS…

If you were sure the keys were kept secure you could jump through some hoops like adding an IV that is also XOR'd with your key and a MAC at the end that is a hash of all encrypted bytes encrypted with your key and IV…

But rolling your own crypto is generally a bad idea if your going to go to the trouble you may as well implement AES-CTR for your platform.

Starting with aes, someone has done the heavy lifting already.
https://github.com/kokke/tiny-AES128-C

Keep in mind that CTR is also not authenticated.
https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Counter_.28CTR.29