Re: Time Invariant String Comparison

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

On Sun, Jan 19, 2014 at 7:37 PM, William Ahern
<william@25thandclement.com> wrote:
> On Sun, Jan 19, 2014 at 05:57:13PM -0430, Andres Perera wrote:
>> 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.
>

> First, your comment about mathematical illogic makes no sense. You're saying
> that asymptotic costs are irrelevant because you can balance the variables
> in an algebraic formula. I don't even know what to say to that.

There's no balancing involved, and the best/worst case were never
picked one above the other. Were you implicitely talking about a
certain expectative?

I want a concise response to why the following doesn't hold:

s = "foo"

2^strlen(s) * 2^repcount = 2^(strlen(s)+repcount)

>
> Second, note that I was responding to the recommendation for bcrypt and
> PBKDF2, and in particular to the blog links. The first one I read was just
> cargo cultish explanation of why bcrypt and PBKDF2 are the new hawtness.

How does that affect the growth pattern of computational complexity of
key derivation functions?

>
> Third, scrypt is slightly different than either bcrypt or PBKDF2. It forces
> an attacker into a space/time complexity tradeoff in an attempt to prevent
> attackers from easily creating dedicated cracking hardware.

The excerp that explains computational complexity, which I quoted from
the scrypt paper, applies to scrypt, bcrypt, and PBKDF2. How are any
of the space requirements revelant?

>
>         Providing that the number of iterations used is increased as
>         computer systems get faster, this allows legitimate users to spend a
>         constant amount of time on key derivation without losing ground to
>         attackers’ ever-increasing computing power — as long as attackers
>         are limited to the same software implementations as legitimate
>         users. However, as Bernstein famously pointed out in the context of
>         integer factorization, while parallelized hardware implementations
>         may not change the number of operations performed compared to
>         software implementations, this does not prevent them from
>         dramatically changing the asymptotic cost, since in many contexts —
>         including the embarrassingly parallel task of performing a
>         brute-force search for a passphrase — dollar-seconds are the most
>         appropriate units for measur- ing the cost of a computation3. As
>         semiconductor technology develops, circuits do not merely become
>         faster; they also become smaller, allowing for a larger amount of
>         parallelism at the same cost. Consequently, using existing key
>         derivation algo- rithms, even if the iteration count is increased
>         such that the time taken to verify a password remains constant, the
>         cost of finding a password by using a brute force attack implemented
>         in hardware drops each year.
>
>         This paper aims to reduce the advantage which attackers can gain by
>         using custom-designed parallel circuits.
>
> Fourth, my original comment is quite literally the mantra of modern
> cryptography. Read any of the literature. And you completely glossed over
> the most important adjective: _difference_. Exponential... cost...
> DIFFERENCE. That means that the security of most cryptographic primitives is
> predicated on the notion that what the user can compute in constant takes an
> attacker exponential time to break.

Key derivation functions RELY on cryptographic primitives; they are
not replacements, nor equal, nor can they compete with the block
ciphers on which they depend on!

> But how do these key stretching systems work? They work by increasing the
> computational cost of _both_ user and attacker an equivalent amount. That
> doesn't actually provide much of any security, because even if you increase
> your work by 100x, it's not beyond belief that an attacker could increase
> his computational power by 100x. Trying to out-compete an attacker in
> computational resources is not a smart strategy.
>
> scrypt works by trying to hobble attackers and limit how much better they
> can do compared to your tiny server. This has practical utility, no doubt,
> but conceptually it's no better than bcrypt, which conceptually is no better
> than a straight-up hashing.
>
> Thought exercise: if you increase your hash iteration to 32768 (2^15),
> you've just also increased the cost to your attacker to break a single
> password by 32768x. Yeah! But, wait, how many hash operations does somebody
> like Google or Yahoo compute every second? Probably way more than that. So
> our additional iterations are ridiculously tiny in cryptographic terms. The
> amount of computational power available to an attacker is immense. Compare
> those to real exponential costs, such as brute-forcing a cipher or hash
> function (2^128, more than the number of atoms in the universe).
>
> Note that password hacking is riduculously easy to parallelize. scrypt tries
> to prevent parallel implementations of a single password hashing operation.
> But that's not the salient characteristic to worry about! scrypt can't
> prevent an attacker from firing up EC2 and cracking your passwords.
>
> Understand? Not even scrypt is going to magically save your bacon. Yes, it's
> better in absolute terms. But in cryptographic terms it's marginal utility
> is less than you already received from password salting.
>
> Human-entered passwords have fundamental limitations. scrypt is a very smart
> implementation. But it's also narrowly focused on a mostly inconsequential
> aspect of the problem, and in real-world terms doesn't buy you much.
>
> Finally, I'll leave you with this big question mark. Ask _anybody_ who has
> ever used bcrypt, scrypt, or something similar. After their initial
> installation, did they _ever_ bother increasing the round variable the next
> year, or the year after that?
>
> The marginal security is so low, that's the kind of thing you need to on a
> regular basis to make them worthwhile. That's not the kind of thing you need
> to do with traditional cryptographic primitives. My 2048-bit RSA key from
> 2000 is in real-terms just as safe today as it was 14 years ago. But a
> PBKDF2 round variable would be laughable after 14 years.
>
>