GoogleCTF 2017 - Rubik write-up | Blog

This post is a mirror of the original publication available here.

An interactive server implements a login challenge with a variant of Diffie-Hellman on the group of permutations of the Rubik’s cube. After computing a discrete logarithm on this (non-abelian) group, we can compute the handshake to log in as admin and obtain the flag.

Description
Solution
Comments

Description

We found some spies using Rubik’s cubes as paper weights. Can you break their crypto?

Challenge running at rubik.ctfcompetition.com:1337

handshake.rs

Details

Points: 298

Category: Cryptography

Validations: 20

TL;DR

A solution in Python is available here, with a transcript of the communication. And here is an interactive visualization that takes as input cube configurations with the same serialization as in the challenge.

Can you extract admin’s private key from this cube?

Rust source code

We are given a source code in Rust that seems to implement a variant of Diffie-Hellman on the group of permutations of the Rubik’s cube. More precisely, given two generators $U$ and $L$ , the public key associated to two private exponents $a$ and $b$ is the permutation $pk = L^b \circ U^a$ . This public key is serialized as a configuration of the Rubik’s cube $pk(\textsf{defaultcube})$ , where $\textsf{defaultcube}$ is a solved Rubik’s cube.

There is also some code to compute a handshake. Given a peer’s public key $pk$ and one’s private key $(a, b)$ , the associated handshake is the permutation $L^b \circ pk \circ U^a$ . Then again, this permutation is applied to the default cube, converted to a string and hashed (along with a salt) with BLAKE-2.

Interactive server

The interactive server at rubik.ctfcompetition.com:1337 proposed several options.

$ nc rubik.ctfcompetition.com 1337
Welcome to the Rubik's cube authentication server!

You have the following options:
1) Public key service
2) Register
3) Login
q) Quit

Solution

Register and log in

Let’s start with option 1! We are prompted $a$ and $b$ and obtain a cube configuration.

1
What is your value of a?
0
What is your value of b?
0
Your public key is (0 * "U x'" + 0 * "L y'") ==
WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY

Nice, so we can see that the default cube really looks like a solved cube, with colors {white, green, red, blue, orange, yellow}, serialized in the following order: top face, circles on the sides, bottom face.

Rubik’s cube in default configuration

We can also extract $U$ and $L$ with $(a=1, b=0)$ and $(a=0, b=1)$ .

U = OOOOOOGGGGGRWWWOBBYYYGGRWWWOBBYYYGGRWWWOBBYYYBBBRRRRRR
L = WWWWWWOOOOOYGGGWRRBBBOOYGGGWRRBBBOOYGGGWRRBBBRRRYYYYYY

Rubik’s cube after permutation U

Rubik’s cube after permutation L

OK, now let’s try to register a new user. We are prompted for a public key, what to choose??

We are probably going to do a handshake with the server, so let’s try with a zero key, i.e. $(a=0, b=0)$ and $pk = \textsf{defaultcube}$ . That way, the handshake computed by a peer will collapse to the peer’s public key, no need to extract their secret key.

2
What username do you want to register?
user
What public key do you want to register?
WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY
User registered!

We can now log in. We are challenged to compute the handshake with the server’s public key.

3
What user do you want to log in as?
user
My public key is:
WYBORYGWYBWWOBRGGRYRRRWOYGRGYGOBBOYGYORGRBOGWOBWBOWBWY

Please give me the result of:
mykey.handshake(yourkey, "420823cb18a31058".from_hex().unwrap()).to_hex()

As expected, we are challenged to obtain the handshake that a peer would compute with their secret key and our public key. Since we chose a dummy public key, the handshake’s cube is equal to the peer’s public key! The same would happen in any Diffie-Hellman handshake if someone selects a zero exponent.

An example of challenger’s public key

The server quickly closes the connection, so let’s automate the computation. I used Python2 with pyblake2 library for the hash. However, after some failed attempts and looking at Rust’s BLAKE-2 code, it turns out that what the CTF calls salt is what BLAKE-2 calls key!

sock = socket.socket()
# ...
h = blake2b(key=salt, digest_size=16)
h.update(cube)
handshake = h.hexdigest()
sock.send(handshake + '\n')

We are now logged in! And the flag is…

Not here.

However, we have a new option to list users.

4) List users

We obtain a list of logins and public keys.

Username: admin
Key: GWYROYBBRYGWROGYGBRROGBYBYYRGBWWWOOWRYOWRYBGWGOGWRBBOO
Username: user
Key: WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY

At this point we cannot use the zero private key trick anymore to compute admin’s handshake. We really need to extract secret keys from public keys.

Finding the generator permutations $U$ and $L$

Given a public key $\textsf{cube}$ , we could try to bruteforce $a$ and $b$ and check whether $\textsf{cube} = L^b \circ U^a (\textsf{defaultcube})$ . However, we need to implement arithmetic on Rubik’s cubes. I have already played with a Rubik’s cube before and $L/U$ probably means turn the left/up face one quarter round, but it’s not obvious to visualize from those long strings of 6 letters…

This is when I realized that permutations on the cube can just be seen as permutations of 54 letters! So for $U$ we just need to find a permutation of $\{1, \ldots, 54\}$ such that WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY is mapped to OOOOOOGGGGGRWWWOBBYYYGGRWWWOBBYYYGGRWWWOBBYYYBBBRRRRRR.

Unfortunately, there are only 6 colors so there are many possible permutations, e.g. the first W can be mapped to 9 locations. To retrieve the exact permutation, I simply asked the server $U^a(\textsf{defaultcube})$ for $a = 0, 1, \ldots$ and derive constraints on $U$ by comparing pairs $(U^a(\textsf{defaultcube}), U^{a+1}(\textsf{defaultcube}))$ .

# Solve permutation U
def solveU(sock):
    cube = getcubeU(sock, 0)
    # Init a NxN matrix with ones
    constraints = []
    for i in range(N):
        constraints.append([1] * N)

    k = 0
    while True:
        k += 1
        newcube = getcubeU(sock, k)

        # Update constraints on permutation
        for i in range(N):
            for j in range(N):
                if cube[i] != newcube[j]:
                    constraints[i][j] = 0
        cube = newcube

        # Try to extract the permutation
        p = getperm(constraints)
        if p is not None:
            return p


##### Util functions #####

# Extract a permutation from constraints, or None if several solutions exist
def getperm(constraints):
    l = [0] * N
    for i in range(N):
        found = False
        for j in range(N):
            if constraints[i][j] == 1:
                if found:
                    return None
                found = True
                l[i] = j
    return l

# Read line from a socket
def recvline(sock):
    buf = ''
    while True:
        tmp = s.recv(1)
        if len(tmp) == 0:
            raise socket.error
        buf += tmp
        if tmp == '\n':
            break
    return buf

# Read a cube for (a, b=0)
def getcubeU(sock, a):
    for i in range(6):
        recvline(sock)

    sock.send(sock, '1' + '\n')
    recvline(sock)
    sock.send(str(a) + '\n')
    recvline(sock)
    sock.send(str(b) + '\n')
    recvline(sock)
    cube = recvline(sock)
    return cube

After 12 iterations, the set of constraints reduces to only one possible permutation (same for $L$ ). Here are $U$ and $L$ (using the convention that $i$ is mapped to the value of cell $U[i]$ ).

U = [14, 26, 38, 13, 25, 37, 12, 24, 36,
      8,  7,  6, 11, 23, 35, 45, 46, 47,
     39, 27, 15, 10, 22, 34, 48, 49, 50,
     40, 28, 16,  5,  4,  3,  9, 21, 33,
     51, 52, 53, 41, 29, 17,  2,  1,  0,
     44, 43, 42, 32, 31, 30, 20, 19, 18]
L = [15,  3,  0, 27,  4,  1, 39,  5,  2,
     14, 26, 38, 47, 16, 17, 18, 19, 20,
      9, 10,  8, 13, 25, 37, 46, 28, 29,
     30, 31, 32, 21, 22,  7, 12, 24, 36,
     45, 40, 41, 42, 43, 44, 33, 34,  6,
     35, 50, 53, 23, 49, 52, 11, 48, 51]

Discrete logarithm in subgroup of Rubik’s cube permutations

A quick check shows that $U$ and $L$ both have order 1260, which is fairly small! We could brute-force all pairs $(a, b)$ for $0 \le a, b \lt 1260$ , but a more efficient method is to adapt the baby-step giant-step algorithm to our (non-abelian) group of permutations.

Namely, we start by caching in a hash table the pairs $(U^a(\textsf{defaultcube}), a)$ for $0 \le a \lt 1260$ . Then, given a public key $\textsf{cube}$ to break, we compute $L^{-b}(\textsf{cube})$ for $0 \le b \lt 1260$ until there is a match $L^{-b}(\textsf{cube}) = U^a(\textsf{defaultcube})$ in the hash table. The corresponding pair $(a, b)$ is the secret key.

I applied this discrete logarithm algorithm to both the challenger’s public key and the admin’s public key, hoping to find two pairs $(a, b)$ and $(a', b')$ and obtaining the handshake as $L^{b+b'} \circ U^{a+a'} (\textsf{defaultcube})$ .

However, only the challenger’s public key factorizes! It seems that the admin cheated and did not provide a public key of the form $L^b \circ U^a$ …

Extracting a permutation between two cubes

OK so we are back to the following problem: given a cube configuration, what is the permutation $P$ of its 54 squares such that $\textsf{cube} = P(\textsf{defaultcube})$ ? The 6 colors are repeating, so this time we really need to visualize a Rubik’s cube…

It turns out that the physical structure of the cube gives more constraints: corners can only be permuted with corners, sides can only be permuted with sides, and centers can only be permuted with centers. What’s more, the 3 squares that form a corner are bound together, and same goes for the 2 squares that form a side. Finally, given 3 colors (e.g. white, red, blue), there is at most one corner that combines these colors. Same goes for sides.

Great, so now we have to identify where centers/sides/corners are on the 54-character strings… The default cube has clear patterns and if we assume that it is a solved cube we can already guess that squares are numbered in the following order: top face, circles on the sides, bottom face. By looking more closely, permutation $U$ seems to rotate the top face by a quarter round, then rotate the whole cube. This gives some insight about the order of traversal of the top and bottom faces, and after some manual testing I ended up finding a mapping between $\{1, \ldots, 54\}$ and the squares on the physical cube.

Once the correct mapping is found, we can extract a permutation between two cubes!

# Extract permutation between the default cube and any cube
def cube2perm(zero, cube):
    # Indices of distinguished squares
    CENTERS = [
        4, # top
        22, 25, 28, 31, # sides
        49 # bottom
    ]
    SIDES = [
        (3,10), (7,13), (5,16), (1,19), # top
        (23,24), (26,27), (29,30), (32,21), # sides
        (34,48), (37,46), (40,50), (43,52) # bottom
    ]
    CORNERS = [
        (0,9,20), (6,11,12), (8,14,15), (2,17,18), # top
        (51,44,33), (45,35,36), (47,38,39), (53,41,42) # bottom
    ]

    perm = [0] * N

    for i in CENTERS:
        for a in CENTERS:
            if zero[i] == cube[a]:
                perm[i] = a
                break

    for i, j in SIDES:
        for a, b in SIDES:
            if sorted([zero[i], zero[j]]) == sorted([cube[a], cube[b]]):
                if zero[i] == cube[b]:
                    a, b = b, a
                perm[i] = a
                perm[j] = b
                break

    for i, j, k in CORNERS:
        for a, b, c in CORNERS:
            if sorted([zero[i], zero[j], zero[k]]) == sorted([cube[a], cube[b], cube[c]]):
                if zero[i] == cube[b]:
                    a, b = b, a
                elif zero[i] == cube[c]:
                    a, c = c, a
                if zero[j] == cube[c]:
                    b, c = c, b
                perm[i] = a
                perm[j] = b
                perm[k] = c
                break

    return perm

Wrapping-up

So now we can put everything together to log in as admin and extract the flag! First, we extract admin’s permutation $P_{admin}$ from its public key using the above cube2perm function. Then, when challenged to find a handshake from some public key $pk$ , we extract the associated $a$ and $b$ as $pk = L^b \circ U^a(\textsf{defaultcube})$ and we can compute the handshake $L^b \circ P_{admin} \circ U^a(\textsf{defaultcube})$ to log in.

Here is a Python script that solves the challenge: rubik.py. I also recorded a transcript of the communication.

The flag is CTF{StickelsKeyExchangeByHand}.

You can also play with my interactive visualization of cube configurations in webGL here.

Comments

Some last comments about the problem behind this challenge.

First, can both peers compute the same handshake? If everyone uses a public key of the form $L^b \circ U^a$ , the handshake is indeed symmetric:

L^b \circ (L^{b'} \circ U^{a'}) \circ U^a = L^{b'} \circ (L^b \circ U^a) \circ U^{a'}

However, if someone cheats and does not issue a key of this form (as did the admin in the challenge), it is not obvious that they can compute the handshake, unless of course they can recover the other’s private key.

More generally, the method could work for non-abelian groups as long as they have large-order subgroups on which computing discrete logarithms is hard.

Comments

To react to this blog post please check the Twitter thread.

RSS | Mastodon | GitHub

Description

Details

TL;DR

Rust source code

Interactive server

Solution

Register and log in

Finding the generator permutations UUU and LLL

Discrete logarithm in subgroup of Rubik’s cube permutations

Extracting a permutation between two cubes

Wrapping-up

Comments

Comments

You may also like

Finding the generator permutations $U$ and $L$