New factoring hardware designs suggest that 1024 bit numbers can be factored for $1 million. That's significant - that brings ordinary keys into the reach of ordinary agencies.
If so, that means most intelligence agencies can probably already crunch most common key sizes. It still means that the capability is likely limited to intelligence agencies, which is some comfort for many of us, but not of comfort if you happen to live in a country where civil liberties are not well respected and keys and data are considered to be "on loan" to citizens - you be the judge on that call.
Either way, with SHA1 also suffering badly at the hands of the Shandong marauders, it puts DSA into critical territory - not expected to survive even given emergency surgery and definately no longer Pareto-complete. For RSA keys, jump them up to 2048 or 4096 if you can afford the CPU.
Here is the source of info, posted by Steve Bellovin.
Open to the PublicDATE: TODAY * TODAY * TODAY * WEDNESDAY, Sept. 14 2005
TIME: 4:00 p.m. - 5:30 p.m.
PLACE: 32-G575, Stata Center, 32 Vassar Street
TITLE: Special-Purpose Hardware for Integer Factoring
SPEAKER: Eran Tromer, Weizmann InstituteFactoring of large integers is of considerable interest in cryptography and algorithmic number theory. In the quest for factorization of larger integers, the present bottleneck lies in the sieving and matrix steps of the Number Field Sieve algorithm. In a series of works, several special-purpose hardware architectures for these steps were proposed and evaluated.
The use of custom hardware, as opposed to the traditional RAM model, offers major benefits (beyond plain reduction of overheads): the possibility of vast fine-grained parallelism, and the chance to identify and exploit technological tradeoffs at the algorithmic level.
Taken together, these works have reduced the cost of factoring by many orders of magnitude, making it feasible, for example, to factor 1024-bit integers within one year at the cost of about US$1M (as opposed to the trillions of US$ forecasted previously). This talk will survey these results, emphasizing the underlying general ideas.
Joint works with Adi Shamir, Arjen Lenstra, Willi Geiselmann, Rainer Steinwandt, Hubert K?pfer, Jim Tomlinson, Wil Kortsmit, Bruce Dodson, James Hughes and Paul Leyland.
Some other notes:
http://www.keylength.com/index.php
http://citeseer.ist.psu.edu/287428.html
Don't panic. Discrete logarithms mod p (where p is a Sophie-Germain prime that is (p-1)/2 is also prime) seems to be, in the light of these same developments, considerably harder than factorization. The same Number Field Sieve can be used for both, except that the resources for the matrix step are squared, and with them pretty much the cost.
Also, it seems that SHA1 (and even MD5) can be fixed. The number of "problematic" blocks seems to be small and they seem to be easily detectable, meaning that it is possible to construct MD5+ and SHA1+ that give the same hash for most data (which does not contain problematic blocks) while being resistant to the collision attack. So not all is lost.
I'll dig up the references next week.
Also, if you have to hog some $1M hardware for almost a year in order to break one key, then you need to be very determined to follow through. It's still a very expensive excercise, in short. Assuming $1M being the marginal cost, NSA may spend, say, $10G (given a very generous budget) to build 10k such machines, which, given the months spent on each individual key, is still not terribly many.
Posted by: Daniel A. Nagy at September 14, 2005 08:35 PM