How to attack a "many-time pad" based on what happens when an ASCII space is XORed with a letter? I've already sent my correct solution to a homework exercise from Dan Boneh's Introduction to Cryptography class on Coursera:

&quot;Let us see what goes wrong when a stream cipher key is used more than once. Below are eleven hex-encoded ciphertexts that are the result of encrypting eleven plaintexts with a stream cipher, all with the same stream cipher key. Your goal is to decrypt the last ciphertext, and submit the secret message within it as solution.
Hint: XOR the ciphertexts together, and consider what happens when a space is XORed with a character in [a-zA-Z].&quot;

I managed to get the key by XORing ciphertexts #1 and #2, then XORing the result with the string &quot; the &quot; at each possible position.  Combined with a lot of guesswork, this gave me the first plaintext.
My question is: What would I have to do if I want to follow the hint? I know that if I XOR a space with a letter, I change the case of the letter, but then what?
I don't understand how I can recognize spaces!  Suppose I see a letter in $c_1 \oplus c_2$; how can I tell if there was a space in one of the plaintexts?
"Hint: XOR the ciphertexts together, and consider what happens when a space is XORed with a character in [a-zA-Z]." 


Let's assume that the plaintexts consist only of spaces and ASCII letters.  Given the hint, that seems like a reasonable assumption to start with, even if it might turn out to be only mostly correct.

Now, take one of the ciphertexts and XOR it with each of the others.  Of course, the XOR operation cancels out the keystream, so you end up with the plaintext corresponding to the chosen ciphertext XORed with each of the other plaintexts.

Now look at each character position in turn.  By assumption, the character at that position in the chosen plaintext might be either a letter or a space.


If it's a space, then the characters at that position in the pairwise XORed plaintexts will be either letters (if the character at that position in the other plaintext is a letter) or nulls (if both of the characters are spaces).
If it's a letter, then the characters at that position in the pairwise XORed plaintexts will be random control characters (if the character at that position in the other plaintext is a letter with the same case), numbers or punctuation (if the other character is a letter with different case) or that particular letter with the case flipped (if the other character is a space).


Those two cases should be pretty easy to tell apart.  Furthermore, in the first case, you can easily get the actual characters at that position in all the plaintexts just by flipping the case of all the letters you obtained by XORing the ciphertexts together.

In this manner, you can decode all the characters at the positions where the plaintext corresponding to the chosen ciphertext has spaces.  Once you've done that, choose another ciphertext and repeat the process.  Hopefully, by the time you've done this with all the ciphertexts in turn, you will have solved most of the character positions and can easily fill in the rest.



Ps. To see why this works, it helps to know that the 7-bit ASCII character set can be divided into four 32-character blocks, like this:

Bit 4:     0000000000000000 1111111111111111 |
Bits 0-3:  0123456789ABCDEF 0123456789ABCDEF | Block:
---------+-----------------------------------+---------------------------
Bits  00 | ................ ................ | Control characters
5-6:  01 |  !"#$%&amp;'()*+,-./ 0123456789:;&lt;=&gt;? | Numbers and punctuation
      10 | @ABCDEFGHIJKLMNO PQRSTUVWXYZ[\]^_ | Uppercase letters (mostly)
      11 | `abcdefghijklmno pqrstuvwxyz{|}~. | Lowercase letters (mostly)


In particular, a consequence of this structure is that, if you XOR two ASCII characters in the same row (e.g. two uppercase letters or two lowercase letters), the result will be a control character.  Similarly, XORing an uppercase and a lowercase letter will produce a character in the second row, i.e. a number or a punctuation character.  Also, as pointed out in the hint, the position of the space character at the beginning of the second row means that XORing it with any other character just flips bit the fifth bit of the character code, moving the character one row up or down.