phc-discussions - Re: [PHC] Missed opportunity re: unpredictable addressing?

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: <541C8CEB.8070007@ciphershed.org>
Date: Fri, 19 Sep 2014 16:07:07 -0400
From: Bill Cox <waywardgeek@...hershed.org>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Missed opportunity re: unpredictable addressing?

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

On 09/19/2014 10:08 AM, Krisztián Pintér wrote:
> On Fri, Sep 19, 2014 at 5:59 AM, Alex Elsayed
> <eternaleye@...il.com> wrote:
>> In particular, a salt is defined as 1.) public and 2.) random. I
>> suspect that salt-dependent, password-independent addressing
>> might well prove a useful trick.
> 
> the problem is exactly that salt should be treated as public. this 
> concept would be fine for secret salts, which is an option, but 
> unusual. for public salts, it does not help, but hinder. why it
> does not help, was explained by Dmitry. let me explain why it
> hurts.
> 
> predictable but wildly irregular pattern is harder to optimize,
> but can be optimized. it is typically a situation which urges the
> good guys to omit optimization (to avoid complexity), but urges
> attackers to do the optimization, and thus gain advantage. we want
> optimization options to either be not there, or so easy that
> everybody will implement them. difficult optimizations mean
> advantage to attackers, and disadvantage to defenders.
> 

I agree.  Here's one particular optimization I might use.  Since for a
given salt, all the memory access patterns will be the same,
independent of the password guess, I can interleave the memory for
several guesses together, so that when I run them in lock-step, I
reduce the cache-miss penalty for reading small blocks of memory.
That's just one example, but there are a number of them.

There are several optimizations that can be made when predictable
addressing is used.  For example, a TMTO generally improves because
you only need to keep memory you know you will use.  You can mount a
pebbling attack and minimize memory for any given TMTO using my
auto-pebbler, for example :-)

Also, some timing information can be leaked.  It might be possible for
an attacker to detect who has logged in based on a cache timing
signature, for example.

I thought a lot about how to use salt and not the password, but I
couldn't come up with anything worth pursuing.

Bill
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQIcBAEBAgAGBQJUHIznAAoJEAcQZQdOpZUZlYoP/1j07sGYiD9fDKTNUcl1+0mm
oy5FsC55ZdVBC6ltx2eok35IaL2VcOBkBIdzSoCWrgrYugffsmHYd78spCOXwxGM
d5MNAFAYiBGueGV+3BZOQzRuJHL1kD2stdwrguhiR2bbHOtUfsLDQKNMhBvuVTm0
Ltz/aRrlKmS+Rf9bYONwJabIe2/eO0oZEbkDAkif8eE0OBTFAKLKroSzS3XMqO3/
TipLjtYT5H5OVUXn3m8jk0OBuuxfWl2akVRt7BXOahHid4x6ttHON8csvQ598WfB
NtUMScOhuLMVi9VLbXE61Z6xtLfa+fND0PLYLRhIFM6mDo7Unom8KU4NjiTwGsVz
Sx31hFibPOcVkBnjOC23H/cweSQki+mv98YDM9ZQgSOzXZqIIZjd+d0GKy0A5KvH
qIiACs46QXo/UIz7bKZP6DDSpS2U9EL85Ztigc8rmOqbuvAGw8w2uHgBnnc+PXtZ
UGPK7RI5nWk1KXkWGpTV9jXpg5AAc8RmzmlnkkH1/V7kRjPdHb4j6+8hR9NcSh/F
NuKpPYtiLSYcZknMBYUU52cfMNAg9kXALc1WwHN9LngLONMEv6ML0JTp1kG3CNT9
0EL/NDMDBhz50lHRcuPcN8migZpqyguQ3VZtDPtALC23Xf9yjkVa5SfLN03pPkq/
0y5D4+01Ca+Wg8LpP3E6
=JRpf
-----END PGP SIGNATURE-----