phc-discussions - Re: [PHC] pufferfish

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: Mon, 24 Mar 2014 16:48:19 -0000
From: pornin@...et.org
To: discussions@...sword-hashing.net
Subject: Re: [PHC] pufferfish

> Note that L1 cache sizes haven't changed much in the last 25 years -
> that's more than bcrypt's age!

That's a point I make sometimes: the amount of "fast RAM" in a computer is
mostly fixed over time.

What I call "fast RAM" is "RAM that is accessed most efficiently, within
one or two clock cycles". My first computer (in 1984) had 32 kB of fast
RAM (1MHz 6809E, no cache). My current computer does not have more than
that... although it has a much higher clock rate, does a lot more
computing within one cycle, and has lots of not-so-fast RAM.

The maximum amount of fast RAM was reached in the late 1980s, in the days
of the Atari ST and Amiga: 68000 at 7 or 8 MHz, and _megabytes_ of fast
RAM (no choice here: the CPU had no cache at all). Then it went downhill
from that local maximum, with, as you note, the PA-RISC exception.

> Oh, and PA-RISC systems will be rather attractive to attackers. ;-)
> Luckily, they might be behind the curve in terms of clock rates, and are
> pricey, but HP might appreciate the free advertising from pufferfish
> cracker benchmarks anyway (they might be cited in other contexts). ;-)

However, HP stopped selling PA-RISC machines in 2009. It seems that the
last incarnation of the PA-RISC architecture dates from 2005, with no
plans to make a new one+. Instead, HP tried to use Itanium, with mixed
success; and of course x86, like everybody else.

> I am currently considering the range of 8 KB to 16 KB for bcrypt-like
> accesses from escrypt's BlockMix.

There are a number of "small architectures" with 8 kB L1 cache around.
Typically, home WiFi routers use Mips-derivatives with that much L1 cache,
but not necessarily more than that. (My WRT54G has 8 kB for code and 8 kB
for data, and I think it is quite representative.)

When talking password hashing, we usually think about login servers, which
are basically big PC, with 64-bit registers. However, there are some usage
contexts where the hashing will have to be done on much smaller systems,
such as home routers or not-so-smart phones. This is not a good situation
(all this password hashing is an arms race between defender and attackers,
and small defenders are then at a disadvantage), but sometimes this is
unavoidable. In that sense, a bcrypt-like scheme who wants to fit in the
available "fast RAM" should target a data size of at most 8 kB.

(It is quite possible that there is no good one-size-fits-all.)

        --Thomas Pornin