Re: Time Invariant String Comparison

[Andres Perera <andres.p@...>]

On Sun, Jan 19, 2014 at 5:35 PM, William Ahern
<william@25thandclement.com> wrote:
> On Sun, Jan 19, 2014 at 02:21:12PM -0430, Andres Perera wrote:
>> On Thu, Jan 16, 2014 at 4:42 PM, William Ahern
> <snip>
>> > Cryptographic security depends on exponential cost differences. Key
>> > stretching solutions like bcrypt and PBKDF2 add linear costs. Their security
>> > is, therefore, mostly hype, IMNSHO.
>>
>> this is a mathematically rediculous statement
>>
>> if the increment to, eg, bcrypt number of rounds, entails linear cost,
>> it can be adjusted to match exponential
>>
>> n = 16777216 = 2 ^ 24
>>
>> if the iterator for *anything* entails linear growth, it can be
>> adjusted to match exponential
>>
>
> I'm not going to bother responding to this because I'm an optimistic person,
> and I believe that someday, after further reflection, you'll understand the
> problems with your reply, and with your initial grasp of what I was trying
> to say. I think it's self-evident without anybody having to spell it out.
>

I, on the other hand, will bother responding, because I'm perplexed by
what you said about bcrypt/scrypt incurring linear costs.

>From "Stronger Key Derivation via Sequential Memory-hard Functions" [0]:

"By using a key derivation function which requires 2^s cryptographic
operations to compute, the cost of performing a brute-force attack
against passwords with t bits of entropy is raised from 2^t to 2^s+t
operations [19]."

[0] http://www.tarsnap.com/scrypt/scrypt.pdf
[19] J. Kelsey, B. Schneier, C. Hall, and D. Wagner. Secure
applications of low-entropy keys. In ISW ’97: Proc. of the first
international workshop on information security, pages 121–134, 1998.

>
>