16
$\begingroup$

I need to crack a stream cipher with a repeating key.

The length of the key is definitely 16. Each key can be any of the characters numbered 32-126 in ASCII.

The algorithm goes like this:

Let's say you have a plain text:

"Welcome to Q&A for people studying math at any level and professionals in related fields."

Let's say that the password is:

"0123456789abcdef"

Then, to encrypt the plaintext, just XOR them together. If the key isn't long enough, just repeat it. e.g.,

Welcome to Q&A for people studying math at any level and professionals in related fields.

                                 XOR

0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef0123456789ab

I have 2 English messages encrypted with the above algorithm and with the same key. I know about the communicative property of xor and that it can be exploited for the example above. I've read that this is a pretty weak cipher and it has been cracked. However, I have no idea how to do it. So, where can I find a cryptanalysis tool to do it for me?

$\endgroup$
2
  • 2
    $\begingroup$ with repeated key you don't even need a second message, because first message itself acts as multiple key-length messages, so it makes your task easier $\endgroup$
    – Anurag Uniyal
    Nov 13, 2012 at 21:56
  • $\begingroup$ This is a version of the Vigènere cipher en.wikipedia.org/wiki/Vigen%C3%A8re_cipher $\endgroup$
    – Matthew Towers
    Feb 3, 2015 at 11:34

4 Answers 4

Reset to default
16
$\begingroup$

Take the two encrypted messages and XOR them with each other. You'll get the XOR of the two original, unencrypted messages since the identical keys cancel out. Deciphering this just requires patience and a good understanding of the encoding (what exactly is being XORed - the ASCII values of the letters? Some other binary encoding? Are spaces retained?).

You can try some common words and letter combinations and look for places where XORing the word with the ciphertext yields an English-looking string (which would then be the corresponding word or letter combination at the other text). Also, the ciphertext will likely have numerous 0 values corresponding to places where both messages have the same letter. Such matches are more likely to be a pair of E's or a pair of Spaces than a pair of Q's or X's.

Having said all that, I don't know where you can find a tool to do it for you, and if you find one it'll be very sensitive to the particular encoding. It's much more fun to do this yourself.

EDIT: in the comments you're mentioning that it's indeed ASCII encoding. This makes the task much easier since many 8-bit sequences don't correspond to any legal ASCII character at all. Make a table of all the possible XORs of legal ASCII characters in your plain text and this will tell you, for each position in your text, what are the possible pairs of letters from the two messages.

$\endgroup$
4
  • $\begingroup$ Yes, the ASCII values of the letters are being XORed. Also, like I said, I was aware of the communicative property (XOR the two encrypted messages will give the XOR of the original messages). However, I don't know how to use this information. How do I get the original message with the XOR of those 2 messages? $\endgroup$
    – user8689
    Mar 25, 2011 at 7:25
  • $\begingroup$ Oh right, spaces are also retained. Basically, it XORS the ASCII value of every character with the ASCII values of the key. $\endgroup$
    – user8689
    Mar 25, 2011 at 7:36
  • 2
    $\begingroup$ Suppose you guess that one of the messages has the word "and" starting at the 10 letter. Given the XOR, you can determine what the other message must be at that location. If it's "xqf", you're guessing wrong. If it's "hei", you could be right. Keep trying this with different words across all locations and you'll be sure to decipher the thing. $\endgroup$
    – Alon Amit
    Mar 25, 2011 at 9:06
  • 1
    $\begingroup$ Worth noting for anyone stumbling upon this from a Google search, that this strategy is valid any time messages are XORed with the same key, whether the key is repeating or not. $\endgroup$
    – matt b
    Jan 25, 2013 at 20:15
3
$\begingroup$

The other answers can work but they make this a much harder problem than it is.

The first step it to determine the key length with IC or the Chi Test, but you seem to have done and determined the key to be 16 bytes.

After that, take the first byte and one every 16 after that. If the message is standard English the most common byte in that group should be a space (0x20) so xor that common byte with 0x20 to find the first byte of the key. Repeat that starting with the next byte, etc. until you have the entire key.

$\endgroup$
1
$\begingroup$

If you want to decrypt these texts, a good method is the old "Kasysky's method":

First, you have to know the frequencies of the characters in your plain text (if you know the language, it's easy). Then, search repeated characters and measure the space between them. If you make the greatest common divisor of the distances, it's probably that the GCD is the length of the key (name it L).

Lastly, when you know the length of the key, you can divide the ciphered message into chunks and measure the frequencies of characters (join the characters spaced by L positions). It's probably that the frequencies of characters in the ciphered text are similar to the frequencies of characters in the language that are written.

$\endgroup$
1
  • 2
    $\begingroup$ The message needs to be pretty long for this method to work. $\endgroup$
    – Yuval Filmus
    Mar 25, 2011 at 13:24
0
$\begingroup$

There's a good description of an approach that can be used to crack this in the cryptopals.com challenges, see set 1, problem 6 for details.

I've written a PowerShell script that can crack repeating xor key crypto based on the info in cryptopals.com's description of the algorithm. It generally works well, though this is a problem of probability not certainty, so your mileage may vary.

The Cryptopals.com method uses Hamming Distance at the bit level, which is effectively the Index of Coincidence.

If you want to try my script or read through it to understand the problem better, you can find a link to the script and a write up on its usage, deficiencies and workarounds at http://trustedsignal.blogspot.com/2015/07/cracking-repeating-xor-key-crypto.html.

$\endgroup$

You must log in to answer this question.