Symmetric Key Diversification

In symmetric cryptography it is often necessary to "derive" new key material from a master key. This is called "key diversification" or "key derivation", both meaning the same thing in this context. A system that creates key material from a master key is called a "KDF" (Key Derivation Function).

KDF Basics

The basics of how a Key Derivation Function works are quite simple. The KDF takes as input:

1. The Master Key value
2. Some unique input (product serial number, password, etc)

This all gets fed into a PRF (Psuedo-Random Function) which is really the core component of the KDF. And the output from this is a brand new key, derived from the Master Key using the unique information.

An important constraint of the KDF is that it operates as a "One Way Function". This means that you can go from Master Key -> Derived Key, but you can't go backwards from Derived Key -> Master Key.

This means that only someone in posession of the Master Key can create the derived keys, but those derived keys can then be distributed to people/smart cards/devices without exposing the Master Key at all. In fact the Master Key stays private to the issuer of the derived keys.

NIST 800-108 in Counter Mode

The National Institute of Standards and Technology publishes recommendations for some key derivation functions. Here I will outline how the "counter mode" KDF in SP800-108 is functioning, and provide a working implementation to play with.

The NIST 800-108 Counter Mode depicts the process working in Fig.1 in their document, as follows:

The diagram shows a PRF (Psuedo-Random Function) as the core component, rather than a KDF. Why? 🤔

The answer is that this system describes PRFs being used for the purpose of deriving keys, and the system as a whole is a KDF. In practice this would be a black box to which the user supplies the Master Key and the Diversifier, and gets the derived key as an output. But here we are looking under the bonnet of the KDF.

The PRFs themselves can be any cryptographic function that qualifies as a PRF. So it could be a HMAC with a Cryptographic Hash Function (HMAC-SHA1 for example) or it could be a PRF based on a Block Cipher (for example CMAC-AES).

The NIST diagram is slightly confusing, in my opinion, because it depicts three separate inputs to the internal PRFs: the Master Key, Fixed Input Data, and a counter variable 'i'.

In fact, there are only two inputs to the PRFs - the Master Key, and the Fixed Input Data.

The counter is present, but it's actually part of the Input Data. Which should really not be called "Fixed" anymore, because it has a dynamic component of it called the Counter and this gets incremented for each round of PRF in the process.

So let's adapt their diagram a little to try and make this more clear:

Here we show that the PRFs in the process take just two inputs; Unique Input Data and Master Key. You could further argue that inside the PRF itself, in the nuts and bolts of it, it's all one single input with the Master Key woven into the algorithm of the PRF along with the unique data in some very specific way. But when you invoke a PRF via some software procedure you will typically provide Key and Input Data as separate parameters to the function and my aim here is to mirror the lived experience of Software Developers with a diagram that fits the same scenario.

A constituent part of that Unique Data is the Counter variable, incremented for each round of PRF. And so now it is necessary to define exactly what is the nature of this Unique Data, what is inside it, and what are all of its constituent parts.

Unique Input Data

The first thing to say about the Unique Input Data is that this will be the information in which at least part of it uniquely identifies or applies to the recipient of this diversified key - whether that be a person, an instance of a product, a smart card, etc.

That is how the derived key for this recipient will be different to the derived key for the next recipient. So it needs to be unique in that respect, and it needs to be an identifier so that it can be easily recalled on demand when that person, product etc will use the derived key to communicate with you in the future.

It's important that the construction of the Input Data is defined and understood in your system, so that the key diversification can be repeated properly in the field. Everyone who uses your key diversification process must construct the Input Data in exactly the same way.

The NIST 800-108 specification creates a specification for the constituent parts and construction of the Input Data. So if you wanted to have a common understanding with someone else who told you they implemented the NIST 800-108 specification, the default position (unless you were told otherwise) would be to construct the Input Data in the manner that NIST 800-108 defines.

So now I will look at how NIST 800-108 defines the input data, what are its constituent parts, and how the full blob of data gets constructed according to NIST.

Components of the Unique Input Data

Here's how the Input Data looks in NIST's specification:

The definition of those parts is as follows:

Counter

This is an integer to hold the counter variable that is incremented for each round of PRF invocation.

The size (num bytes) of counter is not defined by NIST 800-108 and therefore has to be agreed in user implementation. It almost certainly doesn't make sense for it to require more than one byte, but in practice when we say "integer" we can mean 8 bits, 16 bits, 32 bits etc and so it depends on implementation as to what space is occupied by the counter in the Input Data.

Label

This is a string intended to convey the purpose of the derived key (what is it used for). But it's up to you to define what gets entered here and it can of course be left blank as well.

Separator

This is a single byte separator with pre-defined value 0x00

Context

This is where the diversifier string goes. Your unique information. Product Serial Number, Smart Card UID, etc.

Length

Here we define the length in bits of the derived key that we require. e.g. 128, 256 etc.

How Does it Work?

The way this whole process works is very simple. Refer to my block diagram above:

The Master Key and Input Data is presented to each iteration of the PRF. The iterations can be sequential or parallel, it depends on your implementation. For each iteration of the PRF, the counter value in the Input Data is incremented by 1.

The output of each PRF is a random-looking string, generated from the Master Key and the Input Data. The strings from each PRF output are concatenated together to create the full diversified key value.

It should be understood that although the output of each round of PRF looks random, the same round supplied with the same input data and master key will always produce the same output. That's why the counter is there: the master key is fixed, the rest of the input data for a given context is fixed, and so something has to change between iterations in order to get something different as output in each iteration. That thing that changes is the counter.

How Many Counter Iterations?

So, how many times do we need to iterate over the process?

This turns out to be an interesting question. First, let's explain why we need to iterate:

Why We Need a Counter and Iterations

To answer this, we need to consider the limitations of the PRF at the core of the KDF. Depending on what you select to use here, you will typically get a fixed-size output. For example if you choose HMAC-SHA1, then the fixed output size will be 160-bits. If you choose CMAC-AES-128, then the fixed output size will be that of AES-128: 128 bits.

So the reason why we would need iterations is if the target output key size is larger than what can be generated by a single instance of the PRF. In that case you invoke multiple iterations, changing the counter variable each time (so that the output will be different), and then you concatenate the outputs of each PRF together to make whatever size derived key that you want.

So now, to answer the question "how many iterations", you will refer to the Key Length that you set in your Fixed Input Data and you will look at the Fixed Output Size of your PRF. Here are some examples:

1. CMAC-AES-128, Required Key Size 128, Number Iterations: 1
2. CMAC-AES-256, Required Key Size 256, Number Iterations: 2
3. HMAC-SHA1, Required Key Size 128, Number Iterations: 1

Simplified NIST 800-108 Counter Mode

This of course means that provided your required output key size is equal to or shorter than the output of a single instance of your PRF, the complicated diagram can be simplified to:

Here we just have a single PRF with the Input Data as the diversifier, and a Master Key input. The output is our diversified key. If our output is longer than the required key size, we simply trim it. And that's all.

We are still feeding in the Counter, but of course it never gets incremented so you can argue that it is totally redundant. And it is! But we still include it in this example because that is the stated structure of Input Data for NIST 800-108. If you prefer to ommit the Counter in your own implementation, you can of course do that.

NIST 800-108 Counter Mode Demo

Below is a fully working implementation of NIST 800-108 Counter Mode. Here you can set the Master Key, All your Input Data, and then you will get a Derived Key as an output. The size of your output is determined by the Key Length that you set. If your Key Length is larger than the output size of the PRF, then the algorithm uses the Counter and iterations of the process as described earlier.

I Require the Simplified Scenario. Do I Even Need NIST here?

If you have asked this question, then you have fully understood what is going on.

Especially for the simplified case, there is nothing special that NIST is doing. They are just using a PRF with Master Key for the key input and a Diversifier for the Input Data. That's all. So you don't even need to make any special implementation - you just invoke the required PRF and feed it those inputs, you will get the same output!

NIST are just specifying how to diversify keys by using a PRF, how to handle the scenario where your required Key is larger than the PRF output, and recommendations for building a consistent Diversifier. That's all.

For the simplified case, it is entirely equivalent to this:

NXP AN10922

Another common method of symmetric key diversification is NXP's application note AN10922, which you can read about here.

AN10922 is really geared towards key diversification on smart cards, and in particular DESFire cards. There's no reason in principal why it couldn't be used more generically (like NIST 800-108), but NXP's intension in creating this process is to use it on Smart Cards and that's how they have structured their associated documentation.

Unlike the NIST 800-108 Counter Mode diversification, which left the choice of PRF entirely to the user, NXP's method explicitly specifies the PRF as being AES-CMAC. They propose methods for AES-128-CMAC, AES-192-CMAC and AES-256-CMAC. But they use a slightly modified CMAC implementation, which I will describe shortly.

Their AES-128-CMAC method is the simplest to describe, so I'll tackle that first. The other methods for AES-192 and AES-256 are only slight extensions of the AES-128 method so they will be easy to understand once the AES-128-CMAC method has been covered.

AES-128-CMAC Block Diagram

Let's take a look at the block diagram for NXP's AES-128-CMAC method, below:

The way this is working is as follows:

We start off with our diversifier. This is your unique information that will be used to diversify the key for your particular context. e.g. Smart Card UID. In AN10922, the diversifier must be between 1 and 31 bytes in length.

Next, we prepend a Div Constant to the diversifier. This is a single byte. For AES-128 diversification, the Div Constant is 01. But for AES-192 and AES-256 the scenario is a bit different and they use different constants. I'll cover the differences there later.

This means that our full length diversifier can now be up to 32 bytes.

Next, we send our diversifier into a padding function. The purpose of this function is to insist that the diversifier as it is presented to the CMAC function is exactly 32 bytes in length. So if our diversifier was already 32 bytes long, it does nothing. If it was less than 32 bytes, it pads the diversifier with a 1 bit and 0s to make it up to 32 bytes altogether.

This 32 byte diversifier is then subjected to a CMAC operation, along with the Master Key. A boolean is also sent to the CMAC operation to tell it whether padding was required or not.

The output of this operation is our diversified key. It's really just a CMAC operation with the Master key and the diversifier input.

Modified CMAC

The CMAC operation I just described is not quite regular CMAC. In regular CMAC, the padding function is done internally within the CMAC operation itself. But in the AN10922 flow, padding is being done externally. Why?

The answer is, that AN10922 wants to insist on a fixed length diversifier. But in regular CMAC, the message that goes in can be an arbitrary length. In order to implement NXP's diversifier restriction, the padding is done externally and fixes the diversifier explicitly to 32 bytes only, with 31 bytes available to the user and 1 byte as the Div Constant.

But the CMAC operation itself needs to know if padding was done, because it uses that as a decision maker for how the final step of the CMAC operation is completed internally. Let's look at how regular CMAC works so we can understand what's going on. I am going to show you in block diagram form below what would happen in regular CMAC if it was fed our diversifier information. In the first scenario, the diversifier supplied is exactly 32 bytes and no padding is done. In the second scenario, the diversifier was somewhere between 17 and 32 bytes and padding was done.

So you can see that the two scenarios, padding and no padding, are broadly similar but with just some small but important details changed.

No Padding

In the no padding scenario, the diversifier gets split into two 16-byte blocks (because AES works with blocks of 16 bytes) and then there is CBC encryption on the two blocks using the Master Key. On the second and final block, the output from block one additionally gets XOR'd with a subkey, K1, before going through the regular encryption and producing the tag - which you use as your derived key - as output.

Padding

In the padding scenario, it's broadly the same but at the final step we do the padding on block 2 to make it 16 bytes, and it then goes through the same process except we use a different subkey, K2, for the XOR operation.

K1 and K2

Where do K1 and K2 come from? These are subkeys that get generated internally within the CMAC algorithm. And essentially what we're saying is that when no padding was required, we use K1 at the final step and when padding was required we use K2 instead. This all gets handled internally within CMAC.

I won't cover in detail the reason for this little dance with K1 and K2 here. But it has to do with fixing some vulnerabilities that were found in previous CBC based MAC implementations.

External Padding Summary

So now you can see that because NXP completes the padding externally in its AN10922 implementation, it has to supply a boolean to the modified CMAC function so it knows whether to use K1 or K2 at the final step.

The padding is done externally so that a strict 32 byte diversifier can be mandated.

Diversifier Construction

What goes in the diversifier?

In practice, anything you want as long as it is between 1 and 31 bytes in length. But if you want to say you are diversifying in accordance with AN10922, you should construct your diversifier in exactly the way that they describe. And they describe it like this:

DIV CONSTANT

This is a pre-described constant. For AES-128, the constant is '01'.

CARD UID

Each smartcard has a unique ID. This is really the meat of the diversifier, because it is how your diversified key will be linked explicitly to your context (a particular individual smart card).

DESFire AID

In this section you place the Smartcard ApplicationID which the key relates to.

SYSTEM IDENTIFIER

And this is a kind of free field where you place some information relating to the system, in ASCII.

AN10922 Example (AES-128)

In NXP's AN10922 documentation, they supply a set of comprehensive worked examples, walking you through what happens at every step. For the AES-128 example I will just cherry pick the pertinent information because I want to show you how it can be done with a simple CMAC function.

In this example they state:

1. Master Key: 00112233445566778899AABBCCDDEEFF
2. Diversifier: 0104782E21801D803042F54E585020416275
3. Diversified Key: A8DD63A3B89D54B37CA802473FDA9175

Note the colours of the information in the diversifier and how this relates to the diagram of the diversifier construction I posted earlier.

NXP are saying that given the above Master Key as input, and the above diversifier, the diversified key should be A8DD63A3B89D54B37CA802473FDA9175. So we can test that by feeding it into a CMAC function, and see if that's what we get as output.

But wait... wouldn't we require a modified CMAC function, with the padding done externally etc?

Answer to that is "sometimes" you would require that. Essentially, if your diversifier length is 16 bytes or less, you will need to build a modified CMAC function in the way that they've described. This is to ensure that the diversifier gets padded properly to 32 bytes.

But if your diversifier is at least 17 bytes long (and not exceeding 32 bytes of course), you can just use a standard CMAC function. Because in that case the padding will be done internally, and correctly, by the standard CMAC function. It will pad the final block out to 16 bytes and that, combined with the previous block, is our 32 bytes.

The worked example that NXP supplies for AES-128 happens to be 17 bytes long: 0104782E21801D803042F54E585020416275.

So this means a standard CMAC function will pad it properly. And if we feed this now, into a standard CMAC function, we should get the output they've listed. Let's try it!

AN10922 Example (AES-128) using standard CMAC function

So go ahead and put the information into this dialogue. Select AES for the algorithm (this is actually AES-128). Make sure you select "Hex" for the Key and Input fields. Then paste the Master Key value into the Key field, and for the Input paste in the diversifier. You should get the stated output!

So now we've understood it. If your diversifier is between 17 and 32 bytes (including the DIV Constant), you can use a standard CMAC function.

If you diversifier is (or can be) less than 17 bytes, you need to implement your own modified CMAC function that will ensure padding gets done to 32 bytes and then send in a boolean that tells the function whether to use K1 or K2 in the final step.

What about AES-192 and AES-256?

AN10922 is supporting a flow for both these algorithms. They follow broadly the same process, but a key difference is that because the output of a CMAC function using AES is always 16 bytes, you need multiple steps to accommodate keys larger than 16 bytes. AES-192 has 24 byte keys, and AES-256 has 32 byte keys.

So the flows for these use two steps and some concatenation to build the required output. And there are also different DIV Constant values to be used. This is all explained in their documentation and I think once you have understood what is going on for the AES-128 case, the extension of that to the AES-192 and AES-256 cases is very straightforward.