# 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 if a KCV is required. Instead of zero's, it would be much better to use a block of bytes that is not likely to be of use to an attacker.

You could of course wonder if CMAC and counter mode should be using an encrypt over zero's in the first place. 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 - it would be easy to define a protocol that specifies the counter that way.

Note that using a KCV for keys can be very useful for key management - it certainly saved our company a lot of time.

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

1. Calculate a temporary value $k_0$ = $E(k,0)$.
2. If $msb(k_0) = 0$, then $k_1 = k_0 ≪ 1$, else $k_1 = (k_0 ≪ 1) ⊕ C$.
3. If $msb(k_1) = 0$, then $k_2 = k_1 ≪ 1$, else $k_2 = (k1 ≪ 1) ⊕ C$.
4. 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.

-
I decided to accept this answer as there has not been another one and the answer addresses CMAC and CTR quite well. I was bit hopeful that somebody would have been able to answer the add-on question "what other modes are likely to interact badly with KCV". The reason KCV works like this is likely that they (the designers of the scheme) had design criteria of trying to avoid one key type depending on unrelated algorithm. When transporting key (i.e. key wrapping), the expansion occurring on key wrapping algorithm (like AES KW or RSA-KEM-KWS) sometimes can avoid need for KCV. – user4982 Nov 27 '13 at 19:37
Yeah, but it would be relatively easy to find an algorithm that does not have the drawback of encrypting an often used block of data... – Maarten Bodewes Nov 27 '13 at 19:39

Owlstead already gave a good answer, but I just wanted to point to a [very] relevant recent paper: Impact of ANSI X9.24-1:2009 Key Check Value on ISO/IEC 9797-1:2011 MACs

After a brief discussion of some general issues, the paper goes on to prove tight bounds on the security of the IEC MACs once the Key-Check-Value has been released.

To quote the abstract:

ANSI X9.24-1:2009 specifies the key check value, which is used to verify the integrity of the blockcipher key. This value is defined as the most significant bits of the ciphertext of the zero block, and is assumed to be publicly known data for verification. ISO/IEC 9797-1:2011 illustrates a total of ten CBC MACs, where one of these MACs, the basic CBC MAC, is widely known to be insecure. In this paper, we consider the remaining nine CBC MACs and derive the quantitative security impact of using the key check value. We first show attacks against five MACs by taking advantage of the knowledge of the key check value. We then prove that the analysis is tight, in a concrete security paradigm. For the remaining four MACs, we prove that the standard birthday bound still holds even with the presence of the key check value. As a result, we obtain a complete characterization of the impact of using ANSI X9.24-1 key check value with the ISO/IEC 9797-1 MACs.

-
Thank you for the link and abstract. The paper contains useful information regarding the subject. – user4982 Mar 15 '14 at 10:42