phc-discussions - Pretty cool: first sequential memory hard KDF secure against timing attacks

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: <CAOLP8p76qy1HkeG635-APZF5_hTPs0EgvywQuiW+W+ynKsYLqA@mail.gmail.com>
Date: Wed, 8 Jan 2014 18:35:12 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Pretty cool: first sequential memory hard KDF secure against timing attacks

If I'm not mistaken, the "cheat killer round" combined with "smoke" that I
mentioned this morning, turns Catena (and also NeolKDF) into a sequential
memory hard algorithm while avoiding timing attacks.

Even better, Catena-N has to compute N rows of data, but only two are
required to be in memory at any time.  The cheat killer round forces an
attacker to prove he still remembers a significant portion of all of the
computed values.  With a password-derived but smoke-randomized set of
memory location access, is there any timing leak?  The sequential memory
hardness is a simple matter to prove, as it becomes similar to scrypt in
the way it accesses memory in a second pass.  The only issue how much
memory do we really need to access?

NoelKDF minimizes the needed memory accesses in the cheat killer round,
because each memory access that is not saved by an attacker trying to use
less than half the memory results in a sub-DAG of values requiring
recomputation that is a significant fraction of the size of the whole DAG
(random DAG with degree 2 and < 1/2 of nodes covered results in a big
recomputation DAG).  1000 smoke covered memory accesses should do the job.

Any weakness here?

Bill

Content of type "text/html" skipped