phc-discussions - Re: [PHC] blakerypt sequential memory-hard function

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]

Message-ID: <CALCETrVSsboE-1e5AkpMuec5MrJy8dZ2=GDmsCkLA9y94zWwDA@mail.gmail.com>
Date: Thu, 5 Dec 2013 09:16:17 -0800
From: Andy Lutomirski <luto@...capital.net>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] blakerypt sequential memory-hard function

On Thu, Dec 5, 2013 at 8:16 AM, Dennis E. Hamilton
<dennis.hamilton@....org> wrote:
> I favor Fibonacci indexes for this sort of thing.  That is k, in a small number of bits, produces work factor fib(k+n) where n is some value that assures a reasonable minimum and the maximum fib(k+n) is decisively out of reach for any forseeable time into the future.
>
> The advantage is that the Fibonacci recurrence provides a nice way of deriving k on the fly by seeing how much time is being taken in real time, and incrementing by the next step if a target threshold has not been reached.  This does mean that k is not known until the hashing has been completed, and the protocol has to accommodate that.

What does this have to do with Fibonacci numbers?  fib(n) is, to an
excellent approximation, ϕ^n (i.e. ~1.618^n).  1.618 < 2, so this
gives a bit more fine-grained control than 2^n, but it seems like it
will come at a cost of being more esoteric.

For what it's worth, it would be possible to implement any strictly
iterative password hashing scheme so that it ran for a preset time and
output the resulting iteration count.  This has nothing to do with
Fibonacci numbers or even with exponential growth.

I'm still not sure I see the advantage of any exponential approach
over just a plain linear work factor (except for losing compatibility
with some fancy chaining schemes).

>
> The advantage is that k will grow along with growth in processor power.  One disadvantage in certain applications is that the speed of the system where the hash is first created determines the work factor that less powerful systems will need to employ in order to verify the hash.
>

This is true for any reasonably password hash as far as I know.

--Andy