KCV and compatibility with block cipher modes of operation There has been lately a question on KCV (key check value), value provided by many CRYPTOKI (PKCS#11) implementations. I don't particularly like KCV, but I decided to ask about proper use of KCV. 

This "KCV" (also known as CKA_CHECK_VALUE object attribute) value is derived as follows:


For most objects: first three bytes of SHA-1 hash of the object.
For cryptographic keys for block ciphers, it is the first three octets of ciphertext produced by ECB mode encryption of a block full of zeros.


Sending KCV (key check value) with cipher text is done rarely, because the check does not ensure correctness of the key very well. The excellent answer from poncho to this question Sending KCV (key check value) with cipher text illustrates a few reasons.

My concern is that KCV could jeopardize confidentiality or authenticity of proper usage of some modes of operation:


CMAC mode uses $k_{0} = E_{k}(0^{128})$ for deriving sub-keys.
If CTR mode is used starting with counter value 0, that would obviously allow revealing three first bytes.


Is it good idea to avoid using KCV in above situations?

Are there some other modes of operation, where revealing the first octets of encryption of zero block is bad?
I've thought quite a lot about this, and I think in general the answer is no, it would not be a good idea to use a KCV for those kind of situations. Using a hash or even better a MAC (using the key as MAC Key) would be a much better idea when a KCV is required. Instead of zero's, it would be much better to use a previously random (block of) bytes that is not likely to be of use to an attacker.

You could of course wonder if all zero input should be used for CMAC and counter mode. For CMAC is would be very easy to use another constant value. For CTR mode it is probably best to always increase the counter before it is used; one way would be to simply start with value 1. It would be easy to define a protocol that specifies the nonce / IV / counter that way.

Using a KCV for keys can be very useful for key management - it certainly saved the company I worked for a lot of time.



For CMAC mode it is easy to show that the KCV returns part or all of the keys...


Calculate a temporary value $k_0$ = $\operatorname{E}(k,0)$.
If $\operatorname{msb}(k_0) = 0$, then $k_1 = k_0 \ll 1$, else $k_1 = (k_0 \ll 1) \oplus C$.
If $\operatorname{msb}(k_1) = 0$, then $k_2 = k_1 \ll 1$, else $k_2 = (k1 \ll 1) \oplus C$.
Return keys $k_1$ and $k_2$ for the MAC generation process.


These keys in turn are used for the last block of the CBC mode encryption that underlies CBC-MAC, which is used to build up CMAC. Now it seems that this would reveal the last block to an attacker before it is encrypted.

Now comes the tricky part, I'm not sure if this negates the security added to CBC-MAC to create CMAC, but it doesn't look good.



As for CTR mode, it is clear that you can directly decrypt (part of) the first block of the ciphertext if you have a nonce (and counter) set to all zeros. You cannot get a more direct attack than that.