5

Given the linear block cipher $\operatorname{LinearCipher}(k, p) = c$

$$\operatorname{LinearCipher}(k, p_1 \oplus p_2) = \operatorname{LinearCipher}(k, p_1) \oplus \operatorname{LinearCipher}(k, p_2)$$

where $k$ and $p$ are 128-bits.

If an attacker uses a chosen-cipher-text attack, how can they decrypt any plaintext by choosing 128 ciphertexts?

I'm not exactly sure in which direction I have to think. I believe decryption will also be linear since in linear algebra the inverse of a linear function is also linear. The fact that the attacker can choose 128 ciphertexts hints at maybe revealing the key 1-bit at a time. Any hints and suggestions would be helpful.

fgrieu
  • 131,696
  • 12
  • 284
  • 553
Dimitar Stratiev
  • 53
  • 1
  • 3
  • That's a possible definition of a linear cipher, but there are more general ones, that do not require $\operatorname{LinCipher}(k, 0) = 0$; that would be the weaker:$$\operatorname{LinCipher}(k, p_1 \oplus p_2 \oplus p_3) = \operatorname{LinCipher}(k, p_1) \oplus \operatorname{LinCipher}(k, p_2) \oplus \operatorname{LinCipher}(k, p_3)$$which is common in cryptanalysis. – fgrieu Feb 13 '16 at 17:07

1 Answers1

5

You already got the answer by yourself.

As a linear cipher with 128 bit, it can be described by a 128x128 matrix over GF(2). To break the cipher is to find that matrix. But that's easy: column k is the decryption of the k'th standard basis, i.e. the vector (0,0,0,...1,...,0,0,0) , with the 1 on the k'th place.

Example:
Decrypt(0001) = 1101
Decrypt(0010) = 0001
Decrypt(0100) = 1010
Decrypt(1000) = 1111

This gives the matrix M:
1011
1001
0011
1101

Now lets say the cipher text is $c= (1111)^T$

The decryption of c is $M*c = (1001)^T$

  • Hmmm... this is still unclear. Could you please elaborate on it. Perhaps an example of say 4-bit blocks instead of 128 will help with the explanation. – Dimitar Stratiev Oct 12 '15 at 19:56
  • Ahh.. I see it now! The fact that the question read "decrypt any plaintext" threw me off. I thought it required some extra work like basis translation but In fact it's asking of how I can decrypt any given ciphertext rather than plaintext. Also isn't the second bit of M*c 0,since 1 xor 0 xor 0 xor 1 = 0? – Dimitar Stratiev Oct 12 '15 at 20:55
  • you are right, I corrected it! –  Oct 12 '15 at 21:02
  • I still have one more question lingering in my head, perhaps I would've known this if I studied linear algebra more thoroughly. I notice that the columns of M are linearly independent. Is it always true that a set of basis vectors will translate to another set of basis vectors? If no, is that only true due to linearity? – Dimitar Stratiev Oct 12 '15 at 21:33
  • 1
    I don't think that's true in general, but in this case the decryption function needs to have that property for the cipher to be a permutation... Otherwise the preimages of the basis vectors would span a smaller vector space and you'd get cipher that's 1-1 but not onto. – pg1989 Oct 13 '15 at 20:18