2
$\begingroup$

I want to build a deterministic key derivation tree, where the root is stored securely in a centralized service and the leaves are embedded in a multitude of devices. When a device wants to communicate with the back-end, the device supplies its ID and salt, and the centralized services derives the device-specific key from the root key and the device ID and salt.

Usually I would favor HKDF or another well known key derivation function for this purpose. But as we intend to run the whole service on a cloud provider, our choice of secure key storage is more limited.

Azure Key Vault has experimental support for AES-GCM on their managed HSMs. My idea is to use the device salt as input nonce (IV) of AES-GCM and device ID as associated data input and no plaintext as input. As output of AES-GCM I would use the generated tag as deterministic pseudo random key:

$\text{KDF}(key, salt, id) := \text{AES-GCM-encryption}(key, \epsilon, salt, id)$

where $key$ is the global root secret stored in the key vault, $\epsilon$ is the empty string used as plaintext GCM input, $salt$ is a 96 bit value used as $nonce$ in GCM, and $id$ is a variable length device identifying string that no device shares with another and is used as associated data input in GCM.

Is that construction secure…

  • assuming the salt / nonce is globally unique among the whole lifetime of the the key and over all device IDs?
  • assuming the salt / "nonce" is only unique for a specific ID and there can be several devices that share the same salt by accident (due to a collision of random values)?

Intuitively, I am pretty certain that with a globally unique salt, this construction should be a secure key derivation function. But this is hard to achieve for the use case we have in mind.

$\endgroup$
3
  • 1
    $\begingroup$ Are you using the nonce as key? Shouldn't it then be 128 bits in size? And why do you call it a nonce if it is a key? How is it created / managed? $\endgroup$
    – Maarten Bodewes
    Jul 23 at 22:19
  • $\begingroup$ Ah, my bad, I was so concerned with the rest that I forgot the important input in the formula. The nonce is the salt in HKDF nomenclature and there actually is a key that is created and backed up outside of the Key Vault and stored non-exportable in the Key Vault. $\endgroup$
    – Perseids
    Jul 24 at 6:36
  • $\begingroup$ Oh and another unfortunate side-effect of this setup is that the second level of the tree (i.e. the result of the first derivation) leaves the secured environment already. Ideally, only the path information (ids and salt for each derivation) would be supplied by the application server, but I don't see how to do that without special key derivation support of the secured environment. (Most dedicated HSMs would be able to do so, but not the managed interface the cloud providers provide.) $\endgroup$
    – Perseids
    Jul 24 at 6:47
3
$\begingroup$

First, to define the construction. AES-GCM when used in the suggested way is equivalent to $$\operatorname{KDF}(K,S,I)=\operatorname{AES}_K(S\|0^{32})\oplus \operatorname{GHASH}_{\operatorname{AES}_K(0^{128})}(I)$$

where $\operatorname{GHASH}_H(M)\approx \sum_i H^iM_i$ for message blocks $M_i$ of size 128-bit and the multiplications and additions being done in a 128-bit finite field with polynomial representation. This is an approximation of GHASH that will work for our below discussion.

Is that construction secure…

I'll call this KDF construction secure if it behaves like a PRF in both the inputs, subject to the named constraints, i.e. unique inputs yield independent pseudo-random outputs.

[Assuming] the salt / nonce is globally unique among the whole lifetime of the the key and over all device IDs?

As you can see from the above expression, assuming your salts are unique, the AES operation will mask any GHASH result and the output will look random and unpredictable. Given the answer to the next part though, it is questionable whether the associated data provides any useful benefit though, besides potentially obscuring a salt-collision event slightly.

[Assuming] the salt / "nonce" is only unique for a specific ID and there can be several devices that share the same salt by accident (due to a collision of random values)?

Unfortunately no. If two derivations use the same $(K,S)$ pair with two different $I,I'$ queries and an adversary learns the corresponding output keys $k,k'$, then an adversary can learn $k\oplus k' = \operatorname{GHASH}_{\operatorname{AES}_K(0^{128})}(I) \oplus \operatorname{GHASH}_{\operatorname{AES}_K(0^{128})}(I')\approx \sum_i H^i(I'_i\oplus I_i)$ which is an expression from which an adversary can recover $H=\operatorname{AES}_K(0^{128})$ allowing them to recover $k\oplus \operatorname{GHASH}_{\operatorname{AES}_K(0^{128})}(I) = \operatorname{AES}_K(S\|0^{32})$ and from there predict the derived key for any $I$ for this fixed $(K,S)$ pair.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.