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

Jason Orendorff jason.orendorff at gmail.com
Tue Mar 27 23:14:30 CDT 2012


On Tue, Mar 27, 2012 at 2:38 PM, Jim Blandy <jimb at red-bean.com> wrote:
> 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???

You don't need to. M2 must in fact be lossy, being non-square, but
that doesn't matter. Once you recover M2 ks, you've completely broken
the cipher, and what's more it's not significantly better than
Caesar's cipher.

    M1 m ⊕ M2 ks = c

We're just scrambling the plaintext a little and XOR-ing it with a
64-bit key. It is totally trivial, and all it takes is a single
plaintext-ciphertext pair, *any* pair, to break it.

I think the lesson is that linear functions really don't make good ciphers.

-j



More information about the Boneh-crypto-course mailing list