I’ve built an app in which each user has a private/public key pair and I want to generate a second one for them, however I cannot store the second private key anywhere.

What would be the drawbacks of deterministically generating the second private key from static information signed by the first one, compared to generating it randomly? I could generate it again each time a user opens the app but is it safe?

This is in the context of a web app on Ethereum, which uses deterministic ECDSA.

  • 2
    $\begingroup$ Is the information it is generated from a secret? It sounds like you're asking about using the output of $\operatorname{sign}(\text{static info}, \text{private key})$ as the source material for generating the second key pair. Is that accurate? $\endgroup$ – Ella Rose Feb 14 '19 at 2:29
  • $\begingroup$ @EllaRose Yes exactly $\endgroup$ – Michael Lorig Feb 14 '19 at 2:33

Several issues with the proposition of generating a derived private/public key pair as (or from) a signature computed with a master private key.

  1. Not all signature schemes are deterministic, thus what's proposed might end up not allowing reproduction of the derived key.
  2. We would need to discriminate the particular message input to the signature scheme used to generate the derived key, and ensure that an adversary can not obtain the signature of that message with the master key, thus ruining the confidentiality of the derived key.
  3. For arbitrary signature scheme, we could imagine some security issue where signatures (past and future) with the master key weaken signatures with the derived key.

A more conservative option is to use the master private key itself as the key input of a symmetric Key Derivation Function (unrelated to the signature scheme), which output is (or is used to deterministically generate) the derived key. This can be generalized to any number of derived keys, using an auxiliary input of the KDF for a derived key type or index. That option assumes that the master private key is not in a box/HSM/Smart Card/enclave restricting its use to signature, and that a strict policy to the same effect is not in force (which is common, e.g. by reference to FIPS 186-4).

Update: a comment mentions that the master private key is not directly accessible (making the above conservative option impossible); and a deterministic (variant of) ECDSA.

If we can reserve a message $C_D$ (solving 2.), post-processing as$$\text{DK}\gets(H(\text{Sign}_\text{MK}(C_D))\bmod(n–1))+1$$seems to be good way to derive a private key $\text{DK}$ from master private key $\text{MK}$, with $n$ the generator's order and $H$ a hash at least 64-bit as wide as $n$ is. The modular reduction and 64-bit limit is per FIPS 186-4 apendix B.4.1. If $H$ is secure in the Random Oracle Model and as costly as a signature verification, then this is computationally secure (argument: an attack allows to forge the signature of $C_D$, or otherwise breaks the signature scheme, or the hash). It can only help to use a purposely slow KDF for $H$.

The above formula assumes ECDSA with only the signature TRNG changed to a deterministic PRF keyed by the private key. For EdDSA, we only need to hash the signature of the reserved message $C_D$ to the width of a private key, and condition that with the masking prescribed in EdDSA.

More generally, with a deterministic signature scheme, a reserved message, and a key generation procedure using a KDF independent of the signature scheme and at least as costly as signature verification, we are good to go.

Caveat: any key derivation should be performed in a safe environment, or otherwise guarded from side channels.

| improve this answer | |
  • $\begingroup$ Thanks for the thoughtful answer. Are those the only 3 drawbacks? The signing algorithm is not arbitrary and is a deterministic ECDSA. Unfortunately I don’t have access to the first private key, only the signing function. $\endgroup$ – Michael Lorig Feb 14 '19 at 14:06
  • $\begingroup$ I presume that generating a stronger key than the original one may not be advisable, as it relies on the strength of the original (if it is used for other purposes). Similarly, the access conditions of the derived key cannot be stronger than the original one. ECDSA is indeterminstic in its most used form and deterministic ECDSA may not always be available (so you may e.g. have to go for a specific software library on some systems). $\endgroup$ – Maarten Bodewes Feb 14 '19 at 14:36
  • $\begingroup$ For EC(DSA) key pair generation is well defined, for others such as RSA it is not (the requirements are clear, but it isn't clear how an implementation meets the requirements). Still, implementations may now allow you to directly inject a private key value. Injecting a seeded Deterministic Random Bit Generator instead is tricky because the key is a number between 1 and the field size (uh, or order?) and there are many ways of generating such a number from a DRBG. fgrieu, feel free to copy some of this into your answer. It's too good to put one next to it. $\endgroup$ – Maarten Bodewes Feb 14 '19 at 14:39

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.