Reihenschieber-solved-bar

Within a few hours, blog reader Norbert Bierman solved the Reihenschieber challenge I introduced last Monday. His work shows that I used this device in a wrong way.

The Reihenschieber is a simple encryption tool developed by Western German crypto experts in the 1950s. Considering that it only consists of a few plastic parts, which could be produced very cheaply, it rendered a high degree of security.

 

The Reihenschieber

The following Reihenschieber belongs to Austrian collector Günter Hütter (it has two stencils, I don’t know if both were used at the same time):

Reihenschieber-Huetter

The Reihenschieber is used to generate a sequence of random letters or numbers that are added to a cleartext. In other words, it produces a key for a One Time Pad.

Reihenschieber-Huetter-2

To get a better understanding of the Reihenschieber, I built a Lego model of it, which is a little simpler than the original.

Reihenschieber-Lego-Stencil

The random sequence I took from the setting above is YSJVFHJTDVOCUXBIRAZG. With a different key (a key consists of the choice of the bars, the order of the bars, the upside of each bar, and the shift of each bar), I created an encrypted text that I introduced as challenge in my blog post from Monday:

TVOFHMUZZKQSYOESLVQU

As a comment, I wrote: “An obvious weakness is that the first part of the ciphertext only depends on the first bar, the second part only on the second bar, and so on.”

 

The solution

Only four hours after publication, blog reader Norbert Biermann posted the correct solution: IT’S A SMALL STEP FOR A MAN.

I was quite overwhelmed. This was incredibly fast. Here’s Norbert’s explanation:

As you pointed out, each bar only affects four continuous characters, leaving only 8 * 4 * 11 = 352 possibilities for these. Thus, a program may compute the 352 plaintext possibilities for characters 1-4, 5-8, and so on, try all combinations of adjacent quadgrams and keep the most promising in memory. My “quick and dirty” program code did not really reveal the solution at once, but when examining the output, I discovered “ITSASMALLSTE” among the best 50 candidates in the list for combined bars 1, 2 and 3. This was clear enough to do the rest by hand.

The weakness I had written about turned out to be so serious that Norbert’s program only needed to check 352 plaintext possibilities per step, which doesn’t take much time.

Concerning this problem, Fliegenschubser wrote: “How would it change the game if you read your random sequence not in rows but in columns?” Of course, he was right. I had made a mistake. The random letters need to be read out from top to bottom, not from left to right. In a Cryptologia publication about the Reihenschieber from 1996, it says the same. So let’s look at the Lego model again:

Reihenschieber-Lego-Stencil

The correct random sequence is: YFURSXADJHVZOVJBGTCI. If we encrypt the sentence KLAUSIPLAYEDWITHLEGO, we get:

KLAUSIPLAYEDWITHLEGO
YFURSXADJHVZOVJBGTCI
--------------------
JRVMLGQPKGADLEDJSYJX

The resulting ciphertext is: JRVMLGQPKGADLEDJSYJX.

 

A new challenge

Based on this new knowlege, I created a new challenge. Again, I used my Reihenschieber model (with a different key, of course, but with the same stencil). Here it is:

TDTWVEPNRAKZQIOLIMXG

Can a reader solve it? It might be a lot more difficult this time.

There’s one last question I want to address: How many keys does my Lego Reihenschieber have? I think the calculation goes as follows:

8×7×6×5×4×(4×11)^5 = 1,108,237,025,280

This is probably too much for an exhaustive key search. Maybe Hill Climbing will work.


Further reading: An Encryption Algorithm Created by Artificial Intelligence
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

Gib Deine E-Mail-Adresse an, um diesen Blog zu abonnieren und Benachrichtigungen über neue Beiträge via E-Mail zu erhalten.

Kommentare (19)

  1. #1 Thomas
    27. Januar 2017

    Does that really increase cipher security?
    If you read the key by columns instead of rows, it should be composed like this (position of letters in the key):

    bar 1: 1, 5, 9, 14
    bar 2: 2, 10, 15, 18
    bar 3: 8, 11, 13, 19
    bar 4: 3, 6, 16, 20
    bar 5: 4, 7, 12, 17

  2. #2 Klaus Schmeh
    27. Januar 2017

    @Thomas:
    No, I don’t think this is correct. Did you take into account that there are eight bars to choose from? What’s your cleartext?

  3. #3 Thomas
    27. Januar 2017

    @Klaus
    I didn’t want to give a solution of your cipher. My only idea was that reading the key by columns doesn’t make this cipher more secure when attacked with Norbert’s software. Whereas reading from left to right takes the keyword positions 1-4 from the first chosen bar, 5-8 from the second chosen bar and so on, reading from top to bottom yields the character sequence #1 because of the pattern of your stencil. But maybe I’m wrong.

  4. #4 Hendrik
    28. Januar 2017

    LOS ANGELES CALIFORNIA

    Combination [purple, position=2, shift=4],
    Combination [black, position=4, shift=5],
    Combination [red, position=1, shift=0],
    Combination [yellow, position=1, shift=10],
    Combination [grey, position=4, shift=8]

    key=HOAVHXKBMHHYEZIWQYOF

  5. #5 Klaus Schmeh
    28. Januar 2017

    @Hendrik:
    Correct!! Congratulations, great job!
    How did you find the solution?

  6. #6 Klaus Schmeh
    28. Januar 2017

    @Thomas:
    In my view the vertical read-out is more secure, because if you read the letters horizontally, you can check if the first bar is at the correct position by subtracting the four letters shown in the stencil from the first four ciohertext letters. If you get a result that looks like a text excerpt, e.g. ANTH, your probably on the right track. If you read the letters vertically, it’s more complicated, as the first four letters come from four different bars.
    However, as Hendrik’s success shows, the vertical variant still sin’t secure enough.

  7. #7 George Lasry
    28. Januar 2017

    I think this does not make the cipher any more secure, it is still possible to use the same technique as used by Norbert, the 4 letters at the top, instead of being 1,2,3,4 in the ciphertext, are now 1, 5, etc…, but still at deterministic places.
    I think that what would make the cipher (even the Lego version) more secure would be the use of nulls, like in the original. Basically, instead of a letter, we have a dot (.) or some other sign at specific places in the strips, which means that this position should be skipped. If there are enough dots in the strips, that produces irregular positions of the ciphertext letters in the respective strips. It is still possible to run Norbert’s algorithm several times, assuming specific spots are nulls, though, but this would take more time.
    George

  8. #8 Klaus Schmeh
    28. Januar 2017

    @George:
    >instead of being 1,2,3,4 in the ciphertext,
    >are now 1, 5, etc
    But that does make a difference. In the case of 1,2,3,4 you can check for frequent quadruplets, which is not possible in the 1,5,9,13 case. However, it is still possible to look for frequent letters, which might be sufficient.

  9. #9 Thomas
    28. Januar 2017

    @Klaus
    Hendrik’s key matches thebsequence in #1.
    Reading the key from top to bottom does change only the sequence inside the key, but, as George pointed out, the key letters are still on deterministic places (1,5,9,14… instead of 1,2,3,4….depending on the stencil pattern). The composition of the key doesn’t affect the search for quadruplets in the results given by the algorithms.

  10. #10 Thomas
    28. Januar 2017

    Correction: quadgrams instead of quadruplets.

    If the sequences of the characters on the bars and the pattern of the stencil are known, cipher security doesn’t depend on the direction in which the key is composed.

  11. #11 Thomas
    28. Januar 2017

    Es fällt mir etwas schwer, es auf Englisch auszudrücken:

    Sofern das Muster der Schablone und die Leserichtung bekannt sind, hat man die Sequenzen ( noch nicht die Lage) auf den Stäben. Die Abfolgen 1,2,3,4 und 5,6,7,8 usw. in dem von Norbert gelösten Beispiel bedeuten nicht, dass die Zeichen benachbart sind, vielmehr ergibt sich folgendes Muster (x = leer)

    1 2 x 3 x 4 x
    5 x x 6 x 7 8
    x x 9 10 11 12
    13 14 x x x 15 16
    17 18 x 19 x 20 x

    Dieses Muster ( und das entsprechende bei vertikaler Ablesung in dem neuen Beispiel) muss beim “Füttern” des Algorithmus berücksichtigt werden. Auf die Suche der Fitness-Funktion nach quadgrams etc. in den Resultaten hat die Bildung des Schlüssels (ob 1,2,3,4… oder 1,5,9,14…) dann aber keinen Einfluss und macht keinen Unterschied.

  12. #12 Klaus Schmeh
    28. Januar 2017

    @Thomas:
    Ich kann doch erst einmal nach der obersten Stange suchen. Dazu gibt es 8x4x11 Möglichkeiten (das schafft man evtl. sogar von Hand). Jede Möglichkeit liefert ein Tetragramm. Bei waagerechtem Auslesen kann ich sicherlich besser beurteilen, ob das Tetragramm richtig ist, da die vier Buchstaben hintereinander im Text stehen. Bei senkrechtem Auslesen wird es schwieriger, da die vier Buchstaben nicht direkt aufeinander folgen. Auf die gleiche Weise kann ich dann auch die zweite Stange ermitteln, usw.

    Wenn ich allerdings nicht eine Stange nach der anderen anderen herausfinden will, sondern mittels Hill Climbing jeweils fünf Stangen gleichzeit verwende und diese variiere, dann spielt es sicherlich keine Rolle, ob ich senkecht oder waagerecht auslese. Allerdings erscheit mir das aufwendiger, als wenn ich eine Stange nach der anderen ermittle.

  13. #13 Hendrik
    28. Januar 2017

    @Klaus:
    Thanks. I used hill climbing with a value function based on quintgram frequencies.
    Branch&bound should also work or even an exhaustive search is possible.

    As the text is so short (20 chars) the value function is a challenge. With the previous cipher (the one on which Norbert did a great job) I got too much possible solutions which had a better quadgram frequency score than the correct one.

  14. #14 Norbert
    28. Januar 2017

    Gratulation an Hendrik! Ich finde es immer wieder erstaunlich, was ein Hill-Climbing- bzw. Simulated-Annealing-Algorithmus (ich nehme an, letzteres in diesem Fall) alles lösen kann. Wobei das Basteln an einer guten Value-Funktion bzw. daran, wie der Key jeweils verändert werden soll, ja manchmal etwas knifflig, aber dafür eine geradezu kreative Arbeit sein kann :-)

    Ich hatte hier, weil es nun einmal schon auf meinem Rechner war, eine angepasste Version meines alten Programms versucht. Dabei ist die Sache hier schon etwas komplizierter: In der alten Version reichte ein “exhaustive search” über nur zwei Reihen (8 * 7 * 11 * 11 * 4 * 4 = 108416 Möglichkeiten), um bereits 8 zusammenhängende Klartextbuchstaben bewerten zu können, das ist diesmal nicht so bequem. Ich hatte gestern abend versucht, zunächst alle Möglichkeiten von Reihe 1, 2 und 4 durchzuprobieren, das ergibt immerhin zwei Trigramme (in Spalte 1 und 6) sowie zwei Bigramme (Spalte 2 und 4) zum bewerten. Das führte nicht zum Erfolg. Kein Wunder, denn bei der Trigrammbewertung stürzt sich das Programm auf Möglichkeiten wie THE, FOR, AND, YOU, ING etc., aber LOS landet wohl zu weit abgeschlagen auf den mittleren Rängen. Hätte der Klartext nicht LOS ANGELES, CALIFORNIA, sondern THE ANGEL OF CALIFORNIA geheißen, hätte ich möglicherweise schnell Erfolg gehabt 😉

    Habe dann gestern abend einen “exhaustive search” für Reihe 1,2,4 und 5 angestoßen, das ergibt 7 zusammenhängende Klartextbuchstaben in Spalte 1-2 sowie noch einmal vier in Spalte 6. Aber der Rechner rechnet noch …

  15. #15 Thomas
    28. Januar 2017

    Bei “Los Angeles” wäre eine spanische Fintness-Funktion besser als eine englische. Aber vielleicht werden spanische Städtenamen in den USA demnächst ja noch in englische geändert, “The Angels” hätte Norberts Funktion wohl eher gefunden.

  16. #16 Hendrik
    28. Januar 2017

    @Norbert:
    Danke. Du hast Recht, bei näherer Betrachtung ist es ein vereinfachter Simulated-Annealing-Algorithmus.

  17. #17 Klaus Schmeh
    28. Januar 2017

    @Thomas:
    >Bei “Los Angeles” wäre eine spanische
    >Fitness-Funktion besser als eine englische.
    Stimmt, habe ich leider nicht dran gedacht. An was man alles denken muss bei so einer Challenge!

  18. #18 Gillogly
    Long Beach, California
    28. Januar 2017

    1580 * losangelescalifornia Purple 2/4 LNEI / Black 4/5 OSFN / Red 1/0 LCLI / Yellow 1/10 SGOA / Grey 4/8 AEAR

    I ordered the 352 possible partial keys for each stencil row by the sum of the logs of single-letter plaintext frequencies for that row, then tried each combination in order up to a cutoff, evaluating the result with a trie-based dictionary lookup. When I got to the top 50 candidates for each of the five stencil rows, the solution was among the 50^5 combinations, less the combinations that used the same colored block.

    The next best was “lor anteles california”, and way before that “ecoin sure i ua assent cog”. I also rather liked “litanies et taais grubs”. Yum!

    Between “ecoin…” and the correct solution was “attritional gem uma cob” which gets a bonus for the long word, but not as much as the right answer.

  19. #19 Rainer
    Paderborn
    7. Februar 2018

    Ihre Entschlüsselungsleistungen fordern mir großen Respekt ab! Ich bin aber auch kein Fachmann in Ver-/Entschlüsselung – nur interessierter Laie.
    Ich habe derzeit Zugriff auf einen (Original-)Reihenschieber und habe mir mal das gesamte RS-Verfahren der Ver- und Entschlüsselung angeeignet.
    Bei bestimmungsgemäßen Gebrauch ist das Verfahren nicht angreifbar!
    Das oben gezeigte LEGO-Modell ist nur einer von mehreren Schritten bei der Verschlüsselung. Es hat den entscheidenden “Fehler”: Mit dieser Schablone (Dekadenschlüssel genannt) wurden Zahlen ausgesiebt – nicht Buchstaben-, die anschließend in einer zweigeteilten Umsetzungstabelle zu Buchstaben gewandelt wurden, die dann den Spruch bildeten.
    Sorry for my bad English:
    Klaus Schmeh wrote at the beginning “The Reihenschieber is used to generate a sequence of random letters or numbers that are added to a cleartext. In other words, it produces a key for a One Time Pad”
    Sorry, even he is the expert, that’s not exact right: The item Reihenschieber generates only a sequence of pseudo-random NUMBERS. These numbers are used in a following step to encrypt the message. The result contains only LETTERS, even if the cleartext contains digits and/or letters.