Is it safe to use the CBC-MAC as a Initial Vector and Key Check Value in deterministic encryption?

Question

I want to deterministically encrypt a short message <50 bytes with AES-128 CBC. I also want to be able to detect if the correct key is being used.

Ciphertext and IV integrity will be guaranteed by a higher layer of software, so its impossible to tamper with the ciphertext, IV or additional data. The encryption key is widely known also by malicious parties, except by one server. The encryption is only used for plausible deniability for this server, so a malicious party is allowed to read everything. The server should be able to group equal messages blindly hence the deterministic encryption.

Since the message size is small, I want to minimize overhead next to the ciphertext. I've read a key check value can be used to detect if the correct key is applied for decryption. This can be done by adding one block of zeros or another constant in front of the message before encrypting with AES.

I was wondering if I can use a 128 bit CBC-MAC of the plaintext as this constant, and use it simultaneously as IV for the encryption of the message. This to prevent only equal first bytes of the messages to result in equal first bytes in the ciphertext.

Basically the idea boils down to concatenating twice the plaintext, apply AES-CBC with an IV of zero. Using the output of the last AES block of the first half as IV and the whole second half as ciphertext. After decryption the receiver can CBC-MAC the decrypted plaintext to see if it matches the used IV and thus the correct key was used.

Note that the CBC-MAC is only used for creating a deterministic IV. Its not needed for all the properties a MAC is intended for.

Am I thinking correctly and will an malicious user (which has access to encryption keys) not (or very hard) be able to generate a collision in my IV-ciphertext combination so that the server is grouping unequal messages together?

Answer 1

Am I thinking correctly and will an malicious user (which has access to encryption keys) not (or very hard) be able to generate a collision in my IV-ciphertext combination so that the server is grouping unequal messages together?

If the server checks all the bytes in the IV-ciphertext (and declares a collision only every byte for two encrypted messages are identical), and if you can decrypt it (and a decryption of an encrypted message will always output the original message), then it is obviously impossible to generate for two distinct messages to be declared as colliding (and you don't have to worry about the details of the encryption method except for these two facts).

Consider two distinct plaintext messages $M \ne M'$, they will be encrypted into ciphertext messages(which includes the IVs) $C = E(M)$ and $C' = E(M')$. Now, the decryption process is a function of the ciphertext and the keys (and nothing else; that's why I counted the IVs as part of the ciphertext). If we had $C = C'$, then what would this common ciphertext decrypt to? If it is $M$, then we have a message $M'$ that, after encryption, could not be decrypted properly (hence violating the assumption that decryption of an encrypted value always gave back the original plaintext).

Hence, a malicious user cannot generate a message that the server would confuse with another message.