Decrypting messages crypted with one time pad (used more than once)

Question

I have a stream cipher with a key (that is unknown to me) that is used more than once. Messages are ciphered in this way:

ciphered_message = message XOR key

Let's assume that I have 23 messages (all ciphered with same key) and the original messages contain only upper and lower case letters and spaces.

I've understood that if you xor a space with a space the result is zero, and if you do Letter uppercase xor Space = Letter lowercase (and vice-versa).

I have to get the original messages (at least a part...). How can I do that? I have to use frequency analysis, right? I'm trying to write some code but I'm stuck!

import binascii

def xor(a, b):
    return bytes(x ^ y for (x, y) in zip(a, b))

def read_msgs(input_filename):
    try:
        with open(input_filename) as f:
            rawmsgs = f.read().splitlines()
    except Exception as e:
        raise Exception("Cannot read {}, error={}".format(input_filename, e))

    return [ binascii.unhexlify(m) for m in rawmsgs ] # each message is an array of byte

def xor_all_msgs( messages ): # return a matrix, first row is the first message xored with the others
    ret= []

    for current_msg in messages: # xor message "current_msg" with the others
        xor_with_current= [ xor(current_msg, other_msg) for other_msg in messages if current_msg is not other_msg ]
        ret.append(xor_with_current)

    return ret

def xor_is_space( c ):
    return (ord('a') <= c <= ord('z')) or (ord('A') <= c <= ord('Z'))

def main():
    msgs= read_msgs("ciphertexts.txt")
    xor_all_msgs(msgs)

if __name__ == "__main__":
    main()

Answer 1

First of all, there is nothing really special about spaces. It is a fact of how the ascii encoding is put together that e.g. chr(ord('a') ^ ord(' ')) = 'A' and vice versa. Your code should just xor things together and not try to do anything special if the key character is a space.

4 important properties of xor are:

1) a xor 0 = a
2) a xor b = b xor a
3) a xor a = 0
4) a xor (b xor c) = (a xor b) xor c

(i.e. xor gives rise to an Abelian group where every element is its own inverse).

This implies that if a and b are both encrypted by the same k, to get cipher texts a xor k and b xor k, then if you xor the two cipher texts together you get:

(a xor k ) xor (b xor k) = (a xor b) xor (k xor k) 
                         = (a xor b) xor 0 
                         = a xor b

k drops out leaving you with a encrypted by b.

Now -- if you have 23 ciphertexts, xor the last 22 with the first one. The result is now 22 new ciphertexts encrypted with the same key (where the first albeit unkown plaintext is the common key). At first this seems pointless -- but note now that the key is far from random whereas the original key was likely to be random. You are assuming something about the alphabet the first message is written in and are hoping that it should have a reasonably common frequency profile.

What you can do is the following -- and this can be automated in Python: For each character position in message 1, pick the character in 'a'-'z','A'-'Z',' ' which renders the statistical profile of the characters at that position in the remaining 22 cipher texts as close to English as possible. As a simple expedient, pick the character which maximizes the count of the 4 or 5 most common letters in the English language (or whatever natural language is being used). This gives you a tentative decryption of message 1. It is almost certainly wrong -- but there should be more than enough for you to guess most of the words in it -- and you have 22 ways to verify each guess. Further more, as more and more words in message 1 fall into place, you start getting trial decryptions of the remaining 22 messages, including words that you can guess and that shed light on any portions of the first message that are still known. Once the dominoes start falling, they should fall quite rapidly.

One possible use of the observation concerning spaces is that, since lower case letters are much more common that upper case letters, if after you get your 22 messages encrypted with the first one, if you see any position in which the overwhelming majority of the 22 characters in that position are upper case, it is somewhat likely that the corresponding position in the first message is a blank, which could help you guess where the word boundaries in the first message is. Also -- I have been assuming that all messages are the same length. Obviously things are slightly more complicated if the messages are of variable length, though these sorts of idea will still work (though the longest message would likely have a tail which in incapable of decryption).