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

Marsh Ray marsh at extendedsubset.com
Fri Jun 10 01:53:26 EDT 2011

On 06/09/2011 08:08 PM, Solar Designer wrote:
> 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.

Cool. Out of curiosity, did they also call it "Reverse Polish Notation", 
or did they have another name for it?

> No, I simply
> used "bc" this time... not even "dc".)

Yeah I need to remember that one.

>> ... 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?

I saw mention of some hardware designed for distributed.net RC5, do you 
have a description of it?

If my reasoning holds up, it might be because:

* RC5 requires significantly different power and chip area than AES @ 
0.25 mm2. I don't see a source for chip area that's not behind a 
paywall. Who except codebreakers are going to benchmark and heavily 
optimize the key expansion part of the algorithm?

* The hardware process and designers simply could not obtain the same 
level of performance relative to the Philips, Intel, and Nvidia numbers 
I started with.

This paper http://www.universitypress.org.uk/journals/ami/ami-27.pdf 
cites a figure of 35 nJ per RC5 on a decade-old FPGA family (Xilinx 
Virtex-II). This does not include key expansion. It amounts to 9.7e-15 
KW-hours per trial, about 150 times more than I'd figured for AES on 
modern processes.

> 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?

Yes, I think you would expect to pay at least that for any box which 
included a custom ASIC design by a professional team. A university group 
might get it done for less, but that could also end up costing more in 
the long run.

> 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.

This program ighashgpu seems to be doing 10.3e9 MD5 operations per 
second on a 450 W TDP graphics card, which comes to 12.4e-15 KWh per 
trial. http://www.golubev.com/blog/?p=210

> 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.

Seems like anything you can do to make the defender's machine the 
optimal machine is a step in the right direction (without weakening it 
of course).

>> 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.

That's certainly valuable, but I think the biggest design payoff comes 
if you can force even the most advanced attacker to move data off and on 
the chip. Anything smaller than that amounts to giving large-die 
attackers a huge advantage over the typical defender.

Of course, as Nico pointed out such a thing will not be usable 
everywhere. But not everything has to run on a cell phone, right?

- Marsh

More information about the cryptography mailing list