Cryptography-Digest Digest #466
Cryptography-Digest Digest #466, Volume #14 Mon, 28 May 01 20:13:00 EDT Contents: Turbo Small Public Key Cryptosystem (Tom St Denis) Re: Fractionated Morse - Help (John Savard) Re: Medical data confidentiality on network comms (Tom McCune) Re: Essay on The need for a look at real life crypto (M.S. Bob) Random number generation. (Benjamin Johnston) Re: Random number generation. (Tom St Denis) Re: Euroean commision will recommend all citizens to use encryption in (Mok-Kong Shen) Re: Medical data confidentiality on network comms (Harris Georgiou) Re: Turbo Small Public Key Cryptosystem (Jack Lindso) Re: Turbo Small Public Key Cryptosystem (Tom St Denis) Re: Random number generation. (Benjamin Johnston) Re: Turbo Small Public Key Cryptosystem (Tony L. Svanstrom) Re: Good crypto or just good enough? (David Hopwood) Re: Quantum Computers with relation to factoring and BBS (Charles Blair) Re: Quantum Computers with relation to factoring and BBS (AY) Re: Turbo Small Public Key Cryptosystem (Tom St Denis) Re: question on Luby's book (Charles Blair) From: Tom St Denis [EMAIL PROTECTED] Subject: Turbo Small Public Key Cryptosystem Date: Mon, 28 May 2001 21:44:18 GMT Ok this is just for fun (so keep that in mind) I wrote a really super small PK system for *NIX today (in about 1.5 hrs) It uses DH and RC4 to encode/decode messages. It doesn't do signatures (what's the point?). It's very compact... in linux it builds to about 32kb in size and is very fast. It doesn't do ascii armor or silly headers etc. (So it's probably very vulnerable if you try to decode /dev/urandom as a message). I've barely tested it (it does encrypt/decrypt afaik). http://tomstdenis.home.dhs.org/tc.zip This is by no means a replacement for PGP since it lacks alot (say signatures, key'ids and such, but I feel those are meaningless anyways!) The source is not commented but it's very easy to follow. It's mostly modular and somewhat organized (comes with a makefile that installs it in /usr/local/bin/) Tom -- From: [EMAIL PROTECTED] (John Savard) Subject: Re: Fractionated Morse - Help Date: Mon, 28 May 2001 21:43:31 GMT On 28 May 2001 12:53:26 -0700, [EMAIL PROTECTED] (Charles Eastwood) wrote, in part: Can anyone point me to references on breaking fractionated Morse messages? I think there are at least two types. In one the Morse string, including X for letter breaks, is divided into groups of three characters. A table is then used to turn each group into one letter of the CT. In the other system a string of numbers is formed based on the number of dots and dashes in each letter. That string of numbers is transposed, and then used to generate a new Morse string which is then converted to letters. I am interested in attacks on both systems. Well, the book Cryptanalysis for Microcomputers from TAB Books talks about the first system. The second system is discussed in Gaines, and since as illustrated the only key is the length of the group over which the lengths are reversed, it can be solved by brute force by hand. Both systems are described on my web site, but their cryptanalysis is not discussed. John Savard http://home.ecn.ab.ca/~jsavard/frhome.htm -- Crossposted-To: comp.security.misc From: Tom McCune [EMAIL PROTECTED] Subject: Re: Medical data confidentiality on network comms Date: Mon, 28 May 2001 21:47:58 GMT In article V7yQ6.46$[EMAIL PROTECTED], Roger Schlafly [EMAIL PROTECTED] wrote: You could use N bits for some large value of N, and those keys will still be accessible by human beings. And usually low-level employees. The general public won't have access to the encrypted data anyway. Not really - this HCFA ruling applies to patient data transferred over the internet. Once its on the internet, it may never disappear, and can possibly wind up anywhere, including such broad government tracking as Carnivore or Echelon So what is the scenario in which 2048-bit RSA is better than 1024 bit RSA (or DH)? That maybe 30 years from now an employee gains access to the encrypted files and a lot of supercomputer time, but not to the keys? And then breaks the RSA key for the purpose of exposing someone as having had some childhood disease? It seems very farfetched to me. I wouldn't place any bets on how secure a 1024 bit key will be in 20 years. And if one of these individuals is then running for US President, or US Senate, is in a sensitive government or corporate position, etc., there could be very significant damage. But regardless of what damage is seen as possible to then occur, we are required to protect this legally and ethically. For what it is or isn't worth, I wouldn't trust a 1024 bit key for such long term needs. For internal purposes, it is a different situation, but these rules apply to the use of the Internet. Again, I
Cryptography-Digest Digest #466
Cryptography-Digest Digest #466, Volume #13 Sat, 13 Jan 01 21:13:01 EST Contents: Is this triple-DES variant secure? (Kenneth Almquist) Re: Big block DES construct. (Benjamin Goldberg) Re: Is this triple-DES variant secure? (Benjamin Goldberg) Re: Security proof (Benjamin Goldberg) Re: On cryptographic proofs and their (lack) of concreteness (Terry Ritter) Yet another cipher idea (Benjamin Goldberg) Re: The Word Problem and Group Isomorphism ("John A. Malley") Re: NSA and Linux Security (Greggy) Re: Security proof (David Wagner) Re: Security proof (David Wagner) Re: The Word Problem and Group Isomorphism (David Wagner) Re: Is this triple-DES variant secure? (David Wagner) From: [EMAIL PROTECTED] (Kenneth Almquist) Subject: Is this triple-DES variant secure? Date: 13 Jan 2001 20:54:58 GMT If triple-DES is used in CBC mode, then it is not possible to pipeline the process because the output of one triple-DES encryption must be xor-ed with the input to the next triple-DES encryption. An alternative is to xor each intermediate encryption values with the preceding intermediate value. The following pseudocode shows what I mean: temp := E(P[i], K1) xor F1[i] F1[i+1] := temp temp := E(temp, K2) F2[i+1] := temp C[i] = E(temp xor F2[i], K1) In this code, E(text, key) is DES encryption, D(text, key) is DES decryption, P and C are the plaintext and cyphertext, respectively, K1 and K2 are DES keys which together form the triple-DES key, and F1 and F2 are feedback variables. This can be pipelined very deeply. The dependency between pipeline stages is that an xor operation must be performed to compute F1[i+1] from F1[i]. If the time required by this xor (and associated wiring delays) is 1/4 of the time required for a DES round, we could create a 192 stage pipeline resulting in very high throughput. High throughput is no good if the encryption can be broken. In fact, the above scheme is vulnerable to the following chosen plaintext attack. We start by guessing the value of K1. To see if we have guessed correctly, we set P[i] = P[i+1] = D(0, K1). Then F1[i+1] = F1[i], so F2[i+1] = F2[i]. Therefore C[i+1] = E(F2[i+1] xor F2[i], K1) = E(0, K1). If this last equation holds, then we have almost certainly guessed K1 correctly. There are 2**56 possible values for K1, and since triple-DES works on 64 bit blocks, the cypher is presumably rekeyed every 2**32 blocks. Since it takes two blocks to check a guess for K1, we would expect to get a match about once every 2**57 blocks, meaning we recoved one K1 value for every 2**25 keys. Getting the value of K2 is a problem if we don't know F1 and F2, but perhaps a differential attack could get us K2 in fewer than 2**112 steps. To avoid this chosen plaintext attack, I propose swapping K1 and K2 on alternate rounds. In pseudocode, this looks like: temp := E(P[i], K1) xor F1[i] F1[i+1] := temp temp := E(temp, K2) F2[i+1] := temp C[i] = E(temp xor F2[i], K1) temp := E(P[i+1], K2) xor F1[i+1] F1[i+2] := temp temp := E(temp, K1) F2[i+2] := temp C[i+1] = E(temp xor F2[i+1], K2) A variant of the previously described attack could be used against this construct, but it would require guessing *both* K1 and K2, so it would have no advantage over an exhaustive search. Can anyone suggest another way to attack this construct? Kenneth Almquist -- From: Benjamin Goldberg [EMAIL PROTECTED] Subject: Re: Big block DES construct. Date: Sat, 13 Jan 2001 21:28:44 GMT Whaa (boo hoo)! Looking around, I discovered the page http://www.io.com/~ritter/NEWS/LBDNEWS.HTM and learned that the 2x2 DES construct I gave is indeed susceptible to meet-in-the-middle attacks. However, although Nx2 DES can be attacked by MIM, Nx3 DES seems not to be susceptible. However, since Nx3 DES is no faster than 3DES, there does not seem to have been any more research on that construct. -- Power interrupts. Uninterruptable power interrupts absolutely. [Stolen from Vincent Seifert's web page] -- From: Benjamin Goldberg [EMAIL PROTECTED] Subject: Re: Is this triple-DES variant secure? Date: Sat, 13 Jan 2001 21:45:41 GMT Kenneth Almquist wrote: [snip] The following pseudocode shows what I mean: temp := E(P[i], K1) xor F1[i] F1[i+1] := temp temp := E(temp, K2) F2[i+1] := temp C[i] = E(temp xor F2[i], K1) In this code, E(text, key) is DES encryption, D(text, key) is DES decryption, P and C are the plaintext and cyphertext, respectively, K1 and K2 are DES keys which together form the triple-DES key, and F1 and F2 are feedback variables. There is a problem with how this psuedocode is written. You should avoid using and reusing a thing like "temp.
Cryptography-Digest Digest #466
Cryptography-Digest Digest #466, Volume #12 Thu, 17 Aug 00 10:13:01 EDT Contents: Re: Cracking RC4-40 in FPGA hardware (Paul Rubin) Re: New quantum computer - any details? (Gordon Walker) Re: New Stream Cipher like SEAL ([EMAIL PROTECTED]) Re: OTP using BBS generator? (Mok-Kong Shen) Re: OTP using BBS generator? (Mok-Kong Shen) Re: blowfish problem (John Hascall) Re: 215 Hz five-qubit quantum processor (Dale Pontius) Re: PGP Algorithm (Sander Vesik) Re: PGP Algorithm (Sander Vesik) Re: Is this Diffie-Hellman modification safe? ("Scott Fluhrer") Re: OTP using BBS generator? (Mok-Kong Shen) From: [EMAIL PROTECTED] (Paul Rubin) Subject: Re: Cracking RC4-40 in FPGA hardware Date: 17 Aug 2000 12:09:59 GMT In article 8ngap1$86k$[EMAIL PROTECTED], [EMAIL PROTECTED] wrote: In article 8mco74$erk$[EMAIL PROTECTED], [EMAIL PROTECTED] wrote: Each cycle requires a memory read and a pair of 8 bit adds, so 10ns looks like a good estimate. Then we have 10 usec/key, or 10^5 keys per second. 2^40 is about 10^12, so even with one such piece of hardware we have 10^7 seconds, or about 2800 hours to search all keys. We expect success on the average in 1/2 this time, or 1400 hours. Sorry guys, I've seen your discussion too late. I'd like to say that it is possible to achieve the speed of 280.000 key/sec on Pentium II/333 (or 45 days to finish 2^40 keys) when cracking simple RC4 (like PDF implementation) and 180.000 keys/sec (or 70 days) when cracking RC4+MD5 (like MS Word does). It means that on _ONE_ modern P III/1000 the average time to crack RC4-40 is one week, not 1400 hours ;-). Remember that the Xilinx chip had 4 of those blocks with 1400 hour average crack time. So the 4 blocks working together crack in 350 hours on average--half the speed of that PIII/1000. That means a machine with 50 Xilinx chips can *always* (worst case) crack in under 24 hours and you'd need 25 PIII's to do the same. But the Xilinx chips cost about 10 USD each and use a lot less power than the Pentiums. The 50-chip Xilinx machine can probably be built in a single PC-sized box (card cage with a few wire-wrapped boards) with materials cost equal to not much more than one or two PIII machines. To the person who was doing this project: any news? -- From: Gordon Walker [EMAIL PROTECTED] Subject: Re: New quantum computer - any details? Date: Thu, 17 Aug 2000 13:20:26 +0100 On 16 Aug 2000 16:23:54 GMT, Sander Vesik [EMAIL PROTECTED] wrote: How long is 'realistical length' and what constitutes a practical quantum computer? A qc that can crack say 512 bit RSA in say 4 weeks is practical, but not overly threatening for 16/32 kbit keys that are still realistically long. Even if you speed it up 4 times, longer keys are still realistic. Beyond that, we need something else than RSA. But by my limited understanding, a quantum computer can bring down the order of complexity of the factoring problem. Previously adding one or two bits to the key required a vast increase in processing power to break it. With an improved O() value for the solving machines you have the situation where the cracking machines are chasing keylength much more quickly and that just a few years research might allow the hardware to catch up with the keylength you have chosen. -- Gordon Walker -- From: [EMAIL PROTECTED] Subject: Re: New Stream Cipher like SEAL Date: Thu, 17 Aug 2000 12:48:35 GMT In article [EMAIL PROTECTED], [EMAIL PROTECTED] (Mark Wooding) wrote: [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: hello tom one question why in your c code return (x(r31)) | (x((32-r)31)); you do 31 the processor realize the mask automatically no ??? No. In C, if you shift a value by its bit length or more, the behaviour is undefined. Some processors will give a zero result for a shift by a value greater than the word length. Others will truncate the the shift amount. Tom's got this one right. OPSO for sc1.dat using bits 23 to 32157695 54.433 1. Ouch! That's really bad. Sometimes it outputs poorly, but for the most part it appears ok. I will have to look into it more. Tom Sent via Deja.com http://www.deja.com/ Before you buy. -- From: Mok-Kong Shen [EMAIL PROTECTED] Subject: Re: OTP using BBS generator? Date: Thu, 17 Aug 2000 15:39:49 +0200 Tim Tyler wrote: : Bryan Olson wrote: : : Many times on sci.crypt people have objected to the proof of : : perfect secrecy for the OTP based on the fact that the zero : : vector is one of the possible keys. The false logic goes : : something like: since the OTP is provably secure, and zero : : is a legal key, then encrypting with the zero key must be : : secure, and since it obviously isn't the proof must be : : wrong. : : : The OTP theorem d
Cryptography-Digest Digest #466
Cryptography-Digest Digest #466, Volume #10 Fri, 29 Oct 99 18:13:05 EDT Contents: Re: announcement: steganography program "steghide" (Tom St Denis) Bruce Schneier's Crypto Comments on Slashdot (Bill Lynch) Re: ComCryption (SCOTT19U.ZIP_GUY) Re: Symetric cipher (Bill McGonigle) Re: Compression: A ? for David Scott (Clinton Begin) Re: Bruce Schneier's Crypto Comments on Slashdot (SCOTT19U.ZIP_GUY) Re: Disk wiping code or utility (Dan Day) Re: the ACM full of Dolts? (SCOTT19U.ZIP_GUY) Re: VXD Memory Allocator for Win9x (Paul Koning) Re: Symetric cipher (SCOTT19U.ZIP_GUY) Re: Bruce Schneier's Crypto Comments on Slashdot (jerome) From: Tom St Denis [EMAIL PROTECTED] Subject: Re: announcement: steganography program "steghide" Date: Fri, 29 Oct 1999 18:09:31 GMT In article [EMAIL PROTECTED], Stefan Hetzl [EMAIL PROTECTED] wrote: Hello, I have written a steganography program called "steghide". It is designed to be portable and configurable and features hiding data in bmp, wav and au files, blowfish encryption, MD5 hashing of passphrases to blowfish keys and pseudo-random distribution of hidden bits in the cover-data. It is copyrighted under the GNU General Public License. Steghide is written in ANSI C so the source code should compile on many systems. Binaries are available for Windows and Linux. It is available from: http://www.crosswinds.net/~shetzl/steghide/index.html Criticism is welcome. While I couldn't get the binaries off your site (too slow) I will take a peek at the source later. A quick comment or two.. 1. It's not usefull for general run-of-the-mill daily messaging. You need too many different pictures/sounds to make it usefull. 2. Software is not copyrighted under the GPL, they are protected under it. Tom Sent via Deja.com http://www.deja.com/ Before you buy. -- From: Bill Lynch [EMAIL PROTECTED] Subject: Bruce Schneier's Crypto Comments on Slashdot Date: Fri, 29 Oct 1999 13:30:06 -0500 VERY interesting read -- thank you Bruce for taking the time to do this: http://slashdot.org/interviews/99/10/29/0832246.shtml -- Bill -- From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) Subject: Re: ComCryption Date: Fri, 29 Oct 1999 19:53:15 GMT In article [EMAIL PROTECTED], [EMAIL PROTECTED] (John Savard) wrote: One "Dr. Richard Crandall of Apple Computer" is credited with suggesting, at a conference in 1998, an encryption idea called "ComCryption", where a key of n bits is used to select one of 2^n compression algorithms...since the result of compression appears random, the cipher might be secure. Do you know if these compression algorithms where one to one or not? I'll have to admit I don't think this is a particularly good idea. It's a fruitful original thought, which one can play with in some more pedestrian ways, such as Huffman coding with random, keyed code assignment as a simple subsitution without easily visible boundaries. But universal algorithms which are relatives of LZW start out by not compressing until they "learn" about the text, so an unknown algorithm of that type could still be guessed at...see if the characters make sense as 9 bits plus a flag bit; if something different comes along, see where the earlier string is that could fit here, and figure out how the following bits might point there. Anyhow, someone had been asking what had become of it. I suppose there is the difference between someone like Dr. Crandall - who threw out a potentially fruitful suggestion for creative thought - and others who, once thinking of an idea that doesn't happen to be really very practical, tirelessly advocate it as the cure for ingrown toenails. Gee did someone on here ask about it? David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE http://www.jim.com/jamesd/Kong/scott19u.zip http://members.xoom.com/ecil/index.htm NOTE EMAIL address is for SPAMERS -- From: [EMAIL PROTECTED] (Bill McGonigle) Subject: Re: Symetric cipher Date: Fri, 29 Oct 1999 14:38:03 -0400 In article [EMAIL PROTECTED], Emmanuel Drouet [EMAIL PROTECTED] wrote: Please, could you give me informations about several cryptosystems : Blowfish, CAST5 and SAFER Run, do not walk to amazon and get Bruce's "Applied Cryptography". :) Really, it's an excellent overview, and good enough for many 'engineers'. -Bill = [EMAIL PROTECTED] / FAX: (419) 710-9745 Dartmouth-Hitchcock Medical Center Clinical Computing -- From: Clinton Begin [EMAIL PROTECTED] Subject: Re: Compression: A ? for David Scott Date: Fri, 29 Oct 1999 18:47:04 GMT I think I found an interesting property of your compression scheme (and most likely all compression
Cryptography-Digest Digest #466
Cryptography-Digest Digest #466, Volume #9 Mon, 26 Apr 99 10:13:05 EDT Contents: Re: Prime Numbers Generator (David Kuestler) Re: WHy would ibm sniff?? ("Douglas A. Gwyn") Re: Prime Numbers Generator ("Douglas A. Gwyn") Re: 128 bit DES (Gurripato (x=nospam)) Re: 128 bit DES (Gurripato (x=nospam)) scramdisk for AMAN ("m. bell") Re: 128 bit DES (Reuben Sumner) Re: True Randomness The Law Of Large Numbers (Mok-Kong Shen) Re: How good is /dev/random... (Mok-Kong Shen) Re: RSA-Myth (Piso Mojado) Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO (Mok-Kong Shen) Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO (Mok-Kong Shen) Re: RSA-Myth ("Trevor Jackson, III") Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO (SCOTT19U.ZIP_GUY) From: David Kuestler [EMAIL PROTECTED] Subject: Re: Prime Numbers Generator Date: Mon, 26 Apr 1999 06:35:16 + "Douglas A. Gwyn" wrote: David Kuestler wrote: Paul Rubin wrote: Why not just store a bit map of where the primes are? 2^32 possible primes = 2^32 bits = 2^29 bytes = 512 MB. Good idea ( 2^31 if you only work with the odds = 269MB ). And even better, omit the multiples of 3, 5, 7, 11, etc. :-) I wonder where in the series the calculation/search efficiency would cross over the straight search efficiency, my guess is somewhere in the first 1000 primes ( CPU dependant/IO dependant/algorithm dependant/ oh gosh- everything depentant ;-) ). -- From: "Douglas A. Gwyn" [EMAIL PROTECTED] Subject: Re: WHy would ibm sniff?? Date: Mon, 19 Apr 1999 22:04:16 GMT John L Singleton wrote: I have seen many assertions that IBM 3COM and others have siffers. one question. WHY? I assume you mean, packet sniffers. If you want to keep an eye out for hacker traffic on your network, they could be useful. Anyway, they're easy to devise and are even shipped with some OSes. -- From: "Douglas A. Gwyn" [EMAIL PROTECTED] Subject: Re: Prime Numbers Generator Date: Mon, 26 Apr 1999 06:04:12 GMT David Kuestler wrote: Paul Rubin wrote: Why not just store a bit map of where the primes are? 2^32 possible primes = 2^32 bits = 2^29 bytes = 512 MB. Good idea ( 2^31 if you only work with the odds = 269MB ). And even better, omit the multiples of 3, 5, 7, 11, etc. :-) -- From: [EMAIL PROTECTED] (Gurripato (x=nospam)) Subject: Re: 128 bit DES Date: Mon, 26 Apr 1999 07:25:16 GMT On Fri, 23 Apr 1999 23:07:10 GMT, "Douglas A. Gwyn" [EMAIL PROTECTED] wrote: [EMAIL PROTECTED] wrote: DES only has a 56 bit key, so double des is 112. 3DES or triple des is considered secure but there are better ciphers check out ... "Better" how? Meaning perpahs that they are faster or more resistant to cryptanalysis. -- From: [EMAIL PROTECTED] (Gurripato (x=nospam)) Subject: Re: 128 bit DES Date: Mon, 26 Apr 1999 07:22:47 GMT On Sun, 25 Apr 1999 13:04:27 +, David Kuestler [EMAIL PROTECTED] wrote: "Gurripato (x=nospam)" wrote: DES is really 56 bits (the other 8 are just for parity checking). You could combine 2 DES keys, but thereĀ“s the chance of a man-in-the-middle attack. 3 DES has a combined key length of 56*3=168 meet-in-the middle Correction taken. Thanx -- From: "m. bell" [EMAIL PROTECTED] Subject: scramdisk for AMAN Date: Sat, 24 Apr 1999 21:14:59 -0500 looked at the program and docs and very interested. however, i noticed in the documentation that problems can occur when the program is installed and one runs a defrag. has this been resolved with the newest version, occur on all machines, occur every time one tries to defrag, any work around for the problem, etc? thanks mike -- From: [EMAIL PROTECTED] (Reuben Sumner) Subject: Re: 128 bit DES Date: 26 Apr 1999 07:50:32 GMT Reply-To: [EMAIL PROTECTED] On 22 Apr 1999 13:49:00 GMT, dino [EMAIL PROTECTED] wrote: Hi again I need some help. My customer ask a crypto application using 128 bit DES. I implemented a double DES with two 64 bit keys. Is that equivalent? If the answer is negative, is a triple DES with two 64 bit keys equivalent to a single 128 bit DES? I apologize for my poor english but i hope someone understand my question DES is a 64 bit block cipher with a 56 bit secret key. You might want a larger block size (all AES candidates have a 128 bit block size) or a longer key. One possibility that addresses both of these issues is a cipher called DEAL (an AES candidate). Essentially DEAL is a mode of operation for triple DES which provides a longer block size. References for DEAL can be found from the AES web pages. Reuben -- From: Mok-Kong Shen