phc-discussions - BlaMka loses entropy

lists.openwall.net		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-next>] [day] [month] [year] [list]

Message-ID: <CAOLP8p4nuvRemavwoEV=XWV3Qzrj5aVqyAJXX7uJknNj1o79Ag@mail.gmail.com>
Date: Mon, 19 Oct 2015 11:17:44 -0700
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: BlaMka loses entropy

This concerns me a great deal.  The Blake2 reduced round G is invertible.
This proves there is zero entropy loss up to the point that we do the
compression.  The BlaMka round does lose entropy.

Basically, the regular Blake2 addition step looks like:

    a = (a + b) % p

After executing it, we know a+b, and b, and can invert it by subtracting b
from a+b.  The BlaMka multiplication step replaces the addition step, and
looks like:

    a = (a + b + 2*(a % 2^32)*(b % 2^32)) % p

The idea was to use something like a latin square defined by a + b + 2*ab,
but that's now what we have here.  The following _is_ invertible:

    a = (a + b + 2*a*b) % p

By using only the low order words of a and b, we lost information.  Here's
a simple Python script to prove it:

def BlaMka(a, b, p, mask):
    return (a + b + 2*((a*b) & mask)) % p

def printSquare(p, mask):
    for a in range(p):
        for b in range(p):
            print "%2d" % BlaMka(a, b, p, mask),
        print

p = 13
mask = 3
printSquare(p, mask)

When run, it produces:

 0  1  2  3  4  5  6  7  8  9 10 11 12
 1  4  7 10  5  8 11  1  9 12  2  5  0
 2  7  4  9  6 11  8  0 10  2 12  4  1
 3 10  9  8  7  1  0 12 11  5  4  3  2
 4  5  6  7  8  9 10 11 12  0  1  2  3
 5  8 11  1  9 12  2  5  0  3  6  9  4
 6 11  8  0 10  2 12  4  1  6  3  8  5
 7  1  0 12 11  5  4  3  2  9  8  7  6
 8  9 10 11 12  0  1  2  3  4  5  6  7
 9 12  2  5  0  3  6  9  4  7 10  0  8
10  2 12  4  1  6  3  8  5 10  7 12  9
11  5  4  3  2  9  8  7  6  0 12 11 10
12  0  1  2  3  4  5  6  7  8  9 10 11

Note that 1 and 5 appear twice in the second column, while 3 and 6 are
missing.  This 4-bit version of BlaMka is clearly not a quasi-group.

My recomendation: switch back to the reduced Blake2b round, and incorporate
something similar to MAXFORM that runs on the scalar unit.  This will
ensure we do long leak entropy until a compression step.  Incorporating
multiplication into the Blake2 reduced round was a poor solution in any
case, IMO, since there is 8X parallelism built into the Argon2 block hash.
The whole point of multiplication chain compute-time hardening is to force
the attacker to run nearly as long as the defender.  A free factor of 8X
speedup is too high.  My top 3 concerns at the moment for Argon2 are:

- Entropy loos
- Too much parallelism
- Poor compute-time hardening (due to parallelism)
- Poor in-cache performance (about 3X slower than TwoCats)
- Somewhat poor GPU resistance.

Using MAXFORM on the scalar unit would solve 4 of my top 5 concerns.  The
poor in-cache performance is not easily fixed, since Argon2's state busts
out of the SIMD unit registers and lives in L1 cache.  For low-memory
in-cache memory hashing, I plan to replace the Argon2 block hash with most
likely either the one from TwoCats or preferably Yescrypt if it is fast
enough.

Bill

Content of type "text/html" skipped