In 2004, Intel, Nokia, Panasonic, and Samsung among others announced plans for a licensing and compliance framework called Content Management License Administrator (CMLA) (see www.cm-la.com). This body was formed to address necessary business concerns and enable rapid delivery of high-quality digital content to mobile handsets and other devices that deploy Open Mobile Alliance (OMA).
CMLA's goal is to provide vendors and service providers with clear processes and guidelines for robust and compliant OMA DRM Version 2.0 implementations making their product development cycles faster and easier. Ultimately, CMLA will assist in bringing consumers greater access to new and emerging digital content such as music, video clips, games etc.
CMLA asked Cryptomathic to help improve the security without influencing performance. To this end, Cryptomathic made a proposal, which has now been adapted by CMLA, and an international patent application has been filed by CMLA with the Cryptomathic cryptographers as inventers.
The approach that was taken was to ensure that keys were of maximum entropy, i.e. "as random as possible". A scientific paper has been submitted for publication and will be published very soon, and we include here an abridged version of the introduction:
A key derivation function (KDF) is a function that takes as input a (short) string of random bits and outputs some number of (pseudo-randomly chosen) keys for some cryptosystem, typically keys for a symmetric cipher such as AES. This can be useful, for instance, in situations where we have a truly random seed of limited size, but we need to generate many keys.
Of course, any secure pseudorandom generator G can be used as a KDF in a simple way: just split the output from G in a number of consecutive k-bit blocks, where k is the length of keys we want, and output each segment as a key.
Now, the important question is, of course, whether the encryption we get by using the KDF-output as encryption keys is as secure as if we had chosen the keys independently and uniformly? For the simple construction just mentioned, we can say that the answer is yes if G is a good pseudorandom generator, since this means that the adversary cannot distinguish G(R) from a genuinely random string.
But this point of view is overly simplified, for several reasons: first, a pseudorandom generator is not simply "good" or "bad", it has a certain amount of strength, depending on exactly how hard it is to distinguish its output from random. It may be prudent to design our KDF construction so that all security is not lost, even if the generator turns out to be weaker than we had hoped. A second - perhaps more important - point is that, while pseudorandom generators are usually seen as general methods for making bits that are as good as random for any practical purpose, we have a specific application in mind, namely to generate cryptographic keys. In this application, certain specific properties may be especially important, and we should consider whether we can make sure they are satisfied.
One such property we consider is called local g-uniformity. A locally g-uniform KDF has the property that any subset of g output keys is genuinely uniform.
Why is this a nice property? In the special case where only a single key is generated, it seems reasonable to demand that this key is genuinely random, as long as the seed contains enough randomness for this to be possible. Local 1-uniformity ensures this. But local 1-uniformity is also desirable when several keys are generated: As mentioned, the adversary will not be looking directly at the keys, instead he will have to try to break the encryptions we produce using the keys. Say we use the keys for some block cipher like AES. Now observe that, as long as the adversary tries to break encryptions produced from a single key Ki, then since Ki is uniform, this will be as hard as simply breaking AES, i.e., using this type of attack, the adversary cannot exploit the fact that the keys are derived by a KDF.
In fact, the only way he can do so, is by attacking at the same time encryptions under at least two different output keys Ki, Kj and somehow use the fact that Ki, Kj are not independent. This can reasonably be expected to be harder than attacking a single key and exploit that this single key is not uniform, which would be a possibility for the adversary if the KDF was not locally uniform.
Motivated by this, we chose a KDF construction which augments a pseudorandom generator G with universal hashing. This construction guarantees local (almost) 1- uniformity for any desired key length, assuming the seed is sufficiently long, given that G satisfies a condition we call local randomness. This is much weaker than local uniformity and loosely speaking says that if we split the output from G in consecutive blocks, then each block contains at least some (small) amount of randomness. This construction needs as secret seed only what is needed as input for G.
Previously published in Cryptomathic NewsOnInk, 2005