Robust CMAC-based key derivation function

I need to select a key derivation function that will likely be used in contexts that I haven't anticipated. It will run on very low-end devices (think potato-powered IoT sensor with a bulk cost of a fraction of a cent). It will also run on higher-end devices that have the luxury of a hardware AES accelerator (costing a larger fraction of a cent), sometimes specifically an AES-CMAC accelerator. As a consequence, the key derivation function must be based on AES-CMAC. Since this is for low-end devices, efficiency is a concern: we want to keep down CPU cycles, RAM usage and code size.

I don't have any strict compliance or interoperability requirements. However, it's likely that some products using this KDF will want to obtain certifications such as FIPS. And it would be nice if the KDF was easy to implement on existing crypto APIs such as PKCS#11.

The obvious candidate is SP 800-108 KDF in counter mode. In a nutshell, output block $$i$$ is $$\mathrm{out}[i] = \mathrm{CMAC}_{K}(i \mathop\Vert \mathrm{info})$$ But it has a number of downsides:

• This requires a secret master key $$K$$ of exactly 128 bits. That's perfectly fine where $$K$$ is a master key that's generated for the sake of this key derivation function. But it isn't suitable, for example, to derive material from an ECDH shared secret.

• If the secrecy of $$K$$ is compromised, this breaks the security of the KDF — if you know $$K$$, you can create collisions in the output. This is fine when this construction is used with HMAC or KMAC but not with CMAC. SP 800-108r1 offers a countermeasure:

$$\mathrm{out}[i] = \mathrm{CMAC}_{K}(i \mathop\Vert \mathrm{info} \mathop\Vert K') \qquad \text{where } K' = \mathrm{CMAC}_{K}(\mathrm{info})$$ But it isn't completely clear to me what the security properties of this construction are with respect to a party that knows $$K$$.

• It processes the whole input for each output block, which is inefficient in terms of both CPU cycles and RAM usage.

Is there a key derivation function that meets the following requirements? If not, what comes closest?

• Requires only AES-CMAC as a cryptographic building block.
• Takes two inputs secret and info of arbitrary length up to a reasonable bound.
• Can produce at least a few kilobytes of output, incrementally.
• Can be implemented in $$O(1)$$ memory with respect to the length of the inputs, even when emitting output blocks incrementally.
• Has good security properties. I'm not sure what the formal security properties should be, but they should cover the case where two parties know the “secret” input and can select part of the non-secret input, and predictability or collisions in the output are a concern. Basically, I'd like to have the same security properties as a hash-based KDF, because it's likely that people will take existing protocols built for a hash-based KDF and they'll substitute my KDF because AES is more efficient on their device.
• Has been studied by cryptographers. I'm reluctantly selecting my own because the world doesn't seem to have settled on one, but I don't want to completely roll my own.
• A comment and questions: What is the plan for randomness extraction? The questions only hints at expansion, but also notes that extraction has to be solved somehow(e.g; when the key is an ECDH output). I believe, CMAC can also serve as an extractor, provided a proper random (non secret)salt is used as AES key. But the salt cannot be attacker controlled and has to be uniform random. Commented Oct 22, 2023 at 22:19
• Can you expand more, on the security requirements for when the attacker knows the secret? Most analyses don’t guarantee anything in that case. IMHO, security is lost at that point. One scenario with such I can think of is key combining when we wish for the prf to be secure when keyed via either the message or the key. But generally other scenarios only require that the inputs are unique. So the output need not be secret with HMAC-like kdfs in this scenario but the collision resistance with respect to the input is at least nice as you mentioned. Commented Oct 22, 2023 at 22:28
• @MarcIlunga Randomness extraction (from a high-entropy secret like an ECDH shared secret, not stretching from a password) is one of the goals. I don't know exactly what the security model is, and that's kind of part of my question (or maybe it should be a separate question?). I don't control what people will do with the KDF once it's established as a primitive that's easy to call. For example EAP-TLS derives IV by calling a PRF with an empty secret, and it's plausible that some people will copy that with whatever KDF I choose here. Commented Oct 23, 2023 at 9:32

It seems to me that your requirements are such that you can't solve the problem as it appears to be stated.

• You only have AES.
• You have no AES key.

And that's an issue. Without a key, then AES is just some function that emits pseudorandom, but guessable numbers.

However, you also have this secret ECDH key. If you had a hash function, you could turn that into a short secret key. But you don't have that. Wellllllll, if you did..... Maybe that's your answer?

Okay, okay, you can't add the extra code. Fine. We can't solve your problem that way. Let's look at other solutions. Here's the best one I can think of:

How did you get the ECDH key on that device? Where did it come from? Can you also send over another 128 bits as an AES key? If you can, you can then use CMAC and Alice is your auntie.

Given your constraints as you have described them, I think your easiest solution is to provision the device with an ECDH key and a CMAC key. If you do that, the problem has a solution. If you don't do that, then you need to do find some solution like adding in a hash function for a KDF.

Do I understand your situation properly?

• I think you misunderstood the question. I'm not trying to deterministically construct a secret without secret data. That's obviously impossible. I'm trying to construct outputs that can't be predicted better than brute force, even knowing the inputs. For example, if $F$ is HMAC with a known key, then $H(A||B) = H(A||B') \implies B = B'$. This is not true if you replace $H$ by CMAC with a known key. There are protocols that rely on this uniqueness property and are normally used with hash-based KDF. I want to construct a function based on AES with that property. Commented Oct 25, 2023 at 11:13
• I thought I might not understand, but now I think I do. You want AES to be a hash function. It isn't. One can form hash functions from block ciphers, but that's tricksy. (I'm one of the Skein creators, by the way.) I'll even say that everyone who made a hash function out of AES or its round function failed one way or the other. Better said, there turned out to be better solutions than using AES. More secure, faster, whatever. AES is not a hash function. You might be able to warp it into a good enough hash, but that adds code size and at some point you could just add in a hash function. Commented Oct 26, 2023 at 21:09
• Thus -- you can't. That's the answer. Your main constraint seems to be code size; the obvious solution to your problem is to throw in a hash and use an HMAC. The less obvious solution is to note that the obstacle to using CMAC as a hash is that the security totally rests on a secret key. Thus, a possible way out of the dilemma is to put a secret key on the device. That was my suggestion above. Bottom line: you either have to provision a 16-byte secret or add code. Either works. If you can do neither, then you're kinda out of luck. Commented Oct 26, 2023 at 21:13
• “You want AES to be a hash function.” Kind of, yes. “It isn't.” If you expand on that, it could be an answer to my question. “the obvious solution to your problem is to throw in a hash and use an HMAC” That was my first answer as a crypto engineer, but there's a very strong push for AES for a technical/business reason (devices with accelerated AES but no accelerated SHA). I still don't understand where you're going on about having a secret on the device — there is one, but that doesn't help because in some scenarios, it's not an input to the KDF. Commented Oct 27, 2023 at 10:31