henry@utzoo.UUCP (Henry Spencer) (09/20/84)
A friend has asked a couple of questions about the security of crypt(1)
that I wasn't able to answer. I know that crypt(1) has been broken,
although the software for it is not generally available and is not
trivial to use, but he's interested in some specific information for
a customer. In particular...
(1) Are there any papers in the open literature discussing
the security/breakability of rotor machines? I had a
vague memory that Cryptologia has published something
like this once, but don't have specifics.
(2) Apparently there is some sort of rating scheme for encryption
systems, based on estimated breaking time on a Cray or
something like that. Or so he thought. Has anyone ever
rated the crypt(1) algorithm on such a scale?
Please reply by mail; I will summarize results for the net.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henryhenry@utzoo.UUCP (Henry Spencer) (10/01/84)
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!henryhenry@utzoo.UUCP (Henry Spencer) (10/15/84)
Several people have written with additions and corrections to my
original posting about crypt(1). The big one is that Jim Reeds, who
wasn't mentioned in my article at all, was the Bell Labs man who
broke crypt. Bob Morris Sr. and Peter Weinberger were involved, but
in lesser ways. Oops. My info did come from within Bell Labs; I guess
my informant simply had it wrong. My apologies to Jim, who was one of
the folks who wrote to me and whose comments I draw on heavily in the
following.
The Bell folks do not think that they can break all possible improved
forms of crypt, although they have broken one or two.
Morris's Cryptologia paper describing how to break the M-209 required
known plaintext, and the M-209 definitely is not the "most modern"
Hagelin machine. Furthermore, V7 crypt(1) is not a Hagelin algorithm
at all, so it's irrelevant. [Blush. I'm not a serious cryptology fan
myself, but I should have remembered *that*!]
Aegean Park Press is no longer the publisher of Cryptologia, although
it used to be.
The Barker book does not work up to full rotor machines, it works up to
a full Hagelin M-209. As mentioned above, there is no relation.
Jim Reeds is doubtful about the suggestion of a multi-rotor machine being
breakable in a few hours; he thinks he can make a small multi-rotor
machine that is nearly unbreakable. This disagreement probably cannot
be resolved in a public forum, since my source for the original comment
probably isn't allowed to elaborate.
Reeds also points out that the chances of your security being breached by
cryptanalysis are much lower than the chances of penetration via superuser
access (legitimate or as a result of a security breach). The knowledge
and skills needed for the latter approach are much more widely available.
There is general agreement about my overall summation: crypt(1) is
probably adequate protection against snoopers, unless you have snoopers
who are sophisticated cryptanalysts or have access to sophisticated
cryptanalytic software. Bear in mind my earlier comments: short files,
each encrypted with a different key, will make the breaker's job harder.
The desirability of long keys is less clear; crypt(1) does chop the keys
at 8 characters, and Jim Reeds says that key length is not really very
significant, but note that very short keys are subject to breaking by
exhaustive search.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henryhenry@utzoo.UUCP (Henry Spencer) (11/07/84)
A friend has pointed out another aspect of using crypt(1) for file
security: decrypting a file, editing it slightly, and then re-encrypting
it WITH THE SAME KEY probably makes life significantly easier for someone
trying to break the encryption. The tail end of your file is probably
the same before and after, and you're giving the snooper a look at the
same text encrypted with two different parts of crypt(1)'s "key stream".
This may be quite revealing, although the exact extent of the security
reduction isn't immediately obvious.
He also points out that if you re-encrypt with a DIFFERENT key, you are
giving the cracker a look at the same text (the beginning of the file)
encrypted with two different keys. Seems to me that this is less of a
problem, although I don't know enough about the details to be certain.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henry