Message-ID: <54137B58.50100@ciphershed.org>
Date: Fri, 12 Sep 2014 19:01:44 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.net
Subject: A review per day - Gambit

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

IMO, Gambit is one of the better fully cache-timing resistant
algorithms in the competition.  It is the only entry using the Keccak
sponge algorithm for memory-hard hashing.  The Gambit algorithm is
very simple and clean.

I carefully reviewed every line of Gambit as soon as it was published.
 I probably unfairly scrutinized Gambit more closely than other
entries because I have difficulty relating to Gambit's author.
However, regardless of what he thinks of me, I have to respect his
code and coding skills.  I will not in the future insult him like I
have in the past.  From his code, I have learned he actually is a
brilliant guy.  We do, however, continue to strongly disagree on some
of the basics in password security.

Gambit is a fully cache-timing resistant algorithm, so resistance to
pebbling attacks is very important.  While I am not convinced that a
good pebbling algorithm does not exist, I tried and failed to find
one, and my automated pebbler failed completely at TMTO attacks at
1/8th memory and below.  I have to give Gambit algorithm an "A" in
resistance to attacks of the sort that I've been mounting against
other algorithms.

I also am impressed that Gambit generates memory data that is
indistinguishable from true random data.  If you are going to throw
efficiency to the wind and rely on nothing but grade-A
cryptographically strong pseudo-random data for filling memory, then
you should at least be hard to differentiate from true random data!
If I haven't overlooked one (I am still reviewing them after all),
Gambit is the *only* cache-timing resistant algorithm using full
cryptographic hashes to fill memory that gets this right.  The author
is not dumb.

Gambit is extremely simple, which is one of it's greatest strengths.
It initializes memory, and then uses a backwards hop through memory to
find a location to hash with the location that increments from 0 to
memmorySize-1.  It never erases data, but XORs into it, which is
something I am still wary of, but I do believe that it is *at least*
as strong as overwriting would be.  However, XORing over memory causes
a read before write, doubling the memory bandwidth to update the
location.  It is similar to Lyra2 in the way it XORs into memory, but
Lyra2 takes advantage of the data that is read and sucks it into the
sponge.  This is a good idea for algorithms that XOR over memory.  You
might as well use any data you read!

The most significant complaint I have about Gambit is it's speed.  It
relies on Keccak, an algorithm known to run poorly for a defender with
a CPU, and well for an attacker with a custom ASIC.  I've had this
debate plenty with the author, and he has a unique position.  While
several entries limit their application scope by relying on hardware
AES acceleration, only Gambit relies on *future* hardware
acceleration.  That's the kind of optimism I usually am guilty of.
It's nice to see it in someone else :-)

In any case, we can fix the low performance of Gambit by plugging
Lyra2 sponge into it.  With that change, it would be a very
competitive cache-timing resistant entry, faster and more secure than
RIG.  It lacks the bells and whistles of Catena, and it strangely
includes ROM hashing support (a Solar Designer innovation) rather than
any of the Catena ideas that I feel would be more natural, but
basically, Gambit seems easy to fix.

I think that if we are interested in having a cache-timing resistant
algorithm as a possible winner, then Gambit should make the next round.

Here's Gambit's benchmarks.  Like all the cache-timing-resistant
algorithms other than RIG, they are quite slow.  1000X lower
time*memory cost than the pack leader seems to be about average.

One minor gripe: t_cost has to be at least m_cost/10.5.  That makes it
more difficult to benchmark.  Also, m_cost has to be odd.  That's odd :-)

4MiB benchmark:

PHC> time phs-gambit 50000 524287
Allocating 4194296 memory

38 e4 ba a7 da fb 9e b9
ed 88 e4 ce 18 82 cd 59
64 17 1b 91 b2 70 83 4c
f0 40 25 1f b4 ee 4a 34      32 (octets)


real	0m0.057s
user	0m0.057s
sys	0m0.000s

This is not horrible speed, just bad.  In comparison, Twocats hashes
4MiB in 6ms.  The Gambit author has been known to say that 10X does
not matter, so let's call this one of those areas where we agree to
disagree.

1GiB benchmark:

PHC> time phs-gambit 12782641 134217727
Allocating 1073741816 memory

65 22 81 58 47 16 4f 95
e9 90 67 1c 1e 68 1b 8b
20 fe 11 f4 42 41 1d a3
e0 3c c6 91 38 48 b0 af      32 (octets)


real	0m15.371s
user	0m15.309s
sys	0m0.060s

In comparison, TwoCats does this in .37 seconds, single threaded, with
high multiplication hardening - it's much faster with default settings.

The problem here is that gambit has no system for busting out of cache
into DRAM without paying a high cache miss penalty.

For academic work, Gambit is excellent.  It probably belongs in the
next round.  However, I don't expect to use it to protect any
passwords any time soon in it's current form.  However, I will say the
same thing in my Catena review when I get to it, so Gambit is in the
running in this category, IMO.

Bill
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAEBAgAGBQJUE3tUAAoJEAcQZQdOpZUZR9gP/R+9jXbcfd5KzdZQUpxs0Ewc
cBRcdPG2FAVsRUGrV1RMsmCKuyjm4RZO0IFsZKcXa9DyUaBW7vSQv/U8VTsaQHs8
R05n2rlOWLLv7Q4s+n24OmvAGA8Pm1AkRFhMiZ6V9hLxj0Xhr7adcsIhrSMFWd5h
Xr4061wFjHbJ77xKrhExXjBNGR8rlXuyePQJKtjbjWH3vwQXAeV1CfIIdHMGdcUh
ek6V5ybvPzeVBbmHmidsgCj0So2ThEqc8MzOTuluj8IJqvRQ+RUdcQABvqPx/0cG
h7vZz74Smue4zrECXiBB+fxeazfU3wdH1VgPGLk/G62Er4VMKcb6P151V2KRz4Qt
ispV//lk8/oIAQk3UNiQKHca8zg52I1HXRUfmLAUl9Ke76IO51KpEUFhAjF+uAjp
XB9FtLZHIUjYgQ2e8bZY3oTwYBF5McObU1MkERWt3Ftby1NjclKMZ4kmSNypDosM
dzsvj7Bzn0OqcNcS9ef8npU4J2j/c9S70j17juwDAN/29aUd+LDYYmzzn5WMpxo4
HLMZC5JIRpLBvEn4oxKMwOXSE2llX7AYNptPz3idnJoytvKUscxX5wf/RpkWDYf5
/US+MGukzRvLS9+A2tXQBBtaNvJmPMeF/KpiYrBDwb6ht6SECOUIJ99x794bNNCY
gpq41SLQsIu4l1J+hpk1
=AKNJ
-----END PGP SIGNATURE-----

Powered by blists - more mailing lists