StartseiteCipherbrain

The Top 50 unsolved encrypted messages: 13. Double Column Transposition Reloaded

Von / 25. Januar 2018 / 11 Kommentare / Seite 2 von 2 / Auf einer Seite lesen
Mehr

The DCT challenge was solved.

It turned out that George had learned about the DCT challenge in a video that shows Craig Bauer talking about unsolved cryptograms. He spent months trying to solve it. He developed new methods to attack a DCT cryptogram, and in the end, he even found two different ways to break the challenge. He published a detailed description of his success in Cryptologia.

When an article I wrote about the DCT challenge for Focus Online was read by Israeli journalists, George became almost a media star in his home country. He even was invited to a TV show.

Meanwhile, George and I are friends. I still feel sorry that I let him wait for three weeks before I confirmed his success.

 

DCT reloaded challenge

Now that the DCT challenge was solved, Arno Wacker, Bernhard Esslinger (both involved in MTC3) and I decided to create a new (and even harder) successor. In fact, we created even three new challenges. The most difficult one is titled “DCT Reloaded 3”. Here are the basic facts about it:

  • Both key words have a length of 27-34 characters.
  • Both key words are chosen randomly.
  • The plaintext is in German.
  • The plaintext was written by ourselves, not taken from an internet source (in fact, Jim Gillogly, another well-known codebreaker, 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).

Here’s the ciphertext of the “DCT Reloaded 3” challenge:

LEHHRGNHTOSHRNCUUHRPEAIENLUNUGGANIADEGFNEEHEMGSIIISGGIDSNZINHETSH
UOMSELLRTSIZEORMEZBEEZPLPEODETTEINIBNNHINUTKASSMTCIICSFTBEDSFTENB
UERNPLMEFEUEUCENDEIRRLNEZUEAMETUESDAENRTCUZUMZCRNPRETIDUUOBCTEEJT
NEILCDGFRMASIMHEULEZENNUGEMRTNEWMHUTGTEKGDNTZNDIEEEEEDINSCELRABKN
TBGIEATSDHEAEBTBOFWVLNECNUUSZUHSNESDHBNIIGHHRZTUEESEZOAEGSSELTMEN
EESEUMIEERHKAIRBSNNEIEUEDLAOEKREEUONHANNEEPINECTENMKITREGUIHCTWRN
FUHDAIUBAKLIREZNEEWREEMEUDDUATEPCUNKDBFSESFSEEDSTTCERMSREAZLRLUEU
EITFNHSBFBRIDBDANPGEEEDDTOBASLENGEERMPCEBUNETTNHATTLHREEEREPNEEMU
AEENSIIKELUMMSELRGWEZNWEHEIZILEZENBEISSKWZSSGTCKDTZIELRHTHERESIRG
GUKSFLMEABLUINDIANLZEWLEUADSFENNIENLNCNTRHSCAEUMEBECFEEEHWUETNBRG
WEEMHAILLRORUEIEETGTAILNNILSBLUEIKNNHNKSIEUCUNNTAFICUEHRTEOLAZEKW
SETSEDIAGIESKLGEIEIEFESZGAEETAEKGBEAEELSEEDOEINVNFEUAHRAITEHTCIHO
AERNRTTETZUNDTNIKNVCITFBNLBTROEOCNENLZHLZMEEHCAEUSKEEEZZWESEDTDTU
RBDMSLIRTRTAZNGITNEIDRTAAMTLEGOLSSBESFIKEESHRTAEGRUWREFTREZSUBHBE
HDEGLHCLUELRLFSITIERETRGRSDNNIIGOURETEEERBDRLGLRLZLNTSNRNERNCPSDB
OUEEEEISMINHEHHFEHMICIINAHOFONM

There’s no doubt that this challenge is an extremely hard one. I expect that it will never be solved. However, I said the same about the first DCT challenge. And I was wrong.


Further reading: The Top 50 unsolved encrypted messages: 45. The World Record 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.

1 / 2
Stichworte: ,
Mehr

Kommentare (11)

  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
    https://zodiackillerciphers.com
    25. Januar 2018

    George,

    I wonder if Google Ngrams can be useful:

    https://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

  9. #9 Marc
    4. März 2018

    @George,
    ich habe noch eine Frage hierzu. Sie schreiben :

    “(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)”

    Haben Sie für die originale Challenge nur hill-climbing verwendet oder zusammen mit IDP-Analyse ? Meine reine hill-climbing-Implementierung (ohne IDP) schafft die originale Challenge nämlich nicht. Auch würde mich interessieren, wie lange der Angriff auf die originale Challenge dauerte. Vielen Dank schonmal für Ihre Antwort.

    Gruß Marc

  10. #10 Encrypted Puzzle | Text Message 20
    28. Februar 2021

    […] The message attached to this post is encrypted using the Grid Cipher I have developed from the Double Columnar Transposition Cipher described by Klaus Schmeh. Here is a link to his article Double Columnar Transposition […]

  11. #11 Encrypted Puzzle - Text Message 21
    25. September 2021

    […] The message attached to this post is encrypted using the Grid Cipher I have developed from the Double Columnar Transposition Cipher described by Klaus Schmeh. Here is a link to his article double column transposition […]