How can I break this block-cipher?

Question

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.

Answer 1

Since you only ask for help on your class assignment, I will not give you the whole answer, but will hopefully point you in the right direction.

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$?