Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This question already has an answer here:

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?

share|improve this question

marked as duplicate by figlesquidge, DrLecter, AFS, rath, Maeher Jan 15 at 10:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
@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! –  sunrise Jan 18 '13 at 18:05
    
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). –  poncho Jan 18 '13 at 19:02
    
@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? –  sunrise Jan 18 '13 at 19:11
    
If you know that the 6th character of the first plaintext is a space, you can then deduce the 6th character of every other plaintext. Extending this observation, you can deduce any character of any plaintext where there's another plaintext with a space at that position. That should give you a large majority of the plaintexts; guessing (based on context) and verifying (based on whether it makes the other plaintexts make sense) the little that is left should be straight-forward. –  poncho Jan 18 '13 at 19:21
    
And good luck doing the programming requirement of Coursera Crypto I from Dan Boneh :) They were fun assignments for sure. –  owlstead Jan 18 '13 at 23:27

2 Answers 2

up vote 12 down vote accepted

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.

share|improve this answer

Hint: Are you familiar with frequency analysis (for breaking classical ciphers)?

Hint: If you have a guess/hypothesis that there is a space at a particular position in one of the ciphertexts, can you think of any way to test whether your guess/hypothesis seems likely to be correct or not?

share|improve this answer

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