Skip to content

Instantly share code, notes, and snippets.

@sasdf

sasdf/solve.cpp

Last active November 29, 2021 06:18
Show Gist options
  • Save sasdf/78fa4f4c9dc9db93534e4742b1de92e1 to your computer and use it in GitHub Desktop.
Save sasdf/78fa4f4c9dc9db93534e4742b1de92e1 to your computer and use it in GitHub Desktop.
Download ZIP
DragonCTF 2021 CRC Recursive Challenge
Raw
solve.cpp
// g++ -O3 solve.cpp -fopenmp && ./a.out
//
// Credits:
// Algorithm: @utaha1228
// Optimization: @sasdf
#include "table.h" // Generated by python3 solve.py
#include <omp.h>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
// defined in table.h
// #define N 16
#define SIZE (N * 4)
#define NTHREADS 10
class LinearBase {
public:
__uint128_t lb[SIZE][2];
LinearBase() {
memset(this->lb, 0, sizeof(this->lb));
};
void add_base(__uint128_t *x) {
__uint128_t num = x[0], mask = x[1];
for (int i=SIZE-1; i>=0; i--) {
if ((num >> i) & 1) {
if (this->lb[i][0] == 0 && this->lb[i][1] == 0) {
this->lb[i][0] = num;
this->lb[i][1] = mask;
break;
} else {
num ^= this->lb[i][0];
mask ^= this->lb[i][1];
}
}
}
}
__uint128_t get_base_rep(__uint128_t num) {
__uint128_t mask = 0;
for (int i=SIZE-1; i>=0; i--) {
if ((num >> i) & 1) {
if (this->lb[i][1] == 0) {
return -1;
}
num ^= this->lb[i][0];
mask ^= this->lb[i][1];
}
}
return mask;
}
};
void print128(__uint128_t x){
fprintf(stderr, "%016llx %016llx\n", (uint64_t)(x >> 64), (uint64_t)(x));
}
int main() {
LinearBase lbcache[NTHREADS][N+1];
bool cache_initialized[NTHREADS] = {0};
uint64_t total = 1ULL << N;
uint64_t report = total / 10000;
uint64_t progress = 0;
uint64_t local_progress[NTHREADS] = {0};
#pragma omp parallel for num_threads(NTHREADS)
for (uint64_t M=0; M<total; M++) {
int tidx = omp_get_thread_num();
local_progress[tidx] ++;
if (local_progress[tidx] == report) {
local_progress[tidx] = 0;
#pragma omp critical
{
progress += report;
fprintf(stderr, "%.2f\r", (double)progress * 100.0 / (double)total);
}
}
LinearBase LB;
int ii = 0;
if (cache_initialized[tidx]) {
int Mdiff = (M - 1) ^ M;
for (ii=0; ii<N; ii++) {
int j = N - 1 - ii;
if ((Mdiff >> j) & 1) { break; }
}
LB = lbcache[tidx][ii];
} else {
cache_initialized[tidx] = true;
}
for (int i=ii; i<N; i++) {
int j = N - 1 - i;
if ((M >> j) & 1) {
for (int z=0; z<4; z++) {
LB.add_base(numbers[i][z]);
}
} else {
for (int z=0; z<4; z++) {
LB.add_base(alphabets[i][z]);
}
}
lbcache[tidx][i+1] = LB;
}
__uint128_t orig_diff = diff_bias;
for (int i=0; i<N; i++) {
if ((M >> i) & 1) {
orig_diff ^= diffs[i];
}
}
__uint128_t res = LB.get_base_rep(orig_diff);
// print128(res);
if (res == -1) { continue; }
bool ok = true;
char buf[33];
memset(buf, 0, 33);
for (int i=0; i<N; i++) {
int j = N - 1 - i;
int d = (res >> (j * 4)) & 0xf;
if ((M >> i) & 1) {
if (d < 10) { buf[i] = '0' + d; }
else { ok = false; break; }
} else {
if (d == 4) { buf[i] = 'a'; }
else if (d == 2) { buf[i] = 'b'; }
else if (d == 14) { buf[i] = 'c'; }
else if (d == 1) { buf[i] = 'd'; }
else if (d == 5) { buf[i] = 'e'; }
else if (d == 3) { buf[i] = 'f'; }
else { ok = false; break; }
}
}
if (ok) {
fprintf(stderr, "\nanswer = %s\n", buf);
// print128(res);
}
}
fprintf(stderr, "\n");
return 0;
}
Raw
solve.py
#!/usr/bin/env python3
#
# Credits:
# Algorithm: @utaha1228
# Optimization: @sasdf
import sys
from tqdm import tqdm
N = 16 # 16 for warmup, 32 for hard
# Search range
start = 0
end = 1 << N
def crc128(buf, crc=0xffffffffffffffffffffffffffffffff):
for val in buf:
crc ^= val << 120
for _ in range(8):
crc <<= 1
if crc & 2**128:
crc ^= 0x14caa61b0d7fe5fa54189d46709eaba2d
return crc
def crc64(buf, crc=0xffffffffffffffff):
for val in buf:
crc ^= val << 56
for _ in range(8):
crc <<= 1
if crc & 2**64:
crc ^= 0x1ad93d23594c935a9
return crc
def getCrc(crc): # a string contains N hex character
assert len(crc) == N
assert all((x in '1234567890abcdef`\0') for x in crc)
if N == 16:
inp = f'My crc64 is 0x{crc}! Cool, isn\'t it?'.encode()
return crc64(inp)
else:
inp = f'My crc128 is 0x{crc}! Cool, isn\'t it?'.encode()
return crc128(inp)
def getDiff(crc):
return getCrc(crc) ^ int(crc.replace('`', '9'), 16)
class LinearBase:
def __init__(self):
self.SIZE = N * 4
self.lb = [(-1, -1)] * self.SIZE # (mat, aug)
def add_base(self, num, mask):
# Echelonize
for i in range(self.SIZE - 1, -1, -1):
if num & (1 << i):
if self.lb[i] == (-1, -1):
self.lb[i] = (num, mask)
break
else:
num ^= self.lb[i][0]
mask ^= self.lb[i][1]
def get_base_rep(self, num):
# Solve matrix
mask = 0
for i in range(self.SIZE - 1, -1, -1):
if num & (1 << i):
if self.lb[i] == (-1, -1):
return "RIP"
num ^= self.lb[i][0]
mask ^= self.lb[i][1]
return mask
def multByX(num):
num <<= 1
if N == 16:
if num & (1 << 64):
num ^= 0x1ad93d23594c935a9
else:
if num & (1 << 128):
num ^= 0x14caa61b0d7fe5fa54189d46709eaba2d
return num
def multByXn(num, n):
for _ in range(n):
num = multByX(num)
return num
def main():
# Precompute tables
# LHS
numbers = []
alphabets = []
for i in range(N):
# delta changes the variable from '0' to '0' ~ '9'
#
# ascii bin delta repr using basis below
# A B A-A0|B-B0 C
# 0: 0000 0000 0000|0000 0000
# 1: 0001 0001 0001|0001 0001
# 2: 0010 0010 0010|0010 0010
# 3: 0011 0011 0011|0011 0011
# 4: 0100 0100 0100|0100 0100
# 5: 0101 0101 0101|0101 0101
# 6: 0110 0110 0110|0110 0110
# 7: 0111 0111 0111|0111 0111
# 8: 1000 1000 1000|1000 1000
# 9: 1001 1001 1001|1001 1001
#
# base0 0001|0001 0001
# base1 0010|0010 0010
# base2 0100|0100 0100
# base3 1000|1000 1000
A = getCrc('0' * N) ^ getCrc(('1' + '0' * i).rjust(N, '0'))
B = (1 << (i * 4))
delta = A ^ B
tmp = []
for j in range(4):
tmp.append([delta, 1 << (i * 4 + j)])
delta = multByX(delta)
numbers.append(tmp)
for i in range(N):
# delta changes the variable from '`' to 'a' ~ 'f'
#
# ascii bin delta repr using basis below
# A B A-A`|B-B` C
# `: 000 001 000|000 0000
# a: 001 010 001|011 0100
# b: 010 011 010|010 0010
# c: 011 100 011|101 1110
# d: 100 101 100|100 0001
# e: 101 110 101|111 0101
# f: 110 111 110|110 0011
#
# base0 100|100 0001
# base1 010|010 0010
# base2 001|011 0100
# base3 000|100 1000
A = getCrc('`' * N) ^ getCrc('`' * (N - 1 - i) + 'a' + '`' * i)
B = (1 << (i * 4))
tmp = [
[multByXn(A, 2) ^ multByXn(B, 2), (1 << (i * 4 + 0))],
[multByXn(A, 1) ^ multByXn(B, 1), (1 << (i * 4 + 1))],
[A ^ B ^ multByXn(B, 1) , (1 << (i * 4 + 2))],
[multByXn(B, 2) , (1 << (i * 4 + 3))],
]
alphabets.append(tmp)
# RHS
diffs = []
diff_bias = getDiff('`' * N)
for i in range(N):
diffs.append(getDiff(('`' * i + '0').ljust(N, '`')) ^ diff_bias)
# Dump all tables for C++ impl
with open('table.h', 'w') as f:
f.write(f'#define N {N}\n')
f.write(f'const char* _numbers = (\n')
for a in numbers:
for b in a:
for x in b:
f.write(' "' + ''.join(f'\\x{d:02x}' for d in x.to_bytes(16, 'little')) + '"\n')
f.write(');\n')
f.write(f'__uint128_t (*__numbers)[{N}][4][2] = (__uint128_t(*)[{N}][4][2])_numbers;\n')
f.write(f'#define numbers (*__numbers)\n')
f.write(f'const char* _alphabets = (\n')
for a in alphabets:
for b in a:
for x in b:
f.write(' "' + ''.join(f'\\x{d:02x}' for d in x.to_bytes(16, 'little')) + '"\n')
f.write(');\n')
f.write(f'__uint128_t (*__alphabets)[{N}][4][2] = (__uint128_t(*)[{N}][4][2])_alphabets;\n')
f.write(f'#define alphabets (*__alphabets)\n')
f.write(f'const char* _diffs = (\n')
for x in diffs:
f.write(' "' + ''.join(f'\\x{d:02x}' for d in x.to_bytes(16, 'little')) + '"\n')
f.write(');\n')
f.write(f'__uint128_t (*__diffs)[{N}] = (__uint128_t(*)[{N}])_diffs;\n')
f.write(f'#define diffs (*__diffs)\n')
f.write(f'const char* _diff_bias = (\n')
x = diff_bias
f.write(' "' + ''.join(f'\\x{d:02x}' for d in x.to_bytes(16, 'little')) + '"\n')
f.write(');\n')
f.write(f'__uint128_t (*__diff_bias) = (__uint128_t*)_diff_bias;\n')
f.write(f'#define diff_bias (*__diff_bias)\n')
# Python impl
# Solve all possible 2^N basis combinations (i.e. numbers or alphabets)
lbcache = [] # Echelonize basis cache
for M in tqdm(range(start, end), desc='Solving'):
LB = LinearBase()
if len(lbcache) == 0:
lbcache, ii = [LB.lb[:]], 0
else:
# Find the first changed basis
Mdiff = (M - 1) ^ M
for ii in range(N):
j = N - 1 - ii
if Mdiff & (1 << j):
break
# Reuse previous echelonize basis
LB.lb = lbcache[ii][:]
lbcache = lbcache[:ii+1]
# Add basis and echelonize it
for i in range(ii, N):
j = N - 1 - i
if M & (1 << j):
for num, mask in numbers[i]:
LB.add_base(num, mask)
else:
for num, mask in alphabets[i]:
LB.add_base(num, mask)
lbcache.append(LB.lb[:])
# Prepare RHS
rhs = diff_bias
for i in range(N):
if M & (1 << i):
rhs ^= diffs[i]
# Solve the equations ( res @ LB == rhs )
res = LB.get_base_rep(rhs)
if res == 'RIP':
continue
# Mapping back to hex
ans = ''
for i in range(N):
j = N - 1 - i
d = (res >> (j * 4)) & 0xf
if M & (1 << i):
if d >= 10:
break
else:
ans += str(d)
else:
if d == 4:
ans += 'a'
elif d == 2:
ans += 'b'
elif d == 14:
ans += 'c'
elif d == 1:
ans += 'd'
elif d == 5:
ans += 'e'
elif d == 3:
ans += 'f'
else:
break
else:
print(ans)
# return
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment