# How can I break this block-cipher?

So we've got to do this assignment for our study, but we can't figure out what to do, can someone help?

Assume that Alice and Bob want to communicate via encrypted email. To this end, they first meet in person and agree on a common secret key k and block cipher $(P,C,K,E,D)$ with plaintext space $P$, ciphertext space $C$, key space $K$ , encryption function $E$, and decryption function $D$. Afterwards, all email communication will be encrypted by using this chosen key and block cipher. Furthermore, assume that Alice and Bob choose a specific block cipher in ECB-mode with $P = C = K = \{0,1\}^{128}$ and with the property that $$E_k(m\oplus m_0) = E_k(m)\oplus E_k(m_0)$$ for the key $k$ and all messages $m,m_0 \in P$.

Now, assume that one day, Alice is using her computer in her office at work and forgets to lock her computer while she is just quickly out of office to get her lunch. In the meantime, you as the hacker go into her office (which is also left unlocked) and get access to her computer. Although you cannot get access to the secret key $k$ (which is securely stored), you can use her email client to decrypt any ciphertext of your choice.

Since you do not have much time as Alice is already coming back to her office, you are able to decrypt exactly 128 ciphertexts.

1. Which are the 128 ciphertexts that you would choose to decrypt so that later on you are able to decrypt all email communication encrypted under the key $k$ (although you’ve never seen that key)?
2. Describe how you successfully decrypt any encrypted e-mail by using your 128 decrypted ciphertexts selected in (1). Concretely, this means that you need to explain, how you compute the plaintext $m$ of an arbitrary ciphertext $c = E_k(m)$ that was encrypted under the above block cipher $(P,C,K ,E,D)$.

Hint. Since Alice and Bob use ECB-mode, we can assume, without loss of generality, that all e-mails have a length of 128 bits.

• Which part are you stuck with - all of them? For a) there's only really one obvious answer, isn't there, given where else the number 128 appears in the question and especially given the relationship Ek(m⊕m0) = Ek(m)⊕Ek(m0) ? Is there anything here you need explaining?
– Rup
Oct 4 '16 at 10:55
• Actually, there is not one correct choice and all others are false. Considering the bitstrings as vectors, any combination is fine where no vectors are linearly dependent.
– tylo
Oct 4 '16 at 12:21
• @tylo Sure - I didn't mean only one answer exists, I meant 'why would you choose anything else?'. And given we have a free choice you're making part 2 more difficult for yourself if you do choose anything else.
– Rup
Oct 4 '16 at 14:01
• Thanks guys I think i undrrstand now, the ciphers i need to decrypt is all 0's and one 1, and change the place of the 1 every Time. With that I can use the flaw to decipher every message. Thanks! Oct 5 '16 at 10:53

You are able to decrypt any ciphertext you want, but only have time to decrypt 128. Let's think about this from another perspective. What if you already knew exactly what ciphertext you wanted to decrypt. Say the ciphertext is 126 zeros, followed by two ones (I'll denote this mathematically as $0^{126}11$). You could just ask for the decryption of that, easy enough.
How could you get the decryption of it, given the decryptions of $0^{127}1$ and $0^{126}10$?