NetNews Usenet Archive 1992 #23

home *** CD-ROM | disk | FTP | other *** search

/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / crypt / 3795 < prev next >

Wrap

Internet Message Format | 1992-10-15 | 27.5 KB

Path: sparky!uunet!zaphod.mps.ohio-state.edu!wupost!waikato.ac.nz!comp.vuw.ac.nz!cavebbs!sideways!patrick Newsgroups: sci.crypt Subject: Re: temporary, independent FAQ file Message-ID: <1992Oct15083657patrick@sideways.welly.gen.nz> From: Pat Cain <patrick@sideways.welly.gen.nz> Date: Thu, 15 Oct 1992 08:36:57 GMT Reply-To: Pat Cain <cain_p@kosmos.wcc.govt.nz> References: <1992Oct13.183131.16614@rchland.ibm.com> Organization: SillyNews, Sideways bulletin board, Lower Hutt, New Zealand Keywords: FAQ cryptography Lines: 625 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.