Date: Mon, 28 Apr 2014 12:11:27 -0400
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] on timing attacks

IMO, if there are to be multiple memory-hard winners, this is the issue
that should separate them.  If we can't agree which form is best (which
seems to be the case), maybe the judges will have trouble too.  In that
case, they can probably still agree on winners in each class.

Krisztián Pintér and Thomas Pornin both make good points.  While doing no
password dependent addressing at all seems like a good thing, it does come
with two significant costs.  First, a cache-timing resistant algorithms
have difficulty having strong TMTO resistance until about the 1/4 memory
usage mark compared to the computation graph size.  To insure the defender
benefits from this as much as the attacker, the cache-timing resistant
entries generally recommend that memory be written about 4 times or more.
 There are some tricks to avoid one of the writes, so this penalty seems to
be about a 3-4X reduction in possible peak memory usage, and 2X to 3X in
terms of average memory usage.  When attacking these cache-timing resistant
algorithms offline, an attacker will gain somewhere from about 2X to 4X in
guesses per dollar.

Second, predictable memory access can be sped up dramatically in custom
hardware, including both FPGA and ASIC implementations.  GPUs may be able
to speed up predictable memory access as well.  Any cache-timing resistant
algorithm runtime hardened primarily by memory bandwidth will not succeed
very well on the runtime portion of the runtime*memory cost.  I would want
to see some other compute time hardening in any cache-timing resistant
algorithm.  Hopefully this can be considered a "tweak".

Combined, offline attackers get a free-ish memory reduction of something >
2X, and he can run that memory full-bore as fast as it's I/O will allow,
mostly eliminating memory latency delays, so he wont have to use that
memory for very long per guess.  That's a reduction on both the time and
memory axis of the time*memory cost.  I am not a fan of that.

On the other hand, Krisztián Pintér is right that timing leaks all sorts of
information, not just information useful for cracking his password faster.
 If an attacker has a scope probe on the power rails, most entries the
competition will leak the password length.  They mostly call memcpy, and
there's a real risk that an attacker with power rail waveforms can detect
exactly how many cycles memcpy takes.  Both PBKDF2 implementations as well
as HKDF call memcpy on the password, so there's no help there.

Even with coarse-grain information such as cache-timing, an attacker may
gain crucial knowledge.  For example, a drone operator might wait for
confirmation that a targeted individual has just attempted to log into a
web account, indicating he is probably at his desk by his computer, before
launching a missile at him.  Even knowing a person has not logged in for a
while can be critical information.  For example, did the missile we
launched last week kill him?  The meta-data gained through a timing leak
can be more sensitive than the password.

Which PHS architecture is preferable seems to be strongly a matter of
opinion, and there are good solid entries with all three architectures.

Personally, I prefer the hybrid first, because it has nearly the off-line
defensive strength of a fully unpredictable addressing schemes, while still
hampering off-line cache-timing attacks on the password.  It's not an
obvious choice, and I only came to this decision after thinking about it
for a couple of weeks, and playing with Catena and some other algorithms.
 The hybrid system is more complex, which can be death for a crypto-system.
 The simplicity and security of Bcrypt and similar unpredictable algorithms
will remain most attractive to some.  Better defense against timing attacks
seems to draw others to cache-timing resistant algorithms.

This seems almost to be a religious war.  Of course, I'm right and everyone
else is wrong :-)

Bill

Content of type "text/html" skipped

Powered by blists - more mailing lists