HXP CTF 2020 - Octothorpe (Crypto Hard)

coll.py

'''
The idea is to reach a state consisting of 00 and FF bytes.
Because of the independence of shifts values, if the message block is the same 32-byte part repeated 2 times,
the state is preserved. We then can change the 32 byte part arbitrarily and keep the hash value unchanged.

To do this we first craft a 32x2 message block that lands on such state after 2nd round (1st round does nothing).
We have 32 bytes of freedom (-charset constraints), so this is reasonable and can be done with 1 byte guess and propagation.

One caveat is that the initial state is rather symmetric and and it's not always easy to land on a desired state,
so we prepend random block first to randomize the state.

$ time pypy3 coll.py
init b'96b51b030a5685a42a1a2df5a805e1248cc4960258fede157379983c69b623a3'
state acba0a20c2036c12dd6d566d29329287
precomp
GOOD1! [65, 0, 114, 57, 66, 73, 87, 98, 71, 103, 119, 113, 48, 85, 110, 80, 89, 0, 85, 82, 69, 116, 84, 106, 70, 112, 69, 79, 107, 109, 50, 81]
GOOD2! [87, 50, 0, 100, 77, 54, 101, 88, 117, 74, 84, 100, 66, 104, 53, 114, 101, 65, 0, 90, 82, 78, 116, 113, 86, 101, 119, 82, 49, 115, 120, 100]
data1 = b'96b51b030a5685a42a1a2df5a805e1248cc4960258fede157379983c69b623a3A2rdB6WXGJwd0hnrYAUZENTqFeERks2dA2rdB6WXGJwd0hnrYAUZENTqFeERks2d&cmd=ls&a=bbbbbbCCCCDDDDCCCCDDDD&cmd=ls&a=bbbbbbCCCCDDDDCCCCDDDD'
data2 = b'96b51b030a5685a42a1a2df5a805e1248cc4960258fede157379983c69b623a3A2rdB6WXGJwd0hnrYAUZENTqFeERks2dA2rdB6WXGJwd0hnrYAUZENTqFeERks2d&cmd=cat%20/fla*&something=12345&cmd=cat%20/fla*&something=12345'
52da1cafb679c3b87ad0ed187fe8f895
52da1cafb679c3b87ad0ed187fe8f895

real    0m0.213s
user    0m0.173s
sys 0m0.040s
'''

import os
import string
from random import choice
from collections import defaultdict

from octothorpe import rol, ror, octothorpe, sbox, shift

def solve(off):
    block = [0] * 32
    while True:
        block[off] = choice(ALLOWED)
        block[off+16] = choice(ALLOWED)
        for j in range(off+1,off+16):
            j %= 16
            jprev = (j-1) % 16
            jnext = (j+1) % 16

            v = state[j]
            b1, b2 = block[jprev], block[jprev + 16]
            for k in range(4):
                b = [b1, b2][k & 1]
                jj = jprev + k*16
                v ^= sbox[b ^ ror(state[jprev], shift[jj], 8)]

            target = min(v, v ^ 0xff)
            if not precomp[jnext][target]:
                break
            block[jnext], block[jnext+16] = choice(precomp[jnext][target])
        else:
            res = forward(state, block*2)
            if all(v in (0, 0xff) for v in res[off^1::2]):
                return block

def forward(x0, block):
    x = list(x0)
    for j in range(16):
        jprev = (j-1) % 16
        jnext = (j+1) % 16
        for k in range(4):
            i = jj = j + k*16
            x[jprev] ^= sbox[block[i] ^ rol(x0[j], shift[jj], 8)]
            x[jnext] ^= sbox[block[i] ^ ror(x0[j], shift[jj], 8)]
    return x


ALLOWED = list((string.ascii_letters + string.digits).encode())

# initial state is weird, too much symmetries to dig out what we want
#state = bytes(octothorpe.initial_state)

# so compress random block first to randomize
init = os.urandom(32).hex().encode()
print("init", init)
o = octothorpe()
o.update(init)
state = bytes(o._state)

print("state", state.hex())

# precompute solutions for each position, targeting any particular value
print("precomp")
precomp = [[[] for _ in range(128)] for _ in range(16)]
for jnext in range(16):
    for b1 in ALLOWED:
        for b2 in ALLOWED:
            val = 0
            for k in range(4):
                b = [b1, b2][k & 1]
                jj = jnext + k*16
                val ^= sbox[b ^ rol(state[jnext], shift[jj], 8)]
            val = min(val, val ^ 0xff)
            precomp[jnext][val].append((b1, b2))

sol1 = solve(0)
print("GOOD1!", sol1)

sol2 = solve(1)
print("GOOD2!", sol2)

sol = [sol1[i] if i % 2 == 0 else sol2[i] for i in range(32)]
sol = bytes(sol)

data1 = init + sol * 2 + b"&cmd=ls&a=bbbbbbCCCCDDDDCCCCDDDD" * 2
data2 = init + sol * 2 + b"&cmd=cat%20/fla*&something=12345" * 2
print("data1 =", data1)
print("data2 =", data2)
print(octothorpe(data1).hexdigest())
print(octothorpe(data2).hexdigest())

octothorpe.py

import math

rol = lambda value, shift, size: ((value << (shift % size)) | (value >> (size - (shift % size)))) & ((1 << size) - 1)
ror = lambda value, shift, size: ((value >> (shift % size)) | (value << (size - (shift % size)))) & ((1 << size) - 1)

class octothorpe:
    digest_size = 16
    block_size = 64
    name = "octothorpe"

    state_size = 16
    shift_count = 64
    round_count = 20
    initial_state = bytearray.fromhex('00112233445566778899aabbccddeeff')

    function = lambda i: math.cos(i ** 3)
    sbox = sorted(range(256), key=function)
    shift = [int(8 * s) % 8 for s in map(function, range(shift_count))]

    new = classmethod(lambda cls, data: cls(data))
    copy = lambda self: octothorpe(_cache=self._cache[:], _length=self._length, _state=self._state[:])
    digest = lambda self: bytes(self._finalize())
    hexdigest = lambda self: self.digest().hex()

    def __init__(self, data: bytes = None, *, _cache: bytes = None, _length: int = None, _state: bytearray = None) -> None:
        self._cache = _cache or b''
        self._length = _length or 0
        self._state = _state or self.initial_state[:]
        assert len(self._state) == self.state_size, 'Invalid state size'
        if data:
            self.update(data)

    def update(self, data: bytes) -> None:
        self._cache += data
        while len(self._cache) >= self.block_size:
            block, self._cache = self._cache[:self.block_size], self._cache[self.block_size:]
            self._compress(block)
            self._length += self.block_size

    def _finalize(self) -> bytearray:
        clone = self.copy()
        clone._length += len(clone._cache)
        clone.update(b'\x80' + b'\x00' * ((self.block_size - 9 - clone._length) % self.block_size) + (8 * clone._length).to_bytes(8, 'little'))
        return clone._state

    def _compress(self, block: bytes) -> None:
        prev_state = lambda index: (index - 1) % self.state_size
        next_state = lambda index: (index + 1) % self.state_size
        for r in range(self.round_count):
            state = self._state[:]
            js = []
            jjs = []
            for i in range(self.block_size):
                j, jj = (i * r) % self.state_size, (i * r) % self.shift_count
                js.append(j)
                self._state[prev_state(j)] ^= self.sbox[block[i] ^ rol(state[j], self.shift[jj], 8)]
                self._state[next_state(j)] ^= self.sbox[block[i] ^ ror(state[j], self.shift[jj], 8)]

sbox = octothorpe.sbox
shift = octothorpe.shift