On Tue, Dec 27, 2005 at 03:26:59AM -0600, Travis H. wrote: > On 12/26/05, Ben Laurie <[EMAIL PROTECTED]> wrote: > > Surely if you do this, then there's a meet-in-the middle attack: for a > > plaintext/ciphertext pair, P, C, I choose random keys to encrypt P and > > decrypt C. If E_A(P)=D_B(C), then your key was A.B, which reduces the > > strength of your cipher from 2^x to 2^(x/2)?
> Almost true. The cardinality of the symmetric group S_(2^x) is > (2^x)!, so it reduces it from (2^x)! to roughly sqrt((2^x)!). That's > still a lot. I'm fairly sure knowing that E(P) = C reduces the key space from (2^x)! to (2^x - 1)!, because you've just got to choose images for the remaining 2^x - 1 possible blocks. I think a problem with Ben's arument is in assuming that knowing E_A(P)=D_B(C) tells you that your key was A.B. For example, suppose my key K is the permutation: 1 -> 2 2 -> 3 3 -> 4 4 -> 1 and my P = 2. Now we know E_K(P) = C = 3. Ben guesses A: 1 -> 1 2 -> 3 3 -> 2 4 -> 4 and B: 1 -> 1 2 -> 2 3 -> 3 4 -> 4 He sees that E_A(P) = E_A(2) = 3 = D_B(3), and so assumes that K = A.B. But A.B = A != K. (In this example, imagine x = 2, and we label the blocks 00 = 1, 01 = 2, 10 = 3, 11 = 4.) David. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]