[cryptography] Current state of brute-forcing random keys?

Solar Designer solar at openwall.com
Thu Jun 9 20:07:40 EDT 2011

On Thu, Jun 09, 2011 at 11:37:16PM +0100, Paul Crowley wrote:
> On 09/06/11 20:35, Solar Designer wrote:
> > ... if we expect
> >attackers with GPUs but maybe not with custom hardware (FPGA, ASIC), we
> >could want to stay away from SHA-2 family functions and use something
> >like Blowfish (Eksblowfish, bcrypt) in the KDF instead.
> Blowfish is less friendly to brute force than SHA-2, but there are 
> functions specifically designed to be brute-force-unfriendly.  There are 
> suggestions in http://www.schneier.com/paper-low-entropy.html about how 
> to build a function to iterate which is unfriendly to brute forcers;

I've seen this paper before, and I just took another look at it.  As
compared to Blowfish key setup, the algorithm given in "5.2 A Design for
a Computationally Expensive Permutation" adds the use of 32-bit integer
multiplication and modulo division.  Yes, this sort of thing falls under
more complete use of a CPU's execution units, which I had mentioned.

More importantly, I think we always need to consider specific kinds of
hardware that we expect defenders and attackers to use.  I wouldn't say
that one crypto primitive is less friendly to brute-force than another
without considering specific kinds of hardware.

It is possible that the defender will use a general-purpose CPU, and an
attacker will use whatever works best.

Or it is possible that the likely attacker will use whatever they
readily have or can acquire cheaply (perhaps GPUs or a botnet mostly
with CPUs).

Or it is possible that the defender can afford FPGA boards, and a goal
is thus to make other kinds of hardware (short of ASIC, indeed) less
suitable for attacks.  (This is what we're trying to do now under the
project I had mentioned.)

...and there can be other scenarios as well.

We have three main kinds of hardware: CPU+RAM, GPU, FPGA/ASIC.

If we look at SHA-256 and Blowfish (many iterations of either, and maybe
also many parallel instances of such loops in a single instance of our
custom KDF), here's what we get:


- Blowfish uses 32-bit operations only, 4 KB of RAM (not much).

- SHA-256 can use SIMD vectors of many parallel 32-bit operations (thus,
making more complete use of the CPU), but only if our KDF has this kind
of parallelism in it.  It uses even less RAM.

In either case, extra parallelism (if available in the KDF) may be
obtained through mixed instructions from multiple instances of these
primitives (as long as the CPU architecture register count permits).

Neither is a clear winner, although Blowfish not being able to make any
use of the 128-bit (SSE2) or 256-bit (AVX/XOP) vectors is not great.
Similarly, KDFs that lack parallelism for SHA-256 to use such vectors
are not great.

For an attacker using a CPU, SHA-256 used by a parallelism-lacking KDF
(such as PBKDF2) is preferable (faster to brute-force), because the
attacker does have plenty of parallelism (different passwords to try).
So the attacker wins 2 to 3 bits (on current CPUs).


- Blowfish can't be implemented efficiently so far.

- SHA-256 can be implemented efficiently.

So if we're the defender and we have a GPU, we prefer SHA-256 (and
lots of parallelism in our KDF).  If we're a defender without a GPU
and we consider attackers with GPUs, we prefer Blowfish.


Either can be implemented efficiently.  If we're the defender and we
consider attackers with GPUs (maybe among others), we prefer Blowfish
(and lots of parallelism in our KDF).


I am not saying that one of these two is the best choice for a crypto
primitive to use in a KDF.  In fact, we're considering other options.
I have simply compared two that have already been mentioned.

As an alternative to choosing the most suitable crypto primitive for
specific hardware of the defender and likely attackers, we may design a
KDF that is good for defenders "on average".  This one will try to make
the maximum use of computing resources of all three kinds of platforms,
so an attacker's advantage by choosing a more suitable platform will be
minimal.  However, this approach is suboptimal for most platforms of the
defenders (for 2 out of 3) and for some kinds of likely attackers (it
does nothing to slow down attackers with GPUs, it only speeds up
defenders to compensate).

> see also Microsoft's "Penny Black" research eg
> http://research.microsoft.com/apps/pubs/default.aspx?id=54395

I haven't seen this one.  I'll take a look.  Thanks!


More information about the cryptography mailing list