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: picking a hash function to be encrypted
Travis H. [EMAIL PROTECTED] writes: On 5/14/06, Victor Duchovni [EMAIL PROTECTED] wrote: Security is fragile. Deviating from well understood primitives may be good research, but is not good engineering. Especially fragile are: Point taken. This is not for a production system, it's a research thing. TLS (available via OpenSSL) provides integrity and authentication, any reason to re-invent the wheel? It took multiple iterations of design improvements to get TLS right, even though it was designed by experts. IIUC, protocol design _should_ be easy, you just perform some finite-state analysis and verify that, assuming your primitives are ideal, no protocol-level operations break it. The 7th Usenix Security Symposium has a paper where the authors built up SSL 3.0 to find out what attack each datum was meant to prevent. They used mur-phi, which has been used for VLSI verification (i.e. large numbers of states). ATT published some code to do it too (called SPIN). It's effective if the set of attacks you're protecting against is finite and enumerable (for protocol design, I think it should be; reflection, replay, reorder, suppress, inject, etc.). I wouldn't consider fielding a protocol design without sanity-checking it using such a tool. Was there an attack against TLS which got past FSA, or did the experts not know about FSA? There have been a number of attacks on TLS since Mitchell et al's paper was published in 1998. The most well known are the attacks on CBC mode described in http://www.openssl.org/~bodo/tls-cbc.txt. -Ekr - 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: picking a hash function to be encrypted
* Travis H.: IIUC, protocol design _should_ be easy, you just perform some finite-state analysis and verify that, assuming your primitives are ideal, no protocol-level operations break it. Is this still true if you don't know your actual requirements? - 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: picking a hash function to be encrypted
Travis H. writes: Excellent point. When I wrote that I had strongly universal hashes in mind, like UMAC, where the hash is chosen from a family of functions based on some secret data shared by sender and recipient. I mistakenly conflated them with ordinary hashes (which they are, once you pick one). Thanks for catching that. A point of terminology, strong universal hash functions are different than what you are probably thinking of. UMAC is a MAC, not a SU hash function. It uses an almost-SU hash function in its construction, but that's different. Universal hashes and their variants (see http://www.cacr.math.uwaterloo.ca/~dstinson/universalhashingdefinitions.html for a bibliography) are actually *weaker* than conventional hashes. They can, in fact, be completely linear. While you are right that the hash is typically part of a parameterized family, once you pick one you do not get an ordinary hash. You are more likely to get an ordinary polynomial that will not serve at all well as a crypto hash. Hal Finney - 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]
Re: picking a hash function to be encrypted
On Sun, May 14, 2006 at 03:04:41AM -0500, Travis H. wrote: Suppose I want a function to provide integrity and authentication, and that is to be combined with a stream cipher (as is the plaintext). I believe that authentication is free once I have integrity given the fact that the hash value is superencrypted using the stream cipher, whose key is shared by only the sender and recipient. I believe what I'm looking for is a strongly universal hash. I don't need much; everything I've seen is simultaneously too much and too little, often calling upon a block cipher, which seems redundant. What I was thinking of doing was using Poly1305, and using the stream cipher instead of AES. I think in this case that I can leave the MAC exposed, since it's a MAC and not a hash. Is there an analogous, hash function that does not use encryption internally? Security is fragile. Deviating from well understood primitives may be good research, but is not good engineering. Especially fragile are: - Non-mainstream ciphers (often broken once someone good bothers to try) - Stream ciphers (additive) - RC4 (poor key schedule) - RSA (multiplicative) The first is to be avoided entirely, the second and third should be used only under duress, when block ciphers are a very poor fit for the application. RSA needs to be used only in very specific ways (PKCS 2.1, for example) that avoid the common pitfalls. TLS (available via OpenSSL) provides integrity and authentication, any reason to re-invent the wheel? It took multiple iterations of design improvements to get TLS right, even though it was designed by experts. -- /\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: picking a hash function to be encrypted
On 5/14/06, Eric Rescorla [EMAIL PROTECTED] wrote: Consider the case where you're transmitting message M. The hash is H(M). You then encrypt (M || H(M)), generating K XOR (M || H(M)). If the attacker knows M and H, he can compute (M || H(M)) and compute K. Then he can re-encrypt a message M' of his choice. Excellent point. When I wrote that I had strongly universal hashes in mind, like UMAC, where the hash is chosen from a family of functions based on some secret data shared by sender and recipient. I mistakenly conflated them with ordinary hashes (which they are, once you pick one). Thanks for catching that. IMHO encrypting MACs is a good defensive measure, because you can then use a smaller hash value, so you end up encrypting as little as 4 bytes instead of transmitting 20 en clair, and now you also know the opponent hasn't learned anything. Does anyone know if MAC-then-encrypt(plaintext) versus encrypt(plaintext)-then-MAC makes a difference if the MAC itself is to be encrypted? I can't think of why it would. -- 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: picking a hash function to be encrypted
On 5/14/06, Victor Duchovni [EMAIL PROTECTED] wrote: Security is fragile. Deviating from well understood primitives may be good research, but is not good engineering. Especially fragile are: Point taken. This is not for a production system, it's a research thing. TLS (available via OpenSSL) provides integrity and authentication, any reason to re-invent the wheel? It took multiple iterations of design improvements to get TLS right, even though it was designed by experts. IIUC, protocol design _should_ be easy, you just perform some finite-state analysis and verify that, assuming your primitives are ideal, no protocol-level operations break it. The 7th Usenix Security Symposium has a paper where the authors built up SSL 3.0 to find out what attack each datum was meant to prevent. They used mur-phi, which has been used for VLSI verification (i.e. large numbers of states). ATT published some code to do it too (called SPIN). It's effective if the set of attacks you're protecting against is finite and enumerable (for protocol design, I think it should be; reflection, replay, reorder, suppress, inject, etc.). I wouldn't consider fielding a protocol design without sanity-checking it using such a tool. Was there an attack against TLS which got past FSA, or did the experts not know about FSA? -- 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]
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]
Re: picking a hash function to be encrypted
On Sun, May 14, 2006 at 07:56:17PM -0500, Travis H. wrote: On 5/14/06, Victor Duchovni [EMAIL PROTECTED] wrote: Security is fragile. Deviating from well understood primitives may be good research, but is not good engineering. Especially fragile are: Point taken. This is not for a production system, it's a research thing. TLS (available via OpenSSL) provides integrity and authentication, any reason to re-invent the wheel? It took multiple iterations of design improvements to get TLS right, even though it was designed by experts. IIUC, protocol design _should_ be easy Once upon a time, everyone agreed that cipher design was hard. Later people discovered that protocol design is hard too. More recently people are discovering that given solid ciphers and protocols, secure implementations are still hard... I could be wrong, but it does not seem that the trend is towards increasingly easy security, in the sense that anyone who learns a programming language reasonably well can develop security toolkits. :-( -- /\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
