What I want to do is deterministically derive a secure key from an RSA private key, such that the RSA private key cannot be derived from the secure key.

The first approach that came to mind was simply using the private key (or some fixed part of it) as the seed for a PRNG.

Since the output of AES is random, another idea is to use AES to generate the secure key, using the first 256 bits of the RSA private key as the AES key, and encrypting some known data.

Can anyone verify either approach, or otherwise suggest an alternative way to do this?

EDIT I left out the details of why I wanted to do this, to keep it focussed, but I guess it may be useful to know more:

I have an installer for a piece of server software that will run as part of a cluster. During installation, the installer will have access to a 'deployment' certificate - an X509 certificate that is used to sign certificates for each instance of the server (so, a CA certificate). Each server will also need to have access to a shared secret, which will be used to encrypt certain data that is shared between the servers (using AES). My thinking is that securely deriving this shared secret from the deployment certificate private key during installation is a low friction way to do it.

  • $\begingroup$ I'm not really sure what you're trying to do here, but couldn't you just use the private key to sign some prearranged block of data? Truncate the output to 256 bits if necessary. $\endgroup$ – r3mainer Jul 13 '17 at 20:52
  • 1
    $\begingroup$ @squeamish ossifrage: an RSA signature is very distinguishable from random for one with the public key (or even without: high bit is 0 more often than 1). Also, not all RSA signatures are deterministic, and that could be a problem in some situation (need to re-generate the same secret). And if an adversary can obtain a signature for the prearranged block of data, the secret leaks. $\endgroup$ – fgrieu Jul 13 '17 at 20:58
  • $\begingroup$ You can use some EC curves where you directly can derive the public key from a random private key. This is used in some schemes (formexample Minlock or Squrrl). For RSA it is better to not do that because of the multitude of steps you need to find proper primes which result in large classes of input values to map to the same keypair. $\endgroup$ – eckes Jul 14 '17 at 6:08

Unless you really want to actually "use" the RSA key in a mathematical way, you could actually just derive a password from it using a key derivation function (KDF) and using the certificate as a password...

There are two different kinds of KDFs: those you use when you have a poor entropy and are afraid of Dictionary Attacks (typically if you store humanly memorable passwords) like Argon2, and those that you use when you have a good entropy, which is the case if you rely on an RSA key. In the latter case, the HKDF is well suited for this.

The advantage of using HKDF is that you already have all the nifty feature you should otherwise implement:

  • you have a Salt, so you can easily generate different keys, if one is compromised, for example.
  • you have the notion of the label, so you can generate different keys for different usages.
  • you have the size as a parameter, so you can easily plug in another encryption function in case AES gets broken, without changing the key generation algorithm.

Nonetheless, just hashing it would still be at least as hard as either:

  1. finding your 'deployment' certificate
  2. finding a preimage to that hash

And in case you worry, since an X509 certificate is certainly not a common password, it would require as much computation power to build a dictionary attack against it than to actually brute-force your certificate... (Which is hard.)

Note that 1. is true since we do not consider obscurity to be of any use, so you should assume that the attacker knows how you derive your secret key.

So in the end, if the "secret key" is compromised, finding the corresponding preimage (aka your certificate) of the cryptographically strong hash is hard for any cryptographic hash.

As hash, I personally like Blake2, since it can produce a digest of any size you may need for AES keys, is fast and is robust, plus it sports a Salt, so you can simply change that salt and keep going if a "secure key" is once compromised. But you could go with SHA-3 (aka SHAKE128 if you want 128 or 190 bits AES keys) and a custom salt you append to your certificate, too. Blake2X is also advertised as a KDF when you have a high entropy source.

  • $\begingroup$ Nice, I love the simplicity of hashing the cert! Using a salted hash is also a good plan, since it means the key can be rotated/changed if it's desired/compromised. I'm working with .NET and need to use a FIPS validated function, which means SHA256 or SHA512/256 $\endgroup$ – Cocowalla Jul 14 '17 at 10:04
  • $\begingroup$ Actually using a good, fast KDF like HKDF should be the preferred way to go, I've edited my answer to mention this. $\endgroup$ – Lery Jul 14 '17 at 13:11
  • 1
    $\begingroup$ X.509 certificates are not usually secret though (e.g. the server will offer it up freely in any TLS connection). Presumably the pivate key, not the cert, should be hashed somehow? $\endgroup$ – Thomas Leonard Aug 26 '17 at 13:07
  • $\begingroup$ @Thomas if used to sign data, it cannot be public. So I assumed we were talking about the private key, yeah $\endgroup$ – Lery Aug 26 '17 at 13:11

I agree with @Lery, that using HKDF would be the best solution. You could use the d or p or q component of your private key (if you have direct access to them) as the IKM or salt value to ensure a deterministic derivation from your key.

If you do not want to do that or can't do because you do not have direct access to the key: RSA encryption/decryption can be used as a Pseudo Random Function (PRF) which can be used for a key derivation. Start with some value (shared secret, seed), and create a textbook-RSA signature for it. Preferably, you should feed that output into HKDF or at least SHA-256 afterwards.


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.