[Cryptography] Pre-image security of SHA-256 reduced to 16 rounds

[Zooko Wilcox-OHearn]

Dear Sergio:

On Sun, Jan 19, 2014 at 1:37 PM, Sergio Lerner
<sergiolerner at pentatek.com> wrote:
> I'm working in a password hashing construction (RandMemoHash, see http://bitslog.wordpress.com/2013/12/31/strict-memory-hard-hash-functions/).
>
> I need the fastest possible crypto "hash" function, even if breaking pre-image resistance requires about 2^32 operations. Collision resistance is unimportant. This is because the algorithm will repeatedly apply the reduced round hash function, so at the end, enough rounds will be applied.

I don't think this is why collision-resistance is unimportant for this
use case. Instead, if I understand correctly, collision-resistance is
unimportant because the attacker does not get to choose the inputs,
but instead the inputs are provided by the defender.

> My first choice is SHA-256 with 16 rounds (out of 64). I want to find the best pre-image attack  that requires little memory. I searched for information on papers but all I found is attacks against 36 and more rounds.

I don't know the answer to your question about SHA-256, but may I
suggest BLAKE2 ¹ instead of SHA-256? SHA-256 reduced to 16 instead of
64 rounds would take about 6 or 7 cycles per byte, on 64-byte inputs,
on Haswell, according to bench.cr.yp.to ². Full-strength (10 round)
BLAKE2s would take 5.75 cycles per byte on Haswell (ibid), and provide
excellent strength against pre-image attack. You could even cut
BLAKE2s down to reduced-round in order to get more efficiency. Exactly
how deeply you could cut it and still retain sufficient
pre-image-resistance is unclear to me. Perhaps ³ sheds some light on
that, but I'm not sure.

Another possible advantage to using BLAKE2 for this application is
that some other password-hashing and/or memory-hardness functions that
have recently been proposed use BLAKE2: ⁴, ⁵, ⁶. So maybe if you use
BLAKE2, your schemes can be more easily compared to those ones.

Disclosure: I'm an author of BLAKE2.
Regards,

Zooko Wilcox-O'Hearn

Chief Publicity And Marketing Officer for the BLAKE2 Team

¹ https://blake2.net

² http://bench.cr.yp.to/results-hash.html

³ http://eprint.iacr.org/2013/467

⁴ http://eprint.iacr.org/2013/525

⁵ http://lyra-kdf.net/

⁶ https://github.com/catid/tabby/blob/master/PASSWORD.md