5
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Commented Feb 13, 2016 at 17:07

1 Answer 1

Reset to default
5
$\begingroup$

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$

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Dimitar Stratiev
    Commented Oct 12, 2015 at 19:56
  • $\begingroup$ 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? $\endgroup$
    – Dimitar Stratiev
    Commented Oct 12, 2015 at 20:55
  • $\begingroup$ you are right, I corrected it! $\endgroup$
    – user27950
    Commented Oct 12, 2015 at 21:02
  • $\begingroup$ 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? $\endgroup$
    – Dimitar Stratiev
    Commented Oct 12, 2015 at 21:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – pg1989
    Commented Oct 13, 2015 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.