[19444] in cryptography@c2.net mail archive
Re: another feature RNGs could provide
daemon@ATHENA.MIT.EDU (David Malone)
Tue Dec 27 19:09:15 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Tue, 27 Dec 2005 22:45:59 +0000
From: David Malone <dwmalone@maths.tcd.ie>
To: "Travis H." <solinym@gmail.com>
Cc: Ben Laurie <ben@algroup.co.uk>,
"Perry E. Metzger" <perry@piermont.com>, cryptography@metzdowd.com
In-Reply-To: <d4f1333a0512270126h78dd9901yad3ceaee57a8b2a6@mail.gmail.com>
On Tue, Dec 27, 2005 at 03:26:59AM -0600, Travis H. wrote:
> On 12/26/05, Ben Laurie <ben@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.)
David.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
