Sending KCV (key check value) with cipher text

Question

I was wondering why it is not more common to send the KCV of a secret key together with the cipher text. I see many systems that send cipher text and properly prepend the IV to e.g. a CBC mode encryption. Wouldn't it be easier to prepend another <blocksize> bytes with the KCV together with it? A good block cipher should not be vulnerable to known plain text, so I personally don't see any issue with sending the KCV.

It would of course be less efficient, but the upside is that you can distinquish with some certainty between using the wrong key and a general decryption failure. I say "some" certainty because if the first [blocksize] bytes are (too) garbled, then the compare would obviously fail. That said, it's unlikely that an single block, ECB mode encrypt of [blocksize] bytes would go wrong in any way.

PS The cryptoki standards only use the first three bytes of the KCV, but I think that this is mostly a convenience, and only partly a security measure (against brute force)?

Answer 1

I suspect that KCV's are in general not used because they don't add enough to be worth the small overhead.

There are a number of cryptographical attacks on encrypted methods that involve the attacker modifying a valid ciphertext, and then having the receiver decrypt the modified message (and watch how the receiver reacts). Because of these attacks, it is generally wise to include an authentication tag along with the message; if the authentication tag does not check out, then the receiver rejects the message (and in a way that is independent of how the message was modified; this prevents the attacker from deducing any information).

There are a number of ways to authenticate the message; you can generate a MAC of the ciphertext, you can sign the plaintext, you can use a cipher mode of operation that encrypts and authenticates (e.g. GCM). One thing which is not a valid method would be adding a KCV value (a valid KCV value means only that the KCV value was computed by someone who knew the keys; it doesn't say anything about whether the rest of the message was modified). So, if you use a KCV, you still would need an authentication method as well.

Which brings up a question: if you're already including an authentication method, what extra does a KCV bring to the table? Well, I can't see much. If the sender made a mistake, the receiver would be able to catch it earlier; however, that's not something we typically care about optimizing for (one possible exception would be a password-keyed file encryption method; you might not want to have to decrypt a full multigigabyte file before noticing that the password was wrong). You might hope to try to distinguish the cases where the sender uses the wrong keys versus he makes another type of error; I don't see how that would be useful in general (and note that an attacker would be able to simulate both types of errors depending on how he modifies the ciphertext; hence if one type of reaction is useful to him, he can induce that).

KCV's don't add much expense (another cipher block evaluation and a few more bytes of encryption overhead), but if they don't bring any benefit (and except for that one case I mentioned above about file encryption, I don't see how they do), it's hard to see why to pay that small additional expense at all.