Private Key Generation from Passwords/phrases

[James A. Donald]

Matthias Bruestle wrote:
> Hi,
> 
> 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