Reminds me of Feb 2003 - "Moderately Hard, Memory-bound Functions" NDSS 03,
Martin Abadi, Mike Burrows, Mark Manasse, and Ted Wobber.
(cached at) http://hashcash.org/papers/memory-bound-ndss.pdf
By microsoft research, but then when exchange and oulook added a
computational cost function, for hashcash anti-spam postage stamp like
purposes they actually used hashcash and not microsoft research's memory
bound puzzle. In fact they cooked up their own format, and made a slight
tweak to SHA1 just to make existing SHA1 hardware inapplicable.
(As part of their Coordinated Spam Reduction Initiative
http://www.microsoft.com/en-us/download/details.aspx?id=17854
there is an open spec).
Actually I worked for microsoft for a year or so around that the time, and
had talked with the anti-spam team to give them a brain dump on anti-spam
and hashcash, but I dont know why they rejected memory bound puzzles. That
particular one has a disadvantage that it requires a few megs of pre-baked
numbers to be shipped with the library. Seems like Percival's one does not.
My guess was there's just something comparatively elegant and simple about
hashcash. (If I recall they also used 8 sub-puzzles to reduce the variance
of the compute cost).
One quite generic argument I could suggest for being wary of scrypt would be
if someone said, hey here's my new hash function, use it instead of SHA1,
its "better" - you would and should very wary. A lot of public review goes
into finding a good hash algorithm. (Yeah I know SHA1 has a chink in its
armor now, but you get the point).
It is entirely possible to have flaws crop up in the non-parallelizable
aspect of the design, or non-reuse of RAM across parallel invocations.
I had a go at making non-parallelizable variants of hashcash also, and its
not so hard to do, but for most applications it doesnt really help
practically because the attacker would get lots of parallelism from trying
different passwords or different users or what have you in parallel.
The main point of scrypt is to increase the hardware cost by needing lots of
ram to evaluate the function which seems like a reasonable objective.
Abadi et al's mbound puzzle objective was to make the bottleneck memory
latency (plus a minimum required amount of RAM) instead of CPU. They made
the argument that there mbound would be "fairer" because there is smaller
variance in RAM latency between eg smartphone ram and desktop server ram
compared to the imbalance between desktop/server cpu (core i7 3930k? vs
arm9). The stats seem to add up. Though that was a few years ago, these
days some of the xeon or i7 have a pretty impressive on die L3 cache!
Adam
On Thu, May 31, 2012 at 10:02:17AM -0500, Nico Williams wrote:
On Thu, May 31, 2012 at 2:03 AM, Jon Callas <[email protected]> wrote:
On May 30, 2012, at 4:28 AM, Maarten Billemont wrote:
If I understand your point correctly, you're telling me that while scrypt might
delay brute-force attacks on a user's master password, it's not terribly useful
a defense against someone building a rainbow table. Furthermore, you're of the
opinion that the delay that scrypt introduces isn't very valuable and I should
just simplify the solution with a hash function that's better trusted and more
reliable.
Tests on my local machine (a MacBook Pro) indicate that scrypt can generate 10 hashes per
second with its current configuration while SHA-1 can generate about 1570733. This
doesn't quite seem like a "trivial" delay, assuming rainbow tables are off
the... table. Though I certainly wish to see and understand your point of view.
My real advice, as in what I would do (and have done) is to run PBKDF2 with
something like SHA1 or SHA-256 HMAC and an absurd number of iterations, enough
to take one to two seconds on your MBP, which would be longer on ARM. There is
a good reason to pick SHA1 here over SHA256 and that is that the time
differential will be more predictable.
If you'll advise the use of compute-hard PBKDFs why not also memory
hard PBKDFs? Forget scrypt if you don't like it. But the underlying
idea in scrypt is simple: run one PBKDF instance to generate a key for
a PRF, then generate so many megabytes of pseudo-random data from that
PRF, then use another PBKDF+PRF instance to generate indices into the
output of the first, then finally apply a KDF (possibly a simple hash
function) to the output of the second pass to generate the final
output. The use of a PRF to index the output of another PRF is
simple, and a simple and wonderful way to construct a memory-hard
PBKDF.
Meory and comput hardness in a PBKDF is surely to be desired. It
makes it harder to optimize hardware for fast computation of rainbow
tables.
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
