Date: Mon, 01 Sep 2014 14:39:56 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] A review per day - PufferFish

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

On 09/01/2014 12:54 PM, Solar Designer wrote:
> On Mon, Sep 01, 2014 at 11:58:15AM -0400, Bill Cox wrote:
>> I read through the code.  I did not properly analyze it for
>> security vs the original bcrypt.  I just read the code.  Others
>> more familiar with bcrypt will have to do a proper
>> cryptanalysis.
> 
> I think we can proceed with that if Pufferfish becomes a finalist. 
> I don't expect any issues there that couldn't be easily tweaked.
> 
> However:
> 
> Bill, you were going to do pre-final-hashing randomness tests on
> all PHC candidates.  What's happened to that plan?

The TrueCrypt fork happened :-)

>> In short, PufferFish is very similar to bcrypt, except that the
>> 4 S-boxes can be bigger, controlled by m_cost, and the iteration
>> count is controlled by t_cost.  It uses 64-bit arithmetic, and
>> just in case it's this modified version of BlowFish is not very
>> secure, it hashes the inputs first with SHA512-HMAC.  The author
>> got the details of the password and salt hashing right, working
>> around the input collisions of HMAC.  Very nice!
> 
> I guess the pre-hashing is needed to avoid a bcrypt-like password
> length limit.  For bcrypt it's 72; while 144 would be much better
> and would satisfy PHC requirements as-is (128+), it would still be
> a drawback.

I'll take your word for this, but I don't understand!  The S-boxes are
initialized with SHA512 data, and the password and salt are properly
hashed with SHA512-HMAC in a way that avoids the HMAC input
collisions.  What further pre-hashing could there be?

>> Overall, for an algorithm that simply wants to extend the life
>> of bcrypt by using more than 4KiB of L1 cache and using 64-bit
>> data types, PufferFish looks great.  It's nice to have an easy
>> review for Labor Day :-)
> 
> Great.
> 
> A drawback of going 64-bit, yet keeping the 4x lookups parallelism,
> is that Pufferfish may be 2x weaker than bcrypt on old or low-end
> 32-bit systems (e.g. some ARM), which use little instruction-level
> parallelism.

Probably.  If there is no 64-bit addition or XOR, the 4 unpredictable
reads might still go fast, but the two 64-bit XORs and the 64-bit ADD
might take another 3 cycles compared to regular bcrypt, because of the
two extra 32-bit XORs and the extra add-with-carry.

> On newer and high-end 32-bit systems, I think the extra parallelism
> is fine, as seen via bcrypt attack vs. defense speedup on CPUs,
> which is up to 2x on many x86-64 CPUs.  In fact, Pufferfish might
> still lack enough parallelism to fully use modern x86-64 CPUs in
> 64-bit mode, with 1 instance of it per core, so CPU-based attacks
> may achieve some speedup by interleaving (like we do for attacks on
> bcrypt).  This may be a fine tradeoff, though, since like I said
> adding more parallelism "hurts" defensive use on smaller systems
> (or more precisely, it provides speedup to attacks on some kinds of
> hardware without a matching speedup for defensive use on those
> smaller systems).  Making instruction-level parallelism
> configurable would add complexity.

Also, to defend against attacker parallelism, using the whole L1 cache
could be somewhat effective, since the S-box sizes are configurable.

> Many other PHC entries, including yescrypt at default settings,
> share this sort of drawback too.  So Pufferfish isn't actually
> worse than them when run on too-old or too-small CPUs.  It's just
> that many PHC entries are (in a way) worse than bcrypt on too-old
> and too-small CPUs.  I'm considering ways of dealing with that in
> yescrypt (non-default settings for such uses; yescrypt is very
> generic and complicated anyway).
> 
> Alexander

I should probably benchmark PufferFish, but I've got a ton of reviews
to get through first.  From the code, I suspect it performs on par
with bcrypt in terms of unpredictable memory accesses per second.
Because of this, and it's bcrypt-like simplicity, I'm currently
picking PufferFish as my first choice for a pure bcrypt replacement,
though not for an Scrypt replacement.  Being a bit slower on older
machines is probably OK, IMO, given how long it will take for adoption.

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

iQIcBAEBAgAGBQJUBL14AAoJEAcQZQdOpZUZbroP/2vo4m843eQaxtFJccJM5+as
aFeYT52qDOT4OsUnguOwSB6RPaToiEfwPF6uL3bLWd+mt/jpC4QY1szuRa/btOHn
D3400KM5SDTAwaRQnVfupBZoDErA4xUYdvz/F56EediUEE0Z2dCf+xtIHRLiOVAA
WzgwTJTsd5gu2jaLYOYR8W4DY3R18b6qI+5gxD53eToPXOmyeOO2kS/90ZbYWhuQ
NZDvzTFFjZ2fmw6uyycm6dyXLyXJLxoBxQfaL5axqJASVCEyf2wB3RwYnkJz1bb8
+WXk8VthdqT5c/VG3uaXKgh85eRj08Idnp71UVlH4HoFhdnMMgYy8TmZGonjsQqT
0vhbS4eqmtv83vTv52541+jAiMQx36kJ/IDHn3V+fdBMvZ9X62oDJjznmoW23vU8
b29+XFOM+4gjc2AhsEVd6fDgFonWzZp2YYM8aCfH+8DgNyE18f4LKNML4jcGasWx
ySksRSNFlExHNQZFfQVQoWF2sPq+4tyEnZCbG5B6n39Faqw/yKRCxbwC/QxFG/yU
3iRzm4v1+vWbmkXV5ff2ut7Mvu9lQ6ugfpP51V1mV8t7g14NjwcU2mk+tQIlmFBT
k/UmlgS9OFBaJi+wn5TCvonMMZ/CkFZJsp5iBA7ksgh4jtNBTgNRM3FSBoVE1kOC
CEFVynCrJnEo47DM0Fnn
=kxOY
-----END PGP SIGNATURE-----

Powered by blists - more mailing lists