🚀 go-pugleaf

lwloen@vnet.ibm.com,
  in article <1992Oct13.183131.16614@rchland.ibm.com> writes:
> "temporary, independent" sci.crypt Frequently Asked Questions

I'm also looking forward to the new FAQ.  Thanks for your version.  For
those who missed it, here's a FAQ that was posted last year.


From: cme@ellisun.sw.stratus.com (Carl Ellison)
Newsgroups: sci.crypt
Subject: FAQ for sci.crypt -- for review
Date: 14 Nov 91 16:41:18 GMT
Organization: Stratus Computer, Inc.
Lines: 609

[The following FAQ file was prepared by 3 of us, based on long reading
of sci.crypt and our own sources.  Before posting this to
news.answers, I thought I would post it here alone -- to gather
comments.  One of my own, so far, is that the initial book list is
probably too long for the rank beginner.  Comments?  --cme ]

============================================================================

				  sci.crypt
			  Frequently Asked Questions
		     with answers by readers of sci.crypt
		 (and subjects which have been beaten to death)

 Compiled by:
	cme@ellisun.sw.stratus.com (Carl Ellison)
	Gwyn@BRL.MIL (Doug Gwyn)
	smb@ulysses.att.com (Steven Bellovin)

o What books can I start with to learn cryptology?
o I forgot my WordPerfect password.  Can I still read the file?
o Breaking Repeated XOR Encryption
o Has DES been broken?
o Differential cryptanalysis
o Did NSA weaken DES (eg., with the 56 bit key)?
o Is Lucifer stronger than DES (longer key)?
o Did NSA put a trap door into DES's S-boxes?
o Did NSA or IBM design the S-boxes?
o NSA's capabilities.
o Is NSA more capable than the public cryptography researchers?
o Why is there structure in the S-boxes?
o Is DES a group?
o Is RSA patented?
o Should it be?
o How do I send encrypted mail?
o Can I use the UNIX crypt command?
o If I first do perfect compression, ....?
o Is there an unbreakable cipher?
o What does "random" mean?
o Is the USA really so stupid as to believe it can restrict export of
  PD encryption software?
o What are the US export regulations?
o Here's the ciphertext from my new algorithm.  Try to break it.  OK,
  that was good, so I'll change it this way.  Now try to break it.
o What is the unicity point (a.k.a. unicity distance)?
o What is "brute force search" and what is its cryptographic relevance?
o How does one determine the strength of a proposed cryptosystem?
o How does one go about cryptanalysis?
o If a cryptosystem is theoretically unbreakable, does that mean that it
  is guaranteed analysis-proof in practice?
o Why are many people still using cryptosystems that are relatively
  easy to break?
o What is key management and why is it important?
o WWII German ENIGMA
o What is TEMPEST?
o Fractal Cryptography
o Chaos Cryptography
o Linear Congruential Pseudo-random Numbers as a Key Stream
o What are MD4 and MD5?


o What books can I start with to learn cryptology?

  Books:

    David Kahn, The Codebreakers, Macmillan, 1967 [history] [The
    abridged paperback edition left out most technical details; the
    original hardcover edition is recommended.]

    H. F. Gaines, Cryptanalysis, Dover, 1956 (originally 1939, as
    Elementary Cryptanalysis)

    Abraham Sinkov, Elementary Cryptanalysis, Math. Assoc. of Amer.,
    1966

    D Denning, Cryptography and Data Security, Addison-Wesley, 1983

    Henry Beker & Fred Piper, Cipher Systems -- The Protection of
    Communications, Wiley-Interscience, 1982

    Wayne Patterson, Mathematical Cryptology for Computer Scientists and
    Mathematicians, Rowman & Littlefield, 1987

    Alan G. Konheim, Cryptography:  A Primer, Wiley-Interscience, 1981

    Davies and Price, Security for Computer Networks, John Wiley & Sons,
    1989, Second Edition.

    Meyer and Matyas, Cryptography:  A New Dimension in Computer Data
    Security, John Wiley & Sons, 1982.

    Publications from the Aegean Park Press P.O. Box 2837, Laguna
    Hills, CA 92654-0837 [especially the volumes of Lambros D.
    Callimahos & William F. Friedman's "Military Cryptanalytics" for
    cryptanalysis; for history, Herbert O. Yardley's "The American
    Black Chamber" and William F. Friedman's "Solving German Codes in
    World War I"]

  Journals:

    Journal of Cryptology; International Association for Cryptologic
    Research; published by Springer Verlag (quarterly since 1988).

    IEEE Transactions on Information Theory [carries many cryptography
    papers.]

    Cryptologia:  a cryptology journal, quarterly since Jan 1977.
    Cryptologia; Rose-Hulman Institute of Technology; Terre Haute
    Indiana 47803 [general: systems, analysis, history, ...]

    The Cryptogram (Journal of the American Cryptogram Association);
    18789 West Hickory Street; Mundelein, IL 60060; [primarily puzzle
    cryptograms of various sorts]

o I forgot my WordPerfect password.  Can I still read the file?

    WordPerfect encryption has been shown to be very easy to break.  The
    method uses XOR with two repeating key streams:  a typed password
    and a byte-wide counter initialized to 1+<the password length>.
    Full descriptions are given in:

    John Bennett; "Analysis of the Encryption Algorithm Used in the
    WordPerfect Word Processing Program"; Cryptologia, vol.XI, #4 (Oct
    87) p206

    H. A. Bergen and W. J. Caelli; "File Security in WordPerfect
    5.0"; Cryptologia, vol.XV, #1 (Jan 91) p57

o Breaking Repeated XOR Encryption

    "A recent post stated that cracking the encryption of a file that
    had been XOR'ed with a password that was not the same length as the
    file was " *trivial* ".  I would appreciate it very much if someone
    would explain an algorithm to me that accomplishes this (short of
    brute force)!"

    If the password is less than 1/2 the length of the file, then you
    can

    1.	discover the length of the password by counting coincidences:
        (see Gaines, Sinkov, Welchman or Deavours)

        Trying each displacement of the ciphertext against itself, count
        those bytes which are equal.  If the two ciphertext portions
        have used the same key, something over 6% of the bytes will be
        equal.  If they have used different key, then less than 0.4%
        will be equal (assuming random 8-bit bytes of key covering
        normal ASCII text).

        The smallest displacement which indicates equal key is the
        length of the repeated password.

    2.	shift the text by that length and XOR it with itself.  This
        removes the password and leaves you with text XORed with itself.
        Since English has about 1 bit of real information per byte, 2
        streams of text XORed together has 2 bits of info per 8-bit
        byte, providing plenty of redundancy for choosing a unique
        decryption (see "unicity distance").

    If the password is short, it might be even easier to treat this as a
    standard polyalphabetic substitution.  All the old cryptanalysis
    texts show how to break those.  It's possible with those methods, in
    the hands of an expert, if there's only 10x more text than password.
    See, for example, Callimahos, Gaines or Sinkov.

o Has DES been broken?
o Differential Cryptanalysis

    At CRYPTO '90, Eli Biham and Adi Shamir presented a paper:
    "DIFFERENTIAL CRYPTANALYSIS OF DES-LIKE CRYPTOSYSTEMS", to be
    published in the Journal of Cryptology.

    They showed that they could break 15-round DES with 2^52 steps but
    16-round DES required 2^58 steps.  [Brute force requires only 2^55
    steps because of DES's symmetry.]

    The New York Times, on p.A18, 3.Oct.91 and again in the Sunday
    paper, 13.Oct.91, ran a story noting that Drs. Shamir and Biham
    have an improved algorithm which breaks DES in fewer steps than
    brute force.  Details of the algorithm have not been released and
    apparently won't be until it is published.  It is a chosen plaintext
    attack and might be a refinement of the differential cryptanalysis
    methods described in 1990.

    This does not mean that the cipher is broken practically, only that
    it's getting nearer to being broken.  The number of operations
    might still be very large and multiple DES operations with different
    keys or use of block-chaining techniques might defeat this attack. 

    [A DES developer was quoted as saying that DES should be adequate
    for 5 to 10 years of life.  He said that in 1978.  (See the article
    mentioned below.)]

o Did NSA weaken DES (eg., with the 56 bit key)?
o Is Lucifer stronger than DES (longer key)?
o Did NSA put a trap door into DES's S-boxes?
o Did NSA or IBM design the S-boxes?

    According to the following article..

    Paul Kinnucan; "DATA ENCRYPTION GURUS:  TUCHMAN AND MEYER";
    Cryptologia; vol.II #4 (Oct 78) p.371 (also in Mini-Micro Systems,
    vol.II #9, Oct 78)

    Tuchman says (p.379) "We developed the DES algorithm entirely within
    IBM using IBMers.  The NSA did not dictate a single wire!"

    Tuchman and Meyer spent a year breaking ciphers and finding
    weaknesses in Lucifer.  They then spent two years strengthening
    Lucifer.  (p.374) 'Their basic approach was to look for strong
    substitution, permutation, and key scheduling functions ... IBM
    has classified the notes containing the selection criteria at the
    request of the NSA....  "The NSA told us we had inadvertently
    reinvented some of the deep secrets it uses to make its own
    algorithms," explains Tuchman.'

    Adi Shamir is quoted to say (NYTimes Oct 13 1991), "I would say
    that, contrary to what some people believe, there is no evidence of
    tampering with the DES so that the basic design was weakened."

o NSA's capabilities.
o Is NSA more capable than the public cryptography researchers?

    Nobody who knows for sure will say what the capabilities of
    government cryptologic agencies might be.  Generally they seem to be
    years, even decades, ahead of public cryptanalysts; thus it would be
    unwise to assume that any cryptosystem (whose strength has not been
    irrefutably proven) would be unreadable by experts.

    One considerable advantage which professional cryptologists have is
    the continuity of practice resulting from decades of accumulated
    experience.  Of course, actual comparisons would be classified and
    are therefore not available to this newsgroup.

o Why is there structure in the S-boxes?

    According to Meyer and Matyas, there is indeed structure, to
    strengthen the system.  The developers knew of certain attacks,
    and of certain characteristics that would prevent them.  They
    started with random S-boxes, but rejected any with the wrong
    characteristics.  The result is S-boxes that are *not* random.

o Is DES a group?

    People have often wondered if DES applied twice, with two different
    keys, is equivalent to its being applied once with some third key.
    This is the same as asking whether it forms a group.  It does not,
    according to:

    B.S.Kaliski Jr., R.L.Rivest, and A.T.Sherman:  "Is the Data
    Encryption Standard a Group?  (Results of Cycling Experiments on
    DES)," Journal of Cryptology, vol.1, #1, pp.3-16, 1988.

o Is RSA patented?

    Yes, at least in the USA.  Prior publication may have invalidated
    patent claims in other countries.

    Other U.S. patents claim to cover the very concept of public-key
    cryptography.  This is a matter for legal experts to debate.

o Should it be?

    This conflict of opinion has been aired in this group many times.
    It is a great user of bandwidth.

o How do I send encrypted mail?

    One popular method uses:

    cat file | compress | des private_key | uuencode | mail

    Meanwhile, there is an Internet standard in the works called PEM
    (Privacy Enhanced Mail).  It was described in RFC-1113, -1114 and
    -1115.

    There is a mailing list for PEM discussions (which has gone
    relatively inactive).  Requests for additions to or deletions from
    the list should be sent to "pem-dev-request@tis.com".

o Can I use the UNIX crypt command?

    Not if you want security.  See:

    J.A. Reeds and P.J. Weinberger, File Security and the UNIX Crypt Command,
    AT&T Bell Laboratories Technical Journal, Vol.63 #8, part 2;
    pp. 1673-1684; October, 1984

o If I first do perfect compression, ....?

    A number of people have proposed doing very good (or perfect)
    compression followed by some simple encryption method (eg., XOR with
    a repeated key).

    A compression scheme that could in fact squeeze out ALL redundancy
    from the pre-encryption plaintext, which is not theoretically
    possible, would make all recovered bit patterns (using all possible
    keys) have equally intelligible unpacked meanings, so that there
    would be no way to select the intended meaning from all these
    possibilities, making brute-force search useless for breaking the
    system.  (This is a similar argument to that used in proving that
    one-time pad encryption is, in principle, absolutely secure.)
    However, in practice there will always be some underlying
    redundancy, and given sufficient material to work with (see "unicity
    distance") the cryptanalyst can, in principle, determine with near
    certainty the intended meaning.

    Note that nearly all practical compression schemes produce output
    that actually starts off with high redundancy; for example,
    Lempel-Ziv-Welch compressed files usually start with runs of
    simply-mapped plaintext characters as the string dictionary is
    initially constructed.  Such characteristics can serve as entering
    wedges for cryptanalysis.

o Is there an unbreakable cipher?

    Yes.  The one-time-pad is unbreakable.  (This requires that a truly
    random key stream be XORed (or otherwise combined) with the source
    -- that the stream be at least as long as the source and that it
    NEVER be used again, for any purpose.)

    Of course, a cryptosystem need not be utterly unbreakable to be useful;
    rather, it needs to be strong enough to resist attacks by likely
    enemies for whatever length of time the data it protects is expected
    to remain valid.

o What does "random" mean?

    Cryptographic randomness doesn't mean just statistical randomness,
    although it implies that.  For a source to be cryptographically
    random, it must be impossible to predict what the next random bit
    will be given complete knowledge of the algorithm or hardware
    generating the stream and *all of the previous bits* in the stream.

o Is the USA really so stupid as to believe it can restrict export of
  PD encryption software?

    This discussion continues to use much bandwidth.

    Opinion is divided.

    B.R.Inman, "THE NSA PERSPECTIVE ON TELECOMMUNICATIONS PROTECTION IN
    THE NONGOVERNMENTAL SECTOR", Cryptologia, vol.3, #3, pp.129-135,
    July 1979 -- writing as director of NSA, argues for controls.

    The House of Representatives did not go along completely.

    "THE HOUSE REPORT ON PUBLIC CRYPTOGRAPHY", Cryptologia, vol.5, #2,
    pp.84-93, April 1981 -- reprints pages 62-69 and 118-120 of "The
    Government's Classification of Private Ideas", House Report No.
    96-1540 (Union Calendar No. 908), 96th Congress, 2nd Session
    (Washington:  GPO, 1980).

    Among other things it "finds no shred of evidence to support a
    notion or claim that private ideas in cryptography are 'born
    classified'." (p.89)

    Among its recommendations (p.93):  "...determine whether 'speech
    scramblers' and 'privacy devices' indeed belong in the Auxiliary
    Munitions Equipment category of the Munitions List, or whether they
    can be deleted as neither exclusively nor primarily military items.

            "In light of the memorandum opinion of the Office of Legal
    Counsel of the Department of Justice in May 1978 on the
    constitutionality under the First Amendment of ITAR restrictions on
    public cryptography, review and rewrite the ITAR to satisfy
    constitutional objections."


    For additional discussion of this issue, by legal scholars,
    Tony_S_Patti@cup.portal.com recommends:  "Public Cryptography, Arms
    Export Controls, and the First Amendment:  A Need for Legislation"
    in _Cornell International Law Journal_, Volume 17, 1984, pages
    199-236.

o What are the US export regulations?

    Apparently "privacy devices" remain on the Munitions List and
    software which achieves privacy (rather than just authentication)
    and which is developed by Americans cannot legally be shipped out
    of the US or to a foreign national within the US, under the ITAR
    (International Traffic in Arms Regulations).

    The exact reading probably requires a lawyer.  Much bandwidth has
    been spent by non-lawyers offering contrasting legal opinions on
    this.

o Here's the ciphertext from my new algorithm.  Try to break it.  OK,
  that was good, so I'll change it this way.  Now try to break it.

    Just providing ciphertext isn't adequate.

    Any new algorithm should be secure even if the opponent knows the
    full algorithm (including how any message key is distributed) and
    only the private key is kept secret.  If such an algorithm is
    proposed, it might be evaluated by the readers -- and if a flaw is
    pointed out, it then becomes the task of the original designer to
    consider the flaw and try to learn cryptanalysis from it -- rather
    than just try to add one more layer of complication and come back
    for another round.

    Often, experts won't invest the time to try to break challenge
    cryptograms, so lack of response does not prove the security of a
    proposed cryptosystem.

    Among professionals, the rule of thumb is that if you want to design
    a cryptosystem, you have to have experience as a cryptanalyst.

o What is the unicity point (a.k.a. unicity distance)?

    C.E.Shannon, "Communication Theory of Secrecy Systems," Bell System
    Technical Journal, 28, October 1949, pp.656-715.

    The Unicity Point is an approximation to that amount of ciphertext
    such that the sum of the real information (entropy) in the
    corresponding source text and encryption key equals the number of
    ciphertext bits used.  Ciphertexts significantly longer than this
    can be shown probably to have a unique decipherment.  This is used
    to back up a claim of the validity of a ciphertext-only
    cryptanalysis.  Ciphertexts significantly shorter than this are
    likely to have multiple, equally valid decryptions and therefore to
    gain security from the opponent's difficulty choosing the correct
    one.

    Unicity distance, like all statistical or information-theoretic
    measures, does not make deterministic predictions but rather gives
    probabilistic results:  namely, the minimum amount of ciphertext for
    which it is likely that there is only a single intelligible
    plaintext corresponding to the ciphertext, when all possible keys
    are tried for the decryption (see "brute force search").  Working
    cryptologists don't normally deal with unicity distance as such, but
    rather directly determine the likelihood of events of interest.

    In fact, actual cryptanalysis seldom proceeds along the lines used
    in discussing unicity distance.  Few practical cryptosystems are
    absolutely impervious to analysis; all manner of characteristics
    might serve as entering "wedges" to crack some cipher messages.
    However, similar information-theoretic considerations are
    occasionally useful, for example, to determine a recommended key
    change interval for a particular cryptosystem.  Cryptanalysts also
    employ a variety of statistical and information-theoretic tests to
    help guide the analysis in the most promising directions.

    Unfortunately, most literature on the application of information
    statistics to cryptanalysis remains classified, even the seminal
    1940 work of Alan Turing (see "Enigma").  For some insight into the
    possibilities, see:

      I.J. Good, Good Thinking: the foundations of probability and its
	applications, Minneapolis, University of Minnesota Press, 1983
	LCCCN 81-24041

      Solomon Kullbach, Information Theory and Statistics, Dover, 1968
	ISBN 0-486-61913-3, LCCCN 68-12910.

o What is "brute force search" and what is its cryptographic relevance?

    One method of attacking a cryptosystem is to try decrypting the
    intercepted ciphertext using each possible key, until viable
    plaintext is found.  This "brute force search" of the key space is
    impractical for well-designed cryptosystems; however, advances in
    technology sometimes change what is considered practical.  One phase
    of a more sophisticated cryptanalysis may involve a "brute force"
    search of some manageably small space of possibilities.

o How does one determine the strength of a proposed cryptosystem?

    "Unicity distance" (described above) is one method for simple
    systems; there appears to have been little public development of
    measures of cryptosystem strength.  Generally it is considered
    essential to let experienced expert cryptanalysts "have a go"
    (unsuccessfully!) at a proposed cryptosystem before it is considered
    secure.

o How does one go about cryptanalysis?

    Cryptanalysis involves an interesting combination of analytical
    reasoning, application of mathematical tools, pattern finding,
    patience and determination.  The best available textbooks on the
    subject are the Military Cryptanalytics series, mentioned in the
    Books section.

o If a cryptosystem is theoretically unbreakable, does that mean that it
  is guaranteed analysis-proof in practice?

    Cryptanalytic methods include what is known as "practical
    cryptanalysis", which refers to techniques other than pure analysis
    of ciphertext (plus general background knowledge).  For example,
    "cribs" (stretches of known or probable plaintext) may be assumed,
    or "isologs" (same plaintext enciphered in more than one
    cryptosystem or key) may be exploited.  Thus, solutions can often be
    obtained even in circumstances for which simple theory might say
    that no solution is probable.

    There are also occasions when cryptosystems malfunction or when
    their users follow incorrect procedures; sometimes these provide
    methods of attack even when correct operation of the cryptosystem
    would have been secure.  Even chosen-plaintext attacks have been
    employed; see, for example, Kahn's account of the Battle of Midway.

o Why are many people still using cryptosystems that are relatively
  easy to break?

    Some don't know any better; often amateurs think they can design
    secure systems, and are not aware of what an expert cryptanalyst
    could do.  Also, sometimes there is insufficient motivation for
    anybody to invest the work needed to crack a system.

o What is key management and why is it important?

    One of the fundamental axioms of cryptography is that the enemy is
    in full possession of the details of the general cryptographic
    system, and lacks only the specific key data employed in the
    encryption.  Repeated use of a finite amount of key provides
    redundancy that can eventually facilitate cryptanalytic progress.
    Thus, especially in modern communication systems where vast amounts
    of information are transferred, security requires not only a sound
    general cryptosystem design but also the ability to obtain
    sufficient key material to cover the traffic.  Transmission of key
    material must be to both communicating parties, and this raises
    issues of protecting the key data itself and of validating the
    identities of parties receiving key material for future use.

    A publicly accessible example of modern key management technology is
    the STU III secure telephone unit, which for classified use employs
    individual coded "Crypto Ignition Keys" and a central Key Management
    Center operated by NSA.  There is a hierarchy in that certain CIKs
    are used by authorized cryptographic control personnel to validate
    the issuance of individual traffic keys and to perform
    installation/maintenance functions, such as the reporting of lost
    CIKs.

    This should give an inkling of the extent of the key management
    problem; for so-called "public key" systems, there are several
    similar issues and others, many having to do with "whom do you
    trust?"

    [See also the Kerberos system for an example of key management.]

o WWII German ENIGMA

    "For a project in data security we are looking for sources of
    information about the German ENIGMA code and how it was broken by
    the British during WWII."


    W. Kozaczuk, Enigma, University Publications of America, 1984

    Gordon Welchman, The Hut Six Story, McGraw-Hill, 1982

    Andrew Hodges, Alan Turing:  The Enigma, Burnett Books Ltd., 1983

    Cipher A. Deavours & Louis Kruh, Machine Cryptography and Modern
    Cryptanalysis; Artech House, 610 Washington St., Dedham MA 02026

    F.H.Hinsley, et al., "British Intelligence in the Second World War",
    Cambridge University Press. (vol's 1, 2, 3a, 3b & 4, so far)

    David Kahn, Seizing the Enigma, Houghton Mifflin, 1991

o What is TEMPEST?

    TEMPEST is a standard for electromagnetic shielding for computer
    equipment.  It is in response to the discovery that information can
    be read from computer radiation (eg., from a CRT) at quite a
    distance and/or with little effort.

    Needless to say, encryption doesn't do much good if the cleartext is
    available this way.

o Fractal Cryptography
o Chaos Cryptography
o Linear Congruential Pseudo-random Numbers as a Key Stream

    "I have heard that nonlinear differential equations and fractals
    share one thing:  small differences in initial condition (or
    parameters) gives big differences in the solution.  This might be a
    good thing to build some kind of cryptographic system on."


    Chaotic equations and fractals produce an apparent complexity from
    relatively compact generators.  Their displayed output shows
    intricate structure at various levels of detail (for fractals, at
    all levels of detail).  This makes fractals particularly interesting
    to those generating computer images.  From a small data seed and an
    efficient program, very complex images can be generated.  By
    contrast, a linear-congruential pseudo-random number generator
    output would look much more complex -- so much so that no one
    bothers to display it:  it's too random to have anything to look at.

    Structure in the output of any form provides a hook for
    cryptanalysis.  Therefore, fractals or chaotic equations are less
    secure than LCPRNGs which, in turn, are notoriously poor
    cryptographic key generators.  See:  J.Reeds, "'Cracking' a Random
    Number Generator", Cryptologia, vol.1, #1, pp.20-26, 1977 --
    reprinted in "CRYPTOLOGY:  Yesterday, Today and Tomorrow" from
    Artech House.

    The problem is that the equation is assumed known as is a portion of
    the plain text.  From that, the parameters of the equation can be
    derived and from those the entire remaining key stream can be
    computed.

o What are MD4 and MD5?

    MD4 and MD5 are message digest functions put into the public domain
    by Ron Rivest.  They are intended to generate a cryptographically
    strong hash of a message so that only the hash needs to be signed to
    sign the message.  They're described in RFC-1113..1115.  Code is
    available by anonymous ftp from RSA.COM.