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:
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.
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.
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.
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 ?
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.
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.
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.