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  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, 19 Oct 2015 17:01:37 -0200
From: Marcos Simplicio <mjunior@...c.usp.br>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Re: BlaMka loses entropy

Hi, Bill.

I was about to point out the mistake with a Java snippet we developed to
check if BlaMka is a permutation for several bit-lengths.

You were faster than me, though :)

BR,

Marcos Simplicio.


On 19-Oct-15 16:39, Bill Cox wrote:
> D'oh!  I was wrong.  The BlaMka round preserves entropy.  Sorry about the
> mistake.  I've been doing mod p arithmetic so much I forgot this is mod
> 2^64, not mod p.
> 
> Bill
> 
> On Mon, Oct 19, 2015 at 11:17 AM, Bill Cox <waywardgeek@...il.com> wrote:
> 
>> 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
>>
> 

Powered by blists - more mailing lists