# Concerns about use of MAC in my specification

Here is the pseudocode for a routine I am designing:

encrypt(password, string):
nonce1 := generate_random_nonce()
nonce2 := generate_random_nonce()
encrypted := cipher(nonce2, key, string)
return (nonce1 || nonce2 || encrypted || mac(key, encrypted))


I realized that an attacker with the encrypted text might be able to brute force the key, since a mac is not slow to compute (like key derivation).

I thought about using a third nonce for the mac key instead of the ciphertext key, but the mac key should be secret so this isn't an option.

How should I correctly use a MAC to authenticate the ciphertext (and thus plaintext) in this situation?

• I thought I should add: derive_key is pkcs5_pbkdf2, cipher is chacha, mac is blake2b. – Brennan.Tobias Jun 18 '15 at 15:53
• That the MAC is not slow to compute is of no consequence in the question. The key for calculating the MAC is slow to compute, so as long as the key is safe then the above protocol is secure with regards to the slow computation from the password. A good MAC algorithm does not allow for computation of the key given just the message & authentication tag. – Maarten Bodewes Jun 18 '15 at 16:55

I would propose a rather different scheme.

encrypt(password, string):
nonce := generate_random_nonce()
mackey := kbkdf(secret, 'mackey')
enckey := kbkdf(secret, 'enckey')
iv := kbkdf(secret, 'iv')
encrypted := cipher(iv, enckey, string)
return (nonce || encrypted || mac(mackey, encrypted))


Note that I've split the derive_key into pbkdf, a password based key derivation function and kbkdf, a key based key derivation function. For the PBKDF you can use PBKDF2 with a high enough iteration count. For the KBKDF you can go for HKDF-extract or maybe just for KDF1 (which is basically a secure hash - say SHA-256 - over the secret and additional data).

As long as the nonce is truly random this scheme should be secure, and you can use related primitives for the cipher and mac without any problems. This is because the KBKDF cannot be reversed. This is also why you don't need to MAC the IV; mackey, enckey and iv will all be different for each call to encrypt.

This scheme also removes the nonce2 from the output making it smaller.

• If you really want you could use PBKDF2 with iteration count 1 as KBKDF. It's a bit of a cheat, but it removes one primitive. – Maarten Bodewes Jun 18 '15 at 17:19
• Other cheats: use IV=0, the encryption key differs each time anyway. Use an AEAD cipher such as GCM and remove everything but the nonce generation and the PBKDF. – Maarten Bodewes Jun 18 '15 at 17:40
• The common cheat of using IV=0 cuts a corner on security. As example: assuming this and AES-128 in CTR mode, an adversary knowing a full block of plaintext at a fixed location in each message can test, with a single AES-128 encryption followed by a hash-table search, if a given key was used in any of the intercepted messages, which would not be possible with random IV. A match would allow to decipher one full message; that's a speed-up of some few orders of magnitude over brute force (likely not making the attack practical, especially compared to password enumeration). – fgrieu Jun 19 '15 at 4:51
• @fgrieu Interesting attack, yes. It would still take way too many messages I agree, but better be safe and either use the random IV or AES-256 (increasing the key space to impossible ranges would mitigate against this attack, only requiring a small slow down). Then again, the only reason not to calculate the IV is a small speedup. – Maarten Bodewes Jun 19 '15 at 11:43

The pseudocode has a serious issue: changing the value of nonce2 in an otherwise valid cryptogram is not detected, and results in invalid deciphered plaintext. That would be fixed by

encrypt(password, string):
nonce1 := generate_random_nonce()
nonce2 := generate_random_nonce()

• The same key is used for cipher and mac; when not done properly, that can be a bad thing, and is a known recipe for disaster, e.g. if both cipher and mac used the key as an AES key for CBC encryption and CBC MAC, rather than using a carefully thought authenticated encryption mode like AES-GCM-SIV. With cipher chacha, and mac blake2b which is based on the chacha core, we should at least worry (even though I see no attack right now), and perhaps use something like proposed by Maarten Bodewes in that other answer.
• We are told that derive_key is pkcs5_pbkdf2; this does key stretching, which is indispensable for any password; but PBKDF2 does not leverage the RAM and possibly multiple CPUs available at no cost to legitimate users, hence is orders of magnitude less safe against serious adversaries (using ASICs or FPGAs for password searching) than something state-of-the-art like scrypt.