(fwd) DES challenge organisation
An announcement forwarded to me (due to being on des-challenge mailing list I think) of proposed organisation for breaking RSADSI's DES challenge. Those interested in participating might wish to join the lists mentioned. In addition the list: des-challenge@muffin.org is for discussion of the DES challenge, and can be subscribed to by sending email to majordomo@muffin.org. -Adam ====================================================================== Subject: Announcement: Organisation Committee From: ths@rz.tu-ilmenau.de (Thomas S.) Date: 15 Feb 1997 18:27:40 +0000 Hi! The six volunteers who answered the call for a committee of management have got together to try to help 'steer' the DES challenge. We have considered the available options of proceeding, and we kindly ask everyone interested in this project to follow our proposals, to avoid waste of efforts. 1. The attempt to break the key will be coordinated. We chose this mainly because we can make a political statement. We don't want it to be a race for money. Each task will be handled by logically separate servers, some of which with be replicated and run as a hierachy. The protocol will use UDP, although there will be gateway servers for other protocols (such as HTTP, SMTP, FAX, etc). We hope that one of the first requests for a key range will be from parties interested in using a "random" approach -- we would appreciate some discussion on how large their ranges should be. 2. There will be one consistent WWW structure for the project. It does not have to managed by a single person. This structure should provide statistics, information for developers, interested users and perhaps even for the press. Several mirrors and translations will be started soon. The starting point is: http://www.des.crypto.org/ [fh28.fa.umist.ac.uk/des/] The url in brackets has to be used till we get the final subdomain. Likewise for the rest of this document. 3. The work of the different groups should be stated and coordinated on the page http://www.des.crypto.org/people.html. [fh28.fa.umist.ac.uk/des/people.html] This is to avoid uncoordinated parallel developmemt. Please write to Thomas S. <webmaster@mail.des.crypto.org> [webmaster@fh28.fa.umist.ac.uk] if you what want to be mentioned on this page. 3a. Several mailing lists have been set up for the different groups: des-coding for the actual DES routine and optimisation des-networking for the network code and protocol des-www for www contributions and mirrors des-pr for press contact, translations etc (like challenge-pr) des-misc :-) des-announce moderated, important information for users of the client List address: <list>@lists.des.crypto.org [@xtn.net] To subscribe, send mail to majordomo@lists.des.crypto.org [@xtn.net] with in the body of the message (several actions allowed): subscribe <list> Achives available (see homepage). 4. The actual DES routine has to be written and optimised. We ask developers to participate and coordinate their efforts using the mailing list des-coding. For obvious reasons, developers outside the USA are prefered, but "publication" of algorithms seems to be a legal way go get around. Please do not use this list to distribute crypto code. 5. The prize money will be split equally between Gutenberg and EFF. There is a possibility of using part of it for stickers or something similar, but don't count on it. We hope to get a working system up and running ASAP. The fact alone that DES is seriously challenged (with a reasonable time frame) should give us quite some publicity (by the time the system is ready). If we can make use of that, we will have significantly more client than for the 48 bit key. The organisation committee: Piete Brooks <Piete.Brooks@cl.cam.ac.uk> Jered Floyd <jered@mit.edu> Tim Newsome <drz@froody.bloke.com> Germano Caronni <caronni@tik.ee.ethz.ch> Thomas Roessler <Thomas.Roessler@sobolev.rhein.de> Thomas S. <ths@fh28.fa.umist.ac.uk>
Thomas S <ths@fh28.fa.umist.ac.uk> writes:
[...]
5. The prize money will be split equally between Gutenberg and EFF. There is a possibility of using part of it for stickers or something similar, but don't count on it.
Not a good idea. How can this be enforced? The RSADSI DES challenge is open to all comers, and how do you prove that someone who finds the key found it through this group effort? I have a suspicion many people would be tempted to fill in the RSA challenge form and email it in themselves. $10,000 is a fair amount of money. I know I would be tempted. I have been running Svend Olaf's DES code, and my intention in the unlikely event that I hit the key had been to claim the money. How does it hurt the publicity if the actual individual who finds the key takes the money? Surely it adds excitement to the story? In fact it would provide people with a possibly more powerful incentive to try to break the key in the first place -- in the hopes of winning the prize! $10,000 means more to a lot of people than opposing ITAR/EAR, and participating in a technical challenge. To start with a lot of people who's CPUs we could be using don't even know what ITAR/EAR are!
We hope to get a working system up and running ASAP. The fact alone that DES is seriously challenged (with a reasonable time frame) should give us quite some publicity (by the time the system is ready). If we can make use of that, we will have significantly more client than for the 48 bit key.
I would have thought announcing that $10,000 can be won by running easy to use windows software on a wide selection of newsgroups would get you lots of CPUs! Adam -- print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<> )]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`
-----BEGIN PGP SIGNED MESSAGE----- On Sat, 15 Feb 1997, Adam Back wrote:
5. The prize money will be split equally between Gutenberg and EFF. There is a possibility of using part of it for stickers or something similar, but don't count on it.
Not a good idea.
How can this be enforced? The RSADSI DES challenge is open to all
Unless people modify the client, we will know about it before they do. Yes, people might cheat. Main point is we don't want to turn this into a race for money. (Also, that way we can't use university machines etc.) This topic has been discussed too often also. Read the archives for more debate. Tim Tim Newsome. Programmer for Megasoft. Student at CMU. Cynic in life. Intel sucks. Motorola forever! If it's not PGP signed, it didn't come from me. Always look on the bright side of life. I think I think therefore I think I am. drz@froody.bloke.com http://www.local.com/~tnewsom/ PGP key: 2048/C32F01A5 -----BEGIN PGP SIGNATURE----- Version: 2.6.3a Charset: noconv Comment: In God we trust. Everybody else we verify using PGP! iQEVAwUBMwh34PKkXTDDLwGlAQE/KggAmWk9rL86fknnXWy9ASPWQokH6J0vEzW+ qhrBklXwv0Lz5HGNV92OM0qh9KI+bqFct9aNY0B15g6APspSUNYr7RaXI2/LaSYb 0gG7YpPe2kHFdSWsodhYyu7DTzYvdDI1AJOmEnSUKHQPKiLwU/RgVZiLEttuvIcS GCjDEGEW7C0YIrQKTkLoYKkSHz6HHXQ+/hr66yCBMD7AIS1C/p9yN2ticmQ3hLnd DYSpVQb9NudLcU0bGZC1U31o70hSVmyETTt9VcuJCOXseiggWTZsZuNK/D+f5TfA WBEcIAWToBHfrWSokuF9nunAarmcddQyPu/93hzRkgODVTWgmnpOGA== =IuAs -----END PGP SIGNATURE-----
At 11:02 PM +0000 2/15/97, Adam Back wrote:
Thomas S <ths@fh28.fa.umist.ac.uk> writes:
[...]
5. The prize money will be split equally between Gutenberg and EFF. There is a possibility of using part of it for stickers or something similar, but don't count on it.
Not a good idea.
How can this be enforced? The RSADSI DES challenge is open to all comers, and how do you prove that someone who finds the key found it through this group effort?
I have a suspicion many people would be tempted to fill in the RSA challenge form and email it in themselves. $10,000 is a fair amount of money.
Once again, the advantages of an "uncoordinated search" should be mentioned. An uncoordinated search, in which people randomly search chunks of keyspace is obviously less efficient than a coordinated search where no part of the space is searched two or more times. However, an uncoordinated search is only less efficient by a small factor of two or three, with a 95% probability that the key will be found with an effort "only" 3 times greater than with a coordinated search. (The Poisson probability distribution is what's involved here, and the math is fairly easy to work out.) A 2-4x factor is significant, and may warrant a coordinated search. However, the various problems implicit in coordinated searches are factors, too. Also, an uncoordinated search solves the "prize" problem, as whomever finds the key makes the contact with RSADSI. One of the problems with a coordinated search, if the remaining keyspace to be doled out is publically announced, is that as the keyspace is searched and a key _not_ found, the remaining keyspace is increasingly more tempting for "independent searchers" to search. Sort of the way the odds on some lotteries actually become "acceptable" as the lottery pot grows. The organizer of the coordinated search must then, I surmise, keep the assignments secret and dole out keyspace securely. Having the prize money go to the finder of the key, as opposed to some artificial division between EFF, Gutenberg, etc., is also an incentive for people to contribute more CPU time. --Tim May
I know I would be tempted. I have been running Svend Olaf's DES code, and my intention in the unlikely event that I hit the key had been to claim the money.
How does it hurt the publicity if the actual individual who finds the key takes the money? Surely it adds excitement to the story?
In fact it would provide people with a possibly more powerful incentive to try to break the key in the first place -- in the hopes of winning the prize! $10,000 means more to a lot of people than opposing ITAR/EAR, and participating in a technical challenge. To start with a lot of people who's CPUs we could be using don't even know what ITAR/EAR are!
We hope to get a working system up and running ASAP. The fact alone that DES is seriously challenged (with a reasonable time frame) should give us quite some publicity (by the time the system is ready). If we can make use of that, we will have significantly more client than for the 48 bit key.
I would have thought announcing that $10,000 can be won by running easy to use windows software on a wide selection of newsgroups would get you lots of CPUs!
Adam -- print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<> )]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`
Just say "No" to "Big Brother Inside" We got computers, we're tapping phone lines, I know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^1398269 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."
Timothy C. May wrote:
The organizer of the coordinated search must then, I surmise, keep the assignments secret and dole out keyspace securely.
Perhaps they should DES-encrypt the list of assignments :-) - mark -------------------------------------------------------------------- I tried an internal modem, newton@dotat.org but it hurt when I walked. Mark Newton ----- Voice: +61-4-1155-2401 ------------- Fax: +61-8-83732527 -----
Adam Back <aba@dcs.ex.ac.uk> writes:
How can this be enforced? The RSADSI DES challenge is open to all comers, and how do you prove that someone who finds the key found it through this group effort?
I have a suspicion many people would be tempted to fill in the RSA challenge form and email it in themselves. $10,000 is a fair amount of money.
Of course they will. If the unsearched portions of the keyspace are published, you can just sit back until the odds go up and then throw some CPU power at it. There is no obligation on the part of the individual who finds the key to not claim the prize personally. The issues of random keyspace assignment to protect against sabotage and centralized monolithic server vs autonomous client have been debated on the "muffin" list, where I have been lurking, but the people in charge seem to like explicit keyspace partitioning and servers a lot. Should be an interesting effort. By the way, does anyone know if des-challenge@muffin.org is alive? I haven't seen any messages from it in over a day and majordomo is not responding to inquiries. -- Mike Duvos $ PGP 2.6 Public Key available $ mpd@netcom.com $ via Finger. $
On Feb 15, 5:01pm, Timothy C. May wrote:
Subject: Re: (fwd) DES challenge organisation However, an uncoordinated search is only less efficient by a small factor of two or three, with a 95% probability that the key will be found with an effort "only" 3 times greater than with a coordinated search. (The Poisson probability distribution is what's involved here, and the math is fairly easy to work out.)
The motivation to crack the DES challenge is more the political one of proving DES (aka 56 bit encryption in the popular press) insecure than the financial one of getting the $10,000 prize. To actually get a good mesaure of the strength of DES using this approach, the number of machines that participated in the attack and the time they spend has to be known. This is a main reason why Germano's team prefers the search to be co-ordinated and why they have been asking people not to start the search before the server is ready.
One of the problems with a coordinated search, if the remaining keyspace to be doled out is publically announced, is that as the keyspace is searched and a key _not_ found, the remaining keyspace is increasingly more tempting for "independent searchers" to search. Sort of the way the odds on some lotteries actually become "acceptable" as the lottery pot grows. The organizer of the coordinated search must then, I surmise, keep the assignments secret and dole out keyspace securely.
Knowing the number of people they were able to get to participate in the RC5 attack, this is not a significant problem. They are going to have 5000 clients nibbling away on the not-yet-searched keyspace. Some Johnny-come-lately trying to muscle in on the action towards the end is not going to make a significant dent in their chances of hitting the correcy key first.
Having the prize money go to the finder of the key, as opposed to some artificial division between EFF, Gutenberg, etc., is also an incentive for people to contribute more CPU time.
Again, they didn't have a problem getting people to join in on the RC5/32/12/6 attack. At least the same number of people can be expected to join in for the DES attack, giving an estimated search time of around eight months, if nobody else builds a hardware DES cracker first. -- Anil Das
Hi! (wow, what a distribution. I should mention that des-challenge is down this weekend, so the response may not be as expected.)
"Timothy" == Timothy C May <tcmay@got.net> writes:
Timothy> At 11:02 PM +0000 2/15/97, Adam Back wrote: >> Thomas S <ths@fh28.fa.umist.ac.uk> writes: >>> [...] >>> >>> 5. The prize money will be split equally between Gutenberg and >>> EFF. There is a possibility of using part of it for stickers >>> or something similar, but don't count on it. >> Not a good idea. >> >> How can this be enforced? The RSADSI DES challenge is open to >> all comers, and how do you prove that someone who finds the key >> found it through this group effort? The client reports the key to the server, not to the user (very simple, and very simple ways to get around of course). In a nutshell: we can't enforce it, at least I can't see a way to do so. We certainly can't keep people from doing their own "treasure hunt". ... Timothy> A 2-4x factor is significant, and may warrant a Timothy> coordinated search. However, the various problems Timothy> implicit in coordinated searches are factors, too. Timothy> Also, an uncoordinated search solves the "prize" problem, Timothy> as whomever finds the key makes the contact with RSADSI. Indeed--that's what we try to avoid. Our project is not a race for money, it is a demonstration with a political impact. The main point in favour of a coordinated search is the availability of progress reports. Nobody can argue that the key was found by chance--as there is exact data about performance and the expected maximum duration for the search. Timothy> One of the problems with a coordinated search, if the Timothy> remaining keyspace to be doled out is publically Timothy> announced, is that as the keyspace is searched and a key Timothy> _not_ found, the remaining keyspace is increasingly more Timothy> tempting for "independent searchers" to search. Sort of Timothy> the way the odds on some lotteries actually become Timothy> "acceptable" as the lottery pot grows. The organizer of Timothy> the coordinated search must then, I surmise, keep the Timothy> assignments secret and dole out keyspace securely. This is a technical problem which is discussed at the moment. The keyspace will not be publically announced (and it wasn't during the last project). Thomas -- OOOO, OOOOOOOO, |, ths@rz.tu-ilmenau.de OO, OO, O, O, |, http://www.rz.tu-ilmenau.de/~ths/ O, O, O, |, ______ __ ___ O, O--O, O, O, |, | (_ |-|-` O, O, O, |, |homas __)te| |en OO, OO, O, O, |, OOOO, OOOOOOOO, |, not to be forwarded without permission
participants (7)
-
Adam Back -
das＠razor.engr.sgi.com -
Mark Newton -
mpd＠netcom.com -
ths＠rz.tu-ilmenau.de -
Tim Newsome -
Timothy C. May