[Mac_crypto] Breaking RSA using Apple Macs

[Nicko van Someren]

Fellow Mac Crypto people,

	Attached is a [slightly edited] copy of a mail I sent internally the 
other day that I thought might be of interest to you guys.

	Cheers,
		Nicko



	From: 	  nicko@ncipher.com
	Subject: 	Breaking RSA using Apple Macs
	Date: 	7 January 2004 13:54:35 GMT

It's a pity my research budget is so small :-(

Not only did Apple launch the new G5 version of the Xserve [1] 
yesterday, along with the stripped down "Cluster Node" model aimed 
squarely at the networked processor market, but they also released 
their Xgrid [2] parallel computation support software.  The network 
processor units have two 2GHz G5 processors in them which, given the 
super-scalar nature of the processor I suspect should deliver about 
8,000 MIPS between them.  As it happens the first factoring of a 512 
bit RSA key took approximately 8,000 MIPS-years [3] for the "sieve" 
step.  So, one of these items should be able sieve a 512 bit number in 
a year or a standard 42 U rack mount case with 40 of them and a couple 
of network hubs should be able to do the sieve stage in about 9 days.

Of course that leaves the matrix reduction stage.  [My research 
assistant] Ben reckons that this is mostly bound by the memory 
bandwidth of the system, especially on how you get to control the use 
of caches and the speed of writing data back.  Not only does the G5 
have instructions for telling the CPU to pre-fetch memory with a 
specified write-back policy but it seems that they have up-rated the 
front side bus to 1GHZ and the Xserve can have up to 8GB of 128 bit 
wide 400MHz DDR memory.  When [My research assistant] Ben did some work 
on the matrix reduction step on the [800 MHz] Itanium for me a couple 
of years back the system looked like it would run in about three weeks 
using 128 bit wide 133MHz SDRAM, so with three times faster memory into 
processors clocked 2.5 times faster we might be able to get it down to 
9 days too :-)

So how far off the budget are we?  Well, one fully loaded Xserver (8GB, 
750MB disc) costs $7,500 and 39 cluster nodes cost $3K each.  Add in a 
pair of hubs and a rack ($500) and you get to the nice round number of 
$125,000, or just a mere [...cut...] over my budget for hardware :-)  
Still, $125K for a machine that cracks 512 bit keys every ten days 
should leave the 25,000 or so web sites that still seem to be using 
short keys very worried!

	Nicko


[1] http://www.apple.com/xserve/
[2] http://www.apple.com/acg/xgrid/
[3] http://www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html