Re: the meaning of linearity, was Re: picking a hash function to be encrypted
On 5/17/06, Kuehn, Ulrich [EMAIL PROTECTED] wrote: Given known plaintext and corresponding ciphertext, there should not be too many keys that map the plaintext to the ciphertext. I don't have the probability at hand how many such 'collisions' you would expect from 256 random permutations, but intuitively I would not expect too many. However, I could be wrong here and would like to be corrected in this case. I'm a little rusty but I'll give it a shot. Well we have a byte x and a mapping f_k(x) = y, with f selected at random (for now I'll assume with replacement since 256 256!) from the set of all permutations, x and y from 0..255. The questions is what fraction of permutations have f_k(x) = y, I think the answer is 1/256. There's 255 other permutations, so the chance that there is at least one k' such that f_k'(x)=y is 255/256 = 99.6%. The chance that there is exactly one such k' is sampling with replacement and if I am not mistaken P(|K|=1) = (255/256)^255 = 0.36. Along those same lines, P(|K|=2) = (255/256)^253 * 254 / 256^2 = 0.001, so it looks like the expected number of equivocating keys is very small. I suspect that's why Terry Ritter's Dynamic Substitution algorithms, which are meant to replace XOR combiner in stream ciphers, maintain state. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: the meaning of linearity, was Re: picking a hash function to be encrypted
On 5/18/06, Travis H. [EMAIL PROTECTED] wrote: ... There's 255 other permutations, so the chance that there is at least one k' such that f_k'(x)=y is 255/256 = 99.6%. The chance that there is exactly one such k' is sampling with replacement and if I am not mistaken P(|K|=1) = (255/256)^255 = 0.36. Along those same lines, P(|K|=2) = (255/256)^253 * 254 / 256^2 = 0.001, so it looks like the expected number of equivocating keys is very small. Oops, I left off a term in the recurrence. P(|K|=2) = (255/256)^253 * ((254*255)/2)/(256^2) = 0.18 So the expected number of equivocating keys, given one byte of known plaintext, is a bit under two. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: the meaning of linearity, was Re: picking a hash function to be encrypted
-Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] The thing I've always wondered about stream ciphers is why we only talk about linear ones. A stream cipher is fundamentally constructed of two things: A stream of bits (alleged to be unpredictable) as long as the plaintext; and a combining function that takes one plaintext bit and one stream bit and produces a ciphertext bit. The combining function has to conserve information. If you only combine single bits, there are only two possible functions: XOR and the complement of XOR. But consider RC4: It actually generates a byte at a time. We just choose to use that byte as a vector of 8 bits. For plaintexts that are multiples of 8 bits long - just about everything these days - there are many possible combining functions. Most aren't even close to linear. I am not sure this will add to the security of the whole thing. My reasoning behind that is: The combining function needs to be invertible (we want to recover the plaintext, don't we?), so we have an 8-bit block cipher with an 8-bit key (supplied by the key stream generator). Given known plaintext and corresponding ciphertext, there should not be too many keys that map the plaintext to the ciphertext. I don't have the probability at hand how many such 'collisions' you would expect from 256 random permutations, but intuitively I would not expect too many. However, I could be wrong here and would like to be corrected in this case. Regards, Ulrich - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: the meaning of linearity, was Re: picking a hash function to be encrypted
| - Stream ciphers (additive) | | This reminds me, when people talk about linearity with regard to a | function, for example CRCs, exactly what sense of the word do they | mean? I can understand f(x) = ax + b being linear, but how exactly | does XOR get involved, and are there +-linear functions and xor-linear | functions? Are they disjoint? etc. XOR is the same as addition mod 2. The integers mod 2 form a field with XOR as the addition operation and integer multiplication (mod 2, though that has no effect in this case) as the multiplication. If you think of a stream of n bits as a member of the vector space of dimension n over the integers mod 2 treated as a field, then adding two of these - the fundamental linear operation - is XOR'ing them bit by bit. The thing I've always wondered about stream ciphers is why we only talk about linear ones. A stream cipher is fundamentally constructed of two things: A stream of bits (alleged to be unpredictable) as long as the plaintext; and a combining function that takes one plaintext bit and one stream bit and produces a ciphertext bit. The combining function has to conserve information. If you only combine single bits, there are only two possible functions: XOR and the complement of XOR. But consider RC4: It actually generates a byte at a time. We just choose to use that byte as a vector of 8 bits. For plaintexts that are multiples of 8 bits long - just about everything these days - there are many possible combining functions. Most aren't even close to linear. Other than post by a guy - Terry someone or another - on sci.crypt a number of years ago - I've never seen any work in this direction. Is there stuff I'm not aware of? -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: the meaning of linearity, was Re: picking a hash function to be encrypted
On 5/15/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Other than post by a guy - Terry someone or another - on sci.crypt a number of years ago - I've never seen any work in this direction. Is there stuff I'm not aware of? That would probably be Terry Ritter, www.ciphersbyritter.com. He calls this function Dynamic Substitution: http://www.ciphersbyritter.com/#DynSubTech You could also probably use a Latin square: http://www.ciphersbyritter.com/#BBMTech -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: the meaning of linearity, was Re: picking a hash function to be encrypted
Travis H. wrote: - Stream ciphers (additive) This reminds me, when people talk about linearity with regard to a function, for example CRCs, exactly what sense of the word do they mean? I can understand f(x) = ax + b being linear, but how exactly does XOR get involved, and are there +-linear functions and xor-linear functions? Are they disjoint? etc. If you have a linear algebra book handy, look up linear transformation. Briefly, a function T from a vector space V to another vector space W (where V and W are defined over the same field) is called a linear transformation if it satisfies i) T(u +_V v) = T(u) +_W T(v) ii) T(c *_V u) = c *_V T(u) iii) T(0_V) = 0_W CRC is a linear transformation because CRC(u + v) = CRC(u)+CRC(v). -James - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
the meaning of linearity, was Re: picking a hash function to be encrypted
- Stream ciphers (additive) This reminds me, when people talk about linearity with regard to a function, for example CRCs, exactly what sense of the word do they mean? I can understand f(x) = ax + b being linear, but how exactly does XOR get involved, and are there +-linear functions and xor-linear functions? Are they disjoint? etc. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
