Date: Thu, 9 Jan 2014 00:48:23 +0000
From: Peter Maxwell <peter@...icient.co.uk>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Lyra, Password Key Derivation Based On The Sponge Construction

On 8 January 2014 23:46, Bill Cox <waywardgeek@...il.com> wrote:

> RC4 is the perfect example to use, and I disagree about the entropy ratio.
>  If you have 20 bits of entropy in a user's password, and 256 bits of
> entropy from salt, using RC4 initialized from this 276 bits to generate 4GB
> of hash data is a *good* idea.
>

​Only if you're talking about the tiny minority of systems that can afford
to use 4Gb of memory that you can guarantee is protected and not ever paged
to disk, *per-login*.  If your server needs to handle even 10 logins per
second, that's a wee bit of a problem... it wasn't that long ago that I was
admining production webservers with 1Gb memory or less.

If you cannot guarantee to protect that entire 4Gb blob leakage then as
Poul-Henning pointed out your lack of entropy becomes an issue, i.e. the
salt is public and therefore doesn't count towards the entropy so your 20
password bits is only 2^20 ~ 1m combinations and an attacker can
potentially determine the password from even a small fragment* of that 4Gb
keystream with less effort than the memory-hard problem.

[*] - in this specific scenario with RC4, it would really need to be near​​
the beginning of the keystream output but the argument generalises better
if the filling algorithm is not cryptographically strong.




>
> My point is that it's useless to worry about the entropy of the data we
> write to memory.  RC4 is already too strong, and a waste of CPU cycles.  So
> long as we don't lose significant entropy along the way, any dumb hash that
> an attacker has to actually compute is good enough.
>

As a side issue: ​RC4 is not generally considered particularly strong these
days, there are non-trivial biases in the keystream.

The main question however concerns the feasibility of protecting memory
regions that large, or for that matter anything anywhere near that large,
when you're filling with password dependent data using an algorithm that
can be easily inverted.  In other words, if - like you said - you're not
losing entropy along the way then it implies a permutation, and if it is
easy to invert said permutation then an attacker only needs a word or two
of memory to undermine your memory-hardness.

​Peter​






>
> Bill
>
>
> On Wed, Jan 8, 2014 at 6:08 PM, Poul-Henning Kamp <phk@....freebsd.dk>wrote:
>
>>
>> In message <CAOLP8p5wwnaOpPGW0rA+Q9nz-jYtKhEL0aujMALuRuG=
>> 8zQtRg@...l.gmail.com>
>> , Bill Cox writes:
>>
>> >Thanks for this very interesting link.  Lyra first fills a matrix with
>> hash
>> >data which is derived from the password, and then randomly picks a "row"
>> >and for each location it updates the hash state from the location's
>> value,
>> >and then XORs into the location the next output of the hashing engine.
>>
>> Two things worry me about the general approach Lyra takes.
>>
>> My first thought was that this sounds vulnerable to the same issue
>> RC4 suffers from:   It takes more entropy to "randomize" it properly
>> than is typically available for the purpose.
>>
>> Lack of entropy is a major issue in any password context, and therefore
>> I think it is wise to pay attention to the:
>>
>>         bits of entropy
>>         ---------------
>>         bits of state
>>
>> ratio not getting too low.
>>
>> The second thought is that a large memory footprint, desirable for
>> all the reasons the Lyra presentation mentions, vastly increases
>> the ways and means to discover what is going on through covert
>> channels.
>>
>> So as a general principle, I'm personally not going to be very
>> impressed by claims on the general form:
>>
>>         "The ${datestructure} can be sized however large you like"
>>
>> even if it comes with a mathematically proof of ${something}, unless
>> it also comes with plan for how it gets initialized with only limited
>> entropy being available, and analysis of to what extent the access
>> patterns may reveal its state.
>>
>> Poul-Henning
>>
>> --
>> Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
>> phk@...eBSD.ORG         | TCP/IP since RFC 956
>> FreeBSD committer       | BSD since 4.3-tahoe
>> Never attribute to malice what can adequately be explained by
>> incompetence.
>>
>
>

Content of type "text/html" skipped

Powered by blists - more mailing lists