Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!utgpu!water!watmath!clyde!rutgers!seismo!mimsy!eneevax!umd5!brl-adm!brl-smoke!gwyn From: gwyn@brl-smoke.UUCP Newsgroups: sci.crypt Subject: Re: DES info wanted Message-ID: <5845@brl-smoke.ARPA> Date: Fri, 8-May-87 03:17:13 EDT Article-I.D.: brl-smok.5845 Posted: Fri May 8 03:17:13 1987 Date-Received: Sat, 9-May-87 08:13:51 EDT References: <2071@hoptoad.uucp> <599@umnd-cs.D.UMN.EDU> <18742@ucbvax.BERKELEY.EDU> <5841@brl-smoke.ARPA> <18771@ucbvax.BERKELEY.EDU> Reply-To: gwyn@brl.arpa (Doug Gwyn (VLD/VMB) ) Distribution: world Organization: Ballistic Research Lab (BRL), APG, MD. Lines: 58 Keywords: DES In article <18771@ucbvax.BERKELEY.EDU> rotondo@ernie.Berkeley.EDU.UUCP (Scott Rotondo) writes: >... However, actually >doing the computation seems to require an exhaustive search of 2^55 >keys (not 2^56 because of a known symmetry in the S-boxes). Let me assure you that cryptanalysts virtually never search a space anywhere near that large. Rather, they exploit algebraic structure of the encipherment system, using a variety of techniques. One rather puny, although publicly-known, example goes by the name "indirect symmetry of position"; it's described in Kahn (unabridged). I once implemented this on a computer and watched messages "unravel". For more modern systems including DES, one would use much more sophisticated algebraic methods than that, but until I find public references I can't disclose even the limited amount I know about this. I don't want to give the impression that cryptanalysis involves merely solving exact equations, however. A barrage of statistical tests are in general performed to steer the analysis into the most productive directions; you can think of this as favoring certain branches of the search tree of possibilities. One of the best public introductions to this area that I know of is the quite old technical paper (more like a book) by Solomon Kullback entitled "Statistical Methods in Cryptanalysis". It was published by the War Department in 1938 (revised edition) and was originally Confidential, later Restricted, now declassified via automatic downgrading rules. I don't know a source for this, but Aegean Press might be one. (I'm getting their book list soon; they have at least some older editions of Mil Cryp for sale.) Certainly there has been a lot of progress in this area since then.. >Does "sufficient cleverness or dumb luck" mean finding a way to factor >large numbers or something else? "Sufficient cleverness" was mostly an oblique reference to the widely- held idea that one would have to factor the product of two large primes to crack a public-key system. Some people have maintained that any algorithm for cracking such a system amounts to an algorithm for the factorization, but I haven't been convinced that this conclusion is warranted. "Dumb luck" means any of a variety of ways a system could be cracked besides exploiting a clever analytic algorithm. Practical cryptanalysis of difficult systems often involves looking for easy wedges into the messages; examples from older systems include finding isomorphs (same message encrypted twice under different keys, sometimes different systems), crib dragging (guessing at the presence of probably plaintext phrases and trying to lever open the key under the assumption that the phrase occurs at a particular location), looking for hardware malfunctions (stuck shift registers, for example), and so forth. These methods, while tedious (unless computers are used), are far, far less work than any brute force approach such as trying all possible keys. Sometimes they pay off and sometimes they don't; when luck is with the analyst, nominally-secure traffic can be read. As you can undoubtedly tell, I find the amount of ingenuity that can be applied to cryptanalysis quite fascinating. I think this would be a wondeful subject for a college curriculum, although the number of potential employers for cryppies isn't very large yet. (It's growing as attention focuses on commercial data transmission.)