Teaching Cryptography: Rubik’s Cube Diffusion

Written by Dominik Joe Pantůček on 16 května, 2019.

Although we are dealing mostly with asymmetric encryption here at Trustica, truth is that in the end you need to encrypt stuff using some symmetric algorithm. Just exchanging the symmetric keys is not enough – the symmetric cipher must be built from strong cryptographic primitives creating both confusion and diffusion. Read on to find out what one of my Cryptography class students proposed.

In cryptography, confusion means changing the meaning of characters – be it actual letters, bytes or just bits. A well-known confusion-only cipher is the Caesar’s cipher[1]. Turns out that if the confusion is not confusing enough, you can use frequency analysis to break such cipher. Different class of ciphers work with diffusion – that is mixing the characters of the message according to some schema. For a diffusion-only cipher, look at the Grille[2] grid-based transposition cipher.

Modern block ciphers add both confusion and diffusion. For each block, some transposition is applied – this adds diffusion. And then each character is substituted for different one, adding confusion to the mix. The confusion part is done via a construct called S-box[3] (short for substitution box) and the diffusion is added using a construct called P-box[4] (short for permutation box).

In the Cryptography class I teach at the local university[5], the students were given a task to design their own symmetric cipher. That is actually just the first part of the task – the second being the crypto-analysis of other student’s cipher. The submitted designs were cool and one of them, made by a talented IFSA[6] student David[7] immediately got my attention, because it mixes Cryptography and 3D graphics – should you try to visualize it.

It is a diffusion-only cipher that uses Rubik’s Cube[8] for performing the actual characters transposition. The secret key is the scrambling specification of the Rubik’s Cube and has to be known by both communicating parties. For those not very familiar with Rubik’s Cubes (like me, to be honest) it might be slightly complicated, but for anyone who knows how to solve the Rubik’s Cube, it should be pretty easy.

The encryption and decryption operations are as follows:

  • for encrypting the message, you take a solved Rubik’s Cube in specified orientation and you write the message on it – one character at each surface of each of the small cubes comprising the whole cube. Then you apply the scrambling rules and write down the transposed message by reading the letters from the cube in unchanged orientation.
  • then for decrypting the message, you take a solved Rubik’s Cube, scramble it using the secret key and write the encrypted message on its surface while retaining the cube’s orientation. Then you solve the Rubik’s Cube and the clear-text message is revealed.

As I mentioned above, this idea immediately captured my attention and I just had to implement it over a weekend in Racket[9]. You can see the result in Picture 1 below.

Picture 1: implementation of Rubik’s Cube Cipher

As you can see, adding the clear-text message „Hello David… This is an encrypted message… Gotcha!“ and scrambling the cube a bit results in the encrypted message „.leapsscmD Hhad! Gr  aoeit.he.c dv.lTyiat n.ee ng.sios“. That looks pretty cryptic, doesn’t it?

Although the results look promising, of course, this is not a cipher that you should use for actually protecting any important secret. Hopefully we will have some time in the future to perform a proper crypto-analysis of this one. But even without going into detail, you can easily see, that the permutations it creates are limited by the valid Rubik’s Cube moves. The letters in the corners will always end up in corners, the adjacent letters on the same small cube will always be adjacent and orientation of the middle small cubes does not change at all. It really would not make a good P-box.

But for a school project this is actually a pretty nice example of how to design a practical transposition cipher. And I can imagine someone can use it as a part of a game or for sending semi-secret messages between students in the class.

 

Hope you enjoyed our journey to symmetric cipher design. See you next Thursday with more!


References

1. Wikipedia contributors. (2019, April 29). Caesar cipher. In Wikipedia, The Free Encyclopedia. Retrieved 10:21, May 13, 2019, from https://en.wikipedia.org/w/index.php?title=Caesar_cipher&oldid=894753583

2. Wikipedia contributors. (2017, October 24). Grille (cryptography). In Wikipedia, The Free Encyclopedia. Retrieved 10:20, May 13, 2019, from https://en.wikipedia.org/w/index.php?title=Grille_(cryptography)&oldid=806806955

3. Wikipedia contributors. (2019, May 6). S-box. In Wikipedia, The Free Encyclopedia. Retrieved 10:20, May 13, 2019, from https://en.wikipedia.org/w/index.php?title=S-box&oldid=895709858

4. Wikipedia contributors. (2018, August 28). Permutation box. In Wikipedia, The Free Encyclopedia. Retrieved 10:20, May 13, 2019, from https://en.wikipedia.org/w/index.php?title=Permutation_box&oldid=856976110

5. Prague College, available online at https://www.praguecollege.cz/

6. Institute for Study Abroad, available online at https://www.ifsa-butler.org/

7. David S. Golden webpage, available online at https://davidsgolden.com/

8. Wikipedia contributors. (2019, May 6). Rubik’s Cube. In Wikipedia, The Free Encyclopedia. Retrieved 10:16, May 13, 2019, from https://en.wikipedia.org/w/index.php?title=Rubik%27s_Cube&oldid=895795378

9. Racket solve problems · make languages, available online at https://racket-lang.org/