Private Key Generation from Passwords/phrases
James A. Donald
jamesd at echeque.com
Thu Jan 11 21:26:08 EST 2007
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
More information about the cryptography
mailing list