Message-ID: <20141030024207.GA14342@openwall.com>
Date: Thu, 30 Oct 2014 05:42:07 +0300
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Overview of PHC Candidates and Garbage-Collector Attacks

Hi Jakob et al.,

On Wed, Oct 29, 2014 at 06:38:26PM +0100, Jakob Wenzel wrote:
> under the following link you can find an overview of all PHC
> candidates which are not yet withdrawn:
> 
> https://eprint.iacr.org/2014/881.pdf
> 
> It focuses on comparing general and security properties. Moreover, it
> formally introduces the two attack types garbage-collector attacks and
> weak garbage-collector attacks. For each candidate, we argue why it
> provides resistance against these attack types or we actually show an
> attack.

This is helpful analysis.  Thank you!

Of all people in PHC, I think Bill has been most concerned about these
issues, due to relevance for use in TrueCrypt.

One thing I don't see in your paper is the mention that we're dealing
with a security tradeoff here.  Hashing schemes (mostly) not susceptible
to (W)GC tend to use less memory (at the same running time limit) than
those that are susceptible.  Similarly, hashing schemes (mostly) not
susceptible to WGC are less likely to offer convincing reasons as to
whether/why they provide basic cryptographic security, unless they use a
full round count cryptographic primitive all the time (in which case
they are at a disadvantage in memory filling speed).  Perhaps this is
something you'd want to add in a revision of the paper?

So for some of the schemes you've reviewed, it's not like you've
discovered new attacks that the authors had overlooked, but it's more
like the tradeoff having been resolved differently than you did in
Catena (although this might not have been your reasoning at the time).

Some likely errors I noticed in the paper:

You specify authors' recommended memory usage for EARWORM as "1 MB (ROM)"
and for scrypt as "1MB" - I guess you meant GB (not MB) in both places?

You marked POMELO as using floating-point - really?  Do I miss something?

yescrypt does support server relief - only a tiny pre-final hash needs
to be transmitted to the server.  (Moreover, it also supports use in a
straightforward modification of SCRAM.)

Not strictly an error, but:
In a sense, scrypt and yescrypt are "flexible".  Surely there are
modifications of scrypt currently in use with Keccak and ChaCha in place
of SHA-256 and Salsa.  (Some cryptocoins use that.)  This is just not
part of the spec.  So the question is how you define flexibility.

yescrypt's memory hardness is of both sequential and ROM-port types at
once, for the RAM and ROM portions, respectively.  Perhaps you need to
list both in the table somehow, since otherwise it falls into the same
category with EARWORM, whereas it's _also_ in the same category with
scrypt (at the same time - that is, with the same settings yescrypt is
in both categories at once).

Your description/analysis for yescrypt is slightly wrong:

"The array VROM is only accessed, if the flag YESCRYPT_RW is set." -
actually, passing of a ROM to yescrypt implies the YESCRYPT_RW flag.
It is not a supported combination of settings to have a ROM but not to
enable YESCRYPT_RW.  (The reference implementation refuses to run if
called that way.)

YESCRYPT_RW unfortunately does not prevent GC attacks.  Only a subset of
RAM locations gets overwritten.  It does complicate and possibly slow
down post-GC offline attacks since the attacker would not know
beforehand which locations were overwritten and which were not, but I do
not consider this even a partial GC attack countermeasure.  (I'd need to
specifically tweak it to ensure overwriting a certain number of initial
locations in order for it to become such a countermeasure.)

"GC attacks [...] are possible when [...] the ROM is used but the
frequency mask is not zero" - are you referring to the ROM-on-SSD case
here, with SSDs' block read counters?  If so, I think you'd need to
include an explanation, since this does not normally fall under your
definition of GC attacks, IIUC.  I think your normal GC attacks are on
data itself rather than on metadata, correct?

Anyway, as I explained when talking about YESCRYPT_RW above, yescrypt as
currently defined is susceptible to GC attacks, so you do not really
need to discuss the ROM.  I did include support for mask=0 to mitigate
metadata leaks on SSDs, which is a similar attack to GC, but I felt it
was more important to deal with because of SSD storage persistence.
Under your definition, yescrypt is susceptible to GC attacks via the RAM
portion anyway.

"yescrypt also uses the password in the final invocation of PBKDF2" -
not exactly.  yescrypt, except in scrypt compatibility mode, uses the
result of the initial PBKDF2 there, which was in turn invoked on
SHA-256(password) rather than on plaintext password.  So what is kept in
memory during most of (native) yescrypt's runtime is
HMAC-SHA256(SHA-256(password), salt).  Since this can be "efficiently
computed" in an attack, it probably does fall under your WGC anyway (or
does the inclusion of salt change this, per your definition?), but
you'll probably want to use the correct description.

I'll consider tweaking yescrypt to resolve these security tradeoffs
slightly differently.

As to explicit zeroizing of sensitive data in an implementation, to
mitigate the risk of compiler optimization and to also do something
useful I intend to include a self-test as the last step.  It will
usually not overwrite the whole arena (as the self-test vectors will be
for some fixed size(s) only, and as we don't want to spend too much time
on this overhead), but it should mitigate these attacks significantly
(overwriting a significant amount of the closest-to-password data).
I've been using this approach to zeroization in crypt_blowfish (although
in its case the whole Blowfish state gets overwritten indeed).

Thanks again,

Alexander

Powered by blists - more mailing lists