Re: Time Invariant String Comparison

[William Ahern <william@...>]

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.

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.

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.

	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.

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.