phc-discussions - Re: [PHC] Question about saturating the memory bandwidth

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: <CAJ7Lr3J6yLojmyQ5-=+SxEtNRTa8QRUx9ZB6oc06w3QFQyFQeQ@mail.gmail.com>
Date: Fri, 17 Jan 2014 23:08:12 +0800
From: Ivica Nikolic <cube444@...glemail.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Question about saturating the memory bandwidth

Hi Bill,

Thank you for your reply.

Do you suggest that aside from the theoretical side channel attack, and
under the assumption that the recomputation of the missing data is
computationally expensive, an attacker cannot achieve more than 2x speedup?

Regards,
Ivica


On Fri, Jan 17, 2014 at 10:35 PM, Bill Cox <waywardgeek@...il.com> wrote:

> On Fri, Jan 17, 2014 at 8:02 AM, Ivica Nikolic <cube444@...glemail.com>
> wrote:
> > I have a question about a possible PHC design strategy:
> > Assume the defender is sitting on a GPU and his/her KDF saturates the
> memory
> > bandwidth. The look-up table used in the KDF is large and it does not
> depend
> > on the password. How can an attacker achieve a speed up?
>
> Can I assume that the KDF does random lookups in memory based on the
> password?  The first problem, which isn't major IMO, is the attacker
> can fill memory once, and then make password guesses without spending
> the time or bandwidth to do it again.  Assuming each password guess
> the same time and bandwidth as filling memory in the first place, an
> attacker only gains a 2X advantage.  That's very good, really
> outstanding, IMO.  On the GPU, you might even be able to make enough
> use of all the cores to begin increasing an attacker's cost
> significantly.  On our CPUs, even 32 parallel multipliers is cheap
> compared to the cost of even 1GB of external RAM.  4096 multipliers in
> parallel begins to be interesting.
>
> Silicon in most processes costs around $0.05/mm^2.  Assume an attacker
> is paying $0.10/mm^2 for 22nm, and package/test takes it to $0.20/mm^2
> (a total WAG).  A carry-save adder is maybe 12 gates of logic, and we
> need around 16x32 of them, for around 6100 gates.  Assuming and-packed
> logic in 22nm does about 1,000,000 gates/mm^2, we can probably pack
> 150 of them per mm^2.  4096 of them would cost around $5.50.  That's
> comparable to the memory cost.
>
> Assuming the defender has a high-end graphics card, he can get better
> protection using it.  Someone else will have to comment on whether
> cache timing attacks are even possible against a graphics card, but if
> they are, an attacker might be able to gain advantage by aborting
> incorrect password guesses early based on memory access pattern.  One
> thing to worry about is time-memory trade-offs.  If an ASIC attacker
> can reduce the external RAM 4X or more, and recompute the missing data
> in parallel with a few cores, he gains a major advantage.
>
> Bill
>

Content of type "text/html" skipped