phc-discussions - RE: [PHC] Lyra, Password Key Derivation Based On The Sponge Construction

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: <ce06147b57de439195deb0ce54098a58@BY2PR03MB074.namprd03.prod.outlook.com>
Date: Thu, 9 Jan 2014 00:06:51 +0000
From: Marsh Ray <maray@...rosoft.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: RE: [PHC] Lyra, Password Key Derivation Based On The Sponge
 Construction

I think we generally assume the salt is known to the attacker, so it doesn't contribute entropy in the same sense as the password.

> My point is that it's useless to worry about the entropy of the data we write to memory.

A. We have to worry that 99.999% of the entropy in the password ends up represented in the resulting hash value.

B. We have to worry about password entropy being lost via side channels such as memory access patterns.

So if the entropy content of certain values is truly not important, a simpler option (which helps prove both A and B) is to initialize them with a fixed pattern or one which is purely salt-derived.

-          Marsh

From: Bill Cox [mailto:waywardgeek@...il.com]
Sent: Wednesday, January 8, 2014 3:46 PM
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Lyra, Password Key Derivation Based On The Sponge Construction

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.

No one is looking at your hashed data, which is the difference.  All that matters in the end is the 256-ish bits of derived key you spit out.  You can't turn the user's 20 bits into more than 2^20 possible outcomes for a given salt, but thrashing all that memory for a full second will force an attacker with a GPU to spend a couple days to guess it.  If that were just protected with one round of SHA-256, it would take a small fraction of a second.

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.

Bill

On Wed, Jan 8, 2014 at 6:08 PM, Poul-Henning Kamp <phk@....freebsd.dk<mailto:phk@....freebsd.dk>> wrote:

In message <CAOLP8p5wwnaOpPGW0rA+Q9nz-jYtKhEL0aujMALuRuG=8zQtRg@...l.gmail.com<mailto: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<mailto: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