Date: Mon, 01 Sep 2014 15:39:54 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.net
Subject: A review per day - POMELO

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

POMELO got off to a rocky start, with an input hashing scheme that was
buggy, resulting in lots of input collisions that people noticed.
Here's a link to the POMELO discussion:

    http://comments.gmane.org/gmane.comp.security.phc/1394

However, once the bugs were fixed, POMELO does have some things going
for it.  On the positive side:

- - Very simple - only 127 lines!
- - hybrid algorithm: first loop cache-timing resistant, second loop
uses password dependent unpredictable addressing
- - It does 4-way parallel 64-bit reads, just like PufferFish, but with
predictable addressing in the 1st half, and unpredictable addressing
in the second half
- - Uses simple mix of ADD, XOR, and ROTATE which is the basis of
several strong cryptographic hashes, such as Blake2.

This algorithm will run painfully slowly if we try to run with more
memory than fits in cache, so POMELO is really closer to a bcrypt
replacement than an Script replacement.  It should have good GPU
defense, though I really can't say for sure, since GPUs aren't
something I understand well.

Compared to PufferFish, POMELO is less than 1/2 the code size.
However, PufferFish also includes encoding/decoding hashing parameters
to a string, and a self-contained SHA512-HMAC implementation.
Benchmarking is required, but I think they would be fairly close in
speed for a total amount of L1 cache read/written.

There are two negatives that I see in the code:

- - Needs input checking!  If password length is > 8192 << m_cost, it
overwrites memory! Line 46.  This can be used to launch Solar
Designer's famed "Return To Libc" attack for arbitrary code execution.
 Same problem with salt.  Adding input checking is a must-have tweak.
- - The end of memory is copied to the output, so we need to either
prove that the last bytes are irreversible and undetectably
non-random, or add a call to a respected hash function, such as SHA512.

POMELO simply must be upgraded to check inputs.  Having a simple
"Return To Libc" attack against a PHC winner is not OK!  However, this
is simple to do.

The author says that in calling these ARX (ADD/ROTATE/XOR) so many
times compared to respected cryptographic hash functions, that the
data should be more than adequately scrambled.  He think he is
probably right.  I'm running the Dieharder tests now on hashes
produced by POMELO with t_cost = 1 and m_cost = 7 (the author says
that t_cost + m_cost should be at least 8).  I think t_cost = 1 is the
weakest hash POMELO does, so that's what I'm using.  It passes the
Birthday test, as well as several more difficult tests, but my sample
data is too small to pass them all.  I'm doing an over-night run that
I think will show that it passes.

Minor nit picks:

- - Step 8 checks output length and returns 1 if it's too large.
Shouldn't this be done before hashing memory?
- - Why limit the input salt + password length so much?  Why not let
them each go to 2048 bytes or so?  Similarly, why limit the output key
length so much?

As for ASIC resistance, PufferFish, and POMELO all fall into the same
category.  Assuming we typically use < 32KiB hashing to maximize small
unpredictable memory accesses, then my ASIC will be memory access
limited, running at 1 F computation per clock cycle.  My CPU likely
will run at less than half that speed, but that's not bad
time-hardening.  The bigger issue is that if the caches are small,
like < 32KiB, then I can start integrating a bunch of them on an ASIC,
and run POMELO hashes in parallel.  The same goes for PufferFish, and
certainly the original bcrypt, with it's tiny 4KiB memory.

Overall, I've come to like POMELO as a potential bcrypt replacement.
It's main advantage is even more simplicity than bcrypt, and I like
it's cache-timing resistant first loop.  I'm keeping PufferFish as my
current favorite for a bcrypt replacement, but that might change if
the input checking is solid, and if more experienced crypto guys give
POMELO a thumbs-up security-wise.  POMELO could be a solid contender
in a bcrypt-replacement category, once it's input checking is fixed.

I should remind people that my opinion doesn't count.  I'm not a
judge, nor a cryptographer of any kind.  This is just a hobby for me.
 This also means I'm more free to be a dick, which occasionally I am.
 However, I'm having fun, so if people don't mind, I'll keep doing
public reviews.

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

iQIcBAEBAgAGBQJUBMuHAAoJEAcQZQdOpZUZrLcQAIjQy+3UF43XWxpYn71tqQYo
IEqkRsO6IeBvfps0XLZzPbUykibzde+BZlrhZ2cOhtOBw12Uv5zOL3tZSppHDAPS
VR1jxyjSV4XBqxtFt2OwSo9AbwAxppzRr+pMUIkRNAtzE6gWrwaaELDY6kL9jGMJ
Yvs2ECGvD9GXFoafAy+HOJ8Crmr6xN0EbY46dqguZk0FRKeEz+v5zznrFjHNltF6
KLKjLU536osXYJ9Yfp+H7XaiKBNBtcJ/7ZSgprazfR5FqPaMDOYR7sCTvkRIIYzX
/GBCEAehXJwa+PlMkE2mcZxLKNKIy/oBHzjhy6cYTz2LLIk+ccxJ/+X8TVd/tFyE
oNx59vvCGNVaG+MtxoJ5wcmtg/8huRmbNngp40E8/ryDWwQ/NahJp439cBKbWMNX
u2HQW3frLZI4Kl0NQQM0rwzaP2P5LTA+mXMRXq7GvTFkLf2I9qdC1ilbtCFzuyHF
Qfzi9eyD2pN4yOcUMFdZ1816qZdXPHG21lTFzqBO0bHQkoqjpHTu/6cLBJJXST0V
719kRX00ad2CVrl8f4YoPozEr3pcgIY1QU2NbYfhSAbrpVxPDQwGTgVTfCouEKod
0qmKxt00tT7m0U4aIHGL9Dgsxg17soMI41L1NgJHu4xJvPrz7xzvp9747bnZwo1l
YMb7JGDmggTUHvDkJ+W4
=DdPj
-----END PGP SIGNATURE-----

Powered by blists - more mailing lists