Message-ID: <54064B41.4060604@ciphershed.org>
Date: Tue, 02 Sep 2014 18:57:05 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] A review per day - Schvrch

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

Just to properly finish the Schvrch code review, I'll do some more of
the standard stuff.

First, Schvrch does no password dependent addressing of memory, and is
essentially an in-cache algorithm with poor performance when running
out of external DRAM.  Because of this, I put it in the Catena-like
category, though it also does rapid small reads, similar to bcrypt.
However, I have no idea if predictable small random reads are a
problem for a GPU.  They certainly are no problem in an ASIC, where
large cache latencies can be eliminated by requesting memory early and
heavily pipelining.

Rather than a Catena competitor, I feel Schvrch might have a technique
that could be plugged into Catena or other entries.  Catena has a
strong framework with good security, but the default block hashing is
slower than most entries.

I have to admit that if the Schvrch stir function proves secure, I
would be tempted to build a SkinnyCat-like simple algorithm using it.
 I do not understand why we have revolve and evolve at all, given that
they don't seem to do mixing well, while stir does, but if I read the
papers, that will likely be clear.

Here's a 1GiB hash benchmark:

PHC> time ./phs-schvrch 0 $((1 << 18))

a6 10 db 2a f5 62 ad ef
00 73 38 62 9f 3e f0 46
7a a1 1c e6 fb d1 32 97
49 21 18 e0 bb a0 6a d3      32 (octets)


real	0m6.442s
user	0m6.408s
sys	0m0.036s

And here's an 8MiB benchmark:

PHC> time ./phs-schvrch 0 $((1 << 11))

6b cc 2c 31 08 91 70 d4
a0 48 d5 a0 9b e0 22 bf
72 c2 a2 96 e9 2e 1f 1d
56 a6 9a c4 0d 4d df 2c      32 (octets)


real	0m0.054s
user	0m0.052s
sys	0m0.002s

Both runs were with t_cost == 0.

This shows in-cache speed is similar to the other Catena-like
algorithms, and much slower than the bcrypt-like algorithms such as
PufferFish, as well as the three more generic Scrypt-like algorithms.
 Like Catena and others in it's category, hashing speeds even in cache
are probably a bit too slow for authentication servers.  Like Catena
and friends, without unpredictable memory reads like the bcrypt-like
algorithms, attackers will have an easier time with TMTO attacks, even
if the existing TMTO weaknesses in Schvrch are fixed.

Also, Alexander wanted me to run tests on the internal memory
generated by the various algorithms through the Dieharder test suite.
 For example, POMELO just passed.

Schvrch fails when I run the stirred memory in the second Dieharder
test, operm5.  This seems reasonable to me, since the mixing in
Schvrch is very slow, and it spits out 2KiB of memory hash data every
4 rounds.  Looking at the code, I would not expect this to pass tests
for statistical randomness.  Frankly, I would prefer that only 1 round
were used, so we could hash 4X more memory in the same time.

The final hashes produced by Schvrch did pass the first several
Dieharder tests.  This will take overnight to complete, but I expect
it to pass.

My recommendation for the implementation of Schvrch is that it remains
dangerously insecure, and is not fit for use in it's present form for
password hashing.  Perhaps Schvrch's hashing algorithm can be adopted
by a more solid framework.

It does not appear from the code that the author intended for this
implementation to be more than a demonstration of the memory hashing
function.  As a demonstration, it seems to succeed, though users
reading the code should be warned about current bugs, and be informed
not to use the algorithm as-is.

Final note - it is not clear to me that having me review a hash
demonstration makes sense.  I tried to avoid it, but failed to pull it
off in a politically correct way.

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

iQIcBAEBAgAGBQJUBks+AAoJEAcQZQdOpZUZcKcP+gNuewDEEDMyyRbZYgKOJEwE
HPAu1GCwl2bk5VQFOKnAOvY7SU7ZhZqBRhCPbXeUA0RgL2fzzZsOhtU5KiRP2x2e
Y7+NBBBCiMsHwC0aPEytPPOU4JeqD+6qCUVkB9MKIFcQxClZbRNu4tDeoxbEdUA6
ArdrOl0+KkFgBKrmoA9V183LNq50SmJpLAjBrLPQHHQapWkDTYSjH1OmpIZB2kf7
WepIjEKPtZMqr8ikxpH4XpL/XmLkhtGfdaMuDXGPBUDHHH57MXRrGcMkijD6Kh0R
BfI+r0Vx1LfmLJiUJnBvdWCu+/EgYZ1VXCWSuD+ZmBxWW/cdxK99blpO5hzsIVqT
S/3/vOuAxT1J9th2fx18HRUdI6bOslvLQGOx8jZZ+6t1GHDbin2LvULfqHtsabkf
rNIH8NXhHv577Q5qKF+oodxC0rlb4ZCc2TaonORTu5UvOM+SPJ6hfmFivVCzhJWz
gjfSiIjEn8gnh3xjhCgffOBSGrT6RzDnX46s8ZpHgUu7/Cze5rU/wMOnYsec9//2
f2rARHsxWRzOwjThtNH6Qb6nBsWECnEsOsXxQgD9pP86ZmMVSCDFhIq99tnYGp0c
VHOaNu3d4YVpzAdIFHQKZvz38GCcmczAez1HA1G16PsQSKw7cGWkzpLWaOOSs9px
5+iQUyp4YELjFcYmXKmK
=k8uB
-----END PGP SIGNATURE-----

Powered by blists - more mailing lists