phc-discussions - Re: [PHC] Tradeoff cryptanalysis of Catena, Lyra2, and generic memory-hard functions

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: <CAMtf1HuxAE0M-o__oB008jrDURx7ZVxu6ROh04zKxMWq+E1QrQ@mail.gmail.com>
Date: Sun, 15 Feb 2015 21:42:46 +0800
From: Ben Harris <ben@...rr.is>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Tradeoff cryptanalysis of Catena, Lyra2, and generic
 memory-hard functions

Hi Dimitry,

Tiny typing error in the paper. Page 5, at the bottom, you have "52^n" when
it should be "5 [dot] 2^n".

Awesome job. Thanks.
-Ben

On 13 February 2015 at 23:45, Dmitry Khovratovich <khovratovich@...il.com>
wrote:

> Dear all,
>
> we have prepared a more rigorous and detailed description of our tradeoff
> attacks on Catena and Lyra2 (original submissions to PHC), that were
> presented in Passwords'14 conference in Las Vegas in August.
>
> Abstract: "We explore time-memory and other tradeoffs for memory-hard
> functions, which are supposed to impose significant computational and time
> penalties if less memory is used than intended. We analyze two schemes:
> Catena, which has been presented at Asiacrypt 2014, and Lyra2, the fastest
> finalist of the Password Hashing Competition (PHC).
> We demonstrate that Catena’s proof of tradeoff resilience is flawed, and
> attack it with a novel precomputation tradeoff. We show that using M2/3
> memory instead of M we may have no time penalties. We further generalize
> our method for a wide class of schemes with predictable memory access. For
> Lyra2, which addresses memory unpredictability (depending on the input), we
> develop a novel ranking tradeoff and show how to decrease the time-memory
> and the time-area product by significant factors. We also generalize the
> ranking method for a wide class of schemes with unpredictable memory access
> ."
>
>
> The report is permanently available at
> http://orbilu.uni.lu/handle/10993/20043  and will be soon added to ePrint
> as well.
>
> We stress that versions of Catena and  Lyra2  (especially Catena)
> advancing to the next round of the PHC competition can not be seen as small
> tweaks  and will require completely new cryptanalysis. In the light of
> that, we kindly ask the panel to publish permanent links to the first-round
> submissions.
>
> --
> Best regards,
> Dmitry Khovratovich
>

Content of type "text/html" skipped