2

I am looking for a password based key derivation scheme that results in an asymmetric key pair. I have worked with PBKDF and its variants but could not come up with any way of generating a key pair. I have studied stuff online but the restrictions on the password do not suit me like password must be from a cyclic group etc. Any directions will be much appreciated!

The Nutty Professor
  • 67
  • 1
  • 3
  • Yuck. What problem are you actually trying to solve? – Deer Hunter Mar 01 '16 at 11:36
  • @DeerHunter Basically I need to generate an asymmetric key using PBKDF or anything similar. The input is a password and the output is a keypair. – The Nutty Professor Mar 01 '16 at 11:44
  • An asymmetric key has peculiar mathematical properties that are unlikely to be true for a random bit sequence. Your use case is also mighty unclear. – Deer Hunter Mar 01 '16 at 11:58
  • @DeerHunter I have a device identity which will be used to generate an asymmetric key. I would prefer the PBKDF because the device ID is kept secret. Is there anything you can refer me to? – The Nutty Professor Mar 01 '16 at 12:49
  • Why don't you pre-gen the keypair? IDs have low entropy. – Deer Hunter Mar 01 '16 at 13:55
  • 1
    If you have a password that has sufficient entropy against bruteforcing, you could use it as a seed to an appropriate PRNG to generate large numbers to be sieved by primality tests to obtain a pair of primes to be the modulus of RSA keys. But why do you need to choose a password? You could much better (secure) use system randomness for getting the large numbers and you can also use an algorithm to generate provable primes instead of the statistically highly probable primes. – Mok-Kong Shen Mar 01 '16 at 14:06
  • [Addendum:] To render my earlier comment clear: To get the advantages of asymmetric encryption you have anyway to render your public key public. Once that is done, there is no need/sense at all to keep anything in order to be able to repeat the generation process. That's why I argued that you don't need a password (something to be secretly and securely kept). For RSA key generation with provable primes employing system randomness, I have a Python code at s13.zetaboards.com/Crypto/topic/7234475/1/ – Mok-Kong Shen Mar 01 '16 at 14:35
  • 1
    @DeerHunter I am doing research on a system in which the key pairs are never present on the system. You generate the key pairs and then discard them thus eliminating key theft (an Achilles heel in crypto). – The Nutty Professor Mar 02 '16 at 10:44

1 Answers1

2

Any asymmetric key pair generation can be described as a deterministic algorithm that feeds on a random source. Thus, generically speaking, you can turn a password into a public/private key pair by doing the following:

  1. Process the password into a "seed" of sufficient length (say, at least 128 bits) with a password hashing function.

  2. Feed that seed into a cryptographically secure PRNG to extend that seed into as many pseudorandom bits as necessary.

  3. Run the key pair generation algorithm with the seeded CSPRNG as source of randomness.

This kind of process has several important drawbacks that you should be aware of:

  • It requires a completely specified and unchanging key pair generation algorithm. For instance, for RSA, the algorithm concept is to produce random numbers until prime integers of the right size are found, but in the password-based setup you would have to be very precise on how exactly you turn the random bits into a candidate integer, and so on.

    Using an elliptic-curve based algorithm like ECDSA / ECDH may help, because private key is then just a random integer, with no condition on primality or anything like that. You still have to specify the generation algorithm, but at least it is simple.

  • If you change your password, you also change your key pair, which might have consequences in whatever system you are envisioning.

  • Good password hashing requires a salt, which is not a secret value, but should not be fixed either. You would need a storage space for that salt, somewhere.

  • The resulting public key would, by construction, be usable in an offline dictionary attack. Offline dictionary attacks are not a good thing for passwords. Properly configured password hashing functions can help fend off dictionary attacks, but there are limits to their power. A password-generated public key thus requires a really random password. Unfortunately, really random passwords are hard to memorize (see this question for some discussion -- the "correct horse" method, as presented in the post, yields passwords with 44 bits of entropy, which is good for a password, but not good enough to make offline dictionary attacks really tolerable).

Community
  • 1
Tom Leek
  • 170,038
  • 29
  • 342
  • 480
  • Could you please elaborate if I use RSA for key generation then where do I get my prime number pairs from? – The Nutty Professor Mar 02 '16 at 12:47
  • The primes are "just there", mathematically speaking. See [this answer](http://security.stackexchange.com/a/116262/5411). – Tom Leek Mar 02 '16 at 12:50
  • So you mean that the prime numbers are part of using RSA? – The Nutty Professor Mar 02 '16 at 13:06
  • "produce random numbers until prime integers of the right size are found" - this is done for security reasons, not procedural ones. If you're deducing a key from password, the prime number search may be sequential after the seed starting point. – Kind Contributor Jun 05 '17 at 01:13