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

Date: Fri, 13 Feb 2015 16:45:35 +0100
From: Dmitry Khovratovich <khovratovich@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Cc: Dmitry Khovratovich <khovratovich@...il.com>
Subject: Tradeoff cryptanalysis of Catena, Lyra2, and generic memory-hard functions

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