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)?
