Google CTF 2017 Quals - Rubik

0handshake.rs

use permutation::Permutation;
use cube::Cube;
use crypto::blake2b::Blake2b;

#[derive(Copy, Clone, Eq, PartialEq, Hash)]
pub struct SecretKey {
    pub a: u64,
    pub b: u64,
}

#[derive(Copy, Clone, Eq, PartialEq, Hash)]
pub struct PublicKey {
    pub key: Permutation,
}

impl SecretKey {
    pub fn to_public(&self) -> PublicKey {
        let pa = Permutation::parse("U x'").unwrap();
        let pb = Permutation::parse("L y'").unwrap();

        PublicKey { key: self.a * pa + self.b * pb }
    }

    pub fn handshake(&self, key: PublicKey, salt: &[u8]) -> [u8; 16] {
        let pa = Permutation::parse("U x'").unwrap();
        let pb = Permutation::parse("L y'").unwrap();
        let cube = Cube::default().apply(self.a * pa + key.key + self.b * pb);
        let mut out = [0; 16];
        Blake2b::blake2b(&mut out, &cube.serialize().as_bytes(), salt);
        out
    }
}

impl PublicKey {
    pub fn serialize(&self) -> String {
        Cube::default().apply(self.key).serialize()
    }

    pub fn unserialize(s: &str) -> Option<PublicKey> {
        if let Some(cube) = Cube::unserialize(s) {
            if let Some(perm) = Permutation::from_cube(cube) {
                return Some(PublicKey { key: perm });
            }
        }
        None
    }
}

1hash.py

#-*- coding:utf-8 -*-
'''
Rubik's Cube based key exchange!

Two simple moves are defined:
A = "U x'"
B = "L y'"

Secret key is a, b.
Public key is A^a B^b.

To merge public key P with secret key, we compute A^a P B^b = A^(a+a') B^(b+b').
So the order does not matter and the key exchange is possible.

By simple check we can see that the orders of A, B are 1260.
So we can simply break any public key (very fast with meet-in-the-middle).

---

When we auth with our own key, we can see admin's public key.
Interestingly, the attack does not work! Meaning that it does not have the necessary form.

Anyway, we know how the checker works. We can break the challenger's key and wrap the admin's key properly.

WASTED: "salt" is passed in the Blake2b's "key" parameter!
Blake2b::blake2b(&mut out, &cube.serialize().as_bytes(), salt);

---

hash.py simply hashes a cube string with given salt/key.
solve.py takes challenger's public key, admin's public key and salt and returns valid response.
'''

import sys
from pyblake2 import blake2b
print blake2b(sys.argv[1], key=sys.argv[2].decode("hex"), digest_size=16).hexdigest()

2solve.py

#-*- coding:utf-8 -*-

# https://github.com/pglass/cube modified to support hashing (for dict)
from rubik.cube import Cube
from rubik.solve import Solver

PUB0 = "WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY"

def tos(cube):
    return "".join(str(cube).split())

def recover(pub):
    cur = Cube(PUB0)
    d = {tos(Cube(cur)): 0}
    for i in xrange(1, 1261):
        cur.U()
        cur.Xi()
        if tos(cur) not in d:
            d[tos(cur)] = i
    cur = Cube(pub)
    for i in xrange(1261):
        if tos(cur) in d:
            return d[tos(cur)], i
        cur.Y()
        cur.Li()
    assert 0

def make(a, b, mid=None):
    c = Cube(PUB0)
    for i in xrange(a):
        c.U()
        c.Xi()
    if mid is not None:
        c.sequence(mid)
    for i in xrange(b):
        c.L()
        c.Yi()
    return c

import sys
from pyblake2 import blake2b

a, b = recover(sys.argv[1])
print "Challenger private key", a, b

# Get sequence of moves to get admin's key
s = Solver(Cube(sys.argv[2]))
s.solve()
test = Cube(sys.argv[2])
for m in s.moves:
    test.sequence(m)

# HACK: match colors by rotating cube randomly
import random
for i in xrange(100):
    if tos(test) == PUB0:
        print "GOOD", i
        break
    m = random.choice("XYZ")
    test.sequence(m)
    s.moves.append(m)
else:
    print "FAIL"
    quit()

def inv(m):
    if m[-1] == "i":
        return m[:-1]
    return m + "i"

moves = [inv(m) for m in s.moves[::-1]]
res = tos(make(a, b, " ".join(moves)))
print "Wrapped admin's cube", res

print blake2b(res, key=sys.argv[3].decode("hex"), digest_size=16).hexdigest()

3log.sh

$ nc -v rubik.ctfcompetition.com 1337
rubik.ctfcompetition.com [104.155.121.157] 1337 (?) open
Welcome to the Rubik's cube authentication server!

You have the following options:
1) Public key service
2) Register
3) Login
q) Quit
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

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

$ nc -v rubik.ctfcompetition.com 1337
rubik.ctfcompetition.com [104.155.121.157] 1337 (?) open
Welcome to the Rubik's cube authentication server!

You have the following options:
1) Public key service
2) Register
3) Login
q) Quit
2
What username do you want to register?
q
What public key do you want to register?
WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY
User registered!

You have the following options:
1) Public key service
2) Register
3) Login
q) Quit
3
What user do you want to log in as?
q
My public key is:
YYRYOYYGWOGOBOOGOYBBGGWBWBOBYYRGRRWBRROBRGRGWWBWORWGWY

Please give me the result of:
mykey.handshake(yourkey, "252e84111e53bbbf".from_hex().unwrap()).to_hex()
# hash.py YYRYOYYGWOGOBOOGOYBBGGWBWBOBYYRGRRWBRROBRGRGWWBWORWGWY 252e84111e53bbbf
c5c7b4a32471ecf8346925e651e97ccf
Your are now logged in!
You have the following options:
1) Public key service
2) Register
3) Login
4) List users
q) Quit
4
List of registered users:
Username: admin
Key: BBOBBBRYWOWWGBRBRGWOYWORYWRWRYGYOGORYGYRYWOGOGWBGGOYRB

Username: q
Key: WWWWWWWWWGGGRRRBBBOOOGGGRRRBBBOOOGGGRRRBBBOOOYYYYYYYYY

You have the following options:
1) Public key service
2) Register
3) Login
4) List users
q) Quit
3
What user do you want to log in as?
admin
My public key is:
BBGOYGRYROWWGGGYWOYWYBGBYOGOBBRRORYWGOBWRRBRBOYORWGWWY

Please give me the result of:
mykey.handshake(yourkey, "1869af653f485762".from_hex().unwrap()).to_hex()
# solve.py BBGOYGRYROWWGGGYWOYWYBGBYOGOBBRRORYWGOBWRRBRBOYORWGWWY BBOBBBRYWOWWGBRBRGWOYWORYWRWRYGYOGORYGYRYWOGOGWBGGOYRB 1869af653f485762
0cc14fd977ae28c9c86bf484e128f02f
Your are now logged in!
Here is the flag: CTF{StickelsKeyExchangeByHand}