Cryptanalysis of XOR cipher with repeated key phrase

Question

My assignment is to cryptanalyze cipher text that we know was encrypted with a stream cipher (bitwise XOR of plain text and key stream), and decrypt to plain text. We know the key stream is a repeated English phrase. I have tried a variety of methods without success. They include applying the Kasiski examination to determine the length of the key stream, and analyzing where in the cipher text 0's appear, because x ^ x = 0, and so it might be possible to perform frequency analysis and determine what x is in this case. However, I have not had much success with these methods. Any help or hints would be greatly appreciated.

Answer 1

The first thing you should do is estimate the key length. While you may be able to do this using Kasiski examination, in this modern era of computers I very much recommend instead using the index of coindicence, which you can compute very easily, e.g. with this Python program:

import sys
msg = sys.stdin.read()   # read ciphertext from standard input

for step in range(1, 50):
    match = total = 0
    for i in range(len(msg)):
        for j in range(i + step, len(msg), step):
            total += 1
            if msg[i] == msg[j]: match += 1

    ioc = float(match) / float(total)

    # output the IoC as a percentage, and plot it as an ASCII bar chart
    print("%3d%7.2f%% %s" % (step, 100*ioc, "#" * int(0.5 + 500*ioc)))

(Actually, the ioc value this code computes is the raw ratio of matching pairs to all byte pairs a multiple of step bytes apart; unlike the Wikipedia definition I linked to above, it doesn't multiply it by the size of the alphabet. For simply comparing IoC values between different key lengths, this difference doesn't matter.)

For a quick test, I encrypted your question text (length = 628 bytes) by XORing it with the repeated string This is the key. (length = 16 bytes), and then ran the code above on it, and got the following output:

  1   2.39% ############
  2   2.49% ############
  3   2.38% ############
  4   3.45% #################
  5   2.35% ############
  6   2.55% #############
  7   2.28% ###########
  8   4.77% ########################
  9   2.41% ############
 10   2.40% ############
 11   2.28% ###########
 12   3.52% ##################
 13   2.34% ############
 14   2.26% ###########
 15   2.32% ############
 16   7.30% #####################################
 17   2.51% #############
 18   2.58% #############
 19   2.22% ###########
 20   3.26% ################
 21   2.24% ###########
 22   2.22% ###########
 23   2.43% ############
 24   4.82% ########################
 25   2.05% ##########
 26   2.35% ############
 27   2.40% ############
 28   3.06% ###############
 29   2.20% ###########
 30   2.33% ############
 31   2.15% ###########
 32   7.21% ####################################
 33   2.17% ###########
 34   2.39% ############
 35   1.97% ##########
 36   3.58% ##################
 37   2.07% ##########
 38   2.25% ###########
 39   1.98% ##########
 40   4.44% ######################
 41   2.09% ##########
 42   2.26% ###########
 43   2.06% ##########
 44   3.19% ################
 45   2.41% ############
 46   2.16% ###########
 47   2.16% ###########
 48   7.38% #####################################
 49   2.13% ###########

Looking at the output, you can clearly see the peaks in the IoC at multiples of the key length (16 bytes), as well as lower peaks at multiples of 4 and 8 (which evenly divide the key length).

---

Now that you've determined the key length, you're basically left with the task of solving 16 (or however many characters your key has) single-byte XOR ciphers, one for each key byte.

There are several ways to do that; for example, you could simply split the ciphertext into 16 columns and apply standard frequency analysis to each column:

1. Try to decrypt each column with every possible byte.
2. Compute the number of times each byte appears in the result.
3. Select the key byte that yields a distribution most similar to natural English letter frequencies according to some statistical distance measure.

In fact, we can do better than that: since we know that each of the columns is sampled from the same plaintext, and thus presumably has approximately the same plaintext byte distribution, we can pick any two columns, run a frequency analysis on both, and output the byte that, when XORed with one of the columns, makes its byte frequency distribution most similar (by some measure such as the Battacharyya coefficient) to the other one.

This will not directly give us the key bytes, but it does give us a very good guess about their pairwise XOR, without requiring any prior knowledge of the underlying plaintext byte frequency. Knowing the pairwise XORs of the key bytes, we can then reduce the problem to that of guessing any one of the actual key bytes, which is very easy.

Computing the most likely XOR between each pair of key bytes also gives us a nice built-in consistency check: the XOR values $x_{ij}$ should satisfy the consistency relation $x_{ik} = x_{ij} \oplus x_{jk}$ for all $i$, $j$, $k$; if they do not, that's a sign that (at least) one of the values must be wrong, and it might be worth trying one of the other likely values.

(I ran this test on the same example ciphertext as above, and it guessed all but one of the pairwise XORs between the key bytes correctly. Spotting the single mistake was easy due to the failed consistency check.)

---

For the particular case where the key and/or the plaintext are (mostly) ASCII text, it may be quicker to exploit the bit structure of ASCII, and particularly the following facts:

• Ordinary ASCII uses only 7 bits per character, so the eighth bit will always be zero in plain ASCII text. (If there are any bytes in the ciphertext with the eighth bit set, it implies that either the plaintext and/or the key contains some non-ASCII bytes — possibly UTF-8 or one of the ISO Latin charsets.)

• All ASCII letters have the seventh bit set, while spaces and numbers and (most) punctuation has it unset.

• The sixth bit is set for lowercase letters and unset for uppercase letters. The ASCII space character only has the sixth bit set, and so XORing a letter with a space merely flips the case of the letter!

• All ASCII bytes with both the sixth and the seventh bit unset are unprintable control characters; the only ones likely to appear in normal text are the line feed (LF = 0xA), tab (0x9) and possibly the carriage return (CR = 0xD, normally always followed by a line feed).

• Numbers have the seventh bit unset, and the fifth and sixth bit set.

In particular, this implies that:

1. If one of the ciphertext columns contains only null bytes and letters, and if most of the letters are uppercase, then it's fairly safe to guess that the corresponding key byte is a space (or possibly a punctuation mark).

2. Conversely, if a column contains mostly control characters and a few uppercase letters, with most of the letters being the same, then the corresponding plaintext byte is probably a lowercase letter (and probably the lowercase version of the most common uppercase letter in the column).

3. Finally, if a column contains mostly numbers and punctuation, with a few lowercase letters, then the corresponding plaintext byte is probably an uppercase letter (and probably the uppercase version of the most common lowercase letter in the column).

For example, I took the example ciphertext I got by encrypting your question with the 16-byte key This is the key. and split it into 16 separate files each containing one column. Here are hex dumps of all these files:

Column 0:
0000000: 1974 7420 3720 203d 2726 2c3f 2674 203b  .tt 7  ='&,?&t ;
0000010: 2174 3335 313c 313a 3735 2c3b 2739 2d3a  !t351<1:75,;'9-:
0000020: 2031 3523 303c 2631                       15#0<&1
Column 1:
0000000: 111c 0b48 1a1a 1f06 1c11 1c0d 0d18 1a0e  ...H............
0000010: 1c01 4805 1a48 090f 0118 4848 1b48 1b0d  ..H..H....HH.H..
0000020: 001a 0c01 1b01 0d0c                      ........
Column 2:
0000000: 4906 001e 100c 0049 1b19 4710 1901 0049  I......I..G....I
0000010: 4907 1d00 0406 0449 1919 3700 000f 0049  I......I..7....I
0000020: 0045 491d 4707 0847                      .EI.G..G
Column 3:
0000000: 1253 0316 0312 0007 1607 5353 1601 161e  .S........SS....
0000010: 0010 1b1d 1a15 5f04 1b16 5307 1101 0004  ......_...S.....
0000020: 0053 1e1b 5307 0779                      .S..S..y
Column 4:
0000000: 5343 4800 544d 4545 4100 7753 4141 4445  SCH.TMEEA.wSAADE
0000010: 554c 4541 4e00 0048 4541 5800 4c45 0048  ULEAN..HEAX.LE.H
0000020: 0069 5500 6153 4c                        .iU.aSL
Column 5:
0000000: 1a1b 0c02 0c49 4911 041d 0c1d 1d1a 491d  .....II.......I.
0000010: 0a1c 491d 0c1d 080c 1b1b 4904 0c18 0808  ..I.......I.....
0000020: 0a49 0a1d 0749 10                        .I...I.
Column 6:
0000000: 1a0a 011d 1710 2b07 5a1c 5301 1616 121b  ......+.Z.S.....
0000010: 1017 381a 531b 1d01 535f 4e1a 5306 1d07  ..8.S...S_N.S...
0000020: 121b 1b1b 0a04 53                        ......S
Column 7:
0000000: 4750 004f 0049 6f00 0c00 4b45 440e 004f  GP.O.Io...KED..O
0000010: 4545 414f 5445 4445 5400 0047 5445 4400  EEAOTEDET..GTED.
0000020: 5341 0045 004f 41                        SA.E.OA
Column 8:
0000000: 1a00 0003 0304 2615 5404 1a15 5454 0210  ......&.T...TT..
0000010: 0754 071a 1c54 5454 1116 441c 1b1a 540c  .T...TTT..D...T.
0000020: 1102 0707 1c01 04                        .......
Column 9:
0000000: 0509 0d48 0100 4806 0904 0705 2d21 091b  ...H..H.....-!..
0000010: 1b09 0148 0d03 0901 100d 441c 480b 0c48  ...H......D.H..H
0000020: 460d 1d0d 0d04 18                        F......
Column 10:
0000000: 000b 1d12 1100 0a01 0b04 1245 0b45 1745  ...........E.E.E
0000010: 4b15 1611 4500 0b0b 1106 4545 151c 000c  K...E.....EE....
0000020: 4545 0645 0901 17                        EE.E...
Column 11:
0000000: 4e41 5441 4852 4600 4449 0049 4748 4957  NATAHRF.DI.IGHIW
0000010: 0050 4b4f 4c59 4100 0041 4142 4500 5453  .PKOLYA..AABE.TS
0000020: 684e 434d 5000 45                        hNCMP.E
Column 12:
0000000: 1f07 4b18 4b4b 4b00 4b05 1f18 070a 0e02  ..K.KKK.K.......
0000010: 3f07 024b 0e4b 071f 5b1e 050e 190a 0e4b  ?..K.K..[......K
0000020: 0404 0e0e 4b09 08                        ....K..
Column 13:
0000000: 451c 1145 044d 1500 0145 0d45 0c13 1111  E..E.M...E.E....
0000010: 0d1c 4501 0b16 1c0d 4216 0145 030b 170c  ..E.....B..E....
0000020: 1211 1611 0a00 0c                        .......
Column 14:
0000000: 1003 111c 591b 1500 1c0d 1c18 0a1c 0011  ....Y...........
0000010: 1c10 1c1c 1e0d 031c 0a1c 5909 1618 1417  ..........Y.....
0000020: 1c59 0a11 0b59 18                        .Y...Y.
Column 15:
0000000: 5d4b 4f40 5d47 4f0e 4d4b 0e0e 460e 0e41  ]KO@]GO.MK..F..A
0000010: 5740 565a 5a5c 470e 0e0e 5d41 5c42 470e  W@VZZ\G...]A\BG.
0000020: 5846 0e41 0e49 5a                        XF.A.IZ

You can clearly see that the columns corresponding to spaces (or the period at the end) in the key look completely different from the ones that correspond to letters. The first column, corresponding to the uppercase T, has mostly punctuation and a few lowercase ts mixed in, while the columns corresponding to lowercase key letters contain mostly control characters plus some uppercase versions of the key letter (where the plaintext byte happened to be a space).

There's also a subtle but noticeable difference between the columns where the key byte is a space and the last one where it's a period: while both contain a lot of uppercase letters and some control characters, the last column also contains a bunch of punctuation (particularly @, [, \, ], ^ and _, which have the same sixth and seventh bits as uppercase letters in ASCII), and the control characters are mostly 0x0E (. = 0x2E, XORed with space = 0x20) rather than nulls.