phc-discussions - Re: [PHC] Lyra2 initial review

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]

Date: Thu, 17 Apr 2014 17:40:05 -0300 (BRT)
From: Marcos Antonio Simplicio Junior <mjunior@...c.usp.br>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Lyra2 initial review

Things are getting clearer. Thank you :-) 

> De: "Solar Designer" <solar@...nwall.com>
> Para: discussions@...sword-hashing.net
> Enviadas: Quinta-feira, 17 de Abril de 2014 15:53:15
> Assunto: Re: [PHC] Lyra2 initial review

> On Thu, Apr 17, 2014 at 01:42:01PM -0300, Marcos Antonio Simplicio
> Junior wrote:
> > Actually an explanation would be really good, because I confess
> > that, except for "memory bandwidth", I'm not sure I understand
> > what those numbers mean or how to computed them...

> Does the "memory bandwidth" figure for Lyra2 look correct to you,
> given
> the "time" output Bill posted?

Well, the "time" seems OK, although it is quite worse than what we got in our machine. The number "7" being multiplied by "Peak memory/second" eludes me, though. Each hashing operation in Lyra2 takes as input two memory locations ("prev" and "row*") and then its output is written to two memory locations ("row" and "row*). During Setup, "row" is just written over, while "row*" is XORed with the output (which may count as a "read"?); during the Wandering phase, both "row" and "row*" are XORed with the output. 

Am I missing something? The r/w on the "state" variable, maybe? 

> As to peak and average memory usage "per second", they're
> abstractions
> obtained by dividing actual peak memory usage by actual running time
> (for peak memory usage "per second") and averaging memory usage for a
> hash computation over time and then dividing by the time it took to
> compute a hash (for average memory usage "per second"). They are not
> literally "per second", because they are for certain cost settings
> that
> don't result in a hash computation taking exactly one second and
> because
> they would not stay exactly the same for other cost settings.

> Given this explanation, do these figures for Lyra2, as Bill posted
> given
> the "time" output, look correct to you?

> Is it expected that Lyra2's average memory usage is 3/4 of peak?
> I think Bill may have taken scrypt's ratio for these and applied it
> to
> Lyra2 and yescrypt, even though at least for yescrypt's native mode
> with
> t=0 it's wrong (maybe it's also wrong for Lyra2).

We did not test the algorithm using this metric, so I cannot say for sure. I will come back to this after some tests, but for now let's assume it is correct. 

> > > I am surprised that Lyra2 and TwoCats seem to win significantly
> > > in
> > > terms
> > > of bandwidth usage. I doubt it's the cost of one round of pwxform
> > > (although to find out we can try making it zero rounds, even). It
> > > could
> > > be the cost of r=8.
> >
> > It is likely to have a relationship: we have a compile-time
> > parameter "nCols" that has a similar effect to scrypt's "r". It is
> > part of the algorithm's core rather than a "tweak", but it would
> > not fit in the PHS interface...

> What did you set "nCols" to, and what does it correspond to in bytes?

> [ye]scrypt's r=8 is 1 KiB.

nCols is set to 64 by default, which means that each row has 64*768 bits = 6144 bytes = 6 KiB. In our machine we got better results with nCols = 128 (12 KiB), though. Those are the figures we put in the specification. 

> Alexander

Content of type "text/html" skipped