When the geeks got brutal...

Brute Force
October 7, 2005

In the mid-1970s, IBM developed an encryption system for the US Government that became widely used in commerce, especially in banking systems. The result, the Data Encryption Standard, was criticised from the outset. Academics suspected that spooks from the US National Security Agency (NSA) had tampered with the design to make it weaker, whereas they had in fact made it stronger against a type of attack that did not become public knowledge for nearly 20 years. However, the academics were right about one aspect of DES - the encryption key length of 56 bits was far too short, and so encrypted data could be read by "brute force": trying all possible keys to see which one worked. However, the number of possible keys exceeded 72 quadrillion
(256), so only a major government organisation could afford to build a cracking machine - and it is widely believed that the NSA did just that.

By the mid-1990s, computers had become considerably faster and cheaper, and it was realised that a brute-force cracking effort might be within the capability of private individuals. In January 1997, RSA Inc., a cryptography company, offered a $10,000 prize for reading a DES-encrypted message. This book is the story of how several thousand individuals volunteered their own computers (and those in their university labs) to win that prize, using the internet to co-operate in a brute-force effort they called Deschall. It took them nearly five months, though by the end they had learnt so much about speeding up their programs and enlisting support that a second challenge was solved in just 39 days. Then in January 1999, after the Electronic Frontier Foundation constructed a specialist $250,000 machine, a third and final challenge was solved in a mere 22 hours.

Matt Curtin was right at the heart of the Deschall cracking effort, and his book is excellent in describing the day-by-day progress towards the goal, injecting real tension as rival groups threaten to beat Curtin's group to the prize. Interleaved with this diary is the parallel story of how the US Congress spent that spring considering whether to pass laws to restrict the use of encryption. Accounts of the hearings are told well enough, although there is little attempt to set 1997's battles of the "crypto wars" within the wider context of a campaign that ran for most of the decade; and there is only the briefest mention of the pressures on the legislature to leave the issue alone lest the nascent e-commerce industry be left without a technology to keep it secure.

Sadly, the book is poor in presenting the technical aspects of encryption, with weak analogies, superficial explanations and some rather dubious historical facts. In particular, it repeatedly makes the technical howler of comparing key lengths incorrectly. A 128-bit key is not 72 times harder to break than a 56-bit key, but a thousand, billion, billion times harder.

At heart, this is a geek's book written by a geek. It tries hard to explain geeky things to the lay reader, but it never really rises above describing a contest that only ever interested geeks. Nevertheless, the book deserves notice because of a non-geek issue - how is enthusiasm for co-operative projects built and sustained? There was $10,000 at stake, but most participants would have competed for the glory alone, and key motivators were the daily charts of relative efforts by rival universities (was Georgia Tech testing more keys than the Massachusetts Institute of Technology?) and rival systems (were Macintosh owners contributing more than Windows users?).

Recently, co-operative computing has come off the boil, be it SETI@Home looking for signs of extraterrestrial life in radio-telescope data or Stanford University folding proteins to tackle disease. Perhaps the problems are just of the wrong scale, and although enthusiasm can be generated for a few months, it then becomes a slog? There have been no more DES challenges (you might hope to solve them in 22 minutes by now), and most other cryptographic challenges require many years of effort.

However, this book has appeared at an opportune time to rekindle interest in distributed attacks. The latest results from Xiaoyun Wang in China have reduced the time complexity of finding cryptographic hash collisions on SHA-1, a widely used standard for assuring data integrity, down to a brute-force susceptible value of 263. Right now, there are geeks out there who may be planning just such an attack.

Richard Clayton is a researcher in the Computer Laboratory, Cambridge University. In 2001, he constructed brute-force cracking hardware costing less than $1,000 that found a 168-bit triple-DES key (albeit in very special circumstances) in less than two days.

Brute Force: Cracking the Data Encryption Standard

Author - Matt Curtin
Publisher - Copernicus
Pages - 291
Price - £17.50
ISBN - 0 387 20109 2

You've reached your article limit.

Register to continue

Registration is free and only takes a moment. Once registered you can read a total of 3 articles each month, plus:

  • Sign up for the editor's highlights
  • Receive World University Rankings news first
  • Get job alerts, shortlist jobs and save job searches
  • Participate in reader discussions and post comments
Register

Have your say

Log in or register to post comments