Intro
There are a total of 12 crypto problems in this CTF, and I solved all of them except 'fried_rice'. I'm going to breifly explain the easier ones, and provide detailed solutions and scripts to the harder ones. The problems are ordered by the number of solves.
Babies
fibinary
Skipped.
4096
It's an RSA with \(N\) being the products of multiple 32-bit primes. We can factorize \(N\) by those powerful tools (or even just bruteforce and let the program run for 1.5 hours, which my teammate did) and solve the challenge.
dividing_secrets
The arithmetic operations here are under \(Z/pZ\), and the \(p\) is known. We are given \(g\) and \(g^{flag}\). We can input at most 64 \(div\), and it tells us \(g^{\lfloor \frac{flag}{div} \rfloor}\).
We can calculate \(\left(g^{flag}\right)\left(g^{\lfloor \frac{flag}{div} \rfloor}\right)^{-div} = g^{flag \bmod div}\), if the chosen \(div\) is small enough, we can bruteforce the discrete log, meaning we can retreive the value of \(flag \% div\). Choosing \(div\)s to be distinct 20-bit primes (10-bit is probably enough), we can perform CRT to recover the flag.
supercomputer
This problem is pretty much testing if people know Lifting the Exponent. In this case, since \(n = rp^q\) \[v_p(a_1^n + (n - a_1) ^ n) = v_p(a_0 + (n - a_1)) + v_p(n) = 2q\] with an exception of \(p \mid a_1\), which is really unlikely to happen.
babyrsa
It's a classic coppersmith. Recommend reading (4.2.2 ~ 4.2.4 for this specific challenge).
babypad
Classic padding oracle.
babyrand
Given \(p\), \(x < p\), we have to recover \(a\) and \(b\) by \((ax+b) \bmod p\), where \(a\) and \(b\) are both an approximation of \(p \oplus x\), formally, \(|a - (p \oplus x)| < 2^{200}\) while \(p\) is a 512-bit prime (and \(x\) is randomly chosen).
Let \(a' = a - (p \oplus x)\) and \(b' = b - (p\oplus x)\), by some math, we can get \((a'x+b') \bmod p\) from \((ax+b) \bmod p\). Now transform this into a closest vector problem (CVP): consider the lattice \[\begin{pmatrix} x & 1 \\ p & 1 \\ \end{pmatrix}\] and find the closest vector to \((a'x+b \bmod p, 0)\). Multiply the first row by \(a\), and subtract by the second row multiplied by \(\lfloor \frac{ax}{p} \rfloor\) should be really close, so we can recover \(a\) and \(b\) by solving the CVP. (Be aware that multiply the second row by \(\lceil \frac{ax}{p} \rceil\) is also a possibility, but can be handled in a similar way)
bank
We can measure and apply some gates to control the qubit to the place we want (no matter where the initial position is). Combining it with powerful 'verify' operation, we can check if the bill is a '0' by moving the qubit to '0' and measure. We believe that it is a '0' if it is verified 10 times in a row. Similarly, apply this to '1', '+', and '-'. Therefore, we can recover the bill.
leave_it_to_chance
The arithmetic operations here are under \(Z/pZ\), and the \(p = 4k + 1\) is known. Let the root of \(p \mid x^4 - 1\) be \(\pm 1,\pm a\). The problem provides a signing oracle, where the signature of \(x\) is \(f(x)^4\) and \(f\) is a polynomial with degree \(31\). As there are four possible \(f(x)\), while signing, we also get hints that two out of the 4 possible value is not the actual \(f(x)\) (these two numbers are chosen randomly among the three fake ones).
First, notice that \(f(x)^4\) is also a polynomial, but with degree \(124\), so we can ask for \(124\) signatures and get \(f(x)^4\) with Guassian elimination. Then square root \(f(x)^4\) twice to get a possible \(f(x)\). To square root a polynomial, we need tonelli-shank to get the first coefficient, and the rest is simple math. After getting the possible \(f(x)\), the other 3 possibilities are \(-f(x)\), \(af(x)\), \(-af(x)\). We can use the hints to eliminate the fake ones, until only one is left.
Credits to nakov for the tonelli-shank implementation 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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196from pwn import *
r = remote('crypto.be.ax', 6001)
r.recvuntil(b'p = ')
global p
p = int(r.recvline().decode('ascii'))
debug = []
matrix = []
magic = 125
for t in range(magic + 1):
coe = [pow(t, i, p) for i in range(magic)]
r.recvuntil(b'Choice>')
r.sendline(b'1')
r.sendline(hex(t)[2:])
r.recvuntil(b'Signature: ')
coe.append(int(r.recvline().decode('ascii'), 16))
r.sendline(b'0')
if t < magic: matrix.append(coe[:])
debug.append(coe[:])
print("Guassian Elimination")
assert len(matrix) == magic
for i in range(magic):
if matrix[i][i] == 0:
for j in range(i + 1, magic):
if matrix[j][i] != 0:
matrix[i], matrix[j] = matrix[j], matrix[i]
break
inv = pow(matrix[i][i], -1, p)
for j in range(magic + 1):
matrix[i][j] = matrix[i][j] * inv % p
assert matrix[i][i] == 1
for j in range(i + 1, magic):
coe = matrix[j][i]
for k in range(magic + 1):
matrix[j][k] = (matrix[j][k] - coe * matrix[i][k]) % p
assert matrix[j][i] == 0
for i in range(magic - 1, -1, -1):
for j in range(i):
coe = matrix[j][i]
for k in range(magic + 1):
matrix[j][k] = (matrix[j][k] - coe * matrix[i][k]) % p
poly = [matrix[i][-1] for i in range(magic)]
for i in range(magic + 1):
s = sum(x * y for x, y in zip(debug[i], poly)) % p
assert s == debug[i][-1], f"{i}"
print("square root the poly")
def modular_sqrt(a, p):
def legendre_symbol(a, p):
""" Compute the Legendre symbol a|p using
Euler's criterion. p is a prime, a is
relatively prime to p (if p divides
a, then a|p = 0)
Returns 1 if a has a square root modulo
p, -1 otherwise.
"""
ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls
""" Find a quadratic residue (mod p) of 'a'. p
must be an odd prime.
Solve the congruence of the form:
x^2 = a (mod p)
And returns x. Note that p - x is also a root.
0 is returned is no square root exists for
these a and p.
The Tonelli-Shanks algorithm is used (except
for some simple cases in which the solution
is known from an identity). This algorithm
runs in polynomial time (unless the
generalized Riemann hypothesis is false).
"""
# Simple cases
#
if legendre_symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return p
elif p % 4 == 3:
return pow(a, (p + 1) // 4, p)
# Partition p-1 to s * 2^e for an odd s (i.e.
# reduce all the powers of 2 from p-1)
#
s = p - 1
e = 0
while s % 2 == 0:
s //= 2
e += 1
# Find some 'n' with a legendre symbol n|p = -1.
# Shouldn't take long.
#
n = 2
while legendre_symbol(n, p) != -1:
n += 1
# Here be dragons!
# Read the paper "Square roots from 1; 24, 51,
# 10 to Dan Shanks" by Ezra Brown for more
# information
#
# x is a guess of the square root that gets better
# with each iteration.
# b is the "fudge factor" - by how much we're off
# with the guess. The invariant x^2 = ab (mod p)
# is maintained throughout the loop.
# g is used for successive powers of n to update
# both a and b
# r is the exponent - decreases with each update
#
x = pow(a, (s + 1) // 2, p)
b = pow(a, s, p)
g = pow(n, s, p)
r = e
while True:
t = b
m = 0
for m in range(r):
if t == 1:
break
t = pow(t, 2, p)
if m == 0:
return x
gs = pow(g, 2 ** (r - m - 1), p)
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m
def poly_square_root(poly):
ret = [modular_sqrt(poly[0], p)]
deg = (len(poly) - 1) // 2
for i in range(1, deg + 1):
cur = poly[i]
for j in range(1, i):
cur -= ret[j] * ret[i - j]
cur %= p
cur = cur * pow(2 * ret[0], -1, p) % p
ret.append(cur)
return ret
poly = poly_square_root(poly)
poly = poly_square_root(poly)
a = modular_sqrt(p - 1, p)
print('time to find the actual poly')
possible = [1, -1 % p, a, -a % p]
message = 8787
while len(possible) > 1:
r.recvuntil(b'Choice>')
r.sendline(b'1')
r.sendline(hex(message)[2:])
r.sendline(b'0')
r.recvuntil(b'Hints: ')
hints = r.recvline().split(b' ')
# print(f"debug: {hints}")
hints = [int(x.decode('ascii')) for x in hints]
my_guess = sum(pow(message, i, p) * x for i, x in enumerate(poly)) % p
hints = [x * pow(my_guess, -1, p) % p for x in hints]
if hints[0] in possible:
possible.remove(hints[0])
if hints[1] in possible:
possible.remove(hints[1])
message += 1
print('actual poly found')
for i in range(len(poly)):
poly[i] = (poly[i] * possible[0]) % p
r.recvuntil(b'Choice> ')
r.sendline(b'3')
r.recvuntil(b'space-separated numbers> ')
r.sendline(' '.join([str(x) for x in poly]))
print(r.recvline())
Non-Babies
LCG-k
We are given a typical signing oracle, but the \(k\) is generated by LCG with coefficient \(a\) and \(b\). We are allowed to sign 4 messages, and have to find the private key.
Let's say we sign 4 messages \(m_1\), \(m_2\), \(m_3\), and \(m_4\), we have
\[s_i = \frac{1}{k_i}(H(m_i) + dr_i)\]
and
\[k_2 = ak_1 + b, k_3 = a(ak_1+b) + b, k_4 = a(a(ak_1+b) + b) + b\]
The unknowns are \(a\), \(b\), \(k\), and \(d\). As we have 4 equations, we really have the chance to solve it! First we move the terms a little bit
\[k_i = \frac{H(m_i) + dr_i}{s_i}\]
the idea is that \(k_i\) is the LCG output, so it's better to not put it in denominator. Also, the right hand side has only an unknown \(d\). Now we have
\[k_{i + 1} - k_{i} = \frac{H(m_{i + 1}) + dr_{i+1}}{s_{i+1}} - \frac{H(m_i) + dr_i}{s_i}\]
No matter how ugly the right hand side looks, it is just \(\alpha d + \beta\) for some constant \(\alpha\) and \(\beta\). The reason we do this is because for the left hand side, we have
\[\frac{k_{i + 1} - k_i}{k_i - k_{i - 1}} = a\]
by the idea that \(k\) is exponentially growing regardless of \(b\). Therefore, by
\[\frac{k_4 - k_3}{k_3 - k_2} = \frac{k_3 - k_2}{k_2 - k_1}\]
or
\[(k_3 - k_2) ^ 2 = (k_4 - k_3)(k_2 - k_1)\]
We derived a quadratic equation for \(d\). As the modulo is a prime number, we can solve the equation with tonelli-shank.
mystery_stream
In this problem, we need to decrypt ciphertext that is encrypted by a LFSR stream cipher (the problem use GF(256) instead of xor, but it is not really important). The key generation process hinted that the output of LFSR is periodic, though the period is unknown. This reminds me of Vignere Cipher, but the period can be big, and the trick mentioned in cryptopals probably won't work (after solving, it turned out that bruteforce the period is do-able), so here we made some observation based on generating function.
Let the output bits of LFSR be \(b_0, b_1, \cdots, b_n, \cdots\). Consider the polynomial (the coefficient is in \(GF(2)\) so \(-x\) is the same as \(x\))
\[b_0 + b_1x + b_2x^2 + c\dots = \frac{g(x)}{f(x)}\]
where \(f(x)\) is the LFSR polynomial. To find the period \(t\), it must satisfy
\[\frac{g(x)}{f(x)} = \frac{h(x)}{1 + x^t}\]
so we can factorize \(f(x)\) and looks for the suitable \(t\). It turned out that \(t = 255\) and \(gcd(f(x), 1 + x^{255}) = x^8 + \cdots\). Therefore, \(g(x)\) needs to cancel out all other \(f(x)\) factors other than \(x^8 + \cdot\). Now we know that \(g(x)\) has a degree-56 factor (\(f\) has degree 64), as \(g(x)\) has degree at most 63, there's only 256 possible \(g(x)\). A \(g(x)\) means a key, after bruteforcing the key, we can recover the plaintext.