Message-ID: <20140104080959.GA2960@openwall.com>
Date: Sat, 4 Jan 2014 12:09:59 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Weakness in keystretch hashing, and a solution (I think)

On Fri, Jan 03, 2014 at 11:27:49AM -0500, Bill Cox wrote:
> The lower bound on area*time for an attacker is too low for my current
> "keystretch" hash.  I'll have to make modifications.  I don't know if it's
> helpful to discuss this sort of thing here, but just in case other PHC
> entries have similar weaknesses, there's still a month for authors to fix
> them.  I suspect the other authors consider this a rookie mistake :-)

Thank you for posting about this in here!

> The great thing about memory-hard KDFs is that the longer you run them, not
> only will an attacker have to also run longer, but he will also have to pay
> for more memory.  This is the key advantage vs other KDFs.  An attacker can
> always choose to use less memory than the user, and instead recompute the
> missing data on-the-fly as needed during hashing.  To insure that an
> attacker has a lower bound on area*time, it is critical for a memory-hard
> KDF to increase in runtime by at least a factor of n, when an attacker
> tries to use 1/n of the memory.  Scrypt has this property, though I suspect
> that an attacker using maybe 30% of the memory will reduce his cost*time
> per guess by something like 2X.  That factor hit's a wall quickly, however,
> and the minimum cost*time that he must pay is still very effective.

Right.  For scrypt, extreme TMTO gives a reduction in area*time of up to
4x if we count both of SMix's loops and assume that the attacker somehow
doesn't use CodesInChaos' attack on the first loop (e.g., because of the
also non-negligible area usage by the many cores or because of not
having more cores in a pre-existing device), or 2x on the second loop
alone.  scrypt at TMTO factor of 5 (so 20% memory usage) runs almost
exactly 2x slower on one core than scrypt at full memory usage, so this
is a cost reduction of 2.5x for this example.  And yes, this hits a wall
quickly, never exceeding 4x.

> For my current keystretch hash, I only have 64 bytes of state to generate
> the next memory "page" (just my word for a small block of memory) of
> memory, which I set to 16KB normally, plus a random previous page.  An
> attacker could keep only the 64 bytes per 16KB page, with a memory
> reduction of 256X.  To generate the next page, he must generate the
> previous random page, which depends on a random previous page and so on.
>  There are an average of log2(numPages) that he must compute, which isn't
> strong enough to be considered memory-hard.  An device using minimum memory
> (1/256th) would be much more cost effective for an attacker than what he
> would have to build to attack scrypt.  Logarithmic runtimes are good for
> attackers.

How did you arrive at log2(numPages)?  Is this assuming that the
attacker keeps a certain number of full pages (perhaps some function of
numPages) and thus only recomputes the missing random pages until
finally hitting a present one?  If so, why don't you count those pages
towards attacker's memory usage?

> The simplest fix I see is to increase the state used to compute pages to
> the page length or more (scrypt uses 2X).

Where do you see scrypt using 2x?  The size of "X" in scrypt is the same
as its block size.

> Does anyone see any other weaknesses in my simple approach of generating
> "pages" sequentially from random previous pages, with a very simple hash
> and a page of key state that updates with each page generated?

I currently don't, but I haven't given this enough thought.

> Some thoughts: later pages are accessed less than early pages, but why do I
> care?  If the attacker has to keep later pages in RAM, we've won.

This makes sense, but the attacker may have multiple types of RAM (e.g.
local to the cores vs. far away).  For later pages that are less likely
to ever be read, they may be sent to the far-away memory, thereby
leaving more of the very limited area close to the cores for use for
portions that are more likely to be randomly read from.  This works well
if the address to physical memory location mapping is static (e.g.
hard-wired in the circuit).

That said, you're right that requiring some relatively unlikely to be
read memory is better than not requiring it at all.  It's just that the
advantage from continuing to fill memory after time/2 is less than 2x,
and it is unclear where in the 1x to 2x range it is.  To make matters
worse, this issue arises within the first time/2 iterations as well, as
with your current approach accesses are non-uniform even within the
first half of the allocation and running time.  Thus, it is not clear
whether the total cost is even in the 1x to 2x range, or possibly below
1x of scrypt's.  We avoid this in escrypt by ensuring uniform access
after time/2 (this gives us the 1x scrypt baseline), as well as closer
to uniform access before time/2 (this probably gives us nearly 1.33x
scrypt, but with no guarantee).

In other words, assuming same memory latency and cost (and other costs,
such as routing and access ports), your approach has 2x higher area*time
than scrypt, and escrypt's is exactly 4/3 of scrypt.  (For same running
time.)  However, with the unknowns considered (which may be affecting
the time factor via latency and the area factor via other aspects),
things become unclear, and escrypt's approach provides better assurance
(while possibly only 2/3 of NOELKDF's attack cost in many real-world
scenarios, I admit).

Building upon scrypt, I wanted to stay strictly no worse than it rather
than merely likely no worse in many real-world scenarios.

Alexander

Powered by blists - more mailing lists