Italian cryptologist Luigi Sacco left behind a text encrypted with a Fleissner grille. Paolo Bonavoglia and Bart Wenmeckers, both readers of this blog, solved it.

Next week the Euro HCC, a conference about the history of cryptology, will take place in Bratislava, Slovakia. I will take part in this event and I am looking forward to seeing many interesting people from the crypto history scene, some of which I have never met before.

For instance, Paolo Bonavoglia from Italy will be an attendant of the Euro HCC. Frequent readers of Klausis Krypto Kolumne might remember that Paolo solved an encrypted book written by 19th century poet and patriot Pietro Giannone (1791–1872). Paolo will give a presentation about this codebreaking success in Bratislava.

 

Sacco’s Fleissner cryptogram

A few days ago Paolo Bonavoglia published an encrypted text the Facebook group Cryptograms & Classical Ciphers. This text stems from his grandfather Luigi Sacco, who was a notable cryptologist and crypto book author. Here it is:

Sacco-Notebook-Fleissner

It seems likely that Sacco used a so-called Fleissner grille to create this cryptogramm. A Fleissner grill is a square stencil with holes. The following picture was provided to me by Andreas Önnerfors:

Fleissner-Grille

Here’s how a Fleissner grille works (the stencil is used four times, each step is followed by a 90 degree turn):

Fleissner-Explanantion

A Fleissner encryption represents a transposition cipher. This means that no letter substitution takes place. Only the order of the letters is changed.

 

Bart Wenmecker’s solution approach

A person I won’t meet in Bratislava, although he is a codebreaking expert, is Bart Wenmeckers. Bart lives in New Zealand, which is literally half a world away from the conference site. Too bad, with his cryptologic expertise Bart would certainly be an enrichment for this event.

Paolo already knew the solution of Sacco’s Fleissner cryptogram, but he did not immediately publish it on Facebook. Bart Wenmeckers took the chance to look for a solution himself.

Like many other current specialists for breaking classical ciphers (e.g., George Lasry, Nils Kopal, Armin Krauß, Jim Gillogly and Dan Girard), Bart makes frequent use of Hill Climbing. In recent years, Hill Climbing has become the super algorithm for solving historical ciphers. Among others, the open source software CrypTool 2 features a Hill Climbing function.

Using Hill Climbing for decrypting a ciphertext works as follows (the cipher algorithm must be known, the goal is to find the key):

  • Construct a key at random and use it to decrypt the ciphertext.
  • Take the result as input to a function (“fitness function”) that rates the correctness of the result (for instance, based on whether the letter frequencies ressemble the ones of English text).
  • Change the key slightly (according to a “mutation rule”) and use it again to decrypt the ciphertext. Rate the result again with the fitness function. If the rating is better now, keep the current key, otherwise reload the previous one.
  • Repeat this procedure until the rating doesn’t improve any more.

If one is lucky, the key candidate with the maximum rating is the correct one.

Codebreaking with Hill Climbing only works if small changes in the key cause small changes in the cleartext. This is the case for many classical encryption algorithms, including the Columnar Transposition, the Double Columnar Transposition, and the Fleissner grille (just to name a few). The Enigma can also be attacked with Hill Climbing.

However, Hill Climbing doesn’t work for modern ciphers like DES or AES, as they are designed to be “random oracles”, i.e., even a small change in the input (key and cleartext or ciphertext) completely changes the output (ciphertext or cleartext). This (desired) phenomenon is also referred to as “avalanche effect”.

 

Bart’s Hill Climbing steps

It’s always fascinating to look at the single steps of a successful Hill Climbing attack and to see how the rating of the fitness function grows and how the cleartext candidates more and more mutate to the correct one. Here’s the protocoll of Bart’s Hill Climbing attack on Sacco’s Fleissner cryptogram:

Sacco-Hill-Climbing-Protocol

The sequences of C’s and D’s identify the stencil that was used for decrypting. NOSSUK… is the first cleartext candidate. It receives a rating of 244. About 30 steps later the rating has risen to 442, while the cleartext candidate has evolved to: ESWURDENDREI… This is clearly a German text.

The solution is the following: ES WURDEN DREI PUNKTE GESEHEN OTLLICH WEITESRSUCHEN XY.

This cleartext obviously contains a few mistakes. XY, the last two letters, were added as filling material. Here’s a corrected version: “Es wurden drei Punkte gesehen, östlich weitersuchen.” (“Three points were seen, seek further eastwards”.)

 

An open question

In addition to the Fleissner cryptogram Sacco’s notebook contains a second transposition of the same cleartext:

Sacco-Notebook-Rectangle

Does a reader know how exactly Sacco created this cryptogram? Is there a simple rule that leads from the cleartext to this ciphertext? Any help is welcome.

Editted to add (2020-05-02): Tobias Schrödel has pointed out that the solution of the Fleissner cryptogram is mentioned on the same notebook page as the ciphertext (the numbers in the square indicate the resulting transposition):




Further reading: How my readers solved the Fleissner challenge

Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Kommentare (11)

  1. #1 TWO
    11. Mai 2017

    No idea about a simple rule but the weak spot is XY

  2. #3 Thomas
    12. Mai 2017

    The 2×4 rectangle (starting with k) represents the inner square of the Fleissner cryptogram read clockwise beginning at 9 o’clock. Likewise the 4×4 square (starting with h) and the 6×4 rectangle (starting with n) represent the middle and the outer squares. I don’t know what’s this for, isn’t there an explanation in Sacco’s notebook?

  3. #4 Thomas
    12. Mai 2017

    I bet it has to do with Sacco´s solving method for rotating grilles given in chapter 82 (p. 102) of his “Manuale di Crittografia”, (4th ed. 2014). Sacco shows an example in Italian based on the frequent digraph “qu”. Since the cryptogram in the notebook is in German, here the two digraphs “ch” are marked in red and blue. The c and the h which belong together (red/blue) are in different squares of the cryptogram (middle/outer). Probably the second diagram explains a way of anagramming Fleissner cryptograms.

  4. #5 Thomas
    12. Mai 2017

    The second diagram helps to find the positions of the 12 holes of the grill (4 turns x 12 holes = 48 letters). There are 2 holes on the inner, 4 holes on the middle and 6 holes on the outer square. The diagram shows which letters can be seen through the two inner square holes (group starting with k), through the four middle square holes (group starting with h) and through the six outer square holes ( starting with n).

  5. #6 Klaus Schmeh
    12. Mai 2017

    Bart Wenmeckers via Facebook:

    Nice write up Klaus I feel Sacco’s work along with his notebook is of historically importantance to classical cryptography.

  6. #7 Thomas
    12. Mai 2017

    The holes in the first position (row, column):
    11 16 24 26 27 32 54 55 57 65 74 75

  7. #8 Klaus Schmeh
    12. Mai 2017

    @Bruce Kallick: Thanks for letting me know. It should work now.

  8. #9 Paolo Bonavoglia
    Venezia
    13. Mai 2017

    I see Thomas did brilliantly find the meaning of the rectangle.

    I can give you some more info: Sacco was my grandfather and I’m now studying this WW I notebook covering the July-October 1916 period. A work in progress, quite heavy.

    Sacco who was chief of the radio-interception service of the Italian Army early in 1916 created a parallel Cryptographic Office to decrypt the intercepted radiograms.

    The booklet describes among others the decryption of several irregular rectangle transposition cryptograms, dated July August 1916.

    Only in October 1916 three rotating grille cryptograms appear in the booklet, without a decryption; likely among the first intercepted radiograms of this type; the time is consistent with Kahn Codebreakers pag. 307,308: between 1916 and 1917 the Germans (and maybe the Austrians also) had started using rotating grilles.

    Sacco’s first idea was to transform a grille cryptogram in an equivalent rectangle transposition; this is the meaning of the rectangle on the right.

    Unfortunately the booklet ends a few days later, when Sacco and the Cryptographic Office moved from Codroipo to Rome; so I don’t know if he decrypted this grille and how; from the “Manuale di Crittografia” it’s clear he later found other methods to decrypt a rotating grille.

    Nowadays we have software tools much more powerful than “paper and pencil”, so I and Bart were able with different methods to decrypt it finding the same solution.

  9. #10 Klaus Schmeh
    14. Mai 2017

    Bart Wenmeckers via Facebook:

    Great article Klaus Thanks for the mention.
    Hope you and Paolo have a great time at Euro-HCC.

  10. #11 Thomas
    15. Mai 2017

    @ Bart Wenmeckers:
    How are the “CD” sequences created? Have you implemented a specific algorithm which takes in account the restrictions of a turning grille or did you use a general transposition algorithm which only swaps certain letters and letter groups?