🚀 go-pugleaf

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