[Boneh-crypto-course] If DES were linear... what???

Jim Blandy jimb at red-bean.com
Tue Mar 27 14:38:09 CDT 2012

I didn't understand what he was saying about the troubles that arise if DES
is linear. I don't see how we can necessarily recover the key after 832
chosen plaintext attacks.

Suppose DES were some 832x64 matrix, where 832 = 64 (input bits) + 16
(rounds) * 48 (round key bits). So you multiply this by an 832-bit input
vector, and you get a 64-bit output vector, the ciphertext.

Any time you're computing a matrix x vector product, M v, and M has
dimensions w x h, you can always split that into two side-by-side matrices,
M1 and M2, with widths w1 and w2, where w = w1 + w2, such that when we find
v1 || v2 = v, then M v = (M1 v1) + (M2 v2). It's just splitting up the sums
across the rows after you've done the multiplication.

So let's split our DES matrix into a 64 x 64 M1, and a 768 x 64 M2. The
input to M1 is the plaintext, and the input to M2 is the expanded key ks.
We can choose our plaintext m, and find the ciphertext c, but we don't know
the key.

We know M1 m, so M1 m xor c must be M2 ks.

But there's no reason M2 needs to be invertible. It could *lose*
information about ks.

So how can you recover the key???
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.red-bean.com/pipermail/boneh-crypto-course/attachments/20120327/3b50d3d0/attachment.html>

More information about the Boneh-crypto-course mailing list