DCT-Challenge

In 2013 George Lasry broke a ciphertext many had considered unbreakable. In the wake of this success, a few crypto experts created a similar challenge with an even higher level of difficulty. Is this one unbreakable? So far, nobody has solved it.

Click here for the complete top 50 list

The story of today’s unsolved cryptogram began in 1999, when Otto Leiberich, the former president of the German crypto authority Zentralstelle für das Chiffrierwesen (ZfCh), published an article in Spektrum der Wissenschaft. This article (written in German) is now available online (unfortunately, the box with the most interesting part is missing).

 

The Double Columnar Transposition

In his article, Leiberich mentions the “Doppelwürfel”, also known as the Double Columnar Transposition (DCT), an encryption method that was used by East Erman agents during the Cold War. The DCT is a cipher that can be carried out solely with paper and pencil – no machine or computer program is needed. It is one of the best manual ciphers known.

To explain the DCT let’s encrypt the sentence TO BE OR NOT TO BE. We use RAIN as the keyword. First we write the plaintext below the password:

RAIN
----
TOBE
ORNO
TOTO
BE

Now, we sort the columns of the table such that the letters of the password stand in alphabetical order:

AINR
----
OBET
RNOO
OTOT
 E B

Next, we read out the message column-wise: ORNOBNTEEOOTOTB. What we have done so far, is a single columnar transposition. If we apply the same procedure again (with a different keyword), we get a DCT.

 

The challenge

During the Cold War, Otto Leiberich and his team worked intensively on the cryptanalysis of the DCT. In 1974, one of their results led to the exposition of spy Günter Guillaume, who was chancellor Willy Brandt’s senior aide.

In order to encourage research on the DCT, Leiberich suggested in his article that a double transposition challenge be put forward. Leiberich’s recommendations for this challenge included the following:

  • Both keywords should have 20 to 25 characters.
  • The lengths of the two keywords should be co-primes (no common divisor except 1).
  • The length of the ciphertext should not be a multiple of the length of either keyword.
  • A ciphertext of approximately 500 characters (which is approximately the product of the lengths of the two keys) should be used.

As Otto Leiberich never published a challenge of this kind himself, I decided to do so.

For  my challenge, I chose an English plaintext and encrypted it using two keywords, both derived from English phrases longer than 20 letters. The length of the plaintext was 599. I published this challenge in 2007 in my book Codeknacker gegen Codemacher and on the internet. The cryptographic challenges site, MysteryTwister C3, took it over. In 2013, I published the DCT cryptogram in my top 25 unsolved cryptograms series (in German). Here it is:

VESINTNVONMWSFEWNOEALWRNRNCFITEEICRHCODEEA
HEACAEOHMYTONTDFIFMDANGTDRVAONRRTORMTDHE
OUALTHNFHHWHLESLIIAOETOUTOSCDNRITYEELSOANGP
VSHLRMUGTNUITASETNENASNNANRTTRHGUODAAARAO
EGHEESAODWIDEHUNNTFMUSISCDLEDTRNARTMOOIREEY
EIMINFELORWETDANEUTHEEEENENTHEOOEAUEAEAHUHI
CNCGDTUROUTNAEYLOEINRDHEENMEIAHREEDOLNNIRAR
PNVEAHEOAATGEFITWMYSOTHTHAANIUPTADLRSRSDNOT
GEOSRLAAAURPEETARMFEHIREAQEEOILSEHERAHAOTNT
RDEDRSDOOEGAEFPUOBENADRNLEIAFRHSASHSNAMRLT
UNNTPHIOERNESRHAMHIGTAETOHSENGFTRUANIPARTAOR
SIHOOAEUTRMERETIDALSDIRUAIEFHRHADRESEDNDOION
ITDRSTIEIRHARARRSETOIHOKETHRSRUAODTSCTTAFSTHCA
HTSYAOLONDNDWORIWHLENTHHMHTLCVROSTXVDRESDR

I never expected that the DCT cryptogram could be broken. Neither did Otto Leiberich, who was very interested in this challenge.

 

The solution

Later in 2013, I received an email from a certain George Lasry from Israel. He claimed to have solved the DCT challenge.

Lasry-01

As I receive mails of this kind quite often, I didn’t pay much attention to it. I decided to take a look at this alleged solution later, when I had more time. However, after three weeks, the people from MTC3 informed me that George’s solution in their view was correct. So, I checked George’s mail and I realised that the MTC3 people were right.

1 / 2 / Auf einer Seite lesen

Kommentare (8)

  1. #1 George Lasry
    Israel
    25. Januar 2018

    Klaus

    In fact it was good that you let me wait a little bit, because in the meanwhile, I had time to work on the dictionary-based version of the attack.

    I did try to apply my techniques to the new challenges.

    1) Because of the long keys (> 27), my hill-climbing algorithm could not produce a solution (unlike for the original challenge, which had lengths 21 and 23)

    2) #1 of the 3 challenges uses codephrases to generate the transposition keys. So I wanted to test my dictionary-based attack.

    I downloaded an offline version of Wikipedia (a few tens of GB) and the full Gutenberg project (similar size), and with them I created a database of phrases/expressions – tens of billions of them, to be used as tentative keys (the second transposition key – K2).

    I also had bought (for other purposes) a high-end GPU card, and wrote dedicated code to check 1M keys/second, using the technique I had developed. I let the program run on all possible key lengths, and tested all possible keys from my phrase/expression database. It took a few days.

    I was unable to find the key for #1.

    My assessment is that out of the 3 new challenges, #2 and #3 are not solvable (because they keys are random and long).

    There might be a chance to solve #1, for which there is are non-random keys (driven from phrase/expressions).

    If anyone has idea how to build a new database (apart from Wikipedia and Gutenberg texts), I’ll be happy to join forces.

  2. #2 Marc
    25. Januar 2018

    Hier zwei Erfahrungen, die ich mit dem Doppelwürfel und hill climbing gemacht habe.

    1. Trigramme und höher als Kostenfunktion
    Bringt beim Doppelwürfel scheinbar nichts. Die Ergebnisse waren meiner Einschätzung nach sogar schlechter als mit Bigrammen.

    2. Erweiterung mit Sintflutalgorithmus
    Führt bei Schlüssellängen unter 20 dazu, dass die Lösung schneller gefunden wird, versagt aber auch bei Schlüssellängen über 20.

    Das sind nur meine eigenen Erfahrungen, evtl. hat jemand hierzu andere Erfahrungen gemacht ?

  3. #3 George Lasry
    25. Januar 2018

    @Marc

    To be sure, are you using the same key for both stages or different keys.

    Also, the ciphertext length should not be a multiple of any of the key lengths, even not close to it.

    Otherwise, those cases are not representative.

    If this is not the case, then finding solutions for keys of length 20 is very nice.

  4. #4 David Oranchak
    http://zodiackillerciphers.com
    25. Januar 2018

    George,

    I wonder if Google Ngrams can be useful:

    http://storage.googleapis.com/books/ngrams/books/datasetsv2.html

    Although, they only go up to 5-grams which might not cover the entire key length.

  5. #5 George Lasry
    Israel
    26. Januar 2018

    David@

    Great idea, will look at this.

  6. #6 Gerd
    27. Januar 2018

    “Jim Gillogly, … had shown that the first DCT challenge could be broken by searching the internet for a text of the same length containing the same letters”

    Although this approach is useless for “codebreaking”, I am quite fascinated that such a search can be successful.
    Is there more about how this was done? Is there something like a “google anagram search”?

    Gerd

  7. #7 Klaus Schmeh
    27. Januar 2018

    @Gerd:
    >Is there more about how this was done?
    I took the cleartext from a little-known 19th century novel, which is available online. For his search, Jim used a collection of literary texts that are available on the internet. His search program checked each text letter by letter. One of the texts he tried was the right one.

  8. #8 Marc
    28. Januar 2018

    @George,
    “To be sure, are you using the same key for both stages or different keys.”
    I’m using different keys, of course :-)

    “Also, the ciphertext length should not be a multiple of any of the key lengths, even not close to it.”
    You’re right, i didn’t think about that.

    @Gerd,
    du brauchst einfach nur die Buchstaben zählen und dann überprüfen, ob die Häufigkeiten übereinstimmen, da diese durch die Transposition nicht verändert werden. Wenn dem so ist, dann handelt es sich um einen potentiellen Klartext.

    Hat man den passenden Klartext gefunden, ist der Angriff kein großes Problem mehr. Die einfachste mir bekannte Variante hierfür ist hill climbing und Bigramme als Kostenfunktion. Bei jedem Buchstaben, der mit dem Klartextbuchstaben übereinstimmt, multipliziert man den entsprechenden Bigrammwert einfach mit 2. Das funktioniert prima. Vielleicht hat jemand eine noch einfachere Lösung ?

    Wenn nur wenig Klartext (z.B. die ersten beiden Sätze) bekannt ist, gibt es noch einen etwas komplexeren Angriff, der hier beschrieben wird :

    https://infsec.de/doppelwuerfel/Doppelwuerfel_Tim_Wambach_final.pdf