Brute Force 76
ijones writes "Brute Force, by Matt Curtin, is about an event that
many Slashdotters will remember: the cracking of the Data Encryption
Standard. In June of 1997, a 56-bit DES
key was discovered, and its encrypted
message decoded, by an ad-hoc distributed network of computers,
cooperating over the Internet. Four and a half months earlier, RSA had issued a challenge to the
cryptography community, offering $10,000 to the first group to crack a
56-bit DES encrypted message. In Brute Force, Matt
Curtin offers his first-hand account of the DESCHALL team's winning
effort." Read on for the rest of Jones' review.
Brute Force: Cracking the Data Encryption Standard | |
author | Matt Curtin |
pages | 291 |
publisher | Copernicus Books |
rating | 9 |
reviewer | Isaac Jones |
ISBN | 0387201092 |
summary | Volunteers working collaboratively over the internet manage to crack the Data Encryption Standard. |
Although I wasn't involved with the DES cracking challenge, I am friends with the author of this book. I took a Lisp course from Matt at Ohio State University and I'll be forever grateful that Matt introduced me to functional programming with a great deal of humor and enthusiasm. I don't think I've ever seen Matt stay so serious for so long, but his enthusiasm comes through clearly in this book.
Brute Force can be enjoyed by both nerds and non-nerds interested in cryptography or codes. Those who have been a part of this or subsequent DES challenges may be particularly interested in this book. Curtin covers some technical details of DES and the brute force attack that the DESCHALL team used to discover a DES key. He also discusses the political and historical significance of this event. This is a fairly technical book, but it goes out of its way to explain non-obvious technical topics, so one doesn't need a lot of technical background to understand it.
Curtin briefly explains a lot of stuff: the C programming language, firewalls, UDP, one-time pads, protected memory, etc., in order to make this book readable for novices. Although I generally did not need such explanations, I did not find them annoying or distracting, as they were fairly brief. In fact, it's fun to read concise explanations of such topics. Occasionally, Curtin does go into just a little too much detail. The chapter on Architecture gives an explanation of some of the many pieces of software that were involved in this effort. This chapter sometimes gets a bit bogged down with explanations of useful scripts that folks wrote to analyze data or forward packets through firewalls.
Brute Force is a very readable and enjoyable book. It is well organized as a narrative, though it is not chronological; Curtin presents the background and substance to each aspect of the story together, rather than chronologically. This can be slightly confusing sometimes, but I think it improves the over-all flow of the story.
In a way, Curtin gives away the ending to the book at the beginning (and in the title), but this isn't ancient history, and most readers will probably already know that DES was defeated by this effort. He still manages to maintain a good sense of suspense throughout the book. He presents tables and analysis of the effort, along with predictions about completion dates that volunteers had made at the time. Unfortunately, he doesn't tell us whether those tables turned out to be correct. What percentage of the keyspace was searched by Macintoshes? How many different kinds of client machines were there in the end? Did Ohio State University try more keys than Oregon State University? Which one is the real OSU?
One of the main themes running throughout the book was that of community. The DESCHALL project was made up of thousands of volunteers from all over the US. Anyone with some spare CPU cycles could get involved by downloading the client software. This may remind you of other distributed computing projects like SETI@home. The community was further broken down into sub-groups like schools who would compete for bragging rights. The organization of the DESCHALL project was much like an open source project, though the key-cracking tools were not open source. Spreading the Word is a chapter about how people started to hear about DESCHALL and what the earliest adopters were like. Some of the tables in a later chapter list the operating system and hardware that the clients were running, which was a pretty cool snapshot of the Internet from 1997. It included lots of OS/2 clients, labs full of SGI machines, and plenty of computers which were only connected to the Internet via dial-up modems. Special scripts were developed for such machines so they could phone home when they needed a new block of keys.
Though the key cracking clients were not open source, they were free as in beer, at least for Americans. Since such cryptography-related software could not be exported at the time, this was a US-only effort. There was a European team, however, with their own software, called SolNet, and Curtin keeps us updated on their progress. In fact the DESCHALL project had an impact on the political debate of this time with regard to the export and control of cryptographic technologies. Curtin gives us interesting periodic updates on the political debate as the DES cracking story moves forward. Cryptography control was defeated at that time, but the use of cryptography is a right that will need continued protection.
The political story of DESCHALL was one aspect of the historical impact of the project. Another impact was the explosion of volunteer distributed computing networks after the DESCHALL project, with SETI@home being one of the most obvious examples. DESCHALL clearly demonstrated the viability of this kind of computation. Curtin touches briefly on this here and there, but does not go into detail. I would like him to more clearly spell out the trends in Internet distributed computing. I would like to hear that DESCHALL was derived from project A and that it inspired projects B, C, and D. Was it was the original Internet distributed computing network? Was it a fad that has abated in the last few years? Curtin touches on this a bit, but says, "Some other distributed computing projects like DESCHALL were around," (pg 200.) He says which ones, but doesn't make any claims that DESCHALL inspired SETI@home, for instance. Perhaps such things are never quite clear in the free exchange of ideas on the Internet.
The political and community aspects of the story wrap up very nicely. Curtin outlines DESCHALL's impact on driving the AES standard, and its (perhaps much smaller) impact on the debates on key escrow and encryption exports. Brute Force is a very enjoyable read about an important event, and I can happily recommend my friend Matt's book to the Slashdot crowd. My only criticisms can really be summed up by saying, "I want to hear more."
You can purchase Brute Force: Cracking the Data Encryption Standard from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
For crying out loud... (Score:3, Funny)
Come one..."ad-hok?"
Re:For crying out loud... (Score:3, Funny)
Re:For crying out loud... (Score:2, Funny)
Re:For crying out loud... (Score:1)
--review author
Re:For crying out loud... (Score:3, Funny)
Unfortunately, it's "better than I."
Re:For crying out loud... (Score:2)
I spell better than Matt. Matt spells better than me.
Both of which are really odd things to say, since my name is also Matt.
Re:For crying out loud... (Score:1)
Re:For crying out loud... (Score:1)
Re:For crying out loud... (Score:1)
Re:For crying out loud... (Score:2)
Interesting. And how does one spell "Shakespear" in Latin?
Re:For crying out loud... (Score:3, Funny)
I thought you could continue the sentance like "Matt spells better than I spell.", which clearly only works with "I", but I may be wrong.
That also reminds me of one of my favorite childhood stores "Fortunately Unfortunately" or something like that...
Fortunately, Matt can spell better than me.
Unfortunately, it's "I".
Fortunately, few people care.
Unfortunately, one who does is my boss.
Fortunately, my boss doesn't read slashdot.
Unfortunately, his IT spies do.
Fortunately, they don't know my account nam
Re:For crying out loud... (Score:2)
Homer: [worried] Ooooh, that's bad.
Owner: But it comes with a free Frogurt!
Homer: [relieved] That's good.
Owner: The Frogurt is also cursed.
Homer: [worried] That's bad.
Owner: But you get your choice of topping!
Homer: [relieved] That's good.
Owner: The toppings contains Potassium Benzoate.
Homer: [stares]
Owner: That's bad.
Copied from snpp.com [snpp.com]
Distributed.net (Score:4, Informative)
Re:Distributed.net (Score:3, Interesting)
Yeah, but SETI@Home is searching for intelligent life.
Distributed is searching for things that probably never should have been encrypted in the first place.
When I was in the military, about 90 percent of the SECRET level documents should have been declassified to RESTRICTED or CONFIDENTIAL, and as one of the few subject matter experts
Re:Distributed.net (Score:3, Insightful)
Encryption is generally best when it is an all-or-nothing operation. If you encrypt JUST the one file with sensitive information, you draw attention to it and make it the obvious target.
OTH, if every file in your system is encrypted, it is a lot harder to know which files are important to break, and it will take so many more re
Re:Distributed.net (Score:1)
Re:Distributed.net (Score:2)
Re:Distributed.net (Score:3, Informative)
Back then, we couldn't even use encryption in web browsers. Try banking without that.
Completely Backwards (Score:3, Informative)
Re:Distributed.net (Score:3, Insightful)
Now things like protein folding have much more benefit to the world. Pick your projects carefully.
Re:Distributed.net (Score:2)
In the interest of full disclosure, you might have pointed out that you left distributed.net in not so friendly terms [distributed.net] with the rest of the team. Don't sweat, so did I (I joined distributed.net as a core coder after you left, so we never met.) But whenever I mention something that might be construed as negative about distributed.net in public, I try to disclaim my potential biases. Hence I'm doing this favor to you and the rest of Slashdot readers.
It wouldn't hurt to mention that distributed.net i
Re:Distributed.net (Score:2)
I have a bias against all non-productive uses of energy actually. RC5 and DES were about the legal battle, RC5-72 is just silly.
Servers (Score:2, Interesting)
Re:Servers (Score:2)
Some of you might remember it's original incarnation, the United Devices client. UD is still involved, and it's still on the same projects, like the Human Proteome Folding Project [worldcommunitygrid.org].
Re:Servers (Score:1)
Re:Servers (Score:2)
does it still support biological weapon research (Score:2)
Re:does it still support biological weapon researc (Score:2)
I know the UD client had some issues, which is why they dropped off of the face of the earth for awhile. I personally stopped using it because every time I installed it I ended up with an infected file on my hard drive. I never heard back from their support, so I don't know if it was a false positive, a corrupted mirror, or what. I just went back to SETI. So far this one has been okay. I mainly run it because, as I mentioned, it's kosher on
See DeCSS decrypt! Decrypt, DeCSS, decrypt! (Score:1)
Re:See DeCSS decrypt! Decrypt, DeCSS, decrypt! (Score:2)
de-CSS (Score:2)
R.
Matt... (Score:3, Informative)
He is a very weird and amusing fella [interhack.net]
Re:Matt... [sig] (Score:1)
I probably shouldn't say this, but it's spelt Zealots...
Imagine how much faster (Score:2)
It would have saved 1/6 of the keyspace.
T-shirts (Score:5, Interesting)
Re:T-shirts (Score:1)
Re:T-shirts (Score:2)
Yeah, I've got my shirt still. We really did argue about the design alot, that's for sure.
Re:T-shirts (Score:2)
I for one welcome our new Laten Overlordz (Score:2, Funny)
At least it wasn't an ad-hocked or ad-wocked network, that might have taken longer.
Cogito ergo Zorro. Sprechen sie das Donuts? Je parle Franglish. Que pasa, dude?
Cracking DES (Score:5, Interesting)
We also have a page about Cracking DES [eff.org]
Re:the real osu (Score:3, Funny)
(the real osu) is oklahoma state university, you barbaraous heathens
Yeah, if I were to trumpet Oklahoma State, I would post anonymously, too.
I remember that... (Score:2)
6969 bytes in body (Score:2)
Nerds and... (Score:5, Funny)
Hah! (Score:2, Funny)
We got quite a yelling at a while later, but we spiked our ranking up quite a bit that weekend, which was all that mattered. ;-)
Interesting... (Score:2)
Amusing, now go install Folding@home
Functional programming (Score:1)
Re:Functional programming (Score:1)
---
If nobody notices, it's not illegal.
Generated by SlashdotRndSig [snop.com] via GreaseMonkey [mozdev.org]
Botnets. (Score:3, Insightful)
Every time someone mentions brute-force attacks against encrypted data, all I can think of is the growing number of computers that part of remote controlled botnets [wikipedia.org].
I imagine that brute-force encryption attacks by anyone with a direct or indirect connection to a 20,000+ node net are alarmingly easy.
Re:Botnets. (Score:4, Informative)
Current standards such as 3-DES (triple-DES) and AES require a LOT more comuputing power than that to brute force.
I've taken the Cryptography course [iastate.edu] from Iowa State University [iastate.edu] so I have a bit of information on hand from my class notes...
The best known attack against 3-DES has a complexity of 2^113. Having 20,000 nodes is about 2^14 nodes. Heck, we'll assume 32,000 nodes. so 2^15. This still has a complexity of 2^98 for each machine to handle, or 2^42 more than DES. (2^43 if you consider the complementation property of DES which reduces the complexity of DES to 2^55.)
This means it woudl still be trillions of times longer than than it took to break DES, even if every machine could have performance equal to the custom DES cracker built. I don't know about you, but I don't have trillions of days to consider the problem.
AES is even tougher to crack than 3-DES, I'm not sure if there are any new attacks, but the key-space is 128, 196 or 256 bits. Even with the smallest key, 128 bits, this is thousands of times stronger than 3-DES. (2^128 vs. 2^113)
So relax, use the latest standards to encrypt your information, and for the love of the Flying Spaghetti Monster, don't use a key that is a regular word! The way ciphers are broken today is by trying a variety of dictionary words or sentences as the key. Just like a password, make your keys random, or random in appearance.
the message? (Score:1)
Re:the message? (Score:1, Funny)
A predecessor of DESCHALL (Score:5, Informative)
I was involved (VERY slightly) in an effort called the "Distributed Internet Crack" to brute-force the keyspace of 48-bit RC5 in February 1997.
The project was the brainchild of Germano Caronni, a member of the Swiss Federal Institute of Technology in Zuerich.
The Distributed Internet Crack would be an immediate predecessor to DESCHALL, which started only 8 days after DIC successfully cracked 48-bit RC5.
The possibility of cracking DES is mentioned in the Distributed Internet Crack FAQ: "Paul Foley estimates that DES would be approximately 70 times more difficult to solve than 48-bit RC5". DIC solved 48-bit RC5 in about 13.5 days whereas DESCHALL took about 120 days [privacy.nb.ca] (obviously with many more computers involved).
My impression at the time is that DIC and it's immediate predecessor, which involved much the same team and cracked 40-bit RC5 in 3.5 days, were among the first to use this sort of distributed computing (involving volunteered computer time, coordinated via the internet) on such a large scale. I'd be very interested in learning about any predecessors of these projects.
Reading over the FAQ for the Distributed Internet Crack is actually quite interesting after all these years. You can still see it here:
Also a press release on the project's successful conclusion:
Some quotes from the FAQ:
Solution: 74 a3 53 cc 0b 19
Time: from start of contest until Mon Feb 10 18:52:23 1997 (a little over 13 days)
Method: again, massive distributed coordinated keysearch
The Distributed Internet Crack is harnessing the power of thousands of computers over the internet to crack an encryption challenge offered by RSA Laboratories. The group first attacked the 40-bit RC5 Challenge, cracking it in about 3.5 hours
The Distributed Internet Crack broke new ground in several areas:
Re:A predecessor of DESCHALL (Score:3, Informative)
Sorry, the first major distributed computing project on the 'Net was the factoring of RSA-129 in 1993. Credit goes to Arjen Lenstra, Paul L
Re:A predecessor of DESCHALL (Score:1)
Brute Force does mention the context of the DESCHALL project. Predecessors are mentioned, as are some of the spinoffs and projects that followed. Page 42 mentions not only the 1993 factoring of RSA-129 but also its predecessor, the 1988 effort coordinated by Lenstra and Manasse. distributed.net actually started while DESCHALL was underway and it is mentioned at the appropriate point in the narrative, as well as the others like SETI@Home.
Many of the participants in the project who posted to the mailing l