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: Fri, 26 Dec 2014 09:12:47 +0800
From: Ben Harris <ben@...rr.is>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] [OT] Memory hard proof of work with constant time verification

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.

> 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.

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

Content of type "text/html" skipped