Re: the meaning of linearity, was Re: picking a hash function to be encrypted

2006-05-18 Thread Travis H.

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

2006-05-18 Thread Travis H.

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

2006-05-18 Thread Perry E. Metzger

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

2006-05-18 Thread Ben Pfaff
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.

2006-05-18 Thread Steve Schear

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]