Key derivation is a common operation in cryptographic protocols. It's used, for example, to generate a session key on the basis of contributions from a client and server, or to generate a series of unique keys for devices from a master key. While there are some security results for key derivation functions, it's an area that hasn't received a lot of attention from researchers. And like most crypto, it's surprisingly easy to get wrong.
Key Derivation in PKCS#11
The PKCS#11 API furnishes a whole suite of derivation functions, from those specific to TLS through elliptic curve functions, those based on various symmetric ciphers like AES and DES as well as some simpler functions. Unfortunately, a lot of these have pitfalls. In this post we'll take a look at three attacks.
The "You derive, I encrypt" Attack
One common way to derive a device-specific symmetric key is to take 1) a master key and 2) some public data unique to the device, like a serial number, and encrypt the data under the key. In PKCS#11 you can do this by calling the C_DeriveKey function with, say, CKM_AES_ECB_ENCRYPT_DATA or CKM_AES_CBC_ENCRYPT_DATA. Recall that in PKCS#11, if we want a key value to remain secret, we set its CKA_SENSITIVE attribute to TRUE. As you would expect, if C_DeriveKey is implemented as specified in the standard, deriving a key from a key which is CKA_SENSITIVE produces another key which is CKA_SENSITIVE. So far so good.However, we know there are problems in PKCS#11 if care is not taken with setting key roles using attributes. For example, suppose our master key, as well as having the attribute CKA_DERIVE set to TRUE, also has CKA_ENCRYPT set to TRUE.Bad news - an attacker can execute C_Encrypt using the master key and recover the value of the derived secret keys from the serial numbers. To avoid this, make sure you audit attribute settings carefully, and make sure they can't be manipulated by C_SetAttribute, C_CopyObject, C_Wrap/C_Unwrap...
Creaky Hash Functions
Another common usage for key derivation functions is password storage. For better or worse, many applications use PBKDF2 to derive a value to store in the password file that can be easily checked, but not so easily subjected to a brute-force dictionary attack. Unfortunately, with modern hardware such as GPUs, brute-forcing a password file based on PBKDF2 and the SHA-1 hash function (the only choice in PKCS#11 up to v2.20) has become a realistic threat.Fortunately, help is on the way in PKCS#11 v2.40, currently in public review phase, which will support the whole SHA-2 family for PBKDF2. A tip from a well-placed source: choose SHA-512, which is significantly slower in current GPUs.
Related Key Attack
Clulow's 2003 paper on PKCS#11 security (obligatory reading for anyone implementing or using PKCS#11) presents an elegant related-key attack on triple-DES (3DES) keys using theCKM_XOR_BASE_AND_DATA mechanism.Suppose we want to attack a 3DES key K1 that consists of the concatenation of three single DES keys, k1, k2 and k3. First we derive a new 3DES key K2 by calling CKM_XOR_BASE_AND_DATA and giving DATA Δ,0,0 where Δ is some arbitrary known value and 0 is a 64-bit 0 block.Now, if we encrypt some plaintext P under K1 and then decrypt it under K2, we getP' = d(k1+Δ,e(k2,d(k3,e(k3,d(k2,e(k1,P))))))= d(k1+Δ,e(k1,P)).Note this value only depends on k1, so we can brute-force search k1 in isolation. Clulow explains how to extend this to triple and double length keys, and how to make the brute-force search practical with parallel key search techniques (section 2.6 of Clulow, 2003). There are also attacks based on constructing a reduced key space using extracted bits (section 2.5).
Conclusion
Like most of cryptography, key derivation is tricky. If you're using PKCS#11, make sure your attribute settings and key management procedures don't leave you open these kind of attacks. Download our PKCS#11 Security Whitepaper to find out more.