Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Encryption Books Media Security Supercomputing The Internet Book Reviews

Brute Force 76

Posted by timothy from the gruntwork dept.
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.
This discussion has been archived. No new comments can be posted.

Brute Force More

Brute Force

Comments Filter:

  • For crying out loud... (Score:3, Funny)

    by luna69 ( 529007 ) * on Thursday September 08, 2005 @05:01PM (#13513516)
    > by an ad-hok distributed network

    Come one..."ad-hok?"

  • Distributed.net (Score:4, Informative)

    by Tiberius_Fel ( 770739 ) <fel.empirereborn@net> on Thursday September 08, 2005 @05:07PM (#13513566)
    For those interested in this sort of thing, http://www.distributed.net/ [distributed.net] runs like SETI@Home - lots of small individual clients working together to brute force encryption keys.
    • For those interested in this sort of thing, http://www.distributed.net/ [distributed.net] runs like SETI@Home - lots of small individual clients working together to brute force encryption keys.

      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)

        by Obfuscant ( 592200 )
        I mean, you can encrypt your golf scores. And some people do. Security is usually spent on the wrong areas, and not often enough on the areas that should be protected or encrypted.

        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

    • This is probably a stupid question, but why would lots of small individual clients want to crack encryption keys? (Other than stealing credit card info, etc?)
      • it's another contest hosted by RSA... it's like $10k again, nothing major... basically people do it for the stats [distributed.net] (it proves your technical manhood by having your name on the top 100 or whatever) I think most people understand that the contest being solved in an inevitability over time, and that their chances of actually winning money are extremely small, but it can be fun to race your friends in stats.

      • Re:Distributed.net (Score:3, Informative)

        by Duncan3 ( 10537 )
        To get the laws that said you had to use little keys changed.

        Back then, we couldn't even use encryption in web browsers. Try banking without that.

    • Completely Backwards (Score:3, Informative)

      by zealot ( 14660 )
      Actually, SETI@Home runs like http://www.distributed.net./ [www.distributed.net]

    • Re:Distributed.net (Score:3, Insightful)

      by Duncan3 ( 10537 )
      I think most everyone has moved on now. We did the key cracking, the laws got changed (which was a HUGE gain for the internet), and we won. Woohoo!

      Now things like protein folding have much more benefit to the world. Pick your projects carefully.
      • Mr. Beberg,

        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
        • *chuckles* anyone who has been around /. long enough to know about distributed.net knows I used to run it.

          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)

    by SquadBoy ( 167263 )
    At the ISP I was working for at the time we had this running on all the servers. It was very fun and the best part is that the CEO was in on the whole thing. Hard to find good places with a fun attitude these days. Damn shame.
  • Maybe the author will follow up with a dozen-page illustrated children's book about how CSS was cracked.

  • Matt... (Score:3, Informative)

    by LkDotCom ( 912073 ) * <lk@lastknig[ ]com ['ht.' in gap]> on Thursday September 08, 2005 @05:09PM (#13513574) Homepage
    Once again serving as the "missing bit in every /. editor" I'm proud to preseng (geeeeee!) something more about Matt.

    He is a very weird and amusing fella [interhack.net] ;)
  • it would have been if thay had used an ad-hoc network....

    It would have saved 1/6 of the keyspace.

  • T-shirts (Score:5, Interesting)

    by Leebert ( 1694 ) on Thursday September 08, 2005 @05:11PM (#13513596)
    I still have my DESCHALL t-shirt. As I recall, we spent more time arguing about what the t-shirt should look like AFTER the key was recovered than we spent recovering the key. :) Here were my thoughts on the subject [interhack.net] back then.
  • a 56-bit DES key was discovered, and its encrypted message decoded, by an ad-hok distributed network of computers, cooperating over the Internet

    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)

    by btempleton ( 149110 ) on Thursday September 08, 2005 @05:20PM (#13513664) Homepage
    You will also want to check out Cracking DES [cryptome.org] the story of our building the real DES cracker, the machine on its own that was able to crack DES in just a couple of days, demonstrating finally that DES was not secure.

    We also have a page about Cracking DES [eff.org]
  • It was the first distributed computing project I ever took part in, and as I was just setting up a lab full of then-screaming-fast P166 boxes, it seemed like a good way to test them out...
  • If everyone got their minds out of the gutter and started choosing decent key numbers I'm sure DES wouldn't be broken so quickly. ;-)

  • Nerds and... (Score:5, Funny)

    by MP3Chuck ( 652277 ) on Thursday September 08, 2005 @05:43PM (#13513800) Homepage Journal
    "Brute Force can be enjoyed by both nerds and non-nerds interested in cryptography or codes." So ... nerds. ;)

  • Hah! (Score:2, Funny)

    by unsigned integer ( 721338 )
    I remember this. My local ACM and I did 'bad things' during the Thanksgiving weekend when everyone left. We organized our groups, and went computer to computer launching client after client in almost every computer lab on campus.

    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. ;-)

  • How did you manage to get though that whole review without mentioning the distributed.net or the EFF, who also cracked DES. Yet you metion SETI@home many times which was started years after DESCHALL, EFF, and distributed.net, but has little resemblance to any of them.

    Amusing, now go install Folding@home :)
  • Why is the text "functional programming" linked to the Slashdot front page in the review?

  • Botnets. (Score:3, Insightful)

    by kiddailey ( 165202 ) on Thursday September 08, 2005 @06:54PM (#13514231) Homepage

    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)

      by Bender0x7D1 ( 536254 ) on Friday September 09, 2005 @11:05AM (#13519484)
      You can relax. There isn't a serious danger.

      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.
  • So what was the message that was decoded?

  • A predecessor of DESCHALL (Score:5, Informative)

    by flug ( 589009 ) on Thursday September 08, 2005 @07:29PM (#13514515)
    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?

    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:

    Press Release [herald.co.uk]

    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:

    • The most machines ever working together on a single, public, project: over 5000 at once, at probably over 10,000 altogether (machines often drop in and out over the course of the crack).
    • The most keys per second ever solved in a public project: 440 million keys per second at peak, 140 million keys per second over the course of the project.

    • 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.

      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

      • 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

Slashdot Top Deals

Hotels are tired of getting ripped off. I checked into a hotel and they had towels from my house. -- Mark Guido

Close