Private Key Generation from Passwords/phrases

[Joseph Ashwood]

I'm going to try to make this one a bit less aggregious in tone. I'm also
going to sometimes use (3DES) and (ECC) for designation of work and time
measurements.

----- Original Message ----- 
From: "Matthias Bruestle" <mbruestle at masktech.de>
Cc: <cryptography at metzdowd.com>
Sent: Monday, January 15, 2007 2:31 AM
Subject: Re: Private Key Generation from Passwords/phrases


> Joseph Ashwood wrote:
>> ----- Original Message ----- From: "Matthias Bruestle"
>> <mbruestle at masktech.de>
>> [most offensive parts deleted]

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.

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.

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.

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.
                Joe


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com