another feature RNGs could provide
Ben Laurie
ben at algroup.co.uk
Tue Dec 27 18:34:15 EST 2005
David Malone wrote:
> On Tue, Dec 27, 2005 at 03:26:59AM -0600, Travis H. wrote:
>> On 12/26/05, Ben Laurie <ben at algroup.co.uk> 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.)
If you don't have sufficient plain/ciphertext, then of course you can
choose incorrect pairs.
--
http://www.apache-ssl.org/ben.html http://www.thebunker.net/
"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list