Challenge Description

SusCipher 400 pts (6 solves)

authored by rbtree

I made SusCipher, which is a vulnerable block cipher so everyone can break it!

Please, try it and find a key. nc suscipher.chal.ctf.acsc.asia 13579 nc suscipher-2.chal.ctf.acsc.asia 13579 (Backup) Hint: Differential cryptanalysis is useful. SusCipher.tar.gz

Source files

task.py

Source Analysis

Python132 lines / static highlight

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132

#!/usr/bin/env python3
import hashlib
import os
import signal


class SusCipher:
    S = [
        43,  8, 57, 53, 48, 39, 15, 61,
         7, 44, 33,  9, 19, 41,  3, 14,
        42, 51,  6,  2, 49, 28, 55, 31,
         0,  4, 30,  1, 59, 50, 35, 47,
        25, 16, 37, 27, 10, 54, 26, 58,
        62, 13, 18, 22, 21, 24, 12, 20,
        29, 38, 23, 32, 60, 34,  5, 11,
        45, 63, 40, 46, 52, 36, 17, 56
    ]

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

    ROUND = 3
    BLOCK_NUM = 8
    MASK = (1 << (6 * BLOCK_NUM)) - 1

    @classmethod
    def _divide(cls, v: int) -> list[int]:
        l: list[int] = []
        for _ in range(cls.BLOCK_NUM):
            l.append(v & 0b111111)
            v >>= 6
        return l[::-1]

    @staticmethod
    def _combine(block: list[int]) -> int:
        res = 0
        for v in block:
            res <<= 6
            res |= v
        return res

    @classmethod
    def _sub(cls, block: list[int]) -> list[int]:
        return [cls.S[v] for v in block]

    @classmethod
    def _perm(cls, block: list[int]) -> list[int]:
        bits = ""
        for b in block:
            bits += f"{b:06b}"

        buf = ["_" for _ in range(6 * cls.BLOCK_NUM)]
        for i in range(6 * cls.BLOCK_NUM):
            buf[cls.P[i]] = bits[i]

        permd = "".join(buf)
        return [int(permd[i : i + 6], 2) for i in range(0, 6 * cls.BLOCK_NUM, 6)]

    @staticmethod
    def _xor(a: list[int], b: list[int]) -> list[int]:
        return [x ^ y for x, y in zip(a, b)]

    def __init__(self, key: int):
        assert 0 <= key <= self.MASK

        keys = [key]
        for _ in range(self.ROUND):
            v = hashlib.sha256(str(keys[-1]).encode()).digest()
            v = int.from_bytes(v, "big") & self.MASK
            keys.append(v)

        self.subkeys = [self._divide(k) for k in keys]

    def encrypt(self, inp: int) -> int:
        block = self._divide(inp)

        block = self._xor(block, self.subkeys[0])
        for r in range(self.ROUND):
            block = self._sub(block)
            block = self._perm(block)
            block = self._xor(block, self.subkeys[r + 1])

        return self._combine(block)

    # TODO: Implement decryption
    def decrypt(self, inp: int) -> int:
        raise NotImplementedError()


def handler(_signum, _frame):
    print("Time out!")
    exit(0)


def main():
    signal.signal(signal.SIGALRM, handler)
    signal.alarm(300)
    key = int.from_bytes(os.urandom(6), "big")

    cipher = SusCipher(key)

    while True:
        inp = input("> ")

        try:
            l = [int(v.strip()) for v in inp.split(",")]
        except ValueError:
            print("Wrong input!")
            exit(0)

        if len(l) > 0x100:
            print("Long input!")
            exit(0)

        if len(l) == 1 and l[0] == key:
            with open('flag', 'r') as f:
                print(f.read())

        print(", ".join(str(cipher.encrypt(v)) for v in l))


if __name__ == "__main__":
    main()

Let’s take a look at the relevant parts

main

While True, it asks for an input which is a string of numbers separated by , As long as we input 0x100 or 256 numbers at a time, we can get as many encryptions as we like

If we only enter a single number, and if that number happens to be the secret round key, we can get the flag

Sounds easy? lets take a look into the cipher

The Cipher

The above construction is Substitution Permutation Network (SPN) which is essentially a repeated operation of substitution with a fixed predefined array
here which is

Python10 lines / static highlight

1 2 3 4 5 6 7 8 9 10

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

I.e a number n is replaced with S[n]

followed by a permutation of bits here defined by

Python10 lines / static highlight

1 2 3 4 5 6 7 8 9 10

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

Which means P[t]th bit of the output is actually the tth bit of inpute.g. P[0] = 21 means the 21th bit of output is 0th bit of input as is

followed by a xor operation with a secret key

This process is repeated a fixed number of rounds times with a new secret key each round (which are called the round keys or subkeys)

The encrypt function hence looks like as below

Python10 lines / static highlight

1 2 3 4 5 6 7 8 9 10

    def encrypt(self, inp: int) -> int:
        block = self._divide(inp)

        block = self._xor(block, self.subkeys[0])
        for r in range(self.ROUND):
            block = self._sub(block)
            block = self._perm(block)
            block = self._xor(block, self.subkeys[r + 1])

        return self._combine(block)

(_divide and _combine are just helper functions to make programmers life easier)

One might question, why are we _dividing a good enough input of 48 bits into 8 chunks of 6 bits each? Well, in an ideal world, we would like to have a substitution box of 48 bits, but that would eat up a whopping 2^48 number of entries (which we are somehow fooling with 2^6 entries here

Hence the functions _sub acts as if it sees 8 different values and substitutes them and acts as if it just did 48 bits of substitution

Python3 lines / static highlight

1 2 3

    @classmethod
    def _sub(cls, block: list[int]) -> list[int]:
        return [cls.S[v] for v in block]

So does _perm pretend (because of our design) that it sees a big block of 48 bits which it permutes to a block of 48 bits, but what it does is to take 8 blocks of 6 bits each and create 8 blocks of 6 bits each if they were all connected

Python12 lines / static highlight

1 2 3 4 5 6 7 8 9 10 11 12

    @classmethod
    def _perm(cls, block: list[int]) -> list[int]:
        bits = ""
        for b in block:
            bits += f"{b:06b}"

        buf = ["_" for _ in range(6 * cls.BLOCK_NUM)]
        for i in range(6 * cls.BLOCK_NUM):
            buf[cls.P[i]] = bits[i]

        permd = "".join(buf)
        return [int(permd[i : i + 6], 2) for i in range(0, 6 * cls.BLOCK_NUM, 6)]

Where do subkeys come from?

Python10 lines / static highlight

1 2 3 4 5 6 7 8 9 10

    def __init__(self, key: int):
        assert 0 <= key <= self.MASK

        keys = [key]
        for _ in range(self.ROUND):
            v = hashlib.sha256(str(keys[-1]).encode()).digest()
            v = int.from_bytes(v, "big") & self.MASK
            keys.append(v)

        self.subkeys = [self._divide(k) for k in keys]

As you may have observed from the init function, subkeys are “derived” from a single 48-bit key in a way that we cant recover subkey i from the knowledge of any of the subkeys j>i (to make the challenge hard so that we will definitely need to recover subkey[0] which is the original key

Vulnerability?

If you have seen some cipher constructions before, you may have observed, that the ROUND = 3 is really very low and 6-bit sboxes are still not as robust as you may imagine them to be.

Another hint as provided by the author is Differential Cryptanalysis, and since I am obsessed with SAT solvers, I will overlook the hint and cheeze it with z3

Modelling

While the general methodology to solve a problem with a SAT solver is to write the output as a (symbolic) function of the inputs, and finding an input which leads to the observed output.

So what’s the symbolic input and output here?

For an input inp to the SusCipher(key) producing an encryption out We can write out as symbolic_function(subkeys, inp)

With subkeys acting as unknown inp which we aim for, we can easily get the desired outcome.

Taking heavy inspiration from the implementaion of the challenge cipher, we can similary create the z3 model of suscipher

Python19 lines / static highlight

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class CrackSusCipher:
    ROUND = 3
    BLOCK_NUM = 8
    def _divide(self, v):
        l = []
        for _ in range(self.BLOCK_NUM):
            l.append(v&0b111111)
            v >>=6
        return l[::-1]

    def _combine(self, block):
        res = 0
        for v in block:
            res <<=6
            res |= v
        return res

    def _xor(self, a,b):
        return [x^y for x,y in zip(a,b)]

These functions look identical.

Modelling substitution

First hurdle most of the people face modelling a SPN network or any other cipher is to model substitution.
But z3 is equipped with powerful theories of arrays (and functions)

Thus to model substitution, we can define a symbolic function S, which takes 6-bit inputs and generates 6-bit outputs

Python1 line / static highlight

1

self.S = Function('S', BitVecSort(6), BitVecSort(6))

then self.S(i) would indeed be exactly what we desire
But wait, we just specified that S can be any function, not the exact substitution function we are provided with.
Worry not, we can specify this as a constraint to the solver

Python2 lines / static highlight

1 2

for i,v in enumerate(S): #original S as provided in the challenge
    self.solver.add(self.S(i)==v)

i.e we want S(0) to be nothing else than 43 and so on

And we treat keys as 6 bit unknowns, so there will be (ROUND+1)*8 variables.

Overall our init function will look like

Python6 lines / static highlight

1 2 3 4 5 6

    def __init__(self):
        self.S = Function('S', BitVecSort(6), BitVecSort(6))
        self.solver = Solver()
        for i,v in enumerate(S):
            self.solver.add(self.S(i)==v)
        self.keys = [[BitVec(f'k_{r}_{i}',6) for i in range(8) ] for r in range(self.ROUND+1)]

hence _sub function would be

Python2 lines / static highlight

1 2

    def _sub(self, block):
        return [self.S(simplify(i)) for i in block]

Note that it could have been self.S(i) instead of self.S(simplify(i)) which I used, just to simplify the expression (if possible) before substituting to hopefully speed things up

Modelling permutation

Now what about the permutation? We can model it exactly how we would have calculated a permutation Take the ith bit, put it P[i]th place in the output, just the way to deal with BitVectors vary

Python9 lines / static highlight

1 2 3 4 5 6 7 8 9

    def _perm(self, block):
        x = Concat(block)
        # treat the 8 6-bit vectors as a single 48 bit-vector 
        output = [0]*48 # temporary placeholder for output
        for i,v in enumerate(P):
            # extract the ith bit from the MSB put it at the correct place
            output[v] = Extract(47-i, 47-i, x)
        # rechunk in 6 bit bitvectors
        return [Concat(output[i:i+6]) for i in range(0,48,6)]

Modelling encryption

Finally after getting the required blocks to perform our symbolic encryption, we can model it

Python7 lines / static highlight

1 2 3 4 5 6 7

    def enc(self, block):
        block = self._xor(block, self.keys[0])
        for r in range(self.ROUND):
            block = self._sub(block)
            block = self._perm(block)
            block = self._xor(block, self.keys[r+1])
        return block

Which you can see is almost like the original except we are not _dividing and _combining the 48-bits but rather assume that it operates on 8 6-bit values. And self.keys here are the symbolic unknowns.

Checking if our model is correct

Now a CTF player will be anxious whether the efforts they put in to model the cipher were fruitful or did they mess up the model somewhere?

Worry not, we can always check our symbolic model by plugging in real values and comparing with the original cipher

We will use random values and keys just to check if they match (kinda funny that we have to informally verify a formal verifier XD)

Python16 lines / static highlight

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

print("verifying our modelling")
import random
for i in range(100):
    random_key = random.randint(0,2**48-1)
    sus = SusCipher(random_key)
    sus_model = crack()
    sus_model.solver.check() # to fill in the `S` as the original substitution function
    sus_model.keys = [[BitVecVal(i,6) for i in row] for row in sus.subkeys] # BitVecVal as a symbolic constant value
    for j in range(10):
        inp = random.randint(0,2**48-1)
        real_out = sus.encrypt(inp)
        sym_out_chunks = sus_model.enc(sus_model._divide(inp))
        # evaluating the symbolic output as per the symbolic model
        sym_out = sus_model.solver.model().eval(Concat(sym_out_chunks))
        assert sym_out.as_long() == real_out
print("success")

Adding input output points

Taking care of the _divide business, we will equate the 6-bit chunks of the output and our symbolic output for a given input

Python3 lines / static highlight

1 2 3

    def add_sample(self, inp, oup):
        for a,b in zip(self.enc(self._divide(inp)), self._divide(oup)):
            self.solver.add(a==b)

Getting the key

It’s really simple, just check if there is any satisfying model which would make our constraints possible, and get the first subkey according to that model

Python5 lines / static highlight

1 2 3 4 5

    def get(self):
        if self.solver.check()==sat:
            model = self.solver.model()
            k = [model.eval(i).as_long() for i in self.keys[0]]
            return self._combine(k)

Putting our class together

Python77 lines / static highlight

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

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

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

class crack:
    ROUND = 3
    BLOCK_NUM = 8
    def __init__(self):
        self.S = Function('S', BitVecSort(6), BitVecSort(6))
        self.solver = Solver()
        for i,v in enumerate(S):
            self.solver.add(self.S(i)==v)
        self.keys = [[BitVec(f'k_{r}_{i}',6) for i in range(8) ] for r in range(self.ROUND+1)]

    def _divide(self, v):
        l = []
        for _ in range(self.BLOCK_NUM):
            l.append(v&0b111111)
            v >>=6
        return l[::-1]

    def _combine(self, block):
        res = 0
        for v in block:
            res <<=6
            res |= v
        return res

    def _xor(self, a,b):
        return [x^y for x,y in zip(a,b)]

    def _perm(self, block):
        x = Concat(block)
        output = [0]*48
        for i,v in enumerate(P):
            output[v] = Extract(47-i, 47-i, x)
        return [Concat(output[i:i+6]) for i in range(0,48,6)]

    def _sub(self, block):
        return [self.S(simplify(i)) for i in block]

    def enc(self, block):
        block = self._xor(block, self.keys[0])
        for r in range(self.ROUND):
            block = self._sub(block)
            block = self._perm(block)
            block = self._xor(block, self.keys[r+1])
        return block

    def add_sample(self, inp, oup):
        for a,b in zip(self.enc(self._divide(inp)), self._divide(oup)):
            self.solver.add(a==b)

    def get(self):
        if self.solver.check()==sat:
            model = self.solver.model()
            k = [model.eval(i).as_long() for i in self.keys[0]]
            return self._combine(k)

So how many input-output pairs do we need to figure out the key uniquely?
I guess atmost 256?
Let’s try it out

Python7 lines / static highlight

1 2 3 4 5 6 7

c = crack()
for i in range(256):
    input = random.randint(0,2**48-1)
    output = server(input) #whatever
    c.add_sample(input, output)

key = c.get()

Hmmm, something’s not right, it seems to be stuck indefinitely.
We can get the intuition of difficulty of the solver to find key by reducing the number of constraints i.e the number of input output pairs.

By playing around, one quickly comes to the realisation that it wont workeven for 5 random samples and will time out >200s

Moment of inspiration

How about we address the difficulty of the solver (by addressing the difficulty of the problem being asked to solve)

When we take a random input-output pair, what we ask the solver for Substitution(key[i] ^ some_random)
But if it were just 0 instead of some_random, it would have to guess one less step.
So how about we make 7 out of 8 0 and only keep one key place active in substitution?.

This is really easy with input = (1<<i) for (0<=i<48)

And most importantly, it works!
(To an amazement that it works in around a second with 48 samples as opposed to ~5000 seconds for 5 random samples!)

Getting the flag

Python13 lines / static highlight

1 2 3 4 5 6 7 8 9 10 11 12 13

import pwn
HOST, PORT = "suscipher.chal.ctf.acsc.asia", 13579
REM = pwn.remote(HOST, PORT)

REM.sendline(",".join(str((1<<i)) for i in range(48)))
response = list(map(int,REM.recvline()[2:].strip().split(b', ')))
c = crack()
for i,v in enumerate(response):
    c.add_sample(1<<i,v)

key = c.get()
REM.sendline(str(key))
REM.interactive()

ACSC{There_may_be_a_better_solution_to_solve_this_but_I_used_diff_analysis_:(}

As expected, the author knew there might be other interesting ways like this one ;)

Get the Solve Script