Private Key Generation from Passwords/phrases
James A. Donald
jamesd at echeque.com
Thu Jan 11 21:26:08 EST 2007
Matthias Bruestle wrote:
> I am thinking about this since last night. On the web I haven't found
> much and I want to go in a different direction as I have found.
> Say I want to have 112bit security, i.e. as secure as 3DES. For this I
> would choose (as everybody writes) 224bit ECC (or Tipsy Curve
> Cryptosystem/TCC as I prefer, because the European Citizen Card is also
> called ECC officially). With the Passwords I would have to provide so
> much entropy, that a bruteforce attack needs as much time as 3DES to get
> the same security. (Higher value of ECC key ignored.)
> When I look at benchmarks ratio of the number of 3DES operations and of
> point multiplications is about 4000:1, so I have gained here about 2^12
> bits. (Processing of Password with a hash function is so fast that it
> can be ignored unless the procession is artificially extended.) I am
> aware that a DES unit is cheaper than an ECC unit and that for DES there
> are special implementations for key search possible, so the gain might
> be even more.
> Lets assume the key is only very seldom regenerated. Then we could add a
> short fragment of real entropy to the passwords and throw it away after
> our first key generation. If a point multiplication takes around 4ms
> then we can brute force on one day 2^24 keys. So if the user is willing
> to wait for one day for his key recreation than he can add 3 random
> bytes to his passwords and throw them away.
> If we add this together, than we have already 2^36 bits of security from
> our goal of 2^112 bits. The remaining necessary entropy is then 2^76
> bits which would have then to be provided by the passwords/phrase. That
> means the necessary length is reduced by about one third.
> What do you think about this?
You are not going to get 76 bits of entropy in a password.
Memorizing a 76 bit password is equivalent to memorizing three seven
digit telephone numbers.
Assume that the private key is generated from the password plus an n bit
true random number.
To regenerate the private key we have to try 2^n private keys, looking
for a match to the public key. Assume this takes time X.
Assume the actual entropy in the password is m bits. Then an attacker
who has similar computing resources is going to take time X * 2^m
Any time a password can be subject to offline attack by anyone, it is
not a good design. You are better off fixing it so that only certain
people can offline attack the password, and everyone else has to do an
online attack on the passwrod.
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography