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. Commented Jun 18, 2015 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. Commented Jun 18, 2015 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. Commented Jun 18, 2015 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. Commented Jun 18, 2015 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
Commented Jun 19, 2015 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. Commented Jun 19, 2015 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()
encrypted := nonce2 || cipher(nonce2, key, string)
return (nonce1 || encrypted || mac(key, encrypted))


but leaves two lesser issues:

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

• Sorry for raising an old answer. I may be missing something on "The same key is used for cipher and mac" which leads to a potential disaster. For example AES-GCM, being an authenticated encryption protocol, provides both confidentiality and integrity of the data with the same AES-128 key. Isn't it a contradiction with what you said? Or were you talking about combining two different algorithms, one for encryption and one for authentication with the same key was in general a bad idea? Commented Apr 15, 2020 at 0:56
• I'm stating that it is dangerous to use the same key for distinct algorithms built around similar primitives, especially if they also share the data, as in encrypting and MACing the same data with the same key. I'm not stating that it is impossible to do that safely, only that there is a known potential for pitfalls. AES-GCM does it safely, but that's a delicate arrangement (and incidentally, one that uses a distinct algorithm from AES for the bulk of data authentication). I have clarified.
– fgrieu
Commented Apr 15, 2020 at 4:46
• Thank you for the precision! Commented Apr 15, 2020 at 4:47