30
$\begingroup$

Consider this scenario:

Alice gets a Rubik's Cube and peels off the colors from each piece. She then writes a small message on one of the faces of the cube and fills the remaining pieces with random letters. Then, she scrambles the pieces in a way that was pre-determined between Alice and Bob. And finally, she ships the cube to Bob.

Can this be considered as encryption, and, if so, how secure can this encryption scheme be?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ How will Bob know the correct orientation of the cube so he knows how to hold it when he starts unscrambling? $\endgroup$
    – Barmar
    Aug 28, 2017 at 10:24
  • 1
    $\begingroup$ @Barmar Centers cannot move. Pick any center as the 'root' to determine facing. $\endgroup$
    – Weckar E.
    Aug 28, 2017 at 11:50
  • 1
    $\begingroup$ @WeckarE. But if the colors are removed, how do you know which face is which when decoding? $\endgroup$
    – Barmar
    Aug 28, 2017 at 11:53
  • 1
    $\begingroup$ @Barmar They can also pre-determine that, for example, Bob knows to start solving the puzzle knowing that center piece that contains the letter "A" should face him, and the center piece that contains letter "Y" should be on the right side of the "A" center piece. Or they can decide on something smarter that I didn't thought of yet. $\endgroup$
    – yasar
    Aug 28, 2017 at 16:51
  • 1
    $\begingroup$ For reference, Google CTF in 2017 included one challenge using Stickel's Key Exchange on a Rubik's Cube. Note that Rubik's cube group is non-abelian, so it would fall into the non-commutative crypto category. There are a few crypto papers about Rubik's cube too. $\endgroup$
    – Lery
    Aug 29, 2017 at 12:47

2 Answers 2

Reset to default
38
$\begingroup$

Can this be considered as Encryption

If the sequence of necessary moves is treated as the key, yes.

how secure can this encryption scheme be?

First some details about the cube:

  • 6 faces, each with 9 pieces visible each. Because the faces share some pieces, and the immovable cube center is not visible, there are only 26 pieces in total: 6 centers (of faces), 8 corners (each with 3 colored sides), and 12 edges (each with 2 colored sides).
  • The center piece of each face is, like the cube center itself, not movable. If it is "moved", in reality everything else moves.
  • The 8 corner pieces always are corner pieces, independent of any moves. Same goes for the. 12 edge pieces.
  • There are 8! possible position combinations of the 8 corner pieces (naturally). In their position, 7 of the 8 can have 3 possible "rotations", just the last one depends on the others. With this, there are corner $8! \cdot 3^7$ possible corner positions
  • Similarly, 12! combinations of edge pieces are restricted to $\frac{12!}{2}$ by the corner pieces (for details to everything, see Wikipedia).

Now, we have 9 pieces that contain "good" data: 1 face center, 4 edges (each has two more sides with nonsense data), and 4 corners (each 1 more side with nonsense data). The other 17 pieces contain only nonsense data.

If an attacker wants to (bruteforce-)find the center piece with the good data on it, there are 6 possibilities (6 face centers, just turning the whole cube around to find the right one).

Then there are 4 corner pieces where position and orientation matters, and 4 others that don't matter to find the one good-data face. Meaning, $\frac{8!}{4!} \cdot 3^4$ possibilities to try here.

Finally, 4 edge pieces where position and orientation matters, and 8 others that don't matter to find the one good-data face. Meaning, $\frac{12!}{2} \div \frac{8!}{2} \cdot 2^4$

Multiplying...

$6 \cdot \frac{8!}{4!} \cdot 3^4 \cdot \frac{12!}{2} \div \frac{8!}{2} \cdot 2^4 = 155196518400$ or about $2^{37}$

Your key has 37 bit. With todays computer, that's nothing =>
completely insecure

Aside from that ...

  • A "padding" of 45 byte for 9 byte payload is impractical
  • A cube that contains the same symbol multiple times is less secure
  • The scheme isn't protected against things like known-plaintext attacks etc.etc.
  • Properties like the avalanche effect etc., etc. are completely missing
  • Depending on the choice of padding data, just making statistics what symbols exist might be enough to figure the plaintext out
  • ... and many more
Improve this answer
$\endgroup$
8
  • 8
    $\begingroup$ @SqueamishOssifrage I think if OP meant a non-standard cube, it should have been mentioned in the question... $\endgroup$
    – deviantfan
    Aug 28, 2017 at 3:32
  • 8
    $\begingroup$ Key length is only one factor, and even if there are $2^{128}$ keys, it still means nothing about security. The substitution cipher has a very large key space and it's completely and trivially insecure. $\endgroup$
    – Yehuda Lindell
    Aug 28, 2017 at 6:29
  • 1
    $\begingroup$ Depending if all letters of the original message are oriented equally, your computations regarding the security are way to optimistic. If they should be equal, then most of the time the letters will be wrongly oriented. And you can use this to your advantage. For instance this is why it is possible to solve the Sudoku Cube (en.wikipedia.org/wiki/Sudoku_Cube). $\endgroup$
    – Jakube
    Aug 28, 2017 at 10:04
  • 17
    $\begingroup$ @YehudaLindell A large key does not guarantee security. But an small one does guarantee insecurity. Thus deviantfan only needs to prove an upper bound for the key (an optimistic one) which is small enough to guarantee lack of security. As he has done. $\endgroup$
    – Anonymous Coward
    Aug 28, 2017 at 11:49
  • 1
    $\begingroup$ @JoseAntonioDuraOlmos Indeed, you are right. The problem is that many people will then say stupidities like "so it's OK with a larger cube"... That's just what I was trying to prevent. $\endgroup$
    – Yehuda Lindell
    Aug 28, 2017 at 11:53
8
$\begingroup$

i will defer to deviantfan's judgement on whether this constitutes encryption, but I see no reason to counter his argument. By as to security though...

Brute force in not necessary at all. There's classic permutation, but no substitution is involved. So it's just 3D scrabble and looks like:-

small letters

with small letters ( I didn't spend a great deal of time formatting it but you get the gist), or like this with large letters:-

large letters

The former is fairly trivial as you can see whole words and multiple words. Compared to random letters, some common sense reveals the secret message.

The latter is slightly more difficult as the letters would be permuted individually. The presence or absence of spaces is not really relevant to this answer's premise. Frequency analysis will make short work of decryption. If you look at the details of monogram, bigram and trigram letter frequencies, you'll see that most random combinations are not possible in a language (even if it's Klingon). There are even statistics for whole words. Below is an extract for monograms:-

monogram frequencies

Clearly cubes with a "Q" on them are improbable in constituting a word, but even if then did, you know that the next letter is certainly a "U". Et cetera. The statistical calculations are a little beyond me, but you will easily infer that the message can be extracted much much quicker than brute forcing it. Without knowing the exact term for this level of encryption, I would use Scrabble Junior level.

As a sidebar, one of the most difficult aspects of this encryption might be how to actually convey the permutation sequence /key.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ To convey the permutation sequence / key, all Alice need to do is scramble two cubes the same exact way, and then give Bob one and keep one for herself. She then specifies a key letter that is not symmetrical, e.g. V. She puts the V in the green center square, with the character facing up towards the yellow center and down towards the white center. If you correctly orient the V and then solve the second cube, while copying the movements onto the code cube, it'll also solve the code cube $\endgroup$
    – Hans Z
    Aug 29, 2017 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.