phc-discussions - Re: [PHC] Re: Asymmetric proof-of-work based on the Generalized Birthday problem

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]

Date: Wed, 30 Sep 2015 17:58:25 -0400
From: John Tromp <john.tromp@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Re: Asymmetric proof-of-work based on the Generalized
 Birthday problem

dear Dmitry,

> I could not obtain explicit statements of the time and memory requirements
> of your scheme from the paper.

Have you read the latest version of the paper at
https://github.com/tromp/cuckoo/blob/master/doc/cuckoo.pdf?raw=true
or
https://eprint.iacr.org/2014/059.pdf
?

>From the abstract:
"Our cycle finding algorithm uses one bit per edge, and up to one bit per node.
Runtime is linear in graph size"

So for a graph with N nodes, time is O(N) and memory is 1.5N bits.
This can be tweaked to time O(2^k N) for memory (0.5+2^{-k})N bits.

> Some claims in our paper possibly came from
> some misunderstanding.
>
>  Andersen's analysis stated that what previously can be done in time T and
> memory M

That refers to my "The basic algorithm" in the same named section,
which uses time O(N) and memory 32N bits (NlogN to be precise for
arbitrary N).

> in some form to claim any positive statements about amortization and
> tradeoff resilience.

Amortization is completely orthogonal and is achieved by having an expected
0.025 42-cycles per random graph (i.e. 2.5% chance of having a 42-cycle).

Tradeoff resilience is considered in the section on TMTOs.
The TMTO algorithm uses time O(kN) and memory N/k bits, and
we study the quite important constant factors involved in that O().

> Currently it is unclear from the paper how much
> Andersen's analysis affected the scheme properties. As a result, I had to
> rely on his analysis first and parallelizability he explains.

Andersen's edge-trimming reduced the memory from NlogN to (0.5+2^{-k})N bits.

> If you could make more rigorous claims about behaviour of your scheme under
> certain memory reductions and increases, this would help me to reference
> your work properly.

Memory increases don't help, since runtime is still Omega(N).

regards,
-John