phc-discussions - Re: [PHC] Is bandwidth all that counts?

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: <CAOLP8p6-a-Amt_-cnyPSAaa6AfrdOJ-spRx7Vqn5agWEtSGBrQ@mail.gmail.com>
Date: Wed, 12 Feb 2014 01:18:20 -0500
From: Bill Cox <waywardgeek@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Is bandwidth all that counts?

On Tue, Feb 11, 2014 at 10:01 PM, Peter Maxwell <peter@...icient.co.uk> wrote:
> On 12 February 2014 01:23, Marsh Ray <maray@...rosoft.com> wrote:
>>
>> From: Peter Maxwell [mailto:peter@...icient.co.uk]
>>
>> > My problem is understanding why memory bandwidth is the critical
>>
>> > factor - is memory bandwidth inherently more expensive than the actual
>> > DRAM?

Basically, it's more expensive to double the memory bandwidth than the
DRAM.  For example, if an attacker pays $100 for an FPGA, and $20 for
RAM, he can double his RAM for another $20 or less, but doubling his
memory bandwidth will require another FPGA and another RAM bank,
almost doubling his cost.

I think for memory hard KDFs, it makes financial sense for an attacker
to max out memory bandwidth, and that will be the main limitation.

> So essentially, a hardware attacker can:
>
> - use compute operations much cheaper than defender;
>
> - use memory storage at the roughly the same cost as defender;
>
> - use memory bandwidth at roughly the same cost per hash operation as the
> defender.
>
> Have I got that correct?

Sounds right to me.

> From what I understand - and I don't know how far down the road they
> actually are - there are ASICs being produced to do scrypt hashes because
> it's used in Litecoin, presumably with the side-effect that these appliances
> can be used for cracking password hashes too.  Is it likely that the need
> for significantly improved memory bandwidth in other contexts - for example
> high-performance computing in the sciences - will drive an improvement in
> technology such that the assumptions on memory bandwidth limitations will
> fail in the near future?

One of my dumb ideas of the day is that I could build a cheap FPGA,
maybe for $2, that has a 10GiB/sec DDR3 or DDR4 bus, and a small
amount of logic.  After this password competition, the NSA could
probably use about 50 million of them.

Yes, my assumption that the FPGA or ASIC will be as expensive or more
than the RAM could easily change.  However, the password guessing
cores are cheap, so an attacker will still replicate them until memory
bandwidth is filled.

> And as a slight tangential: is it worth candidate algorithms for PHC having
> a tunable to create ever-so-slight changes in computation such that any
> adoption by a crypto currency isn't going to indirectly encourage hardware
> specifically for cracking password hashes to be produced?

If we hammer bandwidth enough, I'm not sure anyone will bother
building an ASIC, even if it is used for a crypto-currency.  However,
a high memory bandwidth graphics card or FPGA board will still
out-perform most computers in terms of memory bandwidth.  It seems to
me that the hash functions will still be run on graphics cards due to
higher memory bandwidth.

Bill