Rubik-bar

A Rubik’s Cube can be used to implement a highly secure encryption method.

One of the most interesting questions in classical cryptography is the following: How can one encrypt without using a suspicious encryption tool?

This question is especially interesting for a spy, who doesn’t want to be caught with treacherous encryption equipment. A number of different methods have been proposed for this purpose:

In a Cryptologia publication from 1992, Douglas W. Mitchell proposes another interesting cipher not requiring suspicious tools: encryption with a Rubik’s Cube. The Rubik’s Cube was an extremely popular puzzle in the 1980s. Still today, it is absolutely unsuspicious to have one. I even have a whole collection of Rubik’s Cubes and similar toys, and I have never been accused of being a spy.

Rubik-Collection

Encryption

To use Mitchell’s cube encryption algorithm, the surface of the cube should be coated so that it can be written on. The colors on the cube faces are irrelevant.

To begin with, write the numeral “1” on the upper left square of one of the cube faces. Write “2” on an arbitrarily chosen square of any other cube face, write “3” on any square of any other cube face, and so on.

Rubik-Encryption (1)

Then fill in a 48 letter plaintext on the remaining 48 squares of the cube. The first eight letters are written on cube face “1”, letters 9 to 16 on cube face “2”, letters 17 to 24 on face “3” and so on. Always start writing in the upper left cube of the face. As an example, I took the cleartext “ABCDEDGHIJKLMNOPQRSTUVWXabcdefghijklmnopqrstuvwxyz”.

Rubik-Encryption (3)

In the next step, the cube is twisted. Assuming that we always keep the “1” square at the upper left position, 18 rotations are possible in one step (rotating the right column by 90/180/270 degrees, rotating the middle column by 90/180/270 degrees, rotating the lower row by 90/180/270 degrees, rotating the lower row by 90/180/270 degrees, rotating the middle level by 90/180/270 degrees, and rotating the back level by 90/180/270 degrees).

Rubik-Directions

The rotations carried out are the key. I took the key MC90, LR270, RC180, ML90, BL270 (for a real application I would have taken a longer key).

Rubik-Encryption (4)

Now the letters and numbers are read from the cube (front face, right face, back face, left face, top face, bottom face). The result of my encryption procedure is the following ciphertext:

134CTnILp  iwrODWPoV  BENbtual5  SjfAmcv6H  kJKUdgxGX  QRqM2nheF

This looks quite random, considering that the cleartext was “ABCDEF…” and I used only five rotations.

 

Decryption

According to Mitchell, decryption is straightforward. Take the ciphertext and write it on the cube (front face, right face, …). Then carry out the reverse rotations in the reverse order. Then read the letters from the “1” face, the “2” face and so on.

In my view, this decryption procedure does not lead to a unique result, as one doesn’t know which corner of a face is considered the upper left one (except for the “1” face). For the decrypter to know this, the orientation of the number must be given. This could be done in the ciphertext like this:

13→4↑CTnILp  iwrODWPoV  BENbtual5←  SjfAmcv6H  kJKUdgxGX  QRqM2↓nheF

 

An interesting cipher

In my view, Mitchell’s cube encryption algorithm is a quite interesting one. Nevertheless, I am not aware of any additional publication about this method. To date, it is quite unclear whether this algorithm is as secure as it seems and if it can be improved. An interesting question asked by Mitchell himself is how the key should be chosen in order to get maximum security for a certain key length. It is clear that a combination like “MC90, MC180” doesn’t make sense, as it can be replaced by “MC270”, but there might be more. If a reader has any ideas, I would be interested to learn.

1 / 2 / Auf einer Seite lesen

Kommentare (12)

  1. #1 Klaus Schmeh
    10. November 2016

    Richard SantaColoma via Facebook:

    Really cool… I think I followed the process, but don’t trust me to figure out anything important. Me and Rubik’s Cubes never got along very well.

  2. #2 Kaspar
    10. November 2016

    Bei Wiki steht, dass maximal 26 Vierteldrehungen nötig sind, um den Würfel wieder zu sortieren. Das wäre dann auch die maximale Schlüssellänge. Alles darüber hinaus hebt sich irgendwann wieder selbst auf.

    Als One-Time-Pad genutzt dürfte es eine gewisse Sicherheit bieten, wenn jedoch immer die gleichen Verdrehungen Schlüssel sind ergeben sich durch Bigramme denke ich Möglichkeiten den Key zu knacken.

  3. #3 Karsten Hansky
    11. November 2016

    Hallo Kaspar,
    ganz so einfach ist es nicht. Die 26 Drehungen gelten, um den Würfel in eine bestimmte Ausgangsstellung zu bringen. Diese muss allerdings bekannt sein. Wer sagt denn, dass der Klartext auf einen geordneten Würfel geschrieben werden muss?
    Eine schöne Erweiterung zum Mitchell-Vorschlag findet sich auch unter: epublications.regis.edu/cgi/viewcontent.cgi?article=1511&context=theses

    Es gibt auch noch Würfel höherer Ordnung (4x4x4, 5x5x5 usw.)…

    Das Bestechende an der ganze Sache ist, dass man ein unverfängliches Objekt zum Chiffrieren verwendet. Ich fliege heute Abend nach Amsterdam um mir morgen die Sonderausstellung des Crypto Museums anzusehen. Dort treffe ich mich auch mit Klaus. Der Rubik Cube liegt schon im Rucksack. Wetten, dass der am Flughafen kein Aufsehen erregt? 😉

  4. #4 Norbert
    Berlin
    11. November 2016

    Das erinnert doch sehr stark an den “Nerdcube” der Zeitschrift c’t vom letzten Jahr:

    http://www.heise.de/ct/projekte/vertrac-t-Der-c-t-NerdCube-2765682.html

    Diese Aufgabe (bei der im Unterschied zum hier angegebenen Verfahren bei jedem Buchstaben die Orientierung vorgegeben war, von möglichen Symmetrien wie bei “I” einmal abgesehen) war relativ leicht von Hand lösbar. Einen Programmieransatz, der sich vermutlich leicht auf die hier beschriebene Methode anpassen lässt, liefert die Musterlösung:

    http://www.heise.de/ct/artikel/geknac-t-Der-c-t-NerdCube-3296160.html

    Dort wird auch erklärt, wieso das Knacken relativ einfach ist (und die Verschlüsselung folglich m. E. nicht besonders sicher): Es muss gar nicht die richtige Zugfolge (der “Schlüssel”) gefunden werden; stattdessen reicht es, den Würfel virtuell auseinanderzunehmen und seine nur zwanzig(!) “losen” Teile sinnvoll zusammenzubauen (in unserem Fall unter Zuhilfenahme von Trigramm-Häufigkeitsanalyse). Ein “Eckstein” wird ja immer ein Eckstein bleiben und die auf seine drei sichtbaren Seiten geschriebenen drei Buchstaben/Zahlen bleiben folglich immer in derselben Orientierung miteinander “verbunden”, analog bleibt ein “Kantenstein” immer ein Kantenstein, und die sechs “Mittelsteine” kann man sogar als völlig unbeweglich betrachten. Das macht die Zahl auszuprobierenden Möglichkeiten durchaus überschaubar.

  5. #5 michanya
    11. November 2016

    … und Jetzt haben die ein Problem – der Name – ZAUBERWÜRFEL – ist urheberrechtlich geschützt. Vielleicht wusste Herr Einstein eine Patente Losung es war ja sein Gebiet auf dem Patentamt …

    ist mit den GOLDHasen von LINDT auch so gewesen – recht muss Recht bleiben – mindestens 18 Jahre lang – steckt ja viel Arbeit und viele Ideen drin.

    GEBRAUCHSMUSTER absichern – biotec4u

  6. #6 Norbert
    Berlin
    11. November 2016

    Auf die Schnelle gerechnet: Die acht Ecksteine müssen auf acht Positionen verteilt werden, jeweils drei Orientierungen sind möglich. Dazu 12 Kantensteine mit jeweils zwei möglichen Orientierungen, macht einen “Schlüsselraum” von

    8! * 3^8 * 12! * 2^12 ≈ 5.2 * 10^20

    Dass bestimmte Kombinationen nicht durch eine legale Zugfolge aus der Ausgangssituation hervorgehen können, verkleinert den Schlüsselraum. Zusätzlich fallen sehr viele Kombinationen allein durch die Tatsache weg, dass per definitionem auf jeder Seite genau eine Zahl (1-6) stehen muss. Beides lasse ich hier unberücksichtigt. Muss stattdessen in die Berechnung einbezogen werden, dass der Text auf jeder der sechs Seiten in vier verschiedenen Orientierungen geschrieben sein kann? Nein, denn die Orientierung wird durch die auf der jeweiligen Seite befindliche Zahl exakt vorgegeben – sobald der Würfel auf eine der errechneten fünf mal zehn hoch zwanzig Arten zusammengesetzt ist, ist er entweder ungültig (mehrere Zahlen auf ein und derselben Seite) oder es ist völlig eindeutig, in welcher Reihenfolge die Buchstaben zu lesen sind.

    Eine simple monoalphabetische Substitution ergibt bei einem Alphabet mit 26 Buchstaben bereits einen Schlüsselraum von

    26! ≈ 4.0 * 10^26

    Zwar weiß ich nicht, ob ich hier nicht etwas unbedarft Äpfel mit Birnen (Transposition mit Substitution) vergleiche, aber es bestärkt mich in meinem Gefühl, dass die beschriebene Verschlüsselungsmethode nicht besonders sicher ist.

    Ein Verbesserungsvorschlag wäre meines Erachtens, die Sache mit den Ziffern und ihrer Orientierung komplett wegzulassen. Der Empfänger wird auf jeder Seite des “Klartext-Würfels” schnell herausbekommen, in welcher Orientierung die (dann nicht mehr acht, sondern) neun Buchstaben zu lesen sind, und in welcher Reihenfolge die sechs Textblöcke zusammenzusetzen sind, dürfte sich anschließend auch von alleine erschließen.

    Weitere Verbesserungen wären das Einstreuen von Zufallsbuchstaben an vorher festgelegten Positionen und/oder eine zusätzliche Substitution.

    Noch klüger wäre es aber wohl, gleich einen 4x4x4-Würfel zu verwenden, da dürfte die ganze Sache schon wesentlich günstiger aussehen.

  7. #7 Norbert
    11. November 2016

    sobald der Würfel auf eine der errechneten fünf mal zehn hoch zwanzig Arten zusammengesetzt ist, ist er entweder ungültig (mehrere Zahlen auf ein und derselben Seite) oder es ist völlig eindeutig, in welcher Reihenfolge die Buchstaben zu lesen sind.

    Hier muss ich mich korrigieren: Diese Aussage stimmt nur, wenn die Ziffer auf einem Kanten- oder Eckstein geschrieben steht. Falls sie aber in der Mitte platziert ist, ist ihre Orientierung nicht eindeutig, sondern ergibt sich aus der vereinbarten Zugfolge. Eine erste Verbesserung des Verfahrens würde demnach darin bestehen, alle Zahlen nicht auf irgendeine, sondern immer die mittlere Position der jeweiligen Seite zu schreiben. Das beseitigt auch das Problem des verringerten Schlüsselraums, weil automatisch in jeder Kombination alle Zahlen auf die sechs Seiten verteilt sind.

  8. #9 Thomas
    11. November 2016

    Könnte man nicht den Würfel nachher auseinandernehmen und noch für eine zusätzliche Verschlüsselung per Trifid missbrauchen? Oder fehlt dafür in der Mitte ein Würfel, weil man 27 Stück brauchen würde? Vielleicht ginge Trifid aber auch mit intaktem Würfel, man dürfte dann nur jeweils eine Seite eines Miniwürfels beschriften.

  9. #10 Thomas
    11. November 2016

    Die alleinige Transposition per Würfel scheint wirklich nicht besonders gut zu sein, wenn sie sich über Nacht lösen lässt (leider ist nicht mitgeteilt, wie), https://books.google.de/books?id=f4PNBQAAQBAJ&pg=PA143

    Ein anschliießender Trifid mit dem Rubiks Würfel ginge wohl auch, ohne den Würfel auseinanderzunehmen, weil nur 26 Buchstaben zu verschlüsseln sind. Man nimmt drei Papierstreifen mit Kantenlänge und schreibt auf jeden Strefen 1, 2 und 3. Die Streifen klebt man auf drei Kanten, die in einem Eckpunkt zusammenlaufen. Dann vertelit man die 26 Buchstabenaufkleber irgendwie auf den 26 Außenwürfeln. Die aus jeweils drei Ziffern bestehenden Koordinaten des jeweiligen Miniwürfels lassen sich dann an den Streifen ablesen. Jetzt braucht man wohl doch noch Stift und Papier, um die Koordinaten in Spalten aufzuschreiben und dann die Ziffern zeilenweise abzulesen. Die anschließende Umwandlung in die endgültigen Chiffrebuchstaben geht dann wieder mit dem Würfel.
    Eigentlich aber eher was zum Basteln für die Vorweihnachtszeit…

  10. #11 user unknown
    https://demystifikation.wordpress.com/2016/11/04/bnd-gesetz-2/
    12. November 2016

    Es sind in jedem Zug 6 Rotationen möglich a 3 Winkel macht 18 Möglichkeiten.

    Die andere Aussage aus den Kommentaren ist, dass man mit spätestens 22 Zügen (hier aber 1/4-Drehungen angenommen, aber in freier Richtung) zum Ausgangspunkt zurückkommt. Einer 180°-Rotation entsprechen hier also 2 Schritte.

    Man kann also sagen, dass bei 6 Achsen und 2 Richtungen 12^18 Möglichkeiten eine obere Grenze sind, wobei einige Kombinationen von Drehungen neutral sind. Das sind rd. 2,66e19 und schon kleiner als 5,2e20.

    Wenn man auf dem richtigen Weg ist, sollten sich aber schon früher gehäuft sinnvolle Silben finden lassen, so dass man die Suche wohl früher einschränken kann. Allerdings tauchen ja viele Buchstaben im Klartext normalerweise mehrfach auf, so dass man da auch in Sackgassen geraten kann.

  11. #12 Abhishek Ramchandran
    United States
    16. Juli 2017

    I wrote a C++ program when I was in undergrad school that implemented the same cipher! But I used a 4×4 cube because 96 characters could be written on it. I also implemented swapping instead of just shuffling the cube, I discovered this fact that the cube can never be solved if the orientation of the colors was swapped and this discovery was made when I tried peeling out the cube’s stickers! I misplaced the stickers and ended up with an unsolvable cube. Check this out! https://github.com/aramchandran/Cryptography/tree/master/Automated%20126%20digit%20key%20encryption%20ver%201.0/Looped%20Rubik%20Encryption