The Fleissner grille is one of the most popular encryption tools. In spite of its popularity, surprisingly little has been published about deciphering a Fleissner grille. I wonder if a reader can break the Fleissner challenge I am going to present today.
Even if you’re not very familiar with cryptography, you might have heard of the Fleissner grille. The Fleissner grille is named for Edouard Fleissner von Wostrowitz (1825–1888), who described it in one of his publications. However, this method had long been known before.
The Fleissner grille
A Fleissner grille is a square stencil looking like this:
Fleissner grilles exist in different sizes. The one above (provided to me by Andreas Önnerfors) is based on a 12×12 matrix. The following grille (from the Heinz Nixdorf MuseumsForum) is a 15×15 version:
How it works
Here’s how a Fleissner grille works (the stencil is used four times, each step is followd by a 90 degree turn):
A Fleissner encryption represents a transposition cipher. This means that no letter substitution takes place. Instead, the order of the letters is changed. To construct a Fleissner grille you can proceed as follows (start with a square matrix and fill it with numbers from 1 to 4 at random):
A genuine Fleissner cryptogram
The following encrypted message created with a Fleissner grille was found (and broken) by my Dutch friend Karl de Leeuw in an archive in the Netherlands (see here for details):
A Fleissner challenge
Karl de Leeuw broke the Fleissner cryptogram shown above with a marvelous side channel attack. This attack only works, when the user is sloppy in writing down the ciphertext. Of course, there are also cryptoanalytical methods to solve a Fleissner encryption. However, not much has been published about this. The only substantial treatise about breaking Fleissner encipherments I am aware of is a chapter in the book Cryptanalysis by Helen Fouché Gaines (published in the 1950s). Gaines shows how a 6×6 Fleissner message is broken based on the (correct) assumption that the word VIADUCT appears in it. It should be clear that it gets much harder if we deal with a larger matrix and no cleartext word is known.
When Gaines wrote her book, computers were almost non-existent. As this has changed, it would be interesting to know how well a Fleissner cryptogram can be attacked with computer support. To stimulate research in this field I have created a Fleissner challenge. The following ciphertext was created with a 20×20 Fleissner grille from an English cleartext:
EAPTISUZLANEDETHSPNF EIORDEMAARNNAROORFTL AETLMLOIFHATOEUDMVNE OXNPBAOEDOIGTRANEEIU XPNPOURNTASEOMMWDHAN IANHTNEIEODNSOTOTETD MONENANPRRIOLAOGNELN INATCFIVOREATDNIEDDA UHIIEURININGTTEDNSTN ATGHPEESAOAEISETDRMM YANTSOEITESYTEVTTACH BNINCALEHUCHTHALLHLG OIKWESOEHRNGREERRRME SAAMHIBEIDMNSAINARLI DTESGINTETACIARHLYLM ESESRUUISINEADSRANOE COSWOEAUETJPOERNSDTW BYEPFNINGHERHIVNTOSE MNTBERAEOLUNNANSYIIX TPOUTYPFIEOWVULEACRA
Can a reader break this cryptogram? A Hill Climbing algorithm might be a good candidate to try. Hill Climbing means (in this case): a Fleissner grille is constructed at random and used to decrypt the cipher text. The result is fed to a function that rates the correctness of the letter sequence (for instance, based on whether the bigram frequencies ressemble the ones of English text). Then the grille is changed slightly, and again the ciphertext is decrypted and rated. If the rating is better now, the current grille will be kept, otherwise the previous one is reloaded. Again, the grille is changed slightly, used for decryption and the result is rated, and so on. This procedure is carried on, until the rating doesn’t improve any more. If we are lucky, this maximum rating indicates that we have found the correct grille.
Codebreakers like George Lasry, Nils Kopal, Jim Gillogly and Dan Girard have been very successful with Hill Climbing. Maybe this technique will solve the Fleissner challenge, too.
Further reading: How to Use a Rubik’s Cube for Encryption