Score:2

Using whitespace to break many-time-pad stream cipher

th flag

I have a question about the first programming assignment in Dan Boneh's cryptography course on Coursera. You're given 10 ciphertexts that were encrypted with the same key and you can presumably assume that the plaintext consists of letters and whitespace only.

The hint gives that you should consider what happens when a whitespace is xor-ed with a letter. The idea is to check whether the xor-ed subparts of the ciphertext combinations correspond to a letter, which should allow us to figure out the key.

If we do find a letter, I think we should be able to recover that part of the key, that corresponds to the letter we're currently processing, by doing the following:

Let c_sub1 and c_sub2 be the sub-parts of the ciphertexts c1 and c2 that we currently check and let m_sub1 and m_sub2 be the corresponding sub-parts of the plaintexts. One of m_sub1 or m_sub2 must be a whitespace. To figure out which one, we try the following: Assuming m_sub1 is a whitespace, get the corresponding sub-part of the key (k_sub) by xor-ing c_sub1 with 00100000 (the binary representation of a whitespace char), k_sub = xor(c_sub1,00100000), and check if encrypting the case-flipped letter (since xor-ing with a white space flips the case of a letter) with k_sub yields c_sub2, if it does we should know that k_sub is the correct sub-part of the key. If not, try the same with assuming that m_sub2 is a whitespace.

I can't find any logical mistake in that reasoning, but my implementation yields an incorrect solution and I'm fairly sure I've eliminated all other bug possibilities. Can anybody tell me whether this approach is wrong, please?

Score:1
in flag

check if encrypting the case-flipped letter (since xor-ing with a white space flips the case of a letter) with k_sub yields c_sub2, if it does we should know that k_sub is the correct sub-part of the key. If not, try the same with assuming that m_sub2 is a whitespace

Currently you are pairing two ciphertext streams, while you have 10 of them. You should choose one stream out of 10 and then perform the XOR with all other 9 at the same position. If most of those streams return letters (and no invalid combinations of a XOR - but that's harder to test) then you can be pretty certain that the encrypted character is a space, and you can find the key by the XOR you perform in your answer.

I think it might be the case in Boneh's assignment, but beware that you may encounter plaintext combinations that together may produce a letter as well. So you cannot simply perform a XOR with two streams, and validate your guess that way. The more streams you have, the more sure you are; in the end you can of course validate by looking at the plaintext messages as well and/or use your language skills to fill in the blanks.


If I remember correctly I took it on a bit differently. I took one stream, iterated over all characters in the alphabet (note: the possible input characters is called "the alphabet" here, I don't mean the ABC) for each position, and then XOR'ed all three together. If all streams produced results in the alphabet then I hit the right character. This allows you to only handle characters in the alphabet, not weird XOR combinations.

If multiple characters are found, then use the one that produces the most used characters in all the streams together (frequency analysis).

If that still doesn't produce results you can try other streams as well (you would only have to compare stream 2 with 8 streams of course, as you already compared #1 and #2).


OK, so lets say we have the first position (positions are not indicated in the variable names) and a set of streams. Now let us start with the first stream, and XOR it with all other streams, denoted by $y$ where $y != 1$.

You have a pair of two ciphertext values that consist of $c_1 = p_1 \oplus k$ and $c_y = p_y \oplus k$. So XOR'ing together gives you $r = c_1 \oplus c_y = p_1 \oplus p_y$ (nothing new here). Now if you guess $p_1$ and call it $p'_1$ you would get $p'_1 \oplus p_1 \oplus p_y = p'_y$. Now if $p'_y$ is an invalid character then obviously $p'_1$ was a wrong guess. If you're unlucky then you need to perform frequency analysis on all the resulting $p'_y$. But remember that you can do this with all $\binom{n+1}2$ pairs before resorting to that.

Once you have $p'_1 = p_1$ then obviously the key is just the XOR with the ciphertext character: $c_1 \oplus p_1 = k$. That means that you only have to iterate over the alphabet rather than all the keys, and you can really quickly dismiss bad tries.

eager2learn avatar
th flag
Thanks for your answer. I have some questions:
eager2learn avatar
th flag
"beware that you may encounter plaintext combinations that together may produce a letter as well. So you cannot simply perform a XOR with two streams, and validate your guess that way". I was thinking about that, but I don't understand how you would validate this with multiple streams. Should you just count for each position in the key which key resulted from xor-ing two pairs of ciphertext and then choose the most frequently occurring key subsequence?
eager2learn avatar
th flag
" I took one stream, iterated over all characters in the alphabet (note: the possible input characters is called "the alphabet" here, I don't mean the ABC) for each position, and then XOR'ed all three together. If all streams produced results in the alphabet then I hit the right character." Why do you xor three sequences here, the quote only mentions one stream and then a character in each iteration? Also I don't understand why xor-ing an element in the alphabet with a sub-sequence of a ciphertexts should result in a letter
Maarten Bodewes avatar
in flag
Added an explanation with the actual XOR.
eager2learn avatar
th flag
I have one more question: In your approach how do I know whether the element from the alphabet that I guessed correctly ($p'_1=p_1$) corresponds to $c_1$ or $c_y$?
Maarten Bodewes avatar
in flag
You don't, but it becomes more likely when the other streams return expected results. This is always the case of course. Imagine that all streams have the same character at a specific location... This would immediately be apparent from the ciphertext, but *which* character remains unknown - you can only guess it from the rest of the plaintext messages that you *can* recover.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.