As some of you may have noticed, a new attempt to crack the Data Encryption Standard has been started, with a descriptive FAQ located at the following URL http://www.cyberspace.org/~enoch/crakfaq.html A while back, after the first DES challenge was announced, a number of us made the observation that a known plaintext attack on DES, expressed as a system of a few thousand boolean variables with constraints in 3-conjunctive normal form, was not too far from the size and complexity of problems that could be directly solved by bleeding edge combinatorial algorithms, albeit with signficant CPU and memory consumption. We thought this would be an interesting result, and generated a number of problems of various numbers of DES rounds based on the DES Challenge data, and some not particularly optimized S-Box representations, and set about the task of solving them, smaller problems first. We wrote a lot of code, learned a lot about arbitrary systems of boolean variables, and after breaking 2-round and 4-round problems, the first almost instantly, and the second with very reasonable amounts of resources, set about the task of seeing if we could break the higher round problems, and immortalize ourselves by beating DESCHALL to the key. To our very great regret, we did not manage to do this, and once the $10k prize was claimed, we figured the game was over and returned to working on other things. We still thought DES was a problem of approximately the right size to demonstrate the existence of an analytical solution which would beat a well-tuned exhaustive search on a problem of practical interest. Since that time, DES has been broken twice more by exhaustive search, once by distributed.net, and again by a hardware DES cracking machine designed by Net legend John Gilmore and the EFF for a non-trivial amount of money. Remarkably, although most agree DES is dead for new applications, with Moore's Law and additional hardware crackers being possible today for much less than the cost of the prototype, it still seems to enjoy a reputation amongst the public as a cipher that takes 20,000 pentiums running for half a month or a hardware box with $100k of chips running for several days to break, neither of which seems to have thrown the Fear of God into its current users, most notably the Banking Industry. With other analytic attacks like differential and linear cryptanalysis being really practical only for reduced round DES, and all current high-profile cracks on production ciphers employing key trial, the press has latched onto keysize as a synonym for strength, and has made numerous statements which have reinforced this questionable paradigm in the minds of the public. We have therefore been taking another look at our idea of a combinatorial crack of DES, and decided that even with DES having been cracked three times by key trial, it is definitely a project worth doing. This time, rather than working frantically in an unsuccessful attempt to beat other teams on a public challenge, we wish to finish up our original efforts, and repeat the three cracks previously done, this time using our algorithms, and distribute working code continuously as the project progresses, to sponsors who have donated some money to defray our costs. This will offer people the opportunity to participate vicariously in a fun project which has the potential to be a genuine paradigm shift in the way the world thinks about codebreaking. Sometimes, promising areas of research are not followed because of knowlege of some well-known result which suggests that such exploration will be unfruitful. Years ago, for instance, suggestions that programs could be checked by software for proper behavior, and run without using protected memory regions, were usually met with snide comments about the "computer halting problem" and various adjunct results. Today, there are many variants of "safe execution" technology, from prove and carry schemes, to Java bytecode, with a sound theoretical basis behind them. None of these is a violation of the "computer halting problem" results, of course. Similarly, after a large burst of activity decades ago, which resulted in the notion of NP-Completeness, and various results in computational complexity theory, suggestions that an analytic solution exists for some large combinatorial problem of practical interest conjure up visions of exponential resource utilization, speaker cluenessless, and the lack of progress on NP=P. For this reason, we feel this project is definitely a Schnelling Point. If it works, even badly, people will begin to look at lots of problems in ways they would not have considered before, and much new code which improves upon what we have done will be created. This will be an irreversible change in the Order of Things. In the several days since we put up our FAQ, we have gotten quite a few comments, and some concerns. The comments have mostly been along the lines that it is an interesting, even intriguing project. The concerns are generally that we will experience an unexpected "combinatoric explosion" in the higher round problems, and that no one in their right mind would send money to a nym, because it might just vanish and be used by the nym to live in perpetual ecstasy in some place warm and tropical, without the possiblility of the nym being sued for fraud. While we hope the close coupling between the sponsors and the project members will eliminate this latter concern, with weekly progress reports and working code being distributed to permit the sponsors to reproduce our results as they occur. If three people are willing to sponsor and give us the go-ahead to begin, without wanting their money back if other sponsors do not join, we can probably get through the minimal S-Box representations and their proof-of-correctness as well as some cleaned up code for the 2-round problem. Hopefully we will then have a reputation with these people which will encourage others to join in the effort. Clearly, we're after speculative capital, rather than widow and orphan money, and hope a few of the wealthy older retired (and perhaps even crusty) engineer types might find this a productive thing to support. After all, if you've just blown $220,000 on a DES Cracker, making it $220,500 and getting your very own Schnelling Point in return is probably a reasonable amount of fun for your money. I'll stop ranting now. :) -- Sponsor the DES Analytic Crack Project http://www.cyberspace.org/~enoch/crakfaq.html