Private Key Generation from Passwords/phrases

Matthias Bruestle mbruestle at
Tue Jan 23 10:38:17 EST 2007

Joseph Ashwood wrote:
> I'm going to try to make this one a bit less aggregious in tone. I'm also

Thank you.

> ----- Original Message ----- From: "Matthias Bruestle"
>> Joseph Ashwood wrote:
>>> ----- Original Message ----- From: "Matthias Bruestle"

> You also ended up removing a large portion of my point. My primary point
> was
> that 2^76 <> 2^112. You made several assumptions in coming to your
> conclusion that are at least suspect.
> You observe that currently 3DES:ECC-224 speed is about 4000:1, and assume
> that it will stay this way. However, if you look at the history of ECC, the
> speed of ECC doesn't scale linearly against 3DES, in fact a single
> thread of
> 3DES might've actually been faster 1 year ago (during the GHz war, before
> multi-core), whereas ECC is still improving as the ability of the CPU to
> perform complex routing and branch prediction improves. So next year the
> ratio could be 100:1, I doubt it will be that dramatic but it is possible.
> As a result this assumption will have to be reexamined every time a CPU
> revision is released, a slight timing change can actually make a big
> difference to the 3DES:ECC speed ratio. Also you need to consider the
> attack
> speed of the attacker, versus the production speed of the user.

I know there are likely some shifts. Hence I wrote "The relation stays
(mostly) the same." But in my opinion these shifts are minimal compared
to all the other uncertainties, e.g.:

- How long does the protected secret/signature be ok?
- How well is your adversary funded?
- How much entropy has the passphrase really?
- How much is the general speed increase in the next 20 years?
- ...

If you calculate your bits without safety margin, then next year AMD
could add a 3DES unit to an CPU, the speed ratio is 40000:1 and you're
busted. (Because of the hardware friendly design of DES I would say a
faster 3DES is easier to get than a faster ECC.)

> You assume that the fastest way to computer point exponents is through
> counting up to the exponent. While I admit I'm not familiar with point
> exponentiation algorithms, I strongly suspect this one to be incorrect, I
> see no immediate reason that (k*k*k*k) must be decomposed to (((k*k)*k)*k)
> instead of ((k*k)*(k*k)), at exp=4 there is no difference but at
> exp=16million there is an enormous difference. You might be able to make
> this assumption true for your system by somehow proving that the only
> way to compute k^x requires b^x steps (for some b.

My assumption is that the passphrase is properly processed, i.e. nicely
hashed. So an attacker has to go through this process if he wants to
exploit the reduced entropy of the passphrase and (at least) I see no
way how to exploit this reduced entropy then to help algorithms like
Pollard's rho/lambda to speed up the computation. The attacker may use
any point multiplication method he wants to use. (Jacobian, modified
Jacobian, NAF, windowing, ...)

> I see no reason it the arguments presented that the attacker would still
> have to perform 2^76 (ECC)work in 2^112 (3DES)time, instead of 2^76
> (ECC)work in substantially less than 2^112 (3DES)time.

An attacker would have to perform 2^100 (ECC)work, because the ratio
accounts in my calculation only for 2^12 steps. The other 2^24 is a
thrown away 24bit random.

> That is not to say that I don't think you will have > 2^76 (ECC)work
> required to break it, taking longer than 2^76 (ECC)work, but that I
> disagree
> with your result. If you set your target at 2^80 (ECC)work, then I believe
> you can achieve it this way. I also think that if you were to perform
> result[i] = hash(result[i-1], passphrase) (result[0] = 0x000...000) it is a
> safe assumption that there is no faster way than counting to i, which would
> vastly improve your chances of security (see "Secure Applications of
> Low-Entropy Keys" by Hall, Kelsey, Schneier and Wagner for reference). I
> also think that most users would be unwilling to wait the full day you
> spec'd, it is hard enough to get users to wait 5 seconds.

The parameters can be changed as needed. A day can be ok for one
purpose, e.g. for key recovery, while it is not ok for a different
purpose, e.g. recreation of the private key for each decryption. In the
later case the passphrase has to contain more entropy.

Regarding passphrase entropy: Getting entropy into a rememberable
passphrase is a related, but completely different problem.


Matthias Bruestle, Managing Director
Phone +49 (0) 91 19 55 14 91, Fax +49 (0) 91 19 55 14 97
MaskTech GmbH, Nordostpark 16, 90411 Nuernberg, Germany

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list