crypt(1) -- how secure, how breakable?

[Henry Spencer]

A little while ago I asked about the security of crypt(1).  It seems
that nobody has heard of any scheme for rating security based on minutes
of cpu time on a Cray to break, which doesn't surprise me; the idea came
from my friend, and seemed hair-brained to me too.  The more general
issue of crypt(1) security inspired more comments; here is a summary.
Thanks to all the folks who replied.

Bob Morris Sr. and Peter Weinberger have broken crypt(1), and the "Unix
Revisited" issue of the BLTJ (formerly BSTJ), due out any time now, will
include a paper on the subject.  Apparently they can break not only
crypt(1), but any plausible stronger version of it.  A friend from
Bell Labs says, in part, "I wouldn't use ANY rotor scheme to keep a
secret; Morris can almost certainly decrypt them all..."

Another friend, who definitely knows more than he is allowed to discuss
about cryptanalysis in general, comments:  "My estimate of a one-rotor
system is that a good cryppy armed with appropriate computer tools could
break a moderate-sized message in a matter of minutes.  A five-rotor system
might take hours (on a VAX)."

The general conclusion, overall, was that crypt(1) probably will not
stop a knowledgeable person seriously bent on breaking it, especially
if it's Bob Morris or the boys from the NSA.  As usual, you get what you
pay for; DES will do a rather better job, but is much slower unless you
have hardware assistance.

My personal assessment is that crypt(1), used judiciously [any encryption
system will be more secure if you (a) use a different key for each file,
(b) keep the files short, and (c) use long keys], is probably good enough
to keep casual snoopers out, but you shouldn't rely on it for something
that *really* needs to stay secret unless your system is running with a
fairly friendly user community.  I suspect that a cracker would need
either substantial knowledge and motivation, or access to existing breaking
software, but my opinion of this might get revised downwards after I see
the BLTJ paper.

Some further comments (mostly references), verbatim:

-----
About 4 or 5 yrs ago Bob Morris had a paper in Cryptologia
describing how to break the M-209 machine (the `most modern' Hagelin
machine.)
-----
Open literature... see Cryptologia Volume 6, Number 1, January 1982 - the
special issue devoted to Enigma.  That explains how the Poles broke Enigma.
The new Turing biography explains how computational analysis was used by the
English to exploit the cryptographic analysis.
-----
Rotor machines in general: try 1977 cryptologia for several articles, also
IEEE Info Theory Transactions, July 1982..  Of course the ill fated Enigma
was a rotor  machine, see G. Welchman's Hut 6 Story for details.  For the
UNIX crypt command  see october 1984 ish of (what used to be) Bell System
Technical Journal.
-----
Konheim, Alan G.  Cryptography: A Primer, Wiley, 1981
	Chapter V is devoted to the cryptanalysis of rotor machine systems.
	Konheim's treatment is mathematically rigorous, and I've heard it
	said that in general there are heuristic shortcuts he does not
	employ which make the problems he considers easier to solve than
	by using his tortuous methods.
-----
Another detailed description of the Polish attack is contained in:
	Intercept: The Enigma War
	Jozef Garlinski
	Magnum Books, 1979
	(especially the Appendix)
-----
One of the more accessible references is a book by Wayne G. Barker,
_Cryptanalysis of the Hagelin Cryptograph_, $24.80 from Aegean Park
Press, P.O. Box 2837, Laguna Hills, CA 92654.  Thought I had a copy
of it here, but I don't see it.

[I think Aegean Park Press is also the publisher of Cryptologia. -- HS]

The Barker book starts out with simpler machines and works up to the
multi-rotor Enigma, if memory serves.

I once saw a copy of the manual page for crypt(1) at an anonymous DOD
agency ... under BUGS at the bottom was "Uses a Hagelin encryption
algorithm."  I was amused...

There's a measure called the Hellman Time-Memory Trade-off, described in M.
Hellman 1980, A Cryptanalytic Time-Memory Trade-Off, _IEEE Transactions on
Information Theory_ 26: 401-406.  This reference is from _Cryptologia_,
v6#2, April 82, "The performance of Hellman's time-memory trade-off against
some rotor ciphers", by Elliot Fischer.  Fischer presents some results for
a couple of Hebern rotor machines.  Fischer has published several other
papers on different measures of security.
-----
The only rating scheme that I can discuss for the relative strengths
of encryption systems is "unicity distance", which is the guaranteed
minimum length of contiguous ciphertext that one must have to have
a better-than-50% chance of breaking it with the theoretically best
tools possible.  Computation of unicity distance depends on the details
of the encryption scheme.

[My recollection is that there is a good introduction to unicity distance
in the *unabridged*, i.e. hardcover, edition of Kahn's "The Codebreakers".
Some of the other references people have pointed to will probably contain
more rigorous treatments.  -- HS]
-----
-- 
				Henry Spencer @ U of Toronto Zoology
				{allegra,ihnp4,linus,decvax}!utzoo!henry