21
$\begingroup$

I've already sent my correct solution to a homework exercise from Dan Boneh's Introduction to Cryptography class on Coursera:

"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]."

I managed to get the key by XORing ciphertexts #1 and #2, then XORing the result with the string " the " 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?

Improve this question
$\endgroup$
10
  • $\begingroup$ @poncho I can't understand how can I recognize spaces! Suppose in $c_1 \oplus c_2$, I see a letter, how can I say if there was some space in one of the plaintexts? I've asked here because in that question there isn't the explanation of my doubt! $\endgroup$
    – sunrise
    Jan 18, 2013 at 18:05
  • $\begingroup$ Consider bit 6 of $c_1 \oplus c_2$. If $c_1$ and $c_2$ are both betters, bit 6 will be clear (because bit 6 of both $c_1$ and $c_2$ are both set). If one is a letter and one is a space, then bit 6 of $c_1 \oplus c_2$ will be set. Hence, we have a good guess that there is a space in one of the two plaintexts. Now, consider the case where we have 11 ciphertexts; if 3 of the plaintexts have a space at position 7, then that fact should be obvious (because bit 6 of those ciphertexts will be different, and all those ciphertexts will have the same value there). $\endgroup$
    – poncho
    Jan 18, 2013 at 19:02
  • $\begingroup$ @poncho thanks. suppose that I manage to know that the first word of the first ciphertext is 5 letters. How should I go on? How can I discover the word? $\endgroup$
    – sunrise
    Jan 18, 2013 at 19:11
  • 1
    $\begingroup$ Given that we seem to regularly get questions about this specific Coursera assignment, I'd like to suggest reopening this question and treating it as the canonical question about that and other similar exercises. Admittedly, as the author of the accepted answer, I might be biased here, but I still feel that this question is sufficiently distinct from the one it's currently closed as a dupe of to be reopened. $\endgroup$
    – Ilmari Karonen
    Apr 21, 2017 at 15:52
  • 1
    $\begingroup$ I have again voted to reopen this question, since yet another potential duplicate of it was recently asked here. I do not believe this question should be closed as a duplicate of crypto.stackexchange.com/q/2249, since that question does not in any way mention the specific hint that this question asks about (and neither do any of its answers so far). I also considered copying my answer below over to that question instead (and deleting it here), but it just does not naturally fit there. $\endgroup$
    – Ilmari Karonen
    Nov 3, 2018 at 0:44

1 Answer 1

Reset to default
31
$\begingroup$

"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 |  !"#$%&'()*+,-./ 0123456789:;<=>? | 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Maybe I'm being a bit dense at the moment, but could you explain your notation for the table? What's the meaning of "Bit 4", "Bits 0-3", "Bits 5-6"? It's not easy to see how that corresponds to the binary code representation found in this table: ascii-code.com $\endgroup$
    – AutonomousApps
    Nov 2, 2015 at 6:10
  • 2
    $\begingroup$ @AutonomousApps: Look at the "bin" column in the table you linked. Note that bits are conventionally numbered from right to left, with bit 0 being the rightmost (i.e. the numerically least significant) bit. $\endgroup$
    – Ilmari Karonen
    Nov 2, 2015 at 10:56

Your Answer

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

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