Page 10


On Elaboration


I figured that the explanation given in the comic was sketchy at best and it warranted an elaboration.

The periodicity in the cipher text as demonstrated in the example is a result of a repetition in both the keystream and plaintext at the same time. The encryption can be described with the following function: c = e(k, p). Clearly, given the same k and p, e will produce the same c. In a normal text, repetition occurs frequently - names and words like "and", "the" occur frequently. If k is a small repeating word, then the probability of periodicity can be high.

In the above, a simplistic scheme where the key is repeated is used, yielding some interesting results. Observe the following:

Plain:
ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC
Key:
ABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCDABCD
Cipher:
ACEDBDCECBDFACEDBDCECBDFACEDBDCECBDFACEDBDCECBDF

The scheme is simple - the cipher text is the plain text shifted by the difference between the key and the letter "A" or c = (p >> |k-"A"|) mod 26. So "A" will result in a shift of 0, "B" a shift of 1 and "Z" a shift of 25 or -1. In the example above, the 4th letter of the plain text "A" is shifted by 3 to "D".

The plain text is repeated every 3 letters and the key every 4 letters. A further inspection will show that the cipher text is repeated ever 12 letters - 12 being the lowest common multiple of 3 and 4.) The period that results is a multiple of the keys length. By noting the letter count before repetition in the cipher occurs, we have a set of numbers that are multiples of the key length. The lowest common denominator is then likely to be actual key length.

By breaking the cipher text into separate smaller texts where the same key is used to encipher the plain text, we would then have cipher texts where frequency analysis can be used. In the event that the lowest common denominator is not the actual key length, we would end up with a key that is "ALICEALICE" instead of "ALICE"

This example is of course contrived but it does assist in demonstrating the weakness of repeating keystreams in stream ciphers. It is, however, an actual cipher that was used back in the 15th century. The Vignere Cipher was by far one of the most successful polyalphabetic cipher used in those days and remained unbreakable for quite a while. Current ciphers do not actually use the key as the keystream but rather generate the keystream using the key as seed. A modern day example would be the attack on a 32-bit RC4 used in the original implementation of WEP. The attack method is of course different than that used in the above.


Next