lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
Hash Suite for Android: free password hash cracker in your pocket
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 01 Sep 2014 14:39:56 -0400
From: Bill Cox <>
Subject: Re: [PHC] A review per day - PufferFish

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.

Version: GnuPG v1


Powered by blists - more mailing lists