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

Solar Designer solar at openwall.com
Thu Jun 9 21:08:02 EDT 2011


On Thu, Jun 09, 2011 at 05:49:38PM -0500, Marsh Ray wrote:
> On 06/09/2011 04:53 PM, Solar Designer wrote:
> >That's scary.  Even more so if you actually multiply by $0.07, which
> >gives $42.
> 
> Hmm, I thought I had included that.
> 
> I left my trusty old HP RPN calculator at home today and while a good 
> craftsman never blames his tools, apparently I'm not good enough to get 
> the same answer twice out of Ubuntu's. So double-checking my numbers and 
> suggestions on an RPN calculator app for Linux are welcome.

The rest of your numbers passed my double-checking just fine.  BTW,
0.35 um process is not state of the art, so things might actually be
even worse.

(I never had an HP RPN calculator, but I still have two different
Soviet-made programmable RPN calculators in working order.  No, I simply
used "bc" this time... not even "dc".)

> >This means that for relatively small key size like this, the primary
> >cost for using an ASIC implementation is in creating that implementation
> >and in making it solve the specific task, not in electricity.
> 
> ... and we all know folks who would do that sort of thing just for the 
> fun learning experience.

Why didn't they crack RC5-72, then?  The cost in electricity would
appear to be close to $10k (or even less considering that RC5 is simpler
and the tech process may be smaller), and RSA pays a $10k prize.

Maybe building such a machine is still more costly than $250k?

> But what if the attacker doesn't want to pay the $100K minimum foundry 
> cost? How much of a penalty does he pay for using FPGAs, or even a 
> heavily optimized CPU+GPU codebase? Perhaps it's a huge hit, but even a 
> 100x loss amounts to less than 7 bits of key length.

For a 50% chance of cracking a 64-bit key against a crypto primitive as
fast as MD5 or DES (sorry, that's what I had suitable GPU speed numbers
for) in 1 year, I am getting around $10k in hardware (30 ATI 5970 cards)
plus another $10k in electricity.

> I think Scrypt has the right idea with consuming RAM or, more precisely 
> RAM nonlocal latency. CPU frequencies have gone from MHz to GHz, memory 
> has gone from MB to GB, even bus speeds have increased a few times, but 
> the time required to fetch a cold address from DRAM has changed least of 
> all.

Actually, per the scrypt paper, it deliberately consumes RAM itself, not
bandwidth, nor latency.  However, yes, when we consider attackers with
GPUs, those are limited not only by relatively small RAM size (per
stream processor, and even more so per thread), but also by bandwidth,
latency, and poor efficiency with non-sequential access.

> I suspect an ideal work-factor function would thus look something like 
> RC4 (which is actually well defined over any state size) but with a few 
> GB of state rather than the 256 bytes that it's normally used with. Due 
> to some small patterns in the RC4 keystream it would still use a proper 
> hash function for distilling the final output hash value.

I haven't considered RC4 in this context yet.  Thanks for the suggestion.

One thing we're considering for FPGA implementation is Blowfish-like
constructs, but with different S-box sizes - both smaller (to fit in
distributed RAM in Xilinx LUTs) and larger (to optimally use Xilinx
Block RAMs) than normal Blowfish.  Of course, we're talking rather small
memory sizes there (an FPGA chip has only a few megabytes of memory in
it, and accessing external DRAM is not any better than doing so from a
CPU).  So we're also considering including an on-CPU component, which
will use the host machine's RAM like scrypt does.

> A few GB of state would hopefully put it in that size range where it's 
> too large to fit on any attacker's ASIC,

In the scrypt design, there was no attempt to make something too large
to fit, but rather simply to consume more die area and increase cost.

> while at the same time being of 
> a size for which a defender's commodity hardware is heavily optimized.

Right.  I think this implies that ASICs with enough DRAM can be produced
as well, and that's fine.

Thanks for your comments!

Alexander



More information about the cryptography mailing list