Kasiski/Kerckhoff Attack - A worked example

Previously I discussed how to attack a repeating key (e.g. Vigenère or Beaufort) using a method called ‘Index of Coincidences’

I’d also like to demonstrate the ‘Kasiski/Kerckoff’ attack. This article was brought forward due to a comment on the Index of Coincidences article.

In preparing this article, I used a javascript tool.

Let’s look once again at the text to be broken.

VKMHG QFVMO IJOII OHNSN IZXSS CSZEA WWEXU
LIOZB AGEKQ UHRDH IKHWE OBNSQ RVIES LISYK
BIOVF IEWEO BQXIE UUIXK EKTUH NSZIB SWJIZ
BSKFK YWSXS EIDSQ INTBD RKOZD QELUM AAAEV
MIDMD GKJXR UKTUH TSBGI EQRVF XBAYG UBTCS
XTBDR SLYKW AFHMM TYCKU JHBWV TUHRQ XYHWM
IJBXS LSXUB BAYDI OFLPO XBULU OZAHE JOBDT
ATOUT GLPKO FHNSO KBHMW XKTWX SX

In the Kasiski attack, we look for sequences of letters that are repeated. The idea is that a common letter pattern (e.g. THE) has been encoded using the same key fragment and encoded in the same way. If we find repeats then we would count the distance between the repeats. This would be a multiple of one key length.

HNS: occurs 3 times, at pos 16, 94, 256
     distance(s): 78, 240, 162
UHR: occurs 2 times, at pos 45, 201
     distance(s): 156
WEO: occurs 2 times, at pos 53, 77
     distance(s): 24
EOB: occurs 2 times, at pos 54, 78
     distance(s): 24
QRV: occurs 2 times, at pos 59, 161
     distance(s): 102
KTU: occurs 2 times, at pos 91, 151
     distance(s): 60
TUH: occurs 3 times, at pos 92, 152, 200
     distance(s): 60, 108, 48
TBD: occurs 2 times, at pos 122, 176
     distance(s): 54
BDR: occurs 2 times, at pos 123, 177
     distance(s): 54
BAY: occurs 2 times, at pos 166, 220
     distance(s): 54

Listing the distances between repeats we have: 78, 240, 162, 156, 24, 24, 102, 60, 60, 108, 48, 54, 54, 54. Notice how these are all multiples of 2 and 6 - this strongly suggests that the key length is either 2 or 6. However, if the key length was 2, we’d expect multiples of 4 as well! This distribution suggests that the key length is six letters.

Please note, that one should not get hung up on finding one common factor - it is possible by chance that one might get a repeat at some other multiple. Look for the most likely repeat.

A nice way to visualise this is to use a simple plot. One would make an axis from 0 to 240 (in this case) and mark next to the axis each time there was a repeat. The bars would appear predominantly at a seperation equal to the key length (though there may be some exceptions). This is most noticable from 48 to 60 in the above example.

As an aside, this has rather nice parallels with Millikan’s experiment to find the size of the electronic charge.