I know this sounds crazy, but hear me out. As a follow-up to Can the AES-GCM authentication tag be used as a key derivation function?, I'm also considering more creative solutions to derive unique (symmetric) device keys from a securely stored root key.

(The background is that we have a lot of clients (=devices) that can't use asymmetric cryptography (mostly because of hardware constraints). To establish a TLS PSK connection we need a shared secret between backend and client. Instead of securely storing a unique key per client in the backend, we derive the client specific key from a root secret using device unique IDs.)

The motivation for usage of RSA keys comes from the Azure Key Vault pricing scheme and the availability of HSMs in different regions. Symmetric key operations are only available as "advanced keys" on HSMs, if I read the documentation correctly, and are thus 5 times more expensive than RSA operations (in addition to the step hourly HSM rate). Furthermore the limitation to select regions (where managed HSMs are available) might be a deal breaker as well.

So, to make do with ECC or RSA I have the following idea:

$\text{KDF}(key, data) = \text{SHA256}(\text{RSA-PKCS1v1.5-sign}(key, data))$

In words: Store the RSA key non-exportable in the key vault and use the deterministic PKCS1 v1.5 signature scheme as key derivation using arbitrary data as derivation value (e.g. a salt concatenated with device id). To break up the algebraic properties of RSA and to concentrate the keying material down to 256bit, the signature is hashed with SHA-256.

Intuitively, this is secure, because the signature is unforgeable and thus the concrete output value of the sign operation cannot be guessed (without the key). So somewhere in this signature there is enough "entropy" (unguessable bits) to be resilient to brute-force and this "entropy" should be evenly spread throughout the result of the hash operation.

Can some give a more rigorous reasoning (or even proof under standard assumptions)?

  • $\begingroup$ What do you mean with "somewhere in the signature there is enough entropy"? All the entropy is in the key and the salt, there is no additional entropy, as PKCS#1 signing is fully deterministic (of course, otherwise your scheme would not work as KDF, of course). I don't see much wrong with this scheme otherwise, unless salt and ID repeat of course. Unfortunately you cannot wish uniqueness out of thin air. $\endgroup$
    – Maarten Bodewes
    Jul 25 at 15:26
  • $\begingroup$ @MaartenBodewes Formally speaking, my intuition is completely incorrect, as you are right to point out. It's great to get conformation that this works, but I'm mainly looking for an argument that would convince someone skeptical. $\endgroup$
    – Perseids
    Jul 30 at 9:34

Your Answer

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

Browse other questions tagged or ask your own question.