Konstantin Hamidullin from Latvia has solved my Playfair challenge from November 2019. With only 26 letters, this is the shortest Playfair cryptogram ever broken.
The Playfair cipher was invented by Charles Wheatstone in the 19th century. Like most other paper-and-pencil ciphers, it can be broken, provided that the ciphertext is long enough. Last year, George Lasry, …
Source: Schmeh
… solved a Playfair cryptogram consisting of only 50 letters. As far as I know, this success set a new world record in breaking a Playfair with a random matrix. (US cryptanalyst Alf Monge broke a 30-letter Playfair in the 1930s, but this one was based on a matrix created with a keyword, which made things easier.)
The self-written software George used to break this Playfair challenge was based on hill climbing (enhanced with simulated annealing), a technique that guesses keys and rates the correctness of each guess, until finally an acceptable result is found.
In order to check if it is possible to break even shorter Playfair cryptograms, I published a Playfair challenge based on a ciphertext with 40 letters. This time, Nils Kopal solved it (again with hill climbing) and thus reached a new world record.
Source: Bonavoglia
After Nils’ success, I took a 30-letters plaintext for my next Playfair challenge. This time it was Magnus Ekhall, who broke it. His solution was based on hill climbing, too. Magnus is a Swedish computer engineer, working in software development.
Source: Ekhall
My next Playfair challenge was based on a 28-letters plaintext. Again, it was Magnus Ekhall who broke it. With these successes, Magnus became the new Playfair world record holder.
—————————————–
I’m excited to announce I’ll be speaking at RSAConference 2020 on UNDERSTANDING AND EXPLAINING POST-QUANTUM CRYPTO WITH CARTOONS.
—————————————–
How the Playfair works
I assume that meanwhile most readers of this blog know how the Playfair cipher works. For those who don’t, this section gives an introduction.
The Playfair cipher substitutes letter pairs. So, the cleartext needs to be written as a sequence of letter pairs (the following cleartext is a Shakespeare quote taken from Robert Thouless’ life-after-death experiment):
BA LM OF HU RT MI ND SG RE AT NA TU RE SS EC ON DC OU RS EC HI EF NO UR IS HE RI NL IF ES FE AS T
The Playfair cipher requires that no letter pair consist of two equal letters. Therefore, we add an X between the two Ss:
BA LM OF HU RT MI ND SG RE AT NA TU RE SX SE CO ND CO UR SE CH IE FN OU RI SH ER IN LI FE SF EA ST
If the number of letters in the cleartext is odd, another X needs to be added at the last position, but this is not the case here. Next, we set up a 5×5 matrix containing the letters of the alphabet in a random order (we identify the J with the I, in order to get a 25 letter alphabet):
S U R P I E A B C D F G H K L M N O Q T V W X Y Z
As you might have noticed, the letter order in the matrix has been derived with the keyword SURPRISE. It would be more secure to use a completely random order of the letters.
Now, we replace the cleartext letter pairs (BA, LM, OF, HU, …) according to the three Playfair rules. Here are the rules in a diagram:
Here are the same rules in text form (I refer to the letter pair to be replaced as XY):
- If X and Y are not in the same column and not in the same row (this is the most frequent case), form a rectangle and replace the two letters by the other two corner letters (the upper cleartext letter is replaced by the other upper letter in the rectangle, the lower cleartext letter by the lower one). For instance, LM becomes FT.
- If the two letters stand in the same row, each one is replaced by its right neighbor. Here, BA becomes CB.
- If the two letters stand in the same column, each one is replaced by its lower neighbor. In our example, AN becomes GW.
When we apply the Playfair rules on our cleartext with our 5×5 matrix, we get the following ciphertext:
CB FT MH GR IO TS TA UF SB DN WG NI SB RV EF BQ TA BQ RP EF BK SD GM NR PS RF BS UT TD MF EM AB IM
A new Playfair challenge
After Magnus had successfully attacked my 28-letters cryptogram, I decided to take a 26-letters cipherttext for my next challenge. Here’s the ciphertext CrypTool 2 delivered:
DB AQ IH KN RW VB KW NA DQ WR AM OQ IY
A few days ago, a reader posted the correct solution on my blog. He wrote:
One option which looks plausible is:
WAIT FOR FURTHER INSTRUCTIONS
with matrix
rweku yd**s nacfi *b*ho *tmvq
where * stand for remaining letters.
In fact, this solution was correct. Based on the e-mail address the poster had used, I found out that his name was Konstantin Hamidullin. I had never heard of him before, let alone been in contact with him. So I wrote Konstantin an e-mail, and he replied immediately. He told me that he was a programmer from Riga, Latvia, writing mostly in C++.
To my big surprise, Konstantin had not used hill climbing for solving the Playfair challenge. Instead, he had conducted an exhaustive search with several optimizations. Each solution candidate was checked with a fitness function, as known from hill climbing.
Konstantin provided me the following report on how he found the solution:
I believed that 24! possible combinations of a matrix using a dictionary of English words can be somehow reduced to a much smaller set. Of course that was too optimistic, however I noted that if positions of several first letters of ciphertext are guessed correctly then the correct cleartext can be obtained relatively quickly.
After that I read about Magnus Ekhall’s solution and understood that simply mapping to words is not enough – the big obstacle would be making meaningful phrases.
So I changed my approach a little bit and started to generate English phrases and only then placed them on the matrix. At first, this resulted in a slower program, but potentially it was a superior method I believed. A good idea (borrowed from Magnus’ description of his solution) was to download books from Project Gutenberg and use word 2-grams, and then words 3-grams (there RAM limitations are quite sensible).
The general algorithm is the following: construct an English phrase from left to right, adding on each step two letters that a) keep the phrase meaningful and b) can be placed on the matrix. It appeared that combination of two “stop-factors” (a and b) is quite effective in reducing the size of exhaustive search.
How do I measure “meaningfullness”? Basically, each word is assigned a penalty value equal to -log(h/m), where h is frequency of the word and m is frequency of the most frequent word. The phrase is okay if the sum of all penalties doesn’t exceed a certain value.
Thanks and congratulations to Konstantin! This is a marvellous success!
Like so many times before, I’m overwhelmed by my reader’s skills in breaking difficult cryptograms. I’m proud that my challenges stimulate so much valuable research.
Follow @KlausSchmeh
Further reading: A mird in the hand is worth two in the mush: Solving ciphers with Hill Climbing
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/
Kommentare (4)