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

Message-ID: <20141227184742.GA940@reks>
Date: Sat, 27 Dec 2014 10:47:42 -0800
From: Gleb Kurtsou <gleb.kurtsou@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] [OT] Memory hard proof of work with constant time
 verification

On (25/12/2014 11:44), Bill Cox wrote:
> I am not sure if posting off-topic stuff like this here is still OK, but I
> read about the John Tromp's Cuckoo Cycle here, and frankly this list has
> provide amazing feedback in the past, so I'll keep milking this expert
> channel so long as it's not annoying...
> 
> Here's an algorithm I'm thinking about on Christmas.  I hope you enjoy it:
> 
> This algorithm implements a memory hard proof of work scheme with a
> constant time verificatoin capability.  This idea is motivated from:
> 
>       Cuckoo Cycle: a memory-bound graph-theoretic proof-of-work system, by
> John Tromp
> 
> The point is to require enough memory to make it difficult to compute more
> cheaply up  using GPUs, FPGAs or ASICs.  This is the goal of various
> crypto-coins, such as LiteCoin  and GlobalBoost-Y.  However, these schemes
> are forced to use low memory to enable rapid  block-chain verification.
> 
> Like Cuckoo Cycle, much larger memory sizes can be supported because
> verification of the  proof of work is fast and does not require significant
> memory.  In contrast to Cuckoo  Cycle, this algorithm is simpler and
> verification is done in constant time rather than  O(log(N)).
> 
>   Algorithm:
> 
> For a given initial value, compute H(0 | value), H(1 | value),  H(2 |
> value) ... until we have at least a computation cost, c_cost, initial bits
> of the latest hash value being equal to the initial c_cost bits of some
> previous hash value.  To enable a memory cost,
> m_cost, to be independent of c_cost, require that the prior index be within
> 2^m_cost of the current index.  Verification is done with two calls to H.


I had somewhat similar idea this summer. It may be of interest to you.

Create T[i] table (I've used duplex construction as in SHA-3).
Travers all (i,j) pairs accumulating feedback differently if
MSB(T[i], cost) == MSB(T[j], cost).

I've also used multiplication in Galois field in order to achieve memory
access unpredictability while traversing all indexes and thus performing
the same set of operations. The intent was to keep function constant
time.

Proof of concept implementation and pseudo-code available here:
https://github.com/glk/mmcrypt