Is it safe to use a MAC as iv for CTR encoding?

Question

I have devised the following encryption algorithm and would like to know if it is safe. The goal is to use it to encrypt cookie values. I thus want to keep the encoding overhead as small as possible.

The encoding steps are as follow:

1. Append 3 to 5 random bytes to the value. The number of random bytes is encoded in the two less significant bits of the last random byte. The number is picked so that the value length plus random number and MAC is a multiple of 3 bytes. This is to simplify base64 encoding.

2. Compute the hmac(md5) value and append it after the random bytes. It might also be hmac(shaX) but md5 yields 16 bytes which is the block size of AES.

3. Cipher the last 16 bytes of the constructed byte sequence with AES and use the product as iv to cipher the other bytes with CTR AES. The product must have a byte length multiple of 3.

4. Encode the cipher text with base64.

The MAC cumulates all bit variations in the encoded value. The random bytes add some randomness in the produced digest which can be assumed to be pseudo random.

The only weakness I see is the risk to get two identical iv. But the iv should be assumed to be random because it is an encrypted MAC.

The resulting encoding is quite compact because the overhead is limited to the 16 hmac bytes and the 3 to 5 random bytes.

Do you see any problem or defect with this encoding ?

EDIT:

1. my question differ slightly from the other question Can I use MAC as CTR mode nonce if my messages are non repeating in that I suggest to use the encrypted MAC instead of the MAC.

   The question may also be a duplicate of Using HMAC as a nonce with AES-CTR Encrypt-and-MAC. But still differ in that I cipher the MAC, and thus conceal it and randomize the iv.

2. My algorithm differ from the SIV algorithm defined in RFC 5297 by using hmac instead of CMAC-AES defined in RFC 4493 and by using the encrypted MAC as iv. Appart from that the algorithms are equivalent. This indirectly proves the validity of my algorithm. The advantage of SIV over my algorithm is that is uses only the AES encryption primitive and no hashing primitive.

3. The 3 to 5 random number is another difference between SIV and my algorithm. SIV doesn't have this and thus doesn't conceal data equality and length. The user may add random padding bytes to its plain text when this is critical for its application.

   Regarding the number of random bytes, this still needs investigation. What is relevant here is the probability that two same cipher text encode the same clear text. I tend to think that it's not the same as the probability that two identical plain text yield the same cipher text.

Answer 1

First remark here should be don't roll your own crypto. That said, your idea seems to be a variant of Synthetic Initialization Vector mode (SIV, RFC 5297), where a pseudorandom function of the plaintext and associated data is used to generate a value that doubles as the message authentication tag and the IV for the cipher. Your random 3-5 byte value is an optional nonce, which in SIV is just an associated data field.

Note that SIV was designed for deterministic encryption (exceptional cases where it's OK if encrypting the same plaintext twice with the same associated data produces the same ciphertext) and for nonce misuse resistant encryption (cases you don't actually want nonce reuse but you want to minimize the damage if it does happen). This ties to @EnTaroAdun's answer—the low diversity of random nonce values may be a problem, but if it isn't, then SIV is a well-designed, well-vetted mode that handles your scenario out of the box. SIV also allows for arbitrary associated data fields, which can help mitigate potential duplication problems by including other contextual data other than the 3-5 random bytes into the synthetic IV computation.

SIV is not a common mode, so there's a good chance you won't find a ready-made implementation for your language. So apart from a several nasty details (e.g., why not just use truncated HMAC-SHA2 directly? Are you vulnerable to MAC equality comparison timing attacks? How are you generating keys for the MAC and cipher?), your idea is neither obviously wrong nor obviously right either.

Answer 2

Do you see any problem or defect with this encoding ?

For some message lengths you're adding only 3 random bytes. That means if the same message is transmitted over and over an attacker will be able to determine this after a few tens of thousands of messages.

Additionally, if the entropy of the message is low (few possible messages), the attacker may be able to enumerate all combinations of possible messages and the 3 random bytes (since 2 bits are fixed, that leaves 22 bits of entropy added and $2^{22}$ is about 4 million - not the kind of bogglingly-large number one expects in cryptography).

TL;DR You should consider expanding the nonce to at least 64 bits and preferably all the way to 128 bits.