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: <CAMtf1HtbAHg=70igfy3zL2k403WqBFjELL+6JLNAeniFkfTOTQ@mail.gmail.com>
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

Powered by blists - more mailing lists