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]

Message-ID: <002001d016f8$0413c790$0c3b56b0$@acm.org>
Date: Sat, 13 Dec 2014 09:12:45 -0800
From: "Dennis E. Hamilton" <dennis.hamilton@....org>
To: <discussions@...sword-hashing.net>
Subject: RE: [PHC] How important is salting really?

 -- Replying to --
From: epixoip [mailto:epixoip@...dshell.nl] 
Sent: Saturday, December 13, 2014 00:09
To: discussions@...sword-hashing.net
Subject: Re: [PHC] How important is salting really?

On 12/12/2014 11:56 PM, Jeremy Spilman wrote:
> On Fri, 12 Dec 2014 23:03:13 -0800, epixoip <epixoip@...dshell.nl> wrote:
>
>> You eliminate more salts faster by looping over the salts for
>> each word in a wordlist, as opposed to looping over the wordlist for
>> each hash.
>
>
> I'm going to try (and likely fail) to channel @scoobz here;
>
> If you are optimizing the attack by iterating through each salt and
> then going on to incrementally less popular passwords, (makes perfect
> sense) then I would imagine if the defender naively does H(pwd||salt)
> you could gain a significant optimization from that. Do you ever see
> this in practice?

Yes, and this is immediately observable.

Hashtype: md5($pass.$salt)
Workload: 1024 loops, 256 accel
Speed.GPU.#1.: 12279.9 MH/s

Hashtype: md5($salt.$pass)
Workload: 1024 loops, 256 accel
Speed.GPU.#1.:  6757.1 MH/s

<orcnote>
  OK, I now understand what you meant about which way the inner loop
  works.  The following is not a great idea because it can exhaust
  the word list and run exhausting inner loops:

  for (c in Corpus)
      for (try in KnownPWs)
          if (c.h == hash(c.salt, try))
             {  report(c.id, try, c.salt, c.h);
                break;
                };

  The idea is to claim low-hanging fruit first and eliminate those
  quickly.  So, still assuming that the salts are unique,

  for (try in KnownPWs) // assumed in opportunistic ordering 
      {   for (c in Corpus)
             if (c.h == hash(c.salt, try))
		      {  report(c.id, try, c.salt, c.h);
                    Corpus.remove(c);
                    };
          if (Corpus.length == 0)
             break;
          };

  Since try is the same throughout the inner loop, there can 
  be some code motion out of hash(c.salt, try) for setup and 
  unchanging parts when hash uses something like a digest of 
  (try || c.salt).

  So it would be good for hash() to incorporate an initial 
  shuffle(salt || try) for which there is no valuable pre-
  computation no matter which of salt or try changes 
  slowly.

  Thanks for helping me understand this.  Fun.
</orcnote>