Cryptography-Digest Digest #913, Volume #10 Sun, 16 Jan 00 06:13:01 EST Contents: Crypto Regulations (Guy Macon) Chosen/Known/Biased Plaintext (Guy Macon) Re: Chosen/Known/Biased Plaintext (fvw) Re: Chosen/Known/Biased Plaintext ("Douglas A. Gwyn") Re: Forward secrecy for public key encryption (Scott Contini) Re: LSFR ("Marty") Distributed.net completes CSC challenge ("dave avery") Re: Crypto Regulations ("Ryan Phillips") Cryptanalysis of R.A.T (Scott Contini) can someone encrypt for me? (Cutedoggy99) Re: Changing ARC4's State-Space Size ("r.e.s.") Re: A Hash Function Application (Mok-Kong Shen) Re: can someone encrypt for me? (Guy Macon) Re: Cracking DES (Paul Schlyter) ---------------------------------------------------------------------------- From: [EMAIL PROTECTED] (Guy Macon) Subject: Crypto Regulations Date: 15 Jan 2000 23:19:36 EST I was just wodering; if a commercial vendor keeps most of his code secret but publishes the source code for just the crypto algorithm, would he be free to export his product without restriction? ------------------------------ From: [EMAIL PROTECTED] (Guy Macon) Subject: Chosen/Known/Biased Plaintext Date: 15 Jan 2000 23:30:41 EST While searching around trying to learn, I ran into the occasional reference to Chosen Plaintext, Known Plaintext, and Biased Plaintext (biased meaning that the attacker knows that some bit patterns cannot be in the plaintext (No FF bytes in pure 7 bit ASCII) or some way that the plaintext is correlated (Q followed by U) - a good encryption system should be resistant to all three. My question is whether Chosen Plaintext is better than Known Plaintext for mounting an attack. What are the practical differences in real life? ------------------------------ From: [EMAIL PROTECTED] (fvw) Subject: Re: Chosen/Known/Biased Plaintext Reply-To: [EMAIL PROTECTED] Date: Sun, 16 Jan 2000 04:45:09 GMT In <85rhhh$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote: > >While searching around trying to learn, I ran into the >occasional reference to Chosen Plaintext, Known Plaintext, >and Biased Plaintext (biased meaning that the attacker >knows that some bit patterns cannot be in the plaintext >(No FF bytes in pure 7 bit ASCII) or some way that the >plaintext is correlated (Q followed by U) - a good >encryption system should be resistant to all three. > >My question is whether Chosen Plaintext is better than >Known Plaintext for mounting an attack. What are the >practical differences in real life? Yes, chosen plaintext is better than know plaintext. This is because with most algorithms certain plaintexts give more info about the key than others. Note there are also adaptive-chosen-plaintext attack's (you can encrypt something, study it, than encrypt something else you chose on the basis of your study.... repeat), chosen-ciphertext attack (you get to choose the ciphertext and get the corresponding cyphertext), Chosen-key-attack (You have some knowledge about the relationship between different keys. According to Applied crypto (A book I can definately advise), this is "Strange, obscure, not very practical and discussed in section 12.4"). And, last, and least too I guess, cyphertext-only attack. Not nice. -- Frank v Waveren [EMAIL PROTECTED] ICQ# 10074100 ------------------------------ From: "Douglas A. Gwyn" <[EMAIL PROTECTED]> Subject: Re: Chosen/Known/Biased Plaintext Date: Sun, 16 Jan 2000 05:52:34 GMT Guy Macon wrote: > My question is whether Chosen Plaintext is better than > Known Plaintext for mounting an attack. As usual, it depends on the specific cryptosystem. A classic example was the identification of a code group as meaning one of two enemy bases. An attack was ordered against one of the bases, and when the attack was reported in that code it was now clear which base the group meant. More generally, consider encrypting each of the following (chosen) PTs: 0000000000000000000 1000000000000000000 0100000000000000000 0010000000000000000 0001000000000000000 etc. The difference between the first CT and each other CT characterizes the effect of each input bit. (We used to call this "tickling" the system.) ------------------------------ From: [EMAIL PROTECTED] (Scott Contini) Subject: Re: Forward secrecy for public key encryption Date: 16 Jan 2000 05:57:24 GMT In article <85rb0t$sl$[EMAIL PROTECTED]>, David Wagner <[EMAIL PROTECTED]> wrote: >In article <[EMAIL PROTECTED]>, >lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote: >> The latter idea was proposed by Adam Back on the Cypherpunks list on >> May 31, 1998: >> http://www.inet-one.com/cypherpunks/dir.1998.05.25-1998.05.31/msg00171.html >> >> The ensuing discussion did not seem very promising, though. It was hard >> to find a scheme where the key holder had a significant edge. >> >> He needs to be able to compute discrete logs efficiently while making >> sure that an attacker who may have vastly greater resources could not >> factor the modulus or compute discrete logs. > >Here is an idea for an improvement which I didn't see on cypherpunks. > >Adam's original scheme exploits the gap in complexity between factoring >n=pq and taking discrete logs mod p,q. The problem is that there's >not a big enough gap between the two: we'd like to use a 1024-bit n for >adequate security, but then taking discrete logs mod 512-bit primes is >too hard for routine use. > >But what if we choose n as the product of, say, four primes, n=pqrs? >I *think* that known factoring algorithms aren't any better at factoring >product-of-four-prime composites than they are at factoring RSA-composites >of the same size. If I got that right, we'd only need to do discrete >logs mod 256-bit primes to use a 1024-bit n, and that sounds a little >more realistic. > >Can any of our resident factoring experts confirm or refute this? The running time to find a factor p with ECM is order e ^ { (1 + o(1)) sqrt[ 2 * log p * log log p ] } Using ECM to find a 256-bit prime factor is certainly faster than using number field sieve to factor a 1024-bit number. To compute a discrete log modulo p using the linear sieve or the the gaussian integer sieve, it takes order: e ^ { (1 + o(1)) sqrt[ log p * log log p ] } So there still is a gap, but maybe not insurmountable for the size numbers you are suggesting (256-bit primes). Of course, discrete logs can asymptotically be computed faster using the number field sieve discrete log alg, but according to Antoine Joux and Reynald Lercier, in practice it doesn't seem to pass up the other algorithms to about 100 digits (I downloaded a presentation by them from a Waterloo web site). Ok here are some stats which also come from Joux's and Lercier's presentation. 256-bits is approx 78 digits. In 1996, D. Weber used the Gaussian Integer sieve to solve a discrete log modulo a 85-digit prime in 30 mips years. A 78-digit prime should be approx 1/5 times as hard, so a 78-digit prime should take about 6 mips years. What about ECM? Near the end of last year (1999), Nik Lygeros and Michel Mizony posted a record factorisation with ECM - a 127-digit composite was factored into a 54-digit prime and a 73-digit prime. I don't see a CPU time on the posting, which is available at: http://www.loria.fr/~zimmerma/records/p54 However, finding a 78-digit prime should be order 4000 times harder than finding the 54-digit prime. I haven't read Adam Back's idea, but I would think that the gap between solving discrete logs modulo a 256-bit prime and discovering a 256-bit factor of a 1024-digit number is not large enough for a security application. It also should be pointed out that finding the discrete logs can be done, but it takes some effort - 5 mips years is not negligible! And on top of that, you need to be able to solve a reasonably large matrix modulo p - 1 , which is not so easy. Scott ------------------------------ Reply-To: "Marty" <[EMAIL PROTECTED]> From: "Marty" <[EMAIL PROTECTED]> Subject: Re: LSFR Date: Sat, 15 Jan 2000 23:25:56 -0800 Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]... > Marty wrote: > > A fairly easy approach that keeps the logic fairly simple is to use a > > group of LSFR's that have relatively prime periods and are short > > enough to have reasonable sized lookup tables. Just clock them > > in parallel. Knuth, Vol 2 gives an algoritm for reconstructing the > > original count in the section on modular arithmetic. > > As far as that goes, you could run a bunch of rings each of which > circulates a single "1" bit one position per tick. If the rings > have relatively prime sizes, and sampling determines where the > "1" bit is in each ring, the CRT will tell you how many ticks > since the previous sample. Yep, that is sort of the ultimate in simplicity though the approach, being a "one-hot" state machine design, is resource intensive. The proposed approach though is nearly as state efficient as the original LSFR and while it requires more taps, has the same high speed clocking capabilites. -Marty ------------------------------ From: "dave avery" <[EMAIL PROTECTED]> Reply-To: "dave avery" <[EMAIL PROTECTED]> Subject: Distributed.net completes CSC challenge Date: Sun, 16 Jan 2000 00:56:53 -0700 (MST) Greetings! I'm very proud (and quite relieved) to announce that distributed.net has successfully met the CS Communications & Systems CSC encryption challenge. The key was submitted to CS Communications & Systems just moments ago. At 06:26:52 on 01/16/00, we received a success key, 00438EF36FE3FC21. I haven't contacted the user yet, so I can only say that the computer that found the machine was a Sparc box running Solaris and version v2.8002 of the client. Users can expect an official press release with far more information and statistics within a few hours. Please standby for more details. Thanks again for all your support and dedication. Daniel Baker [EMAIL PROTECTED] ------------------------------ From: "Ryan Phillips" <[EMAIL PROTECTED]> Subject: Re: Crypto Regulations Date: Sun, 16 Jan 2000 00:05:20 -0800 With the new crypto regulations you can do that: Swiped from Mike Rosings post: 3. Also in §740.13, to, in part, take into account the "open source" approach to software development, unrestricted encryption source code not subject to an express agreement for the payment of a licensing fee or royalty for commercial production or sale of any product developed using the source code can, without review, be released from "EI" controls and exported and reexported under License Exception TSU. .... To qualify, exporters must notify BXA of the Internet location (e.g., URL or Internet address) or provide a copy of the source code by the time of export. These notifications are only required for the initial export; there are no notification requirements for end-users subsequently using the source code. Notification can be made by e-mail to [EMAIL PROTECTED] Guy Macon wrote in message <85rgso$[EMAIL PROTECTED]>... > >I was just wodering; if a commercial vendor keeps most of his code secret >but publishes the source code for just the crypto algorithm, would he >be free to export his product without restriction? > ------------------------------ From: [EMAIL PROTECTED] (Scott Contini) Subject: Cryptanalysis of R.A.T Date: 16 Jan 2000 08:26:09 GMT Earlier this week, a cipher called "R.A.T." was posted on this newsgroup. This cipher is very weak, and I will show here how to cryptanalyze it. I remark that somebody else named Poncho gave an argument that it is weak, but my attack is simpler. The original positing of the R.A.T. cipher is at the end of this post. My attack is a known plaintext attack - I assume you know plaintexts and their corresponding ciphertexts. However, to simplify explanation, I will present it as a chosen plaintext attack, and I leave it to you as an exercise to convert it to known plaintext. The attack is essentially the same in both forms. Here is (one reason) why the R.A.T. cipher is weak: Whenever a ciphertext byte equals its plaintext byte, you learn one byte of the key. Here is how the cipher algorithm works ( "^" means exclusive or): initialise: A[0] = 0, B[0] = 128 for i = 1 to the number of plaintext bytes { Let X[i] = i'th plaintext byte A1 = X[i] ^ key[ B[i-1] ] B[i] = A1 ^ key[ A[i-1] ] output B[i] as the i'th byte of the ciphertext A[i] = A1 } The key is a permutation of 0, .., 255 (the author also specifies that it has no fixed points, but the exact key generation algorithm is not given). In general, at iteration i we have: B[i] = X[i] ^ key[ B[i-1] ] ^ key[ A[i-1] ] A[i] = X[i] ^ key[ B[i-1] ] For simplicity of explanation, we will assume all the input bytes are 0 (this assumption is not needed). In this case, we have B[i] = key[ B[i-1] ] ^ key[ A[i-1] ] A[i] = key[ B[i-1] ] Suppose the i'th byte of the ciphertext is 0 (i.e. B[i] = 0). Then 0 = key[ B[i-1] ] ^ key[ A[i-1] ] Since the key is a permutation, we must have that B[i-1] equals A[i-1] But, we also know that A[i-1] = key[ B[i-2] ] So, substituting the previous equations, we have: B[i-1] = key[ B[i-2] ] Remember that the B values are ciphertext values that we see as output. So we know B[i-1] and B[i-2] , and hence we now know key[ B[i-2] ]. This is the first attack that came to my mind. There may be simpler attacks, but this shows that R.A.T. is a very weak cipher and should not be used in any security application. Scott ======================================================================== ======================================================================== ======================================================================== >From [EMAIL PROTECTED] Sat Jan 15 16:39:42 EST 2000 Article: 56990 of sci.crypt Path: news.usyd.edu.au!news1.optus.net.au!optus!intgwpad.nntp.telstra.net!newsfeed.berkeley.edu!ihug.co.nz!news.tig.com.au!p15-nas7.syd.ihug.com.au!satan From: Jeff Lockwood <[EMAIL PROTECTED]> Newsgroups: sci.crypt Subject: My Encryption system Date: Sat, 15 Jan 2000 12:01:38 +1100 Organization: The Internet Group (Sydney) Lines: 89 Message-ID: <[EMAIL PROTECTED]> NNTP-Posting-Host: p15-nas7.syd.ihug.com.au Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Server-Date: 15 Jan 2000 01:01:23 GMT X-Sender: [EMAIL PROTECTED] Xref: news.usyd.edu.au sci.crypt:56990 Description of my R.A.T. encoding and decoding system Notes: all values and variables mentioned in this document will be single byte quantities , with values ranging from 0-255. the key is an array of 256 bytes; containing all all the possible values, sorted into a random order, with one extra requirement: the value contained in each cell of the array cannot be the same as the index number of the cell eg: cell 0 cannot contain 0, cell 1 cannot contain 1 ,... Variables: X This contains the data byte to be encoded A This is used as an index into the key array B This is used as an index into the key array, and for the encoded output byte. A1 This is used for temporary storage B1 This is used for temporary storage The Encode function: 1) Initialise variable A with the value 0 and B with 128. 2) read 1 byte into X. 3) The value in X is XORed with the byte in the key indexed by B, and the result is stored in A1. 4) The value in A1 is XORed with byte in the key indexed by A, and the result replaces the value stored in B. 5) Write out the the byte in B 6) Replace the value in A with the value in A1 7) Loop back to step 2 until all bytes have been encoded. The Decode function: 1) Initialise variable A with the value 0 and B with 128. 2) read 1 byte into B1. 3) The value in B1 is XORed with the byte in the key indexed by A, and the result replaces the value in A. 4) The value in A is XORed with the byte in the key indexed by B, and the result is stored in X. 5) write out the value in X 6) replace the value in B with the value in B1. 7) loop back to step 2 until all bytes have been decoded. Aditional notes: The above functions are relesed into the public domain. You may use them in any program (even commercial ones). they may also implemented directly in hardware. I place no restrictions upon their use. I also release this document into the public domain and permit distribution without any restrictions. Jeff Lockwood January 8 2000 I have also written a simple C program to demonstrate these routines, and posted it in sci.crypt on the 8th of january Jeff Lockwood <[EMAIL PROTECTED]> PGP public key: homepages.ihug.com.au/~satan/pgpkey.asc ------------------------------ From: [EMAIL PROTECTED] (Cutedoggy99) Subject: can someone encrypt for me? Date: 16 Jan 2000 08:48:27 GMT Could someone please encrypt this url address for me in crypto version 0: http://www.cutedoggy.com/sponsors/ ------------------------------ From: "r.e.s." <[EMAIL PROTECTED]> Subject: Re: Changing ARC4's State-Space Size Date: Sun, 16 Jan 2000 01:39:09 -0800 "r.e.s." <[EMAIL PROTECTED]> wrote ... [...] : as far as I know, there have been no published : analyses of the Solitaire algorithm. [...] Oops... Paul Crowley posted his empirical findings of some apparent bias in Solitaire, and also pointed out the irreversibility of the algorithm. (Maybe I was thinking of the analyses that its author has hinted may be forthcoming.) r.e.s. ------------------------------ From: Mok-Kong Shen <[EMAIL PROTECTED]> Subject: Re: A Hash Function Application Date: Sun, 16 Jan 2000 11:08:52 +0100 John Savard wrote: > > Each message sent is accompanied by a session key, sent in any > convenient encrypted form (by conventional public-key techniques, or > enciphered by a key-exchange-key which is also a shared secret). > > The large key is then encrypted by the session key, and then a one-way > hash is used to produce the actual long key used to encrypt the > current message. I guess that implemtnted/employed properly your scheme can be used in practical applications, i.e. when it is judged by the user to offer sufficient practical security (using some more or less 'subjectivity') for him. Typical problems with evaluating such schemes consist in my view in the fact that on the one hand it 'appears' not to be extremely secure (i.e. comparable to the currently 'established' 'very secure' ones) and on the other hand it seems difficult to 'compute' its security/insecurity because its design doesn't conform well enough with the 'mainstream' to offer easy/ready ways of discussions. That's why your idea isn't likely to be examined/scrutinized by the experts, I am afraid. M. K. Shen ------------------------------ From: [EMAIL PROTECTED] (Guy Macon) Subject: Re: can someone encrypt for me? Date: 16 Jan 2000 05:33:50 EST In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Cutedoggy99) wrote: > >Could someone please encrypt this url address for me > >http://www.cutedoggy.com/sponsors/ Sure! 9C5D8077ACFC40507512BD1AC17AEF7C235EE9D2A3CF6148B16A2213E0B71A56A382 I hope this helps... ------------------------------ From: [EMAIL PROTECTED] (Paul Schlyter) Subject: Re: Cracking DES Date: 16 Jan 2000 10:57:08 +0100 In article <[EMAIL PROTECTED]>, JPeschel <[EMAIL PROTECTED]> wrote: > [EMAIL PROTECTED] (Paul Schlyter) writes: > >> The only known way to crack single DES is by brute force: if you have >> one cleartext-cryptotext pair, try all possible keys until you >> encounter the correct key. > > It's not always necessary for an attacker to possess one cleartext- > cryptotext pair. OK, but then you must have some other way to determine whether you've obtained the correct cleartext or not. -- ================================================================ Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF) Grev Turegatan 40, S-114 38 Stockholm, SWEDEN e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED] WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch ------------------------------ ** FOR YOUR REFERENCE ** The service address, to which questions about the list itself and requests to be added to or deleted from it should be directed, is: Internet: [EMAIL PROTECTED] You can send mail to the entire list (and sci.crypt) via: Internet: [EMAIL PROTECTED] End of Cryptography-Digest Digest ******************************

- Cryptography-Digest Digest #913 Digestifier
- Cryptography-Digest Digest #913 Digestifier
- Cryptography-Digest Digest #913 Digestifier
- Cryptography-Digest Digest #913 Digestifier
- Cryptography-Digest Digest #913 Digestifier
- Cryptography-Digest Digest #913 Digestifier