### 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]

### Political Cartoon of the Day

http://www.ucomics.com/tomtoles/2006/05/18/ Hat tip again to Steve Bellovin. Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Political Cartoon of the Day

Perry E. Metzger [EMAIL PROTECTED] writes: http://www.ucomics.com/tomtoles/2006/05/18/ Here's one that got my attention: http://www.workingforchange.com/comic.cfm?itemid=20803 -- A computer is a state machine. Threads are for people who cant [sic] program state machines. --Alan Cox - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: NSA knows who you've called.

At 08:05 AM 5/11/2006, Perry E. Metzger wrote: Let me again remind people that if you do not inform your elected representatives of your displeasure with this sort of thing, eventually you will not be in a position to inform them of your displeasure with this sort of thing. I think begging elected representatives to acknowledge your rights is generally a waste of time, especially when there is powerful or ingrained opposition. The Civil Rights movement got nowhere until there was massive civil disobedience. Widespread deployment of generic and otherwise acceptable technologies that can be re-targeted for end-user controlled privacy (not what governments would like to see, which is privacy mediated by corporations, licensed professionals or other regulated entities they can easily pressure) and/or insistence of powerful and wealthy individuals that they have the privacy they deserve and get it in such a way as its easily unavailable to the average citizen. Steve - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]