phc-discussions - Re: [PHC] [OT] Memory hard proof of work with constant time verification

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: Thu, 25 Dec 2014 21:17:55 -0500
From: Bill Cox <waywardgeek@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] [OT] Memory hard proof of work with constant time verification

On Thu, Dec 25, 2014 at 8:12 PM, Ben Harris <ben@...rr.is> wrote:

> On 26/12/2014 12:45 am, "Bill Cox" <waywardgeek <waywardgeek@...il.com>@
> <waywardgeek@...il.com>gmail.com <waywardgeek@...il.com>> wrote:
> > In contrast to Cuckoo  Cycle, this algorithm is simpler and verification
> is done in constant time rather than  O(log(N)).
>
> I though Cuckoo Cycle was constant time verification. Something like 86
> hashes to verify regardless of the number of nodes.
>
I think you're right.  Just reread Cuckoo Cycle, and they specifically
mention that Cuckoo Cycle with cycle length == 2 is basically the same as
Momentum.


> > Time/memory trade-offs are possible.  Lower memory can be used by simply
> imposing a smaller m_cost, with a proportionally higher computation
> requirement. However, the memory*computation time cost does not change,
> making this algorithm memory hard.
>
> Looks like in the 25/60 case, you need about 2^34.48 hashes for a 50%
> chance of finding a match. When you run with half the memory, this becomes
> 2^35.48, further halving the memory doubles the number of hashes (which
> matches your memory*time). In this way, the only effect of the m_cost is
> limiting the speedup a large amount of memory can provide.
>
That was what I was hoping to m_cost would do.

> Have you looked at Momentum also? Similar idea of birthday collision +
> hash table
> https://static.squarespace.com/static/51fb043ee4b0608e46483caf/t/52654716e4b01acd1ac8a085/1382369046208/MomentumProofOfWork.pdf
>

Thanks for this link!  I should have followed the reference to Momentum in
the Cuckoo Cycle paper.  I guess the algorithm I proposed above is only a
slight modification to Momentum.  The Cuckoo Cycle specifically mentions
that it has less of a time-memory trade off than Momentum, and that it is
less susceptible to Bloom filters and rainbow tables.  I think I prefer
Momentum (with a memory limiting addition) over Cuckoo Cycle due to it's
comparative simplicity.  I think Bloom filters increase the memory*time
cost too much to be useful in any application that is not severely memory
limited, so that's not a real problem.  I can't figure out how rainbow
tables could provide an attacker any benefit at all.

Bill

Content of type "text/html" skipped