phc-discussions - scrypt and memory latency

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

Message-ID: <45507080.20130425201216@gmail.com>
Date: Thu, 25 Apr 2013 20:12:16 +0200
From: Krisztián Pintér <pinterkr@...il.com>
To: discussions@...sword-hashing.net
Subject: scrypt and memory latency

hello,

disclaimer: i'm neither a cryptographer, nor an expert in applied cryptography, but it will become clear very soon anyway.

my question is about a part in scrypt reference http://www.tarsnap.com/scrypt/scrypt.pdf page 9 section 6 SMix, in which it is described that we do not want the hash to be memory-access bottlenecked, but rather, CPU bottlenecked (if i understand correctly). what is the exact rationale for that?

here is what i think, and you can call me stupid for that. if the bottleneck is memory latency, there is a possible optimization of not storing all the V's, but for example every Nth V, and compute the missing values on the fly from the closest predecessor. this would allow for a lower memory footprint at the expense of more CPU load, but overall greater performance as far as the bottleneck is the memory latency. since we don't want our algo to be optimizable compared to the straightforward reference implementation, this is to be avoided, and strict CPU bottleneck is required.

is this a correct interpretation of the rationale?

TIA,
Krisztián