[Hardware] RSA Challenges

John L. Bass jbass at dmsd.com
Fri Jun 1 18:51:59 EDT 2007


	If you are thinking of brute-force search, it would have taken a long
	time to get the prize in any case.  If you have some algorithmic
	breakthrough that can search for RC5 keys faster than brute-force,
	however, your achievement will be rewarded by the technology community
	with much more than just prize money.

	-- Burt 

Brute force via any counter driving the entire key schedule and decrypt
is clearly a decade or more work, unless done with a very specialized
high end FPGA array. And even then, the power costs for the project would
far exceed the prize in aggregate, but make an interesting lottery
for those deploying and FPGA based Reconfigurable Computing array.
We have been exploring this via the distributed.net hardware list for
a while, including building some high performance comodity FPGA engines
based on this project.

I have developed another strategy based on partial symbolic solution
to reduce the search effort (something of a bolean SAT approach), for
which I picked up a dozen high end Itanium servers with large caches
to be augmented with an FPGA array, specifically to demonstrate this
approach.  Unfortunately I was counting on some or all of the remaining
prizes to pay for the $30K equipment and significant electric bill this
has been running up for the research. I clearly would not have made this
recient investment had the project sunset been clear.

I doubt, other than the prizes, that there is any other way to recover
the losses for this project. I suspect I'm not the only one either, which
is why a much more graceful termination, with a one or two year sunset
would have been MUCH MUCH better, allowing people to plan and judge the
project risks of not meeting a well known deadline better.

Besides RC5, I and others, have significant factoring projects underway
as well ... at a significant cost. None of us would have spent the electric
bills without some hope of cracking the factoring prizes. Again, a sunset
that was well known, would avoid countless wasted efforts, and some
resentment about the unplanned withdrawal of the challenges.

I'd suggest a sunset of Dec 31, 2009, or even 2008, would have been much
more reasonable, and would avoid some direct resentment of EMC/RSA for
project losses which could have been avoided with planning and advance
notic.

John
	From: kaliski_burt at emc.com
	Subject: RE: RSA Challenges
	Date: Fri, 1 Jun 2007 17:59:08 -0400
	To: <jbass at dmsd.com>
	Cc: <ajuels at rsa.com>

	Dear John --

	Thanks very much for your message.

	The reorganization of RSA Laboratories as the security group of the new
	EMC Innovation Network was an appropriate time to announce a number of
	changes that had been considered for a while, including the challenges
	as well as the new "historical" status of the FAQ, and status changes in
	various PKCS documents.

	I'm sorry that the news was so abrupt, and I appreciate your suggestion
	about a delayed conclusion.

	A distributed effort to solve the RC5-72 challenge
	http://www.distributed.net/rc5/ has been underway for several years,
	with a lot of work remaining (0.4% done), and we didn't see the
	cancelation as significantly affecting that work.  However, I do
	understand that there may be other efforts and explorations that are not
	as public yet, such as the one you mention.  

	If you are thinking of brute-force search, it would have taken a long
	time to get the prize in any case.  If you have some algorithmic
	breakthrough that can search for RC5 keys faster than brute-force,
	however, your achievement will be rewarded by the technology community
	with much more than just prize money.

	-- Burt 

	-----Original Message-----
	From: John L. Bass [mailto:jbass at dmsd.com] 
	Sent: Wednesday, May 30, 2007 3:12 PM
	To: bkaliski at rsa.com
	Subject: RSA Challenges

	Hi Burt,

	I'm curious why they were abruptly cancelled. I've been working on an
	attack for the remaining RC5 challenges that I was hoping would yield
	results later this summer or fall.

	It would have been nice if you guys would have simply left both sets
	of challenges in place, with an update that they end in a year or so.

	Have fun,
	John


More information about the Hardware mailing list