Source code
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
#!/usr/bin/env dart
import 'dart:convert';
import 'dart:io';
// NOTE: calculate and randomize functions are private (i.e., you don't have access).
import 'package:ctf_story/private.dart' show calculate, randomize;
int main(List<String> arguments) {
final flag = File('flag.txt').readAsStringSync();
print('Hello! Please tell me a fairy tale!');
var line = stdin.readLineSync(encoding: utf8);
if (utf8.encode(line).where((i) => i < 32 || i >= 128).isNotEmpty) {
print('There are unprintable characters in your story.');
return 0;
}
final firstText = line.toLowerCase();
var crcValues = calculate(utf8.encode(line));
print('The CRC values of your text are $crcValues.');
List<String> expectedValues;
do {
expectedValues = randomize(utf8.encode(line));
} while (expectedValues == crcValues);
if (expectedValues == null) {
print('Your story is too short. Bye!');
return 0;
}
print('But I am looking for a story of $expectedValues.');
line = stdin.readLineSync(encoding: utf8);
final secondText = line.toLowerCase();
crcValues = calculate(utf8.encode(line));
if (firstText != secondText) {
print('Perhaps you would like to start from scratch? Bye!');
return 0;
}
if (List.generate(
expectedValues.length, (i) => crcValues[i] == expectedValues[i])
.indexOf(false) <
0) {
print('What a lovely story! Your flag is ${flag}');
}
print('Bye!');
return 0;
}
Solution
Input
The first problem we encoutered was that both the calculate and randomize functions are made private so we have no idea what kind of input they are looking for nor what they return and how they return it. After some trial and error we realized that for the input to progress we need to send a string of 256-bytes minimum to see what story the program was looking for.
Reading the source code
While reading the source code, we see the following line:
1
2
var crcValues = calculate(utf8.encode(line));
print('The CRC values of your text are $crcValues.');
From that we can assume that the calculate function calculates CRC values for the input string although we aren’t sure how. One thing to know about CRC is that it is a homomorphic function under XOR. This means that:
With that knowledge, even though we can’t reverse the calculate function to find exactly what the target string would be, we can instead transform this into a lattice problem.
The Lattice Problem
Taking inspiration from one of LiveOverflow’s videos, we found our inspiration and transformed the problem into a lattice problem. A Lattice is a subgroup of a certain problem space generated by a basis of said space. I won’t go over the math required but if you need more check the cryptobook gitbook page on lattices (great read for anything crypto).
Here the space we are working with is the CRC values and their corresponding offsets. Same as in the video, we will be working under GF(2). Working from a base string (it can be anything as long as you keep it constant within your code), we can generate new random strings, get their CRC according to the server and XOR it with the base’s CRC to get the CRC of the both strings XORed using the previous proprety of CRC.
Once we have enough vectors to form a basis of the problem space (in this case 94 vectors), we can build the matrix of all these vectors that will allow us to solve linear equations of the form:
\[A \overrightarrow{x} = B\]where x is the vector that represents all the offsets needed to XOR to the base in order to get to the target B vector and A is our matrix representing the basis of the problem space. In this case, if x_i (the ith coordinate of x) is 1 we XOR the corresponding offset to the base otherwise we do nothing.
Now the last issue is What is the "goal" we want to get to with this lattice? Originaly we thought that we just needed to pass the target CRC values and solve this set of linear eqution. Going back a step, we realized that this wouldn’t work and instead we needed to target the difference between the base and the target.
Solve code
Putting everything together, we threw everything into SAGEMATH so that it would solve the linear equation. To make our testing phase easier, we also pickled the basis once we created it so we wouldn’t have to create it at each iteration of our testing phase.
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
import random
import os
import pickle
from string import ascii_lowercase
from bitarray import bitarray
from pwn import *
F = GF(2)
BASE = ''.join([random.choice(ascii_lowercase) for _ in range(256)]).encode('utf-8')
print(BASE)
# context.log_level = 'debug'
def get_crc(data):
conn = remote('story.2021.ctfcompetition.com', 1337)
conn.recvuntil(b'!\n')
conn.sendline(data)
reply = conn.recvuntil('.\n')
vals = b''.join([bytes.fromhex(v.decode('utf-8'))
for v in reply.split(b'[')[1].split(b']')[0].split(b',')])
return vals
def get_goal(data):
conn = remote('story.2021.ctfcompetition.com', 1337)
conn.recvuntil(b'!\n')
conn.sendline(data)
conn.recvuntil(b'.\n')
reply = conn.recvuntil('.\n')
vals = b''.join([bytes.fromhex(v.decode('utf-8'))
for v in reply.split(b'[')[1].split(b']')[0].split(b',')])
return vals, conn
offsets = []
crcs = []
if not os.path.isfile('basis.p'):
while len(offsets) < 112:
base_crc = get_crc(BASE)
random_offset = bytes([randint(0, 1) * 0x20 for _ in range(256)])
random_crc = xor(get_crc(xor(BASE, random_offset)), base_crc)
random_crc_array = bitarray()
random_crc_array.frombytes(random_crc)
random_crc_vec = random_crc_array.tolist()
print(len(random_crc_vec))
m = matrix(F, crcs + [random_crc_vec]).transpose()
print(m.rank())
if m.rank() > len(crcs):
offsets.append(random_offset)
crcs.append(random_crc_vec)
with open('basis.p', 'wb') as f:
pickle.dump((offsets, crcs), f)
else:
with open('basis.p', 'rb') as f:
offsets, crcs = pickle.load(f)
# Start to solve here.
m = matrix(F, crcs).transpose()
print(m.nrows(), m.ncols())
goal, conn = get_goal(BASE)
base_crc_array = bitarray()
base_crc_array.frombytes(get_crc(BASE))
base_crc_vec = vector(F, base_crc_array.tolist())
target_crc_array = bitarray()
target_crc_array.frombytes(goal)
target_crc_vec = vector(F, target_crc_array.tolist())
diff = target_crc_vec - base_crc_vec
print(len(diff))
solved = m.solve_right(diff)
target = BASE
for t, c in zip(solved, offsets):
if t:
target = xor(target, c)
conn.sendline(target)
print(conn.recvuntil(b'\n'))
FLAG: CTF{eb64749d08bd99b681f2bc75aa65eab35a80310f7426f6872ba869d244e37135}
References:
- https://www.youtube.com/watch?v=EOlddNofKxo
- https://en.wikipedia.org/wiki/Cyclic_redundancy_check
- https://cryptohack.gitbook.io/cryptobook/