phc-discussions - Re: [PHC] cache timing attacks (Re: [PHC] Initial multiply-compute-hardened Catena-3 benchmark)

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: <alpine.DEB.2.10.1401241026150.31733@debian>
Date: Fri, 24 Jan 2014 10:46:16 +0100 (CET)
From: Stefan.Lucks@...-weimar.de
To: discussions@...sword-hashing.net
Subject: Re: [PHC] cache timing attacks (Re: [PHC] Initial multiply-compute-hardened
 Catena-3 benchmark)

On Fri, 24 Jan 2014, Solar Designer wrote:

> If this corresponds to a substantial portion of the full hash
> computation, then that attacker hasn't gained all that much - only a
> speedup of their offline attack by a certain factor, which we may try to
> make reasonably small.

Agreed, the speed-up by knowing the memory-access pattern is low, if you 
just count the clock cycles. For scrypt, the speed-up would be about two. 
But you seem to overlook a crucial point.

Once you know the memory access pattern, one can sort out wrong password 
candidates almost *memoryless*. Thus, the attacker can run the attack on a 
memory-constrained massively parallel hardware (e.g., run on a GPU with 
thousands of cores, using only the L1 caches) -- completely defeating the 
entire purpose of using a memory-intense password-hash function!

The only difficulty is to gather the required information about the memory 
access pattern ("which cache lines may have been read in the first few 
iterations of scrypt").

Stefan

------  I  love  the  taste  of  Cryptanalysis  in  the morning!  ------
     <http://www.uni-weimar.de/cms/medien/mediensicherheit/home.html>
--Stefan.Lucks (at) uni-weimar.de, Bauhaus-Universität Weimar, Germany--