I believe you are incorrect in this statement. It is a matter of public record that RSA Security's DES Challenge II was broken in 72 hours by $250,000 worth of semi-custom machine, for the sake of solidity let's assume they used 2^55 work to break it. Now moving to a completely custom design, bumping up the cost to $500,000, and moving forward 7 years, delivers ~2^70 work in 72 hours (give or take a couple orders of magnitude). This puts the 2^69 work well within the realm of realizable breaks, assuming your attackers are smallish businesses, and if your attackers are large businesses with substantial resources the break can be assumed in minutes if not seconds.

2^69 is completely breakable. Joe Its fine assuming that moore's law will hold forever, but without

Joseph Ashwood wrote: that you can't really extrapolate a future tech curve. with *todays* technology, you would have to spend an appreciable fraction of the national budget to get a one-per-year "break", not that anything that has been hashed with sha-1 can be considered breakable (but that would allow you to (for example) forge a digital signature given an example) This of course assumes that the "break" doesn't match the criteria from the previous breaks by the same team - ie, that you *can* create a collision, but you have little or no control over the plaintext for the colliding elements - there is no way to know as the paper hasn't been published yet.

----- Original Message ----- From: "Dave Howe" <DaveHowe@gmx.co.uk> Sent: Thursday, February 17, 2005 2:49 AM Subject: Re: SHA1 broken?

...

I believe you are incorrect in this statement. It is a matter of public record that RSA Security's DES Challenge II was broken in 72 hours by $250,000 worth of semi-custom machine, for the sake of solidity let's assume they used 2^55 work to break it. Now moving to a completely custom design, bumping up the cost to $500,000, and moving forward 7 years, delivers ~2^70 work in 72 hours (give or take a couple orders of magnitude). This puts the 2^69 work well within the realm of realizable breaks, assuming your attackers are smallish businesses, and if your attackers are large businesses with substantial resources the break can be assumed in minutes if not seconds.

2^69 is completely breakable. Joe Its fine assuming that moore's law will hold forever, but without that you can't really extrapolate a future tech curve. with *todays* technology, you would have to spend an appreciable fraction of the national budget to get a one-per-year "break", not that anything that has been hashed with sha-1 can be considered breakable (but that would allow you to (for example) forge a digital signature given an example) This of course assumes that the "break" doesn't match the criteria from

Joseph Ashwood wrote: the previous breaks by the same team - ie, that you *can* create a collision, but you have little or no control over the plaintext for the colliding elements - there is no way to know as the paper hasn't been published yet.

I believe you substantially misunderstood my statements, 2^69 work is doable _now_. 2^55 work was performed in 72 hours in 1998, scaling forward the 7 years to the present (and hence through known data) leads to a situation where the 2^69 work is achievable today in a reasonable timeframe (3 days), assuming reasonable quantities of available money ($500,000US). There is no guessing about what the future holds for this, the 2^69 work is NOW. ----- Original Message ----- From: "Trei, Peter" <ptrei@rsasecurity.com> To: "Dave Howe" <DaveHowe@gmx.co.uk>; "Cypherpunks" <cypherpunks@al-qaeda.net>; "Cryptography" <cryptography@metzdowd.com>

Actually, the final challenge was solved in 23 hours, about 1/3 Deep Crack, and 2/3 Distributed.net. They were lucky, finding the key after only 24% of the keyspace had been searched.

More recently, RC5-64 was solved about a year ago. It took d.net 4 *years*. 2^69 remains non-trivial.

What you're missing in this is that Deep Crack was already a year old at the time it was used for this, I was assuming that the most recent technologies would be used, so the 1998 point for Deep Crack was the critical point. Also if you check the real statistics for RC5-64 you will find that Distributed.net suffered from a major lack of optimization on the workhorse of the DES cracking effort (DEC Alpha processor) even to the point where running the X86 code in emulation was faster than the native code. Since an Alpha Processor had been the breaking force for DES Challenge I and a factor of > 1/3 for III this crippled the performance resulting in the Alphas running at only ~2% of their optimal speed, and the x86 systems were running at only about 50%. Based on just this 2^64 should have taken only 1.5 years. Additionally add in that virtually the entire Alpha community pulled out because we had better things to do with our processors (e.g. IIRC the same systems rendered Titanic) and Distributed.net was effectively sucked dry of workhorse systems, so a timeframe of 4-6 months is more likely, without any custom hardware and rather sad software optimization. Assuming that the new attacks can be pipelined (the biggest problem with the RC5-64 optimizations was pipeline breaking) it is entirely possible to use modern technology along with GaAs substrate to generate chips in the 10-20 GHz range, or about 10x the speed available to Distributed.net. Add targetted hardware to the mix, deep pipelining, and massively multiprocessors and my numbers still hold, give or take a few orders of magnitude (the 8% of III done by Deep Crack in 23 hours is only a little over 2 orders of magnitude off, so within acceptable bounds). 2^69 is achievable, it may not be pretty, and it certainly isn't kind to the security of the vast majority of "secure" infrastructure, but it is achievable and while the cost bounds may have to be shifted, that is achievable as well. It is still my view that everyone needs to keep a close eye on their hashes, make sure the numbers add up correctly, it is simply my view now that SHA-1 needs to be put out to pasture, and the rest of the SHA line needs to be heavily reconsidered because of their close relation to SHA-1. The biggest unknown surrounding this is the actual amount of work necessary to perform the 2^69, if the workload is all XOR then the costs and timeframe I gave are reasonably pessimistic, but if the required operations are dynamically sized mulitplies then the time*cost is off by some very large amounts. Even simple bulk computation assuming full pipelining says that 4700 4 GHz to complete 2^69 operations in 1 year, even assuming using full 3.8 GHz pentium 4s instead of a more optimal package only leads to a processor cost of 3.1 million for a 1 year 2^69, dropping that down to 2.4GHz celerons requires 7800 of them, but only $538,000. Moving to DSPs and FPGAs the costs will drop substantially, but I don't feel like looking it up, and as the costs drop the number of processors that can be used increases linearly additionally as the individual speeds drop the purchase cost drops better than linearly. I am quite confident that with careful engineering a custom box could be produced for the $500,000 mark that would do 2^69 operations in the proper timeframe. With deep pipelining any complexity of 2^69 operations could be done in the timeframe, but will scale the price. I suppose I should also point out an unspoken qualifier, I am assuming a large number of these machines will be built reducing the engineering overhead to miniscule, for a one-off project this will likely be the dominant cost. 2^69 work is achievable, the cost multiplier associated will be the determining factor. Joe

Joseph Ashwood wrote:

I believe you substantially misunderstood my statements, 2^69 work is doable _now_. 2^55 work was performed in 72 hours in 1998, scaling forward the 7 years to the present (and hence through known data) leads to a situation where the 2^69 work is achievable today in a reasonable timeframe (3 days), assuming reasonable quantities of available money ($500,000US). There is no guessing about what the future holds for this, the 2^69 work is NOW. I wasn't aware that FPGA technology had improved that much if any - feel free to correct my misapprehension in that area though :)

...

I wasn't aware that FPGA technology had improved that much if any - feel free to correct my misapprehension in that area though :) FPGAs are too slow (and too expensive), if you want lots of SHA-1

On Sat, Feb 19, 2005 at 03:53:53PM +0000, Dave Howe wrote: performance, use a crypto processor (or lots of forthcoming C5J mini-ITX boards), or an ASIC. Assuming, fast SHA-1 computation is the basis for the attack -- we do not know that. Indeed so. however, the argument "in 1998, a FPGA machine broke a DES key in 72 hours, therefore TODAY..." assumes that (a) the problems are comparable, and (b) that moores law has been applied to FPGAs as well as CPUs. I am unaware of any massive improvement (certainly to the scale of

Eugen Leitl wrote: the comparable improvement in CPUs) in FPGAs, and the ones I looked at a a few days ago while researching this question seemed to have pretty much the same spec sheet as the ones I looked at back then. However, I am not a gate array techie, and most of my experience with them has been small (two-three chip) devices at very long intervals, purely for my own interest. It is possible there has been a quantum leap foward in FPGA tech or some substitute tech that can perform massively parallel calculations, on larger block sizes and hence more operations, at a noticably faster rate than the DES cracker could back then. Schneier apparently believes there has been - but is simply applying moore's law to the machine from back then, and that may not be true unless he knows something I don't (I assume he knows lots of things I don't, but of course he may not have thought this one though :)