Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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 –  Anurag Uniyal Nov 13 '12 at 21:56

2 Answers 2

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.

share|improve this answer
    
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? –  user8689 Mar 25 '11 at 7:25
    
Oh right, spaces are also retained. Basically, it XORS the ASCII value of every character with the ASCII values of the key. –  user8689 Mar 25 '11 at 7:36
2  
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. –  Alon Amit Mar 25 '11 at 9:06
    
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. –  matt b Jan 25 '13 at 20:15

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

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

When you know the length of the key, you can divide the ciphered message into chunks and measuse 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.

share|improve this answer
1  
The message needs to be pretty long for this method to work. –  Yuval Filmus Mar 25 '11 at 13:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.