Algorithm Choice in PKCS#11 (part 6) - MAC modes

Graham Steel
October 24, 2014

In previous posts we covered the state of the art cryptanalysis results on the RSAmechanisms, hash functions, block ciphers and block cipher modes available in PKCS#11. In this post we look at the message authentication code (MAC) mechanisms available.

Return of the MAC

There are essentially two ways to produce a MAC from a message and a shared secret: one is to use a block cipher in an appropriate MAC mode, the other is to used a keyed hash function (HMAC). During the 1990s, it was hard for US-based companies to export technology containing strong block ciphers, and the state of the art block ciphers were a lot slower than the widely used hash functions. Hence the HMAC construction became very popular.These days, with no export restrictions and AES taking just a few CPU cycles, the performance advantage is less clear. In particular, the fast, widely-used hash functions of the 1990s are considered broken and hence often no longer used. In any case, this post will cover PKCS#11 MAC and HMAC modes, drawing on the excellent block cipher mode survey of Phil Rogaway (for which the HMAC chapter was drafted by Mihir Bellare).

MAC modes

To construct a secure MAC you need to start with a secure block cipher. In PKCS#11 v2.20, if you followed our guide, that means you'll be using AES or for some legacy reason 3DES. There are now two MAC mechanisms available: CKM_*_MAC and CKM_*_MAC_GENERAL, where * is replaced by AES or 3DES. Underlying both is the CBC-MAC construction with 0 padding of the final block, as defined in FIPS 113. In the "general" version you can specify the tag length (i.e. the length of your final MAC output) as anything between 0 (useful) and the blocksize of the blockcipher (128 bits for AES), while the "standard" version fixes the tag-length at half the blocksize (128/2 = 64 bits for AES).It's not clear why half the blocksize should be considered standard, but it's perhaps a throwback to ANSI X9.9 (issued in 1982) which was widely used in the finance industry. The diagram below shows how this works, for a message M = M1 || M2 || ... || Mx, and block cipher encryption function E using key k.

So how secure are these two modes against an attacker who is trying to forge a MAC? The answer is, not very:

  • If messages may be of any length, the 0 padding is already insecure. No matter what the MAC key, the hex string 0x321 has the same MAC as 0x3210 or 0x32100.
  • If messages are always a multiple of block sizes, this isn't secure either since if the attacker knows T to be the MAC of a one-block message M, he can forge a message M || (M xor T) which will also have the MAC T.
  • If messages are all of a fixed length, security can be proved but only up to the "birthday bound", which is 2^(n/2) for a tag length of n. So, if you use CKM_AES_MAC with its fixed tag length of 64 bits, an adversary will be able to find two messages that have the same MAC after about 2^32 queries. Worse, 3DES only has a 64 bit blocksize, so the birthday bound on CKM_DES3_MAC is just 2^16 messages! Conclusion: absent legacy consideration, use the maximum tag length allowed and the method CKM_AES_MAC_GENERAL.

The good news for MAC users is that PKCS#11 v2.40 includes CMAC, which has security proofs for variable message length.

HMAC modes

HMAC is essentially a secure way to insert a shared secret into a hash value calculation and so obtain a MAC which should be unforgeable by anyone who doesn't know the secret.The HMAC function defined in PKCS#11 is what Rogaway calls HMAC2, defined in RFC 2104, which allows any length of shared secret to be used. The shared secret is stored in PKCS#11 as a key of type GENERIC_SECRET.HMAC has well understood security proofs up to the birthday bound, even when the underlying hash function is not collision resistant, as is the case with several of the hash functions available in PKCS#11.

As with block cipher based MACs, PKCS#11 offers two HMAC methods for each hash function h, CKM_h_HMAC and CKM_h_HMAC_GENERAL, where the first has a fixed tag length of the output size of the hash function, and the second has a variable output length size from 0 (useful) to the hash function output size.One last question remains which is how to choose the HMAC keysize. Section 5.3.4 of NIST 800 107 states that the "security strength" of the HMAC is the minimum of the keysize and 2C, where C is the internal chaining length of the hash function (roughly, the amount of the result from the previous block that is fed into the next block when hashing a long string: for the PKCS#11 hash functions, that's 160 bits for SHA-1, 256 bits for SHA-256, and 512 bits for SHA-384 and SHA-512). Note that there's no point using a key which is longer than the input block size of the hash function (which is 512 bits for SHA-1 and SHA-256, 1024 bits for SHA-384 and SHA-512), since if you do, the first HMAC operation will be to hash the key and obtain a shorter one.

Conclusion

Another good reason to move straight to v2.40 of PKCS#11 when it finally arrives is support for a secure variable length MAC. Until then, your only secure choice for variable-length MACs is to use HMAC.

Download our PKCS#11 security white paper for more information.