1

Is there a scheme that let people derive public/private key pair from arbitrary secrets?

As you may know, digital signature schemes have versatile use cases. The problem is, the key pair handling is too difficult for end-users. On the other hand, the concept of password is pretty much ubiquitous; people can handle it without much difficulty.

To enable digital signature for end-users, there must be something or some scheme that bridges the gap.
I can't imagine how non-techies can use ssh-keygen to establish their digital signature and carry the private key around securely, hence the question.

2

It's possible, but there are some caveats to be aware of.

At first glance, it might seem that ECDH lends itself well to this, as an ECDH private key is nothing more than a 256-bit value.

So, in theory, you could simply take the SHA256 hash of your password, which will return a 256-bit value, and use this as the ECDH private key. Then, the ECDH public key can be derived from the private key. However, if your password is easily guessed, or appear on list of known passwords (such as rockyou.txt), your private key may be easy to crack using a rainbow table.

To mitigate the above problem, keys are often derived from passwords using a random salt, and many rounds of hashing (e.g. PBKDF2). However, in your use-case, this poses the problem of where to store the salt?

6
  • 2
    For signature use ECDSA not ECDH (but the key is the same) -- or EdDSA (and it isn't quite just an n-bit value). Bitcoin uses ECDSA with secp256k1, and some people tried using SHA256(password) as the key calling it 'brainwallet' -- i.e. your wallet is in your brain. As predicted most of their keys could be guessed and their bitcoin stolen, which was not considered a resounding success. Bitcoin also came up with BIP-39 which like diceware and some other previous schemes uses machine chosen words from a fixed vocabulary, usually 24 from 2048 = 256 bits, fed into PBKDF2. ... May 28 at 0:25
  • ... People can't actually remember these 'seed phrases' (which aren't really phrases at all, since the words are random) but ordinary non-geek humans can store and transmit them reliably (by writing on a piece of paper, speaking over the phone, etc) which they usually don't with computer-y hexadecimal or Bitcoin's first attempt, base58. May 28 at 0:26
  • @dave_thompson_085 Well an ECDSA (not ECDH) private key is not exactly just n bit value either. It is a number between 0 and n, where n is the order of the curve subgroup used for ECDSA(usually a prime number). EdDSA private key is n bit string used to derive two components, one the private scalar (as in it's parent general Schnorr's or ECDSA) and another to deterministically generate nonce (yet secretly) from the message, in order to solve potential nonce resuse problem due to bad random number generator or low entropy source of seed. (a serious danger because it can reveal the private key) May 28 at 5:45
  • In above comment I did not mean ECDH private key is just a n bit value, it is also a number less than the prime suborder of the group used. I meant it is not a signature algorithm but a key exchange one May 28 at 5:57
  • What I get from this is EdDSA could work, but with more details than what appears in the answer. (As the info presented here, the private key could potentially be derived by hash+mod.) I know I need more details on this, so I'll look into it. Thanks May 28 at 15:10
1

DISCLAIMER: This answer is a wild abuse of RSA keygen. I would think really hard about whether your use-case will allow HMAC signatures instead of RSA signatures before you resort to a kludge like this.

I would also consider a centralized key-management solution where the server generates the user's keys and gives it to them as a password-protected ssh or p12 key file. I've even heard of some digital signature cloud platforms where the user's RSA keys actually live in the cloud and the user needs to do password / API key / SSO MFA auth in order to use the signing platform.

So, I'm answering the question as asked, but I think this solution is ill-advised if any other solution is available that does not weaken the RSA keys themselves by kludging how they are generated.


I have seen terrible-horrible hacks that accomplish deriving RSA keys from short secrets in the following way (java pseudocode):

KeyPair genRsaKeyFromSecret(byte[] secret) {
  byte[] hashedSecret = KDF(secret); // use whatever kdf you think appropriate
  
  // use hashedSecret as your RNG seed
  SecureRandom rng = new SecureRandom(hashedSecret);

  // RSA keygen using that deterministically-seeded RNG
  KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
  keyGen.initialize(2048, rng);
  return keyGen.generateKeyPair();
}

More Security Warning!

Now, just because I've seen it done does not mean it's a good idea.

You've kludged your RNG to generate deterministic RSA keys from a password, which was your stated goal, but it makes the cryptographers of the world collectively shudder because brute-forcing the private key from the public key is only as strong as the password that was used to seed the RNG (though I'll admit that RSA keygen is a damn slow hash function so that brute force would take a long time...).

The typical password has ~ 40 bits of entropy [1], which is roughly equivalent in strength to RSA-512 [2]. If I was evaluating this system, I would ignore the actual RSA key size (2048, 3072, 4096, etc), and I would evaluate the system as if those were RSA-512 keys, which ... spoiler alert ... is gonna fail security review unless you're, I don't know, using them to make art, or something else that does not need more than 40 bits of security.

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.