Cryptography-Digest Digest #542
Cryptography-Digest Digest #542, Volume #9 Thu, 13 May 99 10:13:05 EDT Contents: Cryptography FAQ (06/10: Public Key Cryptography) ([EMAIL PROTECTED]) Cryptography FAQ (07/10: Digital Signatures) ([EMAIL PROTECTED]) From: [EMAIL PROTECTED] Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers Subject: Cryptography FAQ (06/10: Public Key Cryptography) Date: 13 May 1999 13:29:10 GMT Reply-To: [EMAIL PROTECTED] Archive-name: cryptography-faq/part06 Last-modified: 94/06/07 This is the sixth of ten parts of the sci.crypt FAQ. The parts are mostly independent, but you should read the first part before the rest. We don't have the time to send out missing parts by mail, so don't ask. Notes such as ``[KAH67]'' refer to the reference list in the last part. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, sci.answers, and news.answers every 21 days. Contents: 6.1. What is public-key cryptography? 6.2. How does public-key cryptography solve cryptography's Catch-22? 6.3. What is the role of the `trapdoor function' in public key schemes? 6.4. What is the role of the `session key' in public key schemes? 6.5. What's RSA? 6.6. Is RSA secure? 6.7. What's the difference between the RSA and Diffie-Hellman schemes? 6.8. What is `authentication' and the `key distribution problem'? 6.9. How fast can people factor numbers? 6.10. What about other public-key cryptosystems? 6.11. What is the `RSA Factoring Challenge?' 6.1. What is public-key cryptography? In a classic cryptosystem, we have encryption functions E_K and decryption functions D_K such that D_K(E_K(P)) = P for any plaintext P. In a public-key cryptosystem, E_K can be easily computed from some ``public key'' X which in turn is computed from K. X is published, so that anyone can encrypt messages. If decryption D_K cannot be easily computed from public key X without knowledge of private key K, but readily with knowledge of K, then only the person who generated K can decrypt messages. That's the essence of public-key cryptography, introduced by Diffie and Hellman in 1976. This document describes only the rudiments of public key cryptography. There is an extensive literature on security models for public-key cryptography, applications of public-key cryptography, other applications of the mathematical technology behind public-key cryptography, and so on; consult the references at the end for more refined and thorough presentations. 6.2. How does public-key cryptography solve cryptography's Catch-22? In a classic cryptosystem, if you want your friends to be able to send secret messages to you, you have to make sure nobody other than them sees the key K. In a public-key cryptosystem, you just publish X, and you don't have to worry about spies. Hence public key cryptography `solves' one of the most vexing problems of all prior cryptography: the necessity of establishing a secure channel for the exchange of the key. To establish a secure channel one uses cryptography, but private key cryptography requires a secure channel! In resolving the dilemma, public key cryptography has been considered by many to be a `revolutionary technology,' representing a breakthrough that makes routine communication encryption practical and potentially ubiquitous. 6.3. What is the role of the `trapdoor function' in public key schemes? Intrinsic to public key cryptography is a `trapdoor function' D_K with the properties that computation in one direction (encryption, E_K) is easy and in the other is virtually impossible (attack, determining P from encryption E_K(P) and public key X). Furthermore, it has the special property that the reversal of the computation (decryption, D_K) is again tractable if the private key K is known. 6.4. What is the role of the `session key' in public key schemes? In virtually all public key systems, the encryption and decryption times are very lengthy compared to other block-oriented algorithms such as DES for equivalent data sizes. Therefore in most implementations of public-key systems, a temporary, random `session key' of much smaller length than the message is generated for each message and alone encrypted by the public key algorithm. The message is actually encrypted using a faster private key algorithm with the session key. At the receiver side, the session key is decrypted using the public-key algorithms and the recovered `plaintext' key is used to decrypt the message. The session key approach blurs the distinction between `keys' and `messages' -- in the scheme, the message includes the key, and the key itself is treated as an encryptable `message'.
Cryptography-Digest Digest #541
Cryptography-Digest Digest #541, Volume #9 Thu, 13 May 99 10:13:05 EDT Contents: Cryptography FAQ (05/10: Product Ciphers) ([EMAIL PROTECTED]) From: [EMAIL PROTECTED] Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers Subject: Cryptography FAQ (05/10: Product Ciphers) Date: 13 May 1999 13:28:51 GMT Reply-To: [EMAIL PROTECTED] Archive-name: cryptography-faq/part05 Last-modified: 94/06/07 This is the fifth of ten parts of the sci.crypt FAQ. The parts are mostly independent, but you should read the first part before the rest. We don't have the time to send out missing parts by mail, so don't ask. Notes such as ``[KAH67]'' refer to the reference list in the last part. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, sci.answers, and news.answers every 21 days. Contents: 5.1. What is a product cipher? 5.2. What makes a product cipher secure? 5.3. What are some group-theoretic properties of product ciphers? 5.4. What can be proven about the security of a product cipher? 5.5. How are block ciphers used to encrypt data longer than the block size? 5.6. Can symmetric block ciphers be used for message authentication? 5.7. What exactly is DES? 5.8. What is triple DES? 5.9. What is differential cryptanalysis? 5.10. How was NSA involved in the design of DES? 5.11. Is DES available in software? 5.12. Is DES available in hardware? 5.13. Can DES be used to protect classified information? 5.14. What are ECB, CBC, CFB, OFB, and PCBC encryption? 5.1. What is a product cipher? A product cipher is a block cipher that iterates several weak operations such as substitution, transposition, modular addition/multiplication, and linear transformation. (A ``block cipher'' just means a cipher that encrypts a block of data---8 bytes, say---all at once, then goes on to the next block.) The notion of product ciphers is due to Shannon [SHA49]. Examples of modern product ciphers include LUCIFER [SOR84], DES [NBS77], SP-networks [KAM78], LOKI [BRO90], FEAL [SHI84], PES [LAI90], Khufu and Khafre [ME91a]. The so-called Feistel ciphers are a class of product ciphers which operate on one half of the ciphertext at each round, and then swap the ciphertext halves after each round. LUCIFER, DES, LOKI, and FEAL are examples of Feistel ciphers. The following table compares the main parameters of several product ciphers: cipher | block length | key bits | number of rounds LUCIFER 128 12816 DES 645616 LOKI 646416 FEAL 64 1282^x, x = 5 PES 64 128 8 5.2. What makes a product cipher secure? Nobody knows how to prove mathematically that a product cipher is completely secure. So in practice one begins by demonstrating that the cipher ``looks highly random''. For example, the cipher must be nonlinear, and it must produce ciphertext which functionally depends on every bit of the plaintext and the key. Meyer [MEY78] has shown that at least 5 rounds of DES are required to guarantee such a dependence. In this sense a product cipher should act as a ``mixing'' function which combines the plaintext, key, and ciphertext in a complex nonlinear fashion. The fixed per-round substitutions of the product cipher are referred to as S-boxes. For example, LUCIFER has 2 S-boxes, and DES has 8 S-boxes. The nonlinearity of a product cipher reduces to a careful design of these S-boxes. A list of partial design criteria for the S-boxes of DES, which apply to S-boxes in general, may be found in Brown [BRO89] and Brickell et al. [BRI86]. 5.3. What are some group-theoretic properties of product ciphers? Let E be a product cipher that maps N-bit blocks to N-bit blocks. Let E_K(X) be the encryption of X under key K. Then, for any fixed K, the map sending X to E_K(X) is a permutation of the set of N-bit blocks. Denote this permutation by P_K. The set of all N-bit permutations is called the symmetric group and is written S_{2^N}. The collection of all these permutations P_K, where K ranges over all possible keys, is denoted E(S_{2^N}). If E were a random mapping from plaintexts to ciphertexts then we would expect E(S_{2^N}) to generate a large subset of S_{2^N}. Coppersmith and Grossman [COP74] have shown that a very simple product cipher can generate the alternating group A_{2^N} given a sufficient number of rounds. (The alternating group is half of the symmetric group: it consists of all ``even'' permutations, i.e., all permutations which can be written as an even number of
Cryptography-Digest Digest #540
Cryptography-Digest Digest #540, Volume #9 Thu, 13 May 99 10:13:05 EDT Contents: Cryptography FAQ (03/10: Basic Cryptology) ([EMAIL PROTECTED]) Cryptography FAQ (04/10: Mathematical Cryptology) ([EMAIL PROTECTED]) From: [EMAIL PROTECTED] Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers Subject: Cryptography FAQ (03/10: Basic Cryptology) Date: 13 May 1999 13:28:17 GMT Reply-To: [EMAIL PROTECTED] Archive-name: cryptography-faq/part03 Last-modified: 93/10/10 This is the third of ten parts of the sci.crypt FAQ. The parts are mostly independent, but you should read the first part before the rest. We don't have the time to send out missing parts by mail, so don't ask. Notes such as ``[KAH67]'' refer to the reference list in the last part. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, sci.answers, and news.answers every 21 days. Contents: 3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key? 3.2. What references can I start with to learn cryptology? 3.3. How does one go about cryptanalysis? 3.4. What is a brute-force search and what is its cryptographic relevance? 3.5. What are some properties satisfied by every strong cryptosystem? 3.6. If a cryptosystem is theoretically unbreakable, then is it guaranteed analysis-proof in practice? 3.7. Why are many people still using cryptosystems that are relatively easy to break? 3.8. What are the basic types of cryptanalytic `attacks'? 3.1. What is cryptology? Cryptography? Plaintext? Ciphertext? Encryption? Key? The story begins: When Julius Caesar sent messages to his trusted acquaintances, he didn't trust the messengers. So he replaced every A by a D, every B by a E, and so on through the alphabet. Only someone who knew the ``shift by 3'' rule could decipher his messages. A cryptosystem or cipher system is a method of disguising messages so that only certain people can see through the disguise. Cryptography is the art of creating and using cryptosystems. Cryptanalysis is the art of breaking cryptosystems---seeing through the disguise even when you're not supposed to be able to. Cryptology is the study of both cryptography and cryptanalysis. The original message is called a plaintext. The disguised message is called a ciphertext. Encryption means any procedure to convert plaintext into ciphertext. Decryption means any procedure to convert ciphertext into plaintext. A cryptosystem is usually a whole collection of algorithms. The algorithms are labelled; the labels are called keys. For instance, Caesar probably used ``shift by n'' encryption for several different values of n. It's natural to say that n is the key here. The people who are supposed to be able to see through the disguise are called recipients. Other people are enemies, opponents, interlopers, eavesdroppers, or third parties. 3.2. What references can I start with to learn cryptology? For an introduction to technical matter, the survey articles given in part 10 are the best place to begin as they are, in general, concise, authored by competent people, and well written. However, these articles are mostly concerned with cryptology as it has developed in the last 50 years or so, and are more abstract and mathematical than historical. The Codebreakers by Kahn [KAH67] is encyclopedic in its history and technical detail of cryptology up to the mid-60's. Introductory cryptanalysis can be learned from Gaines [GAI44] or Sinkov [SIN66]. This is recommended especially for people who want to devise their own encryption algorithms since it is a common mistake to try to make a system before knowing how to break one. The selection of an algorithm for the DES drew the attention of many public researchers to problems in cryptology. Consequently several textbooks and books to serve as texts have appeared. The book of Denning [DEN82] gives a good introduction to a broad range of security including encryption algorithms, database security, access control, and formal models of security. Similar comments apply to the books of Price Davies [PRI84] and Pfleeger [PFL89]. The books of Konheim [KON81] and Meyer Matyas [MEY82] are quite technical books. Both Konheim and Meyer were directly involved in the development of DES, and both books give a thorough analysis of DES. Konheim's book is quite mathematical, with detailed analyses of many classical cryptosystems. Meyer and Matyas concentrate on modern cryptographic methods, especially pertaining to key management and the integration of security facilities into computer systems and networks. For more recent documentation on related areas, try G. Simmons in [SIM91].
Cryptography-Digest Digest #539
Cryptography-Digest Digest #539, Volume #9 Thu, 13 May 99 10:13:05 EDT Contents: Re: TwoDeck solution (but it ain't pretty) (Boris Kazak) Message for Bob Knauer from Paul Hyett (Paul Hyett) Re: Newbie: Encrypting short strings (wtshaw) Re: Algorithms where encryption=decryption? (Wei Dai) Re: Thought question: why do public ciphers use only simple ops like shift and XOR? (Terry Ritter) Re: DES analysis paper (Jean-Jacques Quisquater) Related keys in TwoDeck ([EMAIL PROTECTED]) Re: Scramdisk/Norton query (Joshua Falkin) Re: True Randomness The Law Of Large Numbers (R. Knauer) 3DES-CBC and key length ("dino") Cryptography FAQ (01/10: Overview) ([EMAIL PROTECTED]) Cryptography FAQ (02/10: Net Etiquette) ([EMAIL PROTECTED]) From: Boris Kazak [EMAIL PROTECTED] Subject: Re: TwoDeck solution (but it ain't pretty) Date: Wed, 12 May 1999 22:19:50 -0400 Reply-To: [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Although I agree, please keep the discussion civil. I (like others) want to keep it cool about these punk @#! losers... Tom --- Tom, this is obviously a female, underdeveloped physically and mentally, an obvious outcast, overconcerned sexually and besides having a crush on you (heaven protect!). Don't look further than your own school, you'll find her there. Best wishes BNK -- From: Paul Hyett [EMAIL PROTECTED] Subject: Message for Bob Knauer from Paul Hyett Date: Thu, 13 May 1999 07:12:57 +0100 Hi Bob, Can you let me know via email whether my replies are getting to you, as my ISP keeps sending me 'message delayed' notifications. Regards, -- Paul Hyett, Cheltenham, England -- From: [EMAIL PROTECTED] (wtshaw) Subject: Re: Newbie: Encrypting short strings Date: Thu, 13 May 1999 00:45:51 -0600 In article [EMAIL PROTECTED], [EMAIL PROTECTED] (Matthias Bruestle) wrote: Mahlzeit Jim Felling ([EMAIL PROTECTED]) wrote: A secure hash will have the properties you look for --just pad with nulls out Steve K wrote: I am looking for an algorithm that will be suitable for encrypting (and decrypting) short strings around 3 to 10 characters in length. I would like He probably needs to decrypt these numbers. The request was for an algorithm that easily produced highly variable ciphertexts that would be difficult to easily change. Checking Ritter on the first matter; I guess the classification of homophonic cipher pretty well defines what you are asking for. I've tried to apply the term probabilistic to this, but homophonic is older, covering what both what I would call inductive encryption and deductive decryption. Schneier uses probabilistic encryption and deterministic decryption, but deterministic could refer to both encryption and decryption in a truely symmetric algorithm as well. Recap: Schneier: "In probabilistic encryption, the encrypting algorithms is probabilistic rather than deterministic. In other words, a large number of ciphertexts will decrypt to a given plaintex, and the particular ciphertext used in any given encryption is randomly chosen." Also,"Under this scheme, the ciphertext will always be larger than the plaintext. You can't get around this; it's a result of the fact that many ciphertexts decrypt to the same plaintexts [sic]." It miht be good to indicate that some systems with few choices might not increase the length when going from plaintext to ciphertext. But, these are not that useful. Now, the GVA does as required, without an IV, merely storing the input randomness in a bread-crumb-trail form. Making a single block for each entry would not be especially good, but several blocks with multiple copies would make simple manipulation difficult. Remembering the acceptable parameters, you wanted a few characters of plaintext to perhaps 20 in ciphertext. It's time for a real example: Assume a set of keys. My defaults require a longer string in the sample implementation and therefore produce a longer output string, but this is all scalable. Inventory item 34568kmn-ert could be represented in 2^56 ways, including {XD'/^9=Y%DS]XF+WY%?S~ } {#L2GS^IC#J"VT,,GBW%:~ } {/CB%5+0;NF=4V%*P*FCR=~ } If you combined two of these, {XD'/^9=Y%DS]XF+WY%?S~ /CB%5+0;NF=4V%*P*FCR=~ }, the result on decryption is: 34568kmn-ert 34568kmn-ert 2^56 is probably overkill, so picking a small number of output possibilites would not lengthen the string as much; figure one character less for each 8 bit decrease in ciphertext possibilities. -- Weathermen prosphesize and insurance companies predict, while both pretend to be doing the other to get an audience. -- From: [EMAIL PROTECTED] (Wei Dai) Subject: Re: Algorithms where encryption=decryption? Date: Sat, 1 May 1999 00:07:22 -0700 In article 7galtg$a9g$[EMAIL PROTECTED], [EMAIL PROTECTED] says...
Cryptography-Digest Digest #543
Cryptography-Digest Digest #543, Volume #9 Thu, 13 May 99 10:13:05 EDT Contents: Cryptography FAQ (08/10: Technical Miscellany) ([EMAIL PROTECTED]) Re: Need to design basic authentication system (Mark Carroll) Cryptography FAQ (09/10: Other Miscellany) ([EMAIL PROTECTED]) From: [EMAIL PROTECTED] Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers Subject: Cryptography FAQ (08/10: Technical Miscellany) Date: 13 May 1999 13:29:44 GMT Reply-To: [EMAIL PROTECTED] Archive-name: cryptography-faq/part08 Last-modified: 94/01/25 This is the eighth of ten parts of the sci.crypt FAQ. The parts are mostly independent, but you should read the first part before the rest. We don't have the time to send out missing parts by mail, so don't ask. Notes such as ``[KAH67]'' refer to the reference list in the last part. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, sci.answers, and news.answers every 21 days. Contents 8.1. How do I recover from lost passwords in WordPerfect? 8.2. How do I break a Vigenere (repeated-key) cipher? 8.3. How do I send encrypted mail under UNIX? [PGP, RIPEM, PEM, ...] 8.4. Is the UNIX crypt command secure? 8.5. How do I use compression with encryption? 8.6. Is there an unbreakable cipher? 8.7. What does ``random'' mean in cryptography? 8.8. What is the unicity point (a.k.a. unicity distance)? 8.9. What is key management and why is it important? 8.10. Can I use pseudo-random or chaotic numbers as a key stream? 8.11. What is the correct frequency list for English letters? 8.12. What is the Enigma? 8.13. How do I shuffle cards? 8.14. Can I foil S/W pirates by encrypting my CD-ROM? 8.15. Can you do automatic cryptanalysis of simple ciphers? 8.16. What is the coding system used by VCR+? 8.1. How do I recover from lost passwords in WordPerfect? 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 Bennett [BEN87] and Bergen and Caelli [BER91]. Chris Galas writes: ``Someone awhile back was looking for a way to decrypt WordPerfect document files and I think I have a solution. There is a software company named: Accessdata (87 East 600 South, Orem, UT 84058), 1-800-658-5199 that has a software package that will decrypt any WordPerfect, Lotus 1-2-3, Quatro-Pro, MS Excel and Paradox files. The cost of the package is $185. Steep prices, but if you think your pw key is less than 10 characters, (or 10 char) give them a call and ask for the free demo disk. The demo disk will decrypt files that have a 10 char or less pw key.'' Bruce Schneier says the phone number for AccessData is 801-224-6970. 8.2. How do I break a Vigenere (repeated-key) cipher? A repeated-key cipher, where the ciphertext is something like the plaintext xor KEYKEYKEYKEY (and so on), is called a Vigenere cipher. If the key is not too long and the plaintext is in English, do the following: 1. Discover the length of the key by counting coincidences. (See Gaines [GAI44], Sinkov [SIN66].) 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 keys, then less than 0.4% will be equal (assuming random 8-bit bytes of key covering normal ASCII text). The smallest displacement which indicates an equal key is the length of the repeated key. 2. Shift the text by that length and XOR it with itself. This removes the key 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. (And in fact one stream of text XORed with itself has just 1 bit per byte.) If the key 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 ten times as much text as key. See, for example, Gaines [GAI44], Sinkov [SIN66]. 8.3. How do I send encrypted mail under UNIX? [PGP, RIPEM, PEM, ...] Here's one popular method, using the des command: cat file | compress | des private_key | uuencode | mail Meanwhile, there is a de jure Internet standard in the works called PEM (Privacy Enhanced Mail). It is described in RFCs 1421 through 1424. To join the PEM mailing list, contact [EMAIL PROTECTED] There is a beta version of PEM being
Cryptography-Digest Digest #546
Cryptography-Digest Digest #546, Volume #9 Thu, 13 May 99 18:13:02 EDT Contents: Re: Need to design basic authentication system (Thomas Wu) Re: Little Irish girl's algorithm? ("Claus Hirth") Re: 3DES-CBC and key length (Jim Gillogly) Re: Little Irish girl's algorithm? (Charles Blair) Re: Thought question: why do public ciphers use only simple ops like (Bryan Olson) Re: Linear Solutions of S-Boxes (SCOTT19U.ZIP_GUY) Re: Fast random number generator (Herman Rubin) Re: Random permutation (Herman Rubin) Re: 3DES-CBC and key length (DJohn37050) Re: Fast random number generator -- Need C code for simulation (catfish) Re: 3DES-CBC and key length (Jim Gillogly) Intel Pentium III actual random bit generator-- does it exist? ("news") Lemming and Lemur (David Wagner) Re: Thought question: why do public ciphers use only simple ops like (Bryan Olson) From: Thomas Wu [EMAIL PROTECTED] Subject: Re: Need to design basic authentication system Date: 13 May 1999 12:34:50 -0700 "Tim Mavers" [EMAIL PROTECTED] writes: For a project I am working on, I need to design (and implement) a basic, secure user-authentication system that will allow a user on a client machine log into a "server" via a name and password. What is the best way of doing this? I was thinking of a challenge-response system, but am not sure how to code one (that is relatively secure). I have read that Kerberos is the perferred method these days. Is that simple (and free) to implement? This should *really* be a FAQ by now. SRP, SPEKE, EKE. Read about them. Pick one. Use it. SRP: http://srp.stanford.edu/srp/ SPEKE: http://world.std.com/~dpj/ I understand that making a completely secure system for this is not something that is "simple". I don't really need it to be 100% safe, just relatively safe so someone can't break the system within a few days. Then don't use Kerberos V4/V5 - without secure pre-auth, they fall to a dictionary attack. -- Tom Wu* finger -l [EMAIL PROTECTED] for PGP key * E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms in Phone: (650) 723-1565 exchange for security deserve neither." http://www-cs-students.stanford.edu/~tjw/ http://srp.stanford.edu/srp/ -- From: "Claus Hirth" [EMAIL PROTECTED] Subject: Re: Little Irish girl's algorithm? Date: Thu, 13 May 1999 21:52:36 +0200 Nemo999 wrote in message [EMAIL PROTECTED]... I think her name was supposed to be Flannery and I couldn't find anything on it. I'm happy I can stop looking for it since its a fake story. How do you know it's a fake story? http://www.zdnet.com/zdnn/stories/news/0,4586,2189301,00.html Maybe someone who has actually seen a paper or source code could comment on this. TIA Claus -- From: Jim Gillogly [EMAIL PROTECTED] Subject: Re: 3DES-CBC and key length Date: Thu, 13 May 1999 13:04:22 -0700 DJohn37050 wrote: The question was for 3 different DES keys. FOr 2 keys the last I know is that it is the minimum of (2**112, 2**120/n) where n is the number of known plaintext/ciphertext pairs. This info is all in X9.52. I have not seen the recent vOW paper, do they say there is a better attack than what I gave above? Don Johnson The van Oorschot Wiener article is from J. of Cryptology Vol 12 #1, Winter 1999, and mentions 2DES (double DES), not 2-key triple DES. However, I thought it might be relevant to this discussion because the obvious MITM attack with a lot of memory (enough to store 2^56 key+ct/pt blocks) takes an average of 1.5 * 2^56 DES operations; but with memory limited to about 2^30 pairs it takes closer to 2^72 DES operations using their techniques. If the 2^112 number you gave for 3DES with 3 keys is based on storing a large number of key+ct/pt pairs, I thought it might be worth re-evaluating it with a reasonable number of pairs. I haven't seen the X9.52 material. In any case, 2^112 is plenty for all practical purposes. -- Jim Gillogly 22 Thrimidge S.R. 1999, 19:46 12.19.6.3.7, 10 Manik 15 Uo, Fourth Lord of Night -- From: [EMAIL PROTECTED] (Charles Blair) Subject: Re: Little Irish girl's algorithm? Date: 13 May 1999 20:08:01 GMT I have not published any research in cryptography, but my experience with other fields suggests a year for a paper to appear is by no means unusual. -- From: Bryan Olson [EMAIL PROTECTED] Subject: Re: Thought question: why do public ciphers use only simple ops like Date: Thu, 13 May 1999 12:48:35 -0700 Terry Ritter wrote: On Tue, 11 May 1999 15:45:55 -0700, in [EMAIL PROTECTED], in sci.crypt Bryan Olson [EMAIL PROTECTED] wrote: [...] Try to follow what people are saying. Without authentication, adversary can influence the choice and
Cryptography-Digest Digest #547
Cryptography-Digest Digest #547, Volume #9 Thu, 13 May 99 20:13:01 EDT Contents: Re: Hello I am paper, please read me. ([EMAIL PROTECTED]) Review of "Cryptonomicon" (John A. Sidles) Re: Hello I am paper, please read me. ([EMAIL PROTECTED]) Re: Hello I am paper, please read me. (Jim Felling) Re: Hello I am paper, please read me. (David Wagner) Re: Thought question: why do public ciphers use only simple ops like shift and XOR? (Terry Ritter) Re: Fast random number generator -- Need C code for simulation (Terry Ritter) Re: Hello I am paper, please read me. (David Wagner) PGP 6.0/6.2 for Macintosh (Lee Kanner) Re: Thought question: why do public ciphers use only simple ops like shift and XOR? (Terry Ritter) Re: Random permutation (Bryan Olson) Re: Fast random number generator -- Need C code for simulation (Terry Ritter) Re: Fast random number generator ([EMAIL PROTECTED]) Re: Fast random number generator -- Need C code for simulation ([EMAIL PROTECTED]) From: [EMAIL PROTECTED] Subject: Re: Hello I am paper, please read me. Date: Thu, 13 May 1999 21:57:30 GMT snip But A() is not known at the start, so how do you solve that? i.e B(A(i)) But A() is not 0,1,2,3,...,255 it could be any N! deck. So how do you know that n = B(A(i)) and n = B(i) are true? Tom --== Sent via Deja.com http://www.deja.com/ ==-- ---Share what you know. Learn what you don't.--- -- From: [EMAIL PROTECTED] (John A. Sidles) Subject: Review of "Cryptonomicon" Date: 13 May 1999 22:20:54 GMT Dear sci.crypter's With Father's day coming up, I just thought I'd post a very favorable review of Neil Stephensen's new book 'Cryptonomicon'. 'Cryptonomicon' is sufficiently complicated that there are plenty of different ways to read it: for me it's a lengthy and very funny meditation on the love-hate relationship that we human beings have with information --- particularly our fondness for destroying, concealing, and obfuscating information, but also our (much less common) love of *creating* information. So if I had to summarize this book in a phrase, it would be: 'Catch 22' meets 'Goedel, Escher, Bach' and 'Gravity's Rainbow' On the other hand, you can also read 'Cryptonomicon' as a Tom Clancy novel, inspired by Eric Temple Bell's 'Men of Mathematics', and written in haste by Mr. Clancy during an acute febrile illness while watching reruns of 'World at War' on cable TV. Many readers of sci.crypt will either have a Father or be a Father, so either way, with Father's Day coming up, it's time to go to the bookstore. Happy information-processing --- John Sidles (PS: I do not know and have never met Mr. Stephensen ... I'm just a fan of his novels.) -- From: [EMAIL PROTECTED] Subject: Re: Hello I am paper, please read me. Date: Thu, 13 May 1999 22:28:15 GMT snip Since Deck A is used in numerical order A(1),, A(i),..., A(n) and A contains all values from 1 to n Not in any given order!!! let deck A' be a simple ordered deck. A'(i)=i, now construct B' as follows B'(i) =C(., i) Not true for N! - 1 cases!!! then B'(i) = B(A(i)). So I now have an isomorphic system to A,B and use it to conduct my stream generation. Same as above... The fact that there is even/odd paterns is not exploitable because after many shuffles the odd/even ness disapears, and is random. Since the chances of having a lsb of 1/0 has a probability of 1/2 you can't predict the even oddness. And since you don't know deck B you can't tell if deck A has even/odd, odd/even or etc.. Can you post more details please? BTW, I already know the key schedule stinks, and the shuffle algorithm could be better. Any ideas? Tom -- PGP public keys. SPARE key is for daily work, WORK key is for published work. The spare is at 'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at 'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first! --== Sent via Deja.com http://www.deja.com/ ==-- ---Share what you know. Learn what you don't.--- -- From: Jim Felling [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] Subject: Re: Hello I am paper, please read me. Date: Thu, 13 May 1999 18:05:35 -0500 Please note that I am using A and B after the key setup phase is done. [EMAIL PROTECTED] wrote: snip Since Deck A is used in numerical order A(1),, A(i),..., A(n) and A contains all values from 1 to n Not in any given order!!! You are correct as to the fact that they are not in any given order, but they are USED in a specific order, as A is used as follows first A(1) is generated, then A(2) and so on. let deck A' be a simple ordered deck. A'(i)=i, now construct B' as follows B'(i) =C(., i) Please note that I am referring not to B, but to B' -- this is a definition. B'(i) = 0 XOR B(A(i)) by your
Cryptography-Digest Digest #549
Cryptography-Digest Digest #549, Volume #9 Fri, 14 May 99 02:13:03 EDT Contents: Toy Function (post didn't work) ([EMAIL PROTECTED]) Re: TwoDeck solution (but it ain't pretty) (David A Molnar) Re: On Contextual Strength (John Savard) Re: Thought question: why do public ciphers use only simple ops like shift and XOR? (John Savard) Re: Thought question: why do public ciphers use only simple ops like (Bryan Olson) Re: Lemming and Lemur ([EMAIL PROTECTED]) Re: Lemming and Lemur: New Block and Stream Cipher ("Craig Clapp") From: [EMAIL PROTECTED] Subject: Toy Function (post didn't work) Date: Fri, 14 May 1999 04:12:23 GMT Obviously my first post didn't work.. Hmm I have a round function where a, b32 bits + addition (mod 2^32) ^ addition (mod 2) S[1024] Array S-Box R[32] Array of round keys for r = 0 to rounds A = A + (((B ^ R[2r]) * S[B 22]) ^ R[2r + 1]) (B,A) = (A,B) next r Where there are two permutations using round keys, and diffusion using an sbox. The multiplication is to ensure a higher rate of diffusion (while maintaining simplicity), and the shift is to use the more active bits as indexes. The diffusion is delayed by one round, but after about 16 rounds I dunno if it matters. The average hamming distance is 31.93 bits after 16 rounds (comparing plaintext from decrypt cipher text with 'random' keys). I used a blowfish style key schedule, which is heavily dependant on the round function. I also used a R[32] and R[33] for post white... Anyways, this cipher may (and is most likely) weak, the point I am trying to get to is Where would I start to analyze this? What could I poke at to exploit? I just want pointers on how to start. I have allready implemented this. And some empiracle testing (hamming distance),. Any pointers? Thanks, Tom -- PGP public keys. SPARE key is for daily work, WORK key is for published work. The spare is at 'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at 'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first! --== Sent via Deja.com http://www.deja.com/ ==-- ---Share what you know. Learn what you don't.--- -- From: David A Molnar [EMAIL PROTECTED] Subject: Re: TwoDeck solution (but it ain't pretty) Date: 14 May 1999 04:09:18 GMT [EMAIL PROTECTED] wrote: This is not a question which an aspiring cryptographer should ask after posting his phone number... Why not? They have to know where to send the money :) combine digital cash with alt.anonymous.messages and a remailer network, and we can get around that tiny little problem. Just kidding -David -- From: [EMAIL PROTECTED] (John Savard) Subject: Re: On Contextual Strength Date: Fri, 14 May 1999 04:35:26 GMT Bryan Olson [EMAIL PROTECTED] wrote, in part: I want to reject ciphers if there exists a tractable break, without regard to whether an adversary may know or discover that break. No. I mean what I wrote. I'd want to reject such ciphers too. However, I am helpless to reject a cipher for which I do not know the break, or of the break - and my adversaries are smarter than I am. If a cipher is strong under the idea I proposed, then _no_ adversary can break it since a break does not exist. So you do mean this. And you are correct - that's a good definition of "strong". But we don't know if tractable breaks exist that we don't know about. We don't _even_ know if tractable breaks exist that we don't know about, but our adversaries know about. We only know about the breaks we know. Terry Ritter asks us to consider the possibility our adversaries know something we don't. You are now saying that you believe in following an even higher standard. I don't think he opposes this higher standard. What he opposes is the *lower* standard of assuming a cipher is strong if we, ourselves, don't know the break. And that lower standard at least _appears_ to be the one followed in practice by the conventional academic cryptographic community. Plus a fudge factor - I tend to think this is unavoidable, even if it could be made a little larger - but Mr. Ritter appears to be seeking to reject that practice completely. Well, I think that even his multi-cipher proposal is just a way of getting a bigger fudge factor - but a _much_ bigger fudge factor without a correspondingly large sacrifice of processing time. John Savard ( teneerf- ) http://members.xoom.com/quadibloc/index.html -- From: [EMAIL PROTECTED] (John Savard) Subject: Re: Thought question: why do public ciphers use only simple ops like shift and XOR? Date: Fri, 14 May 1999 04:23:02 GMT [EMAIL PROTECTED] (Terry Ritter) wrote, in part: We *can't* build in "safety factors" if we don't know that anything is strong. We don't. You assume something