phc-discussions - Re: [PHC] cost upgrades (Re: [PHC] Scripting memory (not so) high vs Catena in PHP (with optimizations))

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-prev] [thread-next>] [day] [month] [year] [list]

Date: Sat, 18 Jan 2014 18:38:15 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] cost upgrades (Re: [PHC] Scripting memory (not so) high vs Catena in PHP (with optimizations))

On Sat, Jan 18, 2014 at 05:41:06PM +0400, Solar Designer wrote:
> On Mon, Jan 13, 2014 at 06:24:40PM +0100, Christian Forler wrote:
> > Without CI-updates, todays password hashes will become easy prey for
> > future (say 2030) state-of-the-art password-cracking frameworks. It is a
> > common wisdom that from time to time security parameters has to be updated
[...]
> With builtin support for cost upgrades in a memory-hard password hashing
> scheme, ignoring the shortcut wiping idea I had mentioned before for
> now, we have to choose between two non-perfect options:

By "the shortcut wiping idea" I was referring to:

http://lists.randombit.net/pipermail/cryptography/2012-November/003451.html

"A much trickier task: support upgrades to a higher memory cost for the
already-computed iterations.  Sounds impossible at first?  Not quite.
This would probably require initial use of some secret component
(allowing for a lower-memory shortcut) and then dropping it at upgrade
time."

on which Christian commented here:

http://www.openwall.com/lists/crypt-dev/2013/12/24/2

saying it "Sound like CI-update. :-)"

So I guess I need to read up on Catena.  Maybe it does these upgrades
better than I had thought, avoiding or improving upon the tradeoffs I
mentioned in the previous message in this thread.

However, per another paragraph in Christian's crypt-dev reply above,
Catena merely uses 3x granularity - or at least that's how I interpret it:

"[...] to compute the additional iteration you
need about the doubled amount of effort (memory and time) as for
computing all the other iterations together. The cost per
iteration doubles. To compute the i-th round you need O(2^i) memory and
O(2^i) time."

Alexander