phc-discussions - Re: [PHC] How important is salting really?

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: Fri, 12 Dec 2014 19:10:43 +0000
From: Brandon Enright <bmenrigh@...ndonenright.net>
To: discussions@...sword-hashing.net
Cc: bmenrigh@...ndonenright.net
Subject: Re: [PHC] How important is salting really?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Fri, 12 Dec 2014 18:39:57 +0800
Ben Harris <ben@...rr.is> wrote:

> On 12 December 2014 at 17:53, epixoip <epixoip@...dshell.nl> wrote:
> 
> > Thus the salt table shrinks with each successful
> > crack, and the effective speed of the attack increases with each
> > eliminated salt.
>
> A rather confusing way to describe things.

I don't think epixoip's description is confusing at all.  It's a
description of how cracking salted lists is traditionally implemented.

> If we are attacking all password hashes, one password at a time (from
> the most common down). Then each time we find a match, the pool of
> hashes decreases and subsequent passwords can be search faster.

Your description ignores an important optimization in the case where
some hashes share a salt.  If you have N unique hashes and M unique
salts then the work per candidate password is O(M) rather than O(N).

All cracking tools use a unique salts table because in many realistic
scenarios M < N so what matters is not eliminating hashes from the hash
table, it's eliminating unique salts from the salt table.

The remainder of my reply is a rant:

This salt discussion highlights by biggest problem with the PHC. Most
of our academic members clearly have no practical experience attacking
real world hash dumps. Without that experience they don't know how to
weigh various attacks and in many cases tend to worry about theoretical
but unrealistic attacks and dismiss practical attacks.  If we're going
to choose good proposals we (engineers and academics) need each other.

Brandon
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iEYEARECAAYFAlSLPbkACgkQqaGPzAsl94IFQwCgw+g0goXozPYsqZnt6E3ULeC8
JNMAn15ao1mgKRUrS71cvkNISt2fPxTL
=2uFI
-----END PGP SIGNATURE-----