A Rubik’s Cube can be used to implement a low-tech encryption method. But is it secure? Here’s a challenge for my readers to solve.

In a Cryptologia publication from 1992, Douglas W. Mitchell proposed an interesting cipher that does not require computer support: encryption with a Rubik’s Cube.

 

The algorithm

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 “ABCDEFGHIJKLMNOPQRSTUVWXabcdefghijklmnopqrstuvwx”.

Rubik-Encryption (3)

For encryption and decryption to work properly, it must be defined, which corner is considered as the upper left one (this is only clear for the front face). I used the following scheme:

Rubic-Cube-Orientation

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 middle row by 90/180/270 degrees, rotating the back level by 90/180/270 degrees, and rotating the middle level by 90/180/270 degrees).

Rubik-Directions

The rotations carried out are the key. For my example 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 with the 1 in the upper left corner, 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 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.

 

A challenge

I published a blog post about Mitchell’s cube encryption algorithm two years ago. There were many comments, some of which doubted the security of this method. As far as I know, nobody has ever published a research paper that discusses attacks on this kind of encryption. So, it is still quite unclear whether this algorithm is as secure as it seems and if it can be improved.

To stimulate research in Mitchell’s cube encryption algorithm, I have created a challenge. I took a sentence consisting of 48 letters and encrypted it with a Rubik’s Cube in the way I described it above. Here is the ciphertext I received:

1GDWOHOER GTNTTROI3 AET2NEV5N EIOYR6IBO WEHM4UCOD TNEIEMYET

Can a reader break this cryptogram? If so, which codebreaking method did you use? Is Hill Climbing an option? I’m looking forward to your comments.

Further reading: The world record crypto challenge

Kommentare (20)

  1. #1 Jerry McCarthy
    England, Europa.
    27. Oktober 2018

    Abo…

  2. #2 Jerry McCarthy
    England, Europa.
    27. Oktober 2018

    Your example plain text “ABCDEDGHIJKLMNOPQRSTUVWXabcdefghijklmnopqrstuvwxyz” seems a bit wrong. I guess it should start “ABCDEF”, and it seems to be too long (50 characters)

  3. #3 Klaus Schmeh
    27. Oktober 2018

    @Jerry: Sorry, you’re right. The plaintext was actually ABCDEFGHIJKLMNOPQRSTUVWXabcdefghijklmnopqrstuvwx
    I corrected it.

  4. #4 George Lasry
    28. Oktober 2018

    This reminds me of the Cryptobox cipher:

    http://users.telenet.be/d.rijmenants/en/boxchallenge.htm

    In this cipher, the effect of one step affects either no more than 20% of the bigrams (vertical moves) and much less in many cases (horizontal moves). So maybe 12% on average. The challenge had 100 letters and 20 steps. It was a very hard challenge.

    With the Rubic code, the effect of each step on the bigrams of resulting text seems to be dramatic (2/3 = 67% of them are affected – all the bigrams on 4 sides out of 6). So after a small number of steps, the disruption is dramatic and would make hillclimbing ineffective. Also, the length of the text – 48 – is way too short, given the key size of the space (assuming we have 10 or more steps). Could even be below the unicity distance(?).

    To check the limits of hillclimbing (maximum number of encryption steps), we would need to implement it, but on the surface, my intuition is that with 10 steps we have a pretty good level of security. An even much more with 20 steps.

    How many steps in the challenge key?

  5. #5 Norbert
    29. Oktober 2018

    @George: I think a hillclimber might be successful. But rather than trying to find the right “moves”, it should just disassemble the whole cube and try to reassemble it in a promising way. Consider that a corner piece always remains a corner piece with only seven possible positions (one corner is fixed according to Klaus, and with it not only the “1” but also another two cipher letters which therefore cannot be moved at all!), and only three orientations per position. Analogously, every edge piece has 12 possible positions with only two orientations. The only problem is that we don’t know in which orientation each side of the cube has been written on. However, I think the keyspace is not that huge as it seems at first glance…

  6. #6 Klaus Schmeh
    1. November 2018

    Bart Wenmeckers via Facebook:
    Great topic. The 3×3 has some major vulnerabilities which would be reduced using 4×4 or 6×6 cubes. I might have a quick go tonight.

  7. #7 Klaus Schmeh
    1. November 2018

    Bart Wenmeckers via Facebook:
    Hi Klaus just to confirm the interpretation of your article is this the correct encrypted layout of the cube?

  8. #8 Klaus Schmeh
    1. November 2018

    @Bart Wenmeckers:
    Yes, this is correct.

  9. #9 Jonas Gerdel
    Koblenz
    5. November 2018

    Hello Klaus,

    if the message is longer (using the same rotations for a longer message) its possible to get the message just by linguistic analysis.
    The main problem in my view is that plain text and ciphered text using the same letters. Its just a somehow scrambled anagram.
    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
    1 1 1 2 8 – 2 2 4 – – – 2 4 6 – – 3 – 6 1 1 2 – 2 –

    Here is my try so far:
    I WONDER WHY YOU ARE NOT GETTING THE CODE
    NO MORE TIME
    Letters not used: EBIMTV
    or
    MOVE IT ONE TIME (RBM)
    MOVE IT MORE TIME (BN)

    If you have an idea about the message content, you will get it, im pretty sure.
    There is no S(!), no F, and only one A.
    It may be completly wrong, it’s just a guess.

    Außerdem ist mein Englisch nicht besonders gut 😉

    when will you show the plaintext?

    PS: in the diagram the letter under the 4 has to be O, not D.

    Kind regards!

  10. #10 Klaus Schmeh
    11. November 2018

    @Jonas Gerdel:
    >the letter under the 4 has to be O, not D.
    Sorry for the mistake.

    >Here is my try so far:
    I’m afraid, you’re on the wrong track. This doesn’t look like the correct solution.

  11. #11 Norbert
    19. Dezember 2018

    @Klaus:
    Maybe I am getting it wrong, but imho your example encryption does not comply with the rules: As can be seen in the picture of the cleartext example, the bottom face (which, in the picture, is the one with “3” on it) is filled with the letter sequence QRSTUVWX, but your starting point (the “Q”) apparently is not the upper left corner as defined by your scheme. Instead, “Q” is written on the upper right corner.

    I “solved” the encrypted example cube by reversing the sequence MC90, LR270, RC180, ML90, BL270, and noticed that you used the following corners as starting points for the cleartext:

    front face: upper left
    right face: lower left
    back face: lower right
    left face: lower right
    top face: upper right
    bottom face: upper right

    So, only one face is filled correctly.

    Reading out the cleartext cube in the prescribed order yields:

    1ABCDEFGH KMPJ2OILN po5nmlkji hgfedc4ba vnqwt6xur V3QWTRXUS

    …which certainly is not what you meant to write on it.

    My question: Was the challenge plaintext written on the cube in compliance with the rules? This is crucial if we want to have any chance to solve it by means of programming.

  12. #12 Klaus Schmeh
    22. Dezember 2018

    @Norbert: I’m afraid, you’re right. The “ABCD…” example is not encrypted in the way explained in this article. This is because I created this example two years ago for a different post. The challenge message introduced in this post is encrypted should be correct (i.e. encrypted exactly the way described here).

  13. #13 Klaus Schmeh
    28. Dezember 2018

    Sîr Waffle via Facebook:
    Hey, this puzzle looks awesome and I will try my hand at it for sure. Not to be nit picky but it would be a lot easier read using proper notation for the cube R (right face) L (left face) F (front face) B (back Face) U(up face) D down face and with the following to indicate which direction
    R-rotate the right face clockwise 90 degree s
    R2- Rotate the right face 180 degrees
    R’- Rotate the right face anti clockwise 90 degrees.
    (always rotate clockwise or anti clockwise as though you were looking at that face)

    And you can also better identify specifics squares on the cube using this system ULB would be the Up left back or top left as you had said. .

    Sorry if this is too much just thought I’d share it, still great anyways! 🙂

  14. #14 Klaus Schmeh
    28. Dezember 2018

    Bart Wenmeckers via Facebook:
    Lol not everyone is familiar with cubes also please note my start pattern above has a couple of typos in it

  15. #15 Klaus Schmeh
    28. Dezember 2018

    Sîr Waffle via Facebook:
    Lol i know, im just a speedcubing nerd

  16. #16 Klaus Schmeh
    28. Dezember 2018

    Bart Wenmeckers via Facebook:
    The biggest short coming of using a 3×3 is that corners can only be corners, centers stay in position and edges remain edges. Still surprisingly a huge key space

  17. #17 Klaus Schmeh
    28. Dezember 2018

    Bart Wenmeckers via Facebook:
    I am just happy I can at least solve under a minute.

  18. #18 Klaus Schmeh
    28. Dezember 2018

    Sîr Waffle via Facebook:
    That’s still great!

  19. #19 Narga
    12. März 2019

    I found the solution last weekend! It’s “Meet you at the wooden bridge in the city tomorrow evening.” I struggled a bit with posting a comment here since 🙂

  20. #20 Klaus Schmeh
    16. März 2019

    @Narga: Congratulations, this is correct!
    I will introduce your solution in a blog post soon.