Cryptography-Digest Digest #522
Cryptography-Digest Digest #522, Volume #14 Tue, 5 Jun 01 09:13:01 EDT Contents: Re: about DH parameters germain primes (Tom St Denis) Re: Def'n of bijection (Tom St Denis) Re: BBS implementation (Tom St Denis) Sophie Germaine Benefits for DH (Tom St Denis) Re: PRP vs PRF (was Luby-Rackoff Theorems) (Tom St Denis) Some questions on GSM and 3G (Arturo) Re: 2,2-multipermutation? (Tom St Denis) Re: 2,2-multipermutation? (Tom St Denis) Re: about DH parameters germain primes (Mark Wooding) PRP = PRF (TRUNCATE) (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: WEB PAGES (SCOTT19U.ZIP_GUY) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) White-Hat Security Arsenal http://white-hat.org/ (New book) (Avi Rubin) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: Def'n of bijection (Tim Tyler) Re: Def'n of bijection (Tim Tyler) Re: RSA's new Factoring Challenges: $200,000 prize. (my be repeat) (Bob Silverman) Re: Sophie Germaine Benefits for DH (Mark Wooding) From: Tom St Denis [EMAIL PROTECTED] Subject: Re: about DH parameters germain primes Date: Tue, 05 Jun 2001 08:47:39 GMT Mark Wooding [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... quequ [EMAIL PROTECTED] wrote: If p, (p-1)/2 both prime, then you can just use any g you please [other than 0, 1, and -1], and you'll get a very large order [at least (p-1)/2] It's right? Yes, it's right. I've tried a 1024bit germain prime P and the generator G set to (P-1)/2. Are these good parameters? (P - 1)/2 is a bit big. This won't affect security, but it can affect performance in some cases. In your case, I'd choose G = 4, which definitely has order (P - 1)/2. At least this way you know exactly what you're getting. On the other hand, I don't really believe in Sophie-Germain primes. They take too long to generate, and I don't see any practical advantage over Lim-Lee primes. Something that bugs me When you do (g^x)^y mod p, is g^x consider a new base wrt to the group the entire operation generates or is it simply g^xy mod p. Like if p=257, g=45, x=17,y=33 we get (g^x) mod p equal to 103, (103^33) mod 257 equal to 167 In the second step is 103 considered a new base? I'm thinking of an example where (g^x mod p) results in a base that generates a small group, for effect suppose g^x mod p = -1. Then -1^y mod p will be 1 or -1 depending on the lsb right? Well with a SG prime this cannot happen (well the -1 and 1 can occur). All bases will generate a huge group. That's one possible benefit? Tom -- From: Tom St Denis [EMAIL PROTECTED] Subject: Re: Def'n of bijection Date: Tue, 05 Jun 2001 08:49:33 GMT JPeschel [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... Tom St Denis [EMAIL PROTECTED] writes, in part: If you're a regular you should know to read what I say with a grain of salt. I.e be cautious because I tend to make mistakes. Espescially with math notation I haven't formally learnt yet. Reviewing, from time to time, the first few chapters from Menezes's book might be a good way to reinforce the notation. Beats being corrected. Good tip. Menezes's book is? HAC? Tom -- From: Tom St Denis [EMAIL PROTECTED] Subject: Re: BBS implementation Date: Tue, 05 Jun 2001 08:50:48 GMT Mark Wooding [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: How do I know it is not on a short or degenerate cycle? Because if it is, you've managed to factor the modulus. As I understand it, if you know the length of the cycle you only know factors of (p-1)(q-1) right? Tom -- From: Tom St Denis [EMAIL PROTECTED] Subject: Sophie Germaine Benefits for DH Date: Tue, 05 Jun 2001 09:35:20 GMT A question was raised whether Lim-Lee primes were better in terms of ease of generation and securtity versus a Sophie Germaine Prime. So we get our terminology all straight a Lim-Lee (LL) prime is one where it has several huge prime factors, a Sophie-Germaine (SG) prime is a prime of the form 2p + 1 where p itself is prime. As a contrived example I chose p=257, g=45. This isn't a LL or SG but shows off the point I started on earlier. Suppose we have one key x=66, the resulting base 45^66 mod 257 = 239 will only generate a group of 128 elements. While this is a contrived example a similar effect is possible with LL and SG primes. In an LL prime for example
Cryptography-Digest Digest #523
Cryptography-Digest Digest #523, Volume #14 Tue, 5 Jun 01 11:13:01 EDT Contents: Re: Def'n of bijection (Tim Tyler) Re: about DH parameters germain primes (Bob Silverman) Re: Def'n of bijection ([EMAIL PROTECTED]) Re: Keyed hash functions (Tim Tyler) Re: Def'n of bijection ([EMAIL PROTECTED]) Re: Def'n of bijection (SCOTT19U.ZIP_GUY) Re: Def'n of bijection (Tim Tyler) Re: Def'n of bijection (Tim Tyler) Re: Def'n of bijection ([EMAIL PROTECTED]) Re: PRP = PRF (TRUNCATE) (Scott Fluhrer) Re: Def'n of bijection ([EMAIL PROTECTED]) From: Tim Tyler [EMAIL PROTECTED] Subject: Re: Def'n of bijection Reply-To: [EMAIL PROTECTED] Date: Tue, 5 Jun 2001 13:00:06 GMT Tom St Denis [EMAIL PROTECTED] wrote: : JPeschel [EMAIL PROTECTED] wrote in message : Reviewing, from time to time, the first few chapters from Menezes's book : might be a good way to reinforce the notation. Beats being corrected. : Good tip. Menezes's book is? HAC? Very likely: HAC [http://cacr.math.uwaterloo.ca/hac/] - by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone -- __ |im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/ -- From: [EMAIL PROTECTED] (Bob Silverman) Subject: Re: about DH parameters germain primes Date: 5 Jun 2001 06:12:42 -0700 quequ [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... Hi, I've found this tip about Diffie-Hellman parameters: If p, (p-1)/2 both prime, then you can just use any g you please [other than 0, 1, and -1], and you'll get a very large order [at least (p-1)/2] It's right? Ask yourself: what are the *possible* orders of the group? 0 is not in the group. The set {1,-1} forms a sub-group whose elements have order 2 and whose index is (p-1)/2. What other sub-groups are there? Look up Lagrange's Theorem. -- Subject: Re: Def'n of bijection From: [EMAIL PROTECTED] Date: 05 Jun 2001 09:44:10 -0400 Tim Tyler [EMAIL PROTECTED] writes: [EMAIL PROTECTED] wrote: : He seems to be trying to create a scheme w.r.t. which every message : of size n is the possible compression of a meaningful message. Yes, this is essentially the idea David is aiming for. Note, however, that I ``don't know what I'm talking about.'' Yes, achieved it for the domain of English language sentences is probably an impractical goal. However, note that progress towards the goal is itself worthwile. Why? What does that goal buy us? Even if you don't have perfect compression, good compression still helps. Good compression exists. Under various hypotheses, optimal compression exists. What do you believe is lacking? And what do you think ``perfect compression'' means? If you can't make all the cyphertexts smaller than n decrypt to correct-looking messages, increasing the proportion that do may still be worthwhile. Note that even OTP does not do this. All messages of size n are equally likely as decrypts, but most possible decrypts are not meaningful. This condition is essentially the best that can be hoped for, and in general it requires that the keyspace be as large as the message space--i.e., that keys be as long as the message. (Though I conjecture that this property can also be achieved if keys are only as long as the compressed message. I.e., if keys contain exactly as much entropy as the original message. But my observation is probably trite; as a mathematician but a non-cryptologist, I further conjecture that this is what the theorems on OTP actually say.) Anyway, that seems to be the problem here: Scott (and some others) are conflating the notions of ``compression'' with the desirable properties of a OTP, and then expressing their confused ideas with confusing language. Len. -- Frugal Tip #64: Find a lucrative new use for mildew. -- From: Tim Tyler [EMAIL PROTECTED] Subject: Re: Keyed hash functions Reply-To: [EMAIL PROTECTED] Date: Tue, 5 Jun 2001 13:41:35 GMT Mark Wooding [EMAIL PROTECTED] wrote: : Tim Tyler [EMAIL PROTECTED] wrote: : Are such keyed hash functions recognised as a primitive cryptographic : type, distint from MACs? : I believe that your idea of a `keyed hash' is attempting to capture what : is usually referred to as a `pseudo-random function family'. A PRF : family is suitable for use as a MAC. However, not all MACs are good : PRFs. [...] : I think there is a hope (rather than anything better informed) that : HMAC with a decent hash function is a passable PRF. [...] : [Note: I *don't* want to talk about hash(CTR|KEY) schemes] : Very wise. A helpful post - thanks. FWIW, my final comment was intended to cover /all/ constructions involving keying orthodox hash functions, /including/ things like HMAC. I'd ideally like an aesthetically pleasing construction for generating a keyed pseudo-random function - and the idea of repeatedly feeding
Cryptography-Digest Digest #524
Cryptography-Digest Digest #524, Volume #14 Tue, 5 Jun 01 13:13:00 EDT Contents: Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P. (Douglas A. Gwyn) Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P. Dulles / AKA Loki) (Scott Fluhrer) Re: Def'n of bijection (Tim Tyler) Re: Def'n of bijection (Tim Tyler) Re: Def'n of bijection (Douglas A. Gwyn) Re: BBS implementation (Mark Wooding) Re: Def'n of bijection (Douglas A. Gwyn) Re: National Security Nightmare? (Douglas A. Gwyn) Re: National Security Nightmare? (Douglas A. Gwyn) Re: Def'n of bijection (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Paul Pires) Re: Def'n of bijection (Mark Wooding) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mark Wooding) From: Douglas A. Gwyn [EMAIL PROTECTED] Subject: Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P. Date: Tue, 5 Jun 2001 14:51:42 GMT Tom St Denis wrote: Dave Howe [EMAIL PROTECTED] wrote... ... Tom St Denis [EMAIL PROTECTED] said : Take all primes and form a composite N. Add one to N. Now N is not divisible by any of the known primes. Thus N+1 is a new prime not in the list. or is divisible by a prime not in the original list That's not possible. Since we already have all consecutive primes... 3*5*7+1 = 106 106 is not divisible by any known prime (assume the only known primes are 3, 5, 7). ... We have been through this before, just a few months ago. The problem is that for purposes of the particular proof, prime is being given a hypothetical meaning that is not what it turns out to actually mean. This is okay, since all that the proof requires is for a contradiction to be produced. However, once the proof is established, we can see other contradictions; for example, N+1 is (sometimes) not a prime after all. If the proof is not carefully stated, then such other contradictions may get in the way of establishing the proof. It certainly confuses many people, who seem to believe that they will always obtain a prime when they add 1 to the product of all smaller primes. Smiley-proof: 2+1 = 3, prime 2*3+1 = 7, prime 2*3*5+1 = 31, prime 2*3*5*7+1 = 211, prime 2*3*5*7*11+1 = 2311, prime ... obviously it works :-) -- From: Scott Fluhrer [EMAIL PROTECTED] Crossposted-To: alt.privacy,alt.security,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server Subject: Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P. Dulles / AKA Loki) Date: Tue, 5 Jun 2001 08:08:24 -0700 Kyle Paskewitz [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... Tom - You've forgotten that 2 is also prime. If you take the product of any number of consecutive primes beginning with 2 (the first prime) and add 1, you will get another prime. E.G. 2*3 + 1 = 7 2*3*5 + 1 = 31 2*3*5*7 + 1 = 211 , etc... Really??? I was under the impression that: 2*3*5*7*11*13+1 = 30031 = 59*509 2*3*5*7*11*13*17+1 = 510511 = 19*97*277 2*3*5*7*11*13*17*19+1 = 9699691 = 347*27953 2*3*5*7*11*13*17*19*23+1 = 223092871 = 317*703763 weren't prime. I must be delusional, I suppose... -- poncho -- From: Tim Tyler [EMAIL PROTECTED] Subject: Re: Def'n of bijection Reply-To: [EMAIL PROTECTED] Date: Tue, 5 Jun 2001 15:15:03 GMT [EMAIL PROTECTED] wrote: : Tim Tyler [EMAIL PROTECTED] writes: : Yes. The case where the key is as large as the original message is not : where compression helps. : Smaller message == smaller key. Compression is a great way to economize : your OTP key material. It also helps with bandwidth - but it doesn't help with security. :: if keys contain exactly as much entropy as the original message...I :: further conjecture that this is what the theorems on OTP actually say. : : I don't think they mention the possibity of compression. : But I'll bet you a beer they mention entropy. I'm sure they do - but I doubt they discuss what you were talking about. : Loosely speaking, the best compression is the one for which ``bits in : output file'' equals ``bits of entropy in input file''. By the definition : of entropy, better (lossless) compression is impossible. And perfect : security can probably be achieved if ``bits of entropy in key'' equals : ``bits of entropy in message''. I wouldn't dispute any of that. :: Anyway, that seems to be the problem here: Scott (and some others) are :: conflating the notions of ``compression'' with the desirable :: properties of a OTP, and then expressing their confused ideas with :: confusing language. : : A bizarrely inaccurate representation of the situation IMO. AFAICS, : nobody is conflating the notions of ``compression'' with anything. : Then think carefully about it. With gzip, brute-forcing the key might : mean,
Cryptography-Digest Digest #525
Cryptography-Digest Digest #525, Volume #14 Tue, 5 Jun 01 15:13:00 EDT Contents: Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mark Wooding) Re: BBS implementation (Tom St Denis) Re: BigNum Question (Harris Georgiou) Re: PRP = PRF (TRUNCATE) (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) Re: Def'n of bijection ([EMAIL PROTECTED]) Re: Def'n of bijection ([EMAIL PROTECTED]) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: Def'n of bijection (Tim Tyler) Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P. (Kyle Paskewitz) Re: Def'n of bijection (Tim Tyler) Re: Def'n of bijection (Tim Tyler) Re: National Security Nightmare? (Mok-Kong Shen) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) From: [EMAIL PROTECTED] (Mark Wooding) Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) Date: 5 Jun 2001 17:19:30 GMT Tim Tyler [EMAIL PROTECTED] wrote: DS And you never anwsered the FACT that a one byte ouput file DS from CTR mode (though you have no working program) would imediately DS lead an attacker to realize that the input file could only have DS come from 1 of 256 possible messages. With BICOM you have many DS many more messages. That alone makes it more secure. [...] This is wrong. I assume here that the BICOM encryption scheme is something along the lines of B_k = E_k o C where E_k is some conventional cipher (Rijndael using some bizarre chaining mode, I think, but it doesn't matter) and C is some permutation over finite bitstrings {0, 1}^* (called a compression -- this is irrelevant here). If there is actually some unkeyed invertible transformation following the encryption step then we can ignore that, because it won't affect the cardinalities of any of the sets we're interested in. Consider the set of 8-bit strings {0, 1}^8. Since we expect a cipher to be invertible, we must have |E_k^{-1}({0, 1}^8})| = |{0, 1}^8| = 256 (since otherwise we'd be unable to recover some distinct plaintexts by decrypting). Now, since C is bijective, we must also have |B_k^{-1}({0, 1}^8})| = 256 Hence, there are at most 256 possible plaintext messages for any one-byte ciphertext. They might not all be one-byte long, but there are at most 256 of them. -- [mdw] -- From: Tom St Denis [EMAIL PROTECTED] Subject: Re: BBS implementation Date: Tue, 05 Jun 2001 17:42:48 GMT Mark Wooding [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... Tom St Denis [EMAIL PROTECTED] wrote: As I understand it, if you know the length of the cycle you only know factors of (p-1)(q-1) right? I'm caught out. If you can find short cycles with nonnegligible probability then you can factor. Just falling over one by accident I believe has a nontrivial probability of allowing you to factor given additional polynomial-time effort, but won't automatically drop the factors out. Depends. If your primes are SG primes then I think it will :-) if you can do it repeatedly then yes you can factor. Tom -- From: Harris Georgiou [EMAIL PROTECTED] Subject: Re: BigNum Question Date: Tue, 5 Jun 2001 20:40:12 +0300 Ï Tim Tyler [EMAIL PROTECTED] Ýãñáøå óôï ìÞíõìá óõæÞôçóçò: [EMAIL PROTECTED] JGuru [EMAIL PROTECTED] wrote: : George [EMAIL PROTECTED] wrote in message : I'm trying to develop a program for Macintosh and I need to operate on : very large numbers. What is the best BigNum library for Macintosh where : the source code is also available? : Java has BigInteger and BigDecimal. As long as there is a JDK available for : your platform, you can write code that can run on any platform. OS = 9 Java: http://www.apple.com/java/ OS XJava: http://www.apple.com/macosx/java2.html The source code for BigInteger and BigDecimal is available. The big number packages in JDK work quite well, they even have embedded functions for most cryptosystem implementations (like secure random prime number generator, modulo exponetials, etc) - I have actually implemented the basic RSA encryption from scratch in less than 100 lines of code. The only problem is that Java is slow and encryption using Java is even slower. -- Harris - 'Malo e lelei ki he pongipongi!' -- From: Tom St Denis [EMAIL PROTECTED] Subject: Re: PRP = PRF (TRUNCATE) Date: Tue, 05 Jun 2001 17:46:49 GMT Scott Fluhrer [EMAIL PROTECTED] wrote in message news:9fisbo$ngc$[EMAIL PROTECTED]... Tom St Denis [EMAIL PROTECTED] wrote in message news:VC2T6.31386$[EMAIL PROTECTED]... Reading the paper David pointed to a bit ago I see they have one way to
Cryptography-Digest Digest #527
Cryptography-Digest Digest #527, Volume #14 Tue, 5 Jun 01 17:13:01 EDT Contents: Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY) Re: Def'n of bijection (SCOTT19U.ZIP_GUY) Re: Def'n of bijection (Mok-Kong Shen) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) Re: fast CTR like ciphers? (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY) Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (Anonymous) Re: Def'n of bijection (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) Date: 5 Jun 2001 19:58:14 GMT [EMAIL PROTECTED] (Tim Tyler) wrote in [EMAIL PROTECTED]: Tim I think TOM is just trying to make ass out of himself The thread will go no where. He will only twist it. He can't even answser the simple fact theat if one used CTR mode so a one byte cipher text file decrypts to 256 messages. And one used BICOM where a one byte output file could represent thousands and thousands of possible input messages. He in this example doesn't know which case is more secure. If he can't comprehend the obvious why keep tryinig. He does not want to know the truth. He doesn't care. You can give a pig singing lessoons but his not going to learn. You just waste your time and the pigs. David A. Scott -- SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE OLD VERSIOM http://www.jim.com/jamesd/Kong/scott19u.zip My website http://members.nbci.com/ecil/index.htm My crypto code http://radiusnet.net/crypto/archive/scott/ MY Compression Page http://members.nbci.com/ecil/compress.htm **NOTE FOR EMAIL drop the roman five *** Disclaimer:I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you! -- From: Tom St Denis [EMAIL PROTECTED] Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) Date: Tue, 05 Jun 2001 20:25:06 GMT SCOTT19U.ZIP_GUY [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... [EMAIL PROTECTED] (Tim Tyler) wrote in [EMAIL PROTECTED]: Tim I think TOM is just trying to make ass out of himself The thread will go no where. He will only twist it. He can't even answser the simple fact theat if one used CTR mode so a one byte cipher text file decrypts to 256 messages. And one used BICOM where a one byte output file could represent thousands and thousands of possible input messages. He in this example doesn't know which case is more secure. If he can't comprehend the obvious why keep tryinig. He does not want to know the truth. He doesn't care. You can give a pig singing lessoons but his not going to learn. You just waste your time and the pigs. Funny. Why can't you answer any simple questions? Again. C = P + K mod 256 C = 55 What is P? Tom -- From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) Date: 5 Jun 2001 20:13:38 GMT [EMAIL PROTECTED] (Tom St Denis) wrote in PQaT6.36859$[EMAIL PROTECTED]: SCOTT19U.ZIP_GUY [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... [EMAIL PROTECTED] (Mark Wooding) wrote in [EMAIL PROTECTED]: Hence, there are at most 256 possible plaintext messages for any one-byte ciphertext. They might not all be one-byte long, but there are at most 256 of them. -- [mdw] Sorry but you whole analysis is full of shit. Even you could sit down and test decrypt 300 keys to decrypt one one byte cipher text message. But like many you spout off shit thats wrong that you could easily test. But you have so much blind belied in your false Gods and false proof you don't even take the honest time to test it. Yes there are strong words but the simple fact is your full of it. Yes you can decrypt it. The problem is you won't know when you found the key. Try this. C = P + K mod 256 C = 56 What was P or K? In this case both P and K are decorrelated and C doesn't reveal P. Which is what the original argument was about. So what if you could guess P=23. There is no way to verify that's the right answer. Tom Tom are you retarded or what. You don't seem to know what the hell is going on. The first person who may not know better
Cryptography-Digest Digest #528
Cryptography-Digest Digest #528, Volume #14 Tue, 5 Jun 01 18:13:00 EDT Contents: Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) One last bijection question (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY) Re: One last bijection question ([EMAIL PROTECTED]) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (JPeschel) Re: One last bijection question (Tom St Denis) Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (P. Dulles / AKA Loki) (Keith) From: Tom St Denis [EMAIL PROTECTED] Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) Date: Tue, 05 Jun 2001 21:10:44 GMT Tim Tyler [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... Tom St Denis [EMAIL PROTECTED] wrote: : Tim Tyler [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... : Tom St Denis [EMAIL PROTECTED] wrote: : : Yes there will be equivalent keys but not enough to tell from random. : : Tell /what/ from random. : Tell the plaintext. [...] I can very likely tell a randomly chosen plaintext from the decrypt of an 1 byte cyphertext using CTR mode. Does the random plaintext have only 8 bits? If not, I can immediately distinguish them. Yes, but you are just brute forcing the key space. If you encode for example 384-bits (three AES blocks) in CTR mode you can most likely tell when you get the key right. However, getting the right key amounts to at least 2^127 work if the key is random. : [...] a cyphertext only having 256 possible decrypts is a : problem with the orthodox CTR mode. : It's not a problem. You're just not looking for the answer. AFAICS, your idea of an answer is one that isn't worth having ;-| : The truth is if the message has a prob of 1/256 and all outputs from the : cipher are equalprobable (i.e 1/256) then it's a provably secure for a : single byte only. Ah - you're sliding in that for a single byte only... As though we're discussing the trivial case of only 256 possible messages... Um yes that's what we were f$$$ talking about. For geez sakes stay on the same model! : Consider the cipher some simple like : C = P xor K : where we discard the 120 upper bits of C before xoring against the message. : Don't you agree this is just an OTP? Yes - it's very much like an OTP. (Hint it is an OTP) : Hence don't you agree it's provably secure? Of course it's not provably secure - unless you think only having 256 possible plaintexts out of the possible billions is something worthwhile. We're trying to stop the attacker getting information about the message. Giving him the length of the message on a plate is a terrible start. Why? Tell me how you can find K from C knowing the length? Just tell me why it's a problem. Tom -- From: Tom St Denis [EMAIL PROTECTED] Subject: One last bijection question Date: Tue, 05 Jun 2001 21:15:10 GMT Ok I thought bijections were when the codomain and domain are the same set. http://www.dictionary.com/cgi-bin/dict.pl?term=surjection Seems to support this thought. A function f : A - B is surjective or onto or a surjection if f A = B Don't A and B represent the domain/codomain sets respectively? I'm most likely wrong can someone explain this? The only other meaning I can find is that A and B are not the same set but can map back and forth. But isn't that an injection? Arrg! -- Tom St Denis --- http://tomstdenis.home.dhs.org -- From: Tim Tyler [EMAIL PROTECTED] Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) Reply-To: [EMAIL PROTECTED] Date: Tue, 5 Jun 2001 21:12:05 GMT SCOTT19U.ZIP_GUY [EMAIL PROTECTED] wrote: : Tim I think TOM is just trying to make ass out of himself He seems to me to have been doing a lot of that recently: First the unicity distance, then the bijection, and now the CTR mode. I guess we just rub him up the wrong way - so that all of his conceptual problems come to the surface at once. : The thread will go no where. He will only twist it. He can't : even answser the simple fact theat if one used CTR mode so : a one byte cipher text file decrypts to 256 messages. And : one used BICOM where a one byte output file could represent : thousands and thousands of
Cryptography-Digest Digest #529
Cryptography-Digest Digest #529, Volume #14 Tue, 5 Jun 01 19:13:00 EDT Contents: Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY) Re: One last bijection question (Stanley Chow) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: One last bijection question (Tom St Denis) Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and Large Primes (sisi jojo) Re: One last bijection question (Tim Tyler) Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY) Re: Welcoming another Anti-Evidence Eliminator stooge to USENET (Tom St Denis) Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and Large Primes (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: One last bijection question (Thorsten Holz) Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY) Re: Best, Strongest Algorithm (gone from any reasonable topic) (SCOTT19U.ZIP_GUY) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) From: Tim Tyler [EMAIL PROTECTED] Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) Reply-To: [EMAIL PROTECTED] Date: Tue, 5 Jun 2001 21:45:49 GMT Tom St Denis [EMAIL PROTECTED] wrote: : Tim Tyler [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... : Tom St Denis [EMAIL PROTECTED] wrote: : : Tim Tyler [EMAIL PROTECTED] wrote in message : : Which only gets us as far as an OTP - which has the *same* security : : problem as counter mode if messages are of varying lengths and : : the plaintexts and cyphertexts are of equal lengths. : : : What problem? : : Lack of perfect secrecy for a start. : Given your limited understanding of perfect secrecy this doesn't mean : much. My *WHAT*!??? How is my understanding limited? : : If all possible messages are uniformly distributed you have : : no advantage hence you can't tell which message is the real one. : : In the case under discussion being given the cyphertext gives a *big* : clue about the plaintext - namely its length. That is likely : to immediately rule out most plaintexts. : Oh yes, the real plaintext can't be trillion bytes long. So what? So all possible messages are *not* uniformly distributed, (given the cyphertext) - so there's *no* perfect secrecy, and your argument that the attacker has no advantage collapses. : : If all messages are uniformly distributed you can't find the real : : message. [...] : : ...but since some messages are longer than 8 bits, the possible plaintexts : are *not* uniformly represented by an 8-bit cyphertext. : : Some (the ones with 8 bits) have probability 1/256. All other plaintexts : have probability 0. That is not a uniform distribution. : Yes, but if you want to use math against me try using it right. the : messages 1 byte are not part of the set. They /are/ possible messages... : The plaintext is assumed to be a byte thus 0x123456 is not a member of : that set. *No*. The plaintext is *not* assumed to be a byte. We're talking about BICOM and CTR mode here. These can encrypt more than just single byte messages. Assuming the plaintext is a byte is a ridiculous, unphysical assumption. What is your basis for assuming this? -- __ |im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/ -- From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) Date: 5 Jun 2001 21:51:26 GMT [EMAIL PROTECTED] (Tim Tyler) wrote in [EMAIL PROTECTED]: SCOTT19U.ZIP_GUY [EMAIL PROTECTED] wrote: : Tim I think TOM is just trying to make ass out of himself He seems to me to have been doing a lot of that recently: First the unicity distance, then the bijection, and now the CTR mode. I guess we just rub him up the wrong way - so that all of his conceptual problems come to the surface at once. I think that he does not reason well. He knows that I think Wagner and Mr BS are pompous phonies. And I think he wishs to appear knowledgeable in there eyes so he just argues to try to look good with ever thinking about it. I think he wrong assumes Wagner would step in and correct his errors. But I am sure he is just laughing at the whole situation. Wagner does not want to say nice things about BICOM becasue it not a product from the crypto insiders club. He can't stand to see a ameutor come up with something. But I am sure the big boys will eventually steal the idea as there own and never give me or Matt any credit for it. : The thread will go no where. He will only twist it. He can't : even answser the simple fact theat if one used CTR mode so : a one byte cipher text file decrypts to 256 messages. And : one used BICOM where a one
Cryptography-Digest Digest #530
Cryptography-Digest Digest #530, Volume #14 Tue, 5 Jun 01 20:13:01 EDT Contents: Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) Re: One last bijection question (Berton Allen Earnshaw) Are RS codes a type of PRF? (Tom St Denis) Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler) CTR mode, BICOM, and hiding plaintext length (David Hopwood) Re: BBS implementation (David Hopwood) Re: Def'n of bijection (David Hopwood) Lim-Lee vs safe primes for DH (David Hopwood) curious about MD3 (Tom St Denis) Re: Def'n of bijection ([EMAIL PROTECTED]) Re: Best, Strongest Algorithm (gone from any reasonable topic) ([EMAIL PROTECTED]) Re: One last bijection question (Douglas A. Gwyn) Re: CTR mode, BICOM, and hiding plaintext length (SCOTT19U.ZIP_GUY) Re: One last bijection question (Douglas A. Gwyn) From: Tim Tyler [EMAIL PROTECTED] Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) Reply-To: [EMAIL PROTECTED] Date: Tue, 5 Jun 2001 22:32:39 GMT Tom St Denis [EMAIL PROTECTED] wrote: : Tim Tyler [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]... : Tom St Denis [EMAIL PROTECTED] wrote: : : Tim Tyler [EMAIL PROTECTED] wrote in message : : Tom St Denis [EMAIL PROTECTED] wrote: : : : Tim Tyler [EMAIL PROTECTED] wrote in message : : : Tom St Denis [EMAIL PROTECTED] wrote: : : : : Yes there will be equivalent keys but not enough to tell from : : : : random. : : : : : : Tell /what/ from random. : : : : : Tell the plaintext. [...] : : : : I can very likely tell a randomly chosen plaintext from the decrypt of : : an 1 byte cyphertext using CTR mode. : : : : Does the random plaintext have only 8 bits? If not, I can immediately : : distinguish them. : : : Yes, but you are just brute forcing the key space. [...] : : Nope - just checking lengths. : WHY DOES THE LENGTH AUTOMATICALLY GIVE YOU THE MESSAGE? It doesn't. I never claimed it did. : : Ah - you're sliding in that for a single byte only... : : : : As though we're discussing the trivial case of only 256 possible : : messages... : : : Um yes that's what we were f$$$ talking about. For geez sakes stay on : : the same model! : : We are *not* discussing the case of 256 possible messages. Both BICOM and : CTR mode can encrypt *any* possible message. : : Given this wide distribution of possible messages, we are asking what : security is offered when encrypting a particular 8-bit message in BICOM : and CTR mode. : : BICOM with a 128 bit key maps it to one of 2^128 possible messages. : CTR mode maps it to one of 256 messages. : : The latter produces an 8-bit cyphertext with only 256 possible : interpretations. : : If you happened to know the message consisted entirely of space : characters, you could uniquely identify the message! : C = 88 5e f7 fe c1 78 f0 6d 61 c8 bc ac 3a a1 09 ae 12 6b 4e 46 58 : What is P? Apparently unable to produce any other coherent reply, Tom presents me with another of his idiotic challenges again :-( : : Of course it's not provably secure - unless you think only having 256 : : possible plaintexts out of the possible billions is something : : worthwhile. : : : : We're trying to stop the attacker getting information about the : : message. : : Giving him the length of the message on a plate is a terrible start. : : : Why? Tell me how you can find K from C knowing the length? : : : Just tell me why it's a problem. : : You go round and round in circles. I've responded in some detail to both : these questions already. : Well those are real questions. [...] Which - as I have stated - I have already replied to, at least once. -- __ |im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/ -- From: Berton Allen Earnshaw [EMAIL PROTECTED] Subject: Re: One last bijection question Date: 05 Jun 2001 16:31:15 -0600 Just to clarify: the words 'bijection' and 'isomorphism' are not the same thing. An isomorphism must also preserve the operations of the two sets, while a bijection has no such requirement. For example, if (A,x) and (B,X) are both groups with x being the group-operation of A and X the group-operation of B, and if f : A-B is an isomorphism, then f is a bijection *and* for all y,z in A, f(y x z) = f(y) X f(z), i.e, f preserves the respective group-operations. -- Berton Earnshaw - [EMAIL PROTECTED] -- From: Tom St Denis [EMAIL PROTECTED] Subject: Are RS codes a type of PRF? Date: Tue, 05 Jun 2001 22:45:55 GMT As far as I can tell RS codes (Reed-Solomon) are form of error correction codes (???) that were (as an example) used in Twofish to map 8 bytes downto 4 bytes such that the distance is 5 bytes. So could we make a 8-byte Feistel by appending a 4 byte key to one half to make the 8 bytes then compute the RS code on it? Do the remaining unfixed four bytes form a permutation
Cryptography-Digest Digest #531
Cryptography-Digest Digest #531, Volume #14 Tue, 5 Jun 01 23:13:01 EDT Contents: Re: Def'n of bijection (SCOTT19U.ZIP_GUY) Re: PRP = PRF (TRUNCATE) (Scott Fluhrer) Re: One last bijection question (Nicol So) Re: fast CTR like ciphers? (Scott Fluhrer) Re: One last bijection question (Robert J. Kolker) Re: One last bijection question (Nicol So) Re: fast CTR like ciphers? (Tom St Denis) Re: Quantum Computers with relation to factoring and BBS (rosi) function notation (injection, bijection, etc..) one last time (Tom St Denis) Re: function notation (injection, bijection, etc..) one last time ([EMAIL PROTECTED]) Re: function notation (injection, bijection, etc..) one last time (Nicol So) Re: function notation (injection, bijection, etc..) one last time (Nicol So) Re: Quantum Computers with relation to factoring and BBS (Nicol So) Re: Knapsack security??? Ahhuh (rosi) Re: function notation (injection, bijection, etc..) one last time ([EMAIL PROTECTED]) Re: Medical data confidentiality on network comms (wtshaw) From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) Subject: Re: Def'n of bijection Date: 5 Jun 2001 23:55:57 GMT [EMAIL PROTECTED] (David Hopwood) wrote in [EMAIL PROTECTED]: is indeed precisely why compression doesn't hinder an attacker in recognising plaintext. Compression cannot change the total entropy of the messages sent under a particular key: that is determined by the usage characteristics of the application. Once sufficient messages have But Dave even you should know something about Shannons theorys. If you compress you can increase the entropy per bit of the message by the very fact of compression. And you miss a big point. For many message with out comprssion they can be breakable becasue message is far greater than the Unicity distance. But that same message may be unbreakable with compression. Not only because it takes less cipher space but because the message may be less than the Unicity distance. However I admit for very long files its unlikely that the either message is shorter than the Unicity distance so if one could check all messages either with compression or without you would get the correct message. But you forget even yet another problem with modern ciphers the fact that error propagation is very low. That means if an attacker knows part of message. He need only attack the blocks where that portion of message is to obtain a break. With say bijective arithmetic compression if he knows what part of file is say half way down. The attacker needs to decrypt and uncompress everything up to and including that point to get a test case. It may be that with a known portion of plain text a fast way to break those blocks may be possible. With Arihtmetic compression even if you knew what the compressed plain text was. It would be very hard to decompress a middle portion of a file. As such its less likely that a simple math short cut could be used on that portion of the file. been sent under a given key, there will be enough information to brute-force it [*]. If we assume that the key size is fixed (i.e. not an OTP), then compression makes no significant difference to when this happens. Even though the distribution of decrypts will be a little closer to the distribution of meaningful messages than it would otherwise have been, in practice it will there will still only be one decrypt that is actually meaningful, and it will be easy to recognise that decrypt automatically, for message distributions that occur in real applications. Note that this is true even if codebooks are used, since the messages in a typical codebook don't have anywhere near equal probability of occurrance. [*] I know that David Scott handwaves about other attacks than brute-force. However, he hasn't put forward any coherent argument as to how bijective compression would help against such attacks. Note that cryptanalytic attacks against commonly used block ciphers generally require large amounts of *exact* known plaintext (at least). In plausible situations where exact known plaintext would be available - when data streams from multiple sources are encrypted under the same key, for example - then it would be available whether compressed or not. If one has the plaintext which I don't think Ben laden or terriost are likely to give. Yes either compression or no compression. You could figure out the key. As I have stated several times this compression encryption does nothing to stop a full dumb blind brute force seach if you have a plaintext file in and a cipher text file out and the time to do it. It just that the cipher text output is what is the easiest to get and where bijective compression helps the most. Bijective compression defintely makes ciphertext only attacks much harder. May I keep finding exceptions. But since hopefully a compressed file is