Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/coll.py

Last active Jan 14, 2021
Embed
What would you like to do?
HXP CTF 2020 - Octothorpe (Crypto Hard)
'''
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())
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment