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-next>] [day] [month] [year] [list]
Date: Sun, 11 Aug 2013 21:39:20 +0200
From: Krisztián Pintér <pinterkr@...il.com>
To: discussions@...sword-hashing.net
Subject: a sponge based approach

hi,

i came up with the following idea. my design goal was to be 100% inside an existing primitive, and not using secret-based branching.

S.Init
Mem[0..m-1] := 0
S.Absorb salt || pwd || pad
loop i in 0 .. t-1
    // squeeze r words, write them to Mem sequentially
    loop j in 0 .. r-1
        Mem[(i*r + j) mod m] ^= S.Squeeze
    end loop
    // absorb r words from Mem using a different pattern
    loop j in 0 .. r-1
        S.Absorb Mem[((i*r + j) * f) mod m]
    end loop
end loop
// save S here
auth_key := S.Squeeze
derived_key_1 := S.Squeeze
derived_key_2 := S.Squeeze
...

with the following notations:

S    a duplexed sponge
t    time/CPU cost 
m    memory cost, m<r*t/4 (see later)
r    the number of words in the r part of the sponge
f    interleave factor


notes on f

the f parameter is tricky, it is simply -1 for sponges that use random functions. for random permutations (that can run backwards), we need f that

gcd(f, m) = 1
gcd(f-1, m) = 1
f is approx m*p/(p+1)

where p is the relative cost of the permutation function backwards. this setup is supposed to defend against obvious memory-time tradeoffs, ensuring that all M[]-s are used, and used in a most unexploitable manner, maximizing the distance from any parallel running sponge instances.

i'm not sure about the access pattern, which is pretty much the lynchpin of the design. anyone cares to attack it?


notes on m

obvious from the design that if you want all memory to be used, m<t*r must hold. if you want all written values to be read, you need m<t*r/2.

because of the predictable manner of the reads/writes, during the first m steps, the used memory grows linearly. during the last m steps, less and less elements will be ever read again. that gives the obvious optimization opportunity to run the next attempt in parallel, using up the gradually released memory of the previous. for that reason, m<t*r/4 can be advised, allowing for 25% optimization for the attacker.

Powered by blists - more mailing lists