We are given some CRT reminders modulo primes of a secret number, together with some fake values. To recover the number, for small instances a simple brute-force solution is enough; for the easy larger instance we can do that using the Coppersmith Method, which however fails for the harder one.
Event Link: DeadSec CTF
Step 1 - Brute-force
The first wave of challenges included two related problems, Loud and Really Loud. Both these two challenges admit a simple (unintended) solution, using the Chinese Reminder Theorem only a few times. However, this solution gives some insights for the next one. Let’s focus on Loud, since the same solution applies directly to Really Loud. We are given this sage code:
1
2
3
4
5
6
7
8
9
10
11
12
B = 2^2048
flag = randint(1, B) # recover this value, wrap the answer in Dead{}
m = 5
n = 30
ps = [getStrongPrime(1024) for _ in range(n)]
S = [[randint(0, ps[i] - 1) for __ in range(m - 1)] + [int(flag % ps[i])] for i in range(n)]
for Si in S:
random.shuffle(Si)
print(ps)
print(S)
together with its output, the two lists ps and S. We see that flag is a 2048 bit random number. ps contains $30$ random 1024-bit prime numbers, and S $30$ lists of $5$ numbers each: 4 of those are just random numbers, while the last one is flag % ps[i]. Since the lists are shuffled at random, we do not know which number is the good one.
This can be solved easily in many ways. The most useful for later is the following. We know that $flag < 2^{2048}$, and expect every $p \in ps$ to be $\sim 2^{1024}$. If we apply the CRT to a tuple of three numbers coming from the first three lists in S, we know that the solution must be unique, and because of the size of the $p_i$ we expect this solution to be $\sim 2^{1024 \cdot 3} = 2^{3072}$. This will likely be true for all random solutions. However, the correct solution, i.e. the value of flag, will be lower than $2^{2048}$ by definition. If we add more (correct) reminders to the correct solution, those will just be satified; this won’t be true for random tuples. This idea is similar to the Broadcast Attack on RSA, for instance.
What we can do is to run a simple script to check all the 3-tuples coming from the first three sets, an check for numbers $<2^{2048}$:
1
2
3
4
5
6
7
8
from sage.all import *
for s in S[0]:
for t in S[1]:
for u in S[2]:
g = CRT([s,t,u], ps[:3])
if g <= 2**2048:
print(f'Hit: {g}')
This quickly solves both Loud and Really Loud. Notice that we only have to compute $5^3 = 125$ CRTs ($1000$ for Really Loud).
Step 2 - Coppersmith Method
This solution is very simple and fast, and hence came out quickly during the challenge. However, the authors said this was unintended, and hence released a second version of the challenges fixing this problem: Loud Revenge and Really Loud Revenge. They only changed the parameters $m$ and $n$ and the bitlength of the numbers. Here is the code for Loud Revenge:
1
2
3
4
5
6
7
8
9
10
11
12
B = 2^4096
flag = randint(1, B) # recover this value, wrap the answer in Dead{}
m = 4
n = 256
ps = [getPrime(128) for _ in range(n)]
S = [[randint(0, ps[i] - 1) for __ in range(m - 1)] + [int(flag % ps[i])] for i in range(n)]
for Si in S:
random.shuffle(Si)
print(ps)
print(S)
As you can see, now we need $32$ 128-bit primes to get to the size of B. The brute-force solution of above would need to compute $4^{32}$ CRTs, which is not feasible.
An unintended solution to those two was found as well, probably involving some random seed cracking, and a third version, LLLoud and LLLoud 2, was released. This version had no substantial difference in the code, except that randint was replaced by a cryptographically secure version of random. However, the name gives us a big hint towards the Lenstra-Lenstra-Lovasz (LLL) algorithm. This algorithm is widely used in cryptography and cryptanalysis when you want to recover information from some partial data. The easiest way to apply LLL to these kind of problems is usually the Copppersmith Method.
The Coppersmith Method is a method to find small integer zeroes of (monic) polynomials modulo a given integer (see for instance wikipedia or this article). More specifically, let
\[F(x) = x^d + a_{d-1}x^{d-1} + \dots + a_1 x + a_0\]be a degree $d$ polynomial. Given a module $N$ and a bound $X$ such that $X \leq 0.5 N^{1/d}$, the Coppersmith Method efficiently recovers all the solutions $x_i \leq X$ such that $F(x_i) \equiv 0 \mod N$.
All we need is to define the right polynomial. Here the observation we made before to build the brute-force solution comes in our help. Let $P = \prod p_i \sim 2^{32768}$ be the product of all the $256$ $p_i$’s. If we define a polynomial that has as zeros all the possible combinations obtained via CRT with all possible reminders we are given, this polynomial will have many very big solution $\mod P$ (of the order of magnitude of $P$ itself), but also a small solution, namely $flag \leq 2^{4096}$. This polynomial is easy to build: for each set $S_i$, we compute
\[f_i = (x-s_1)(x-s_2)(x-s_3)(x-s_4) \mod p_i,\]where $s_1,s_2,s_3,s_4$ are the four elements of $S_i$. We can then obtain the desired polynomial $f$ by taking the CRT of all $f_i$ modulo the $p_i$. In this way, we have $N=P \sim 2^{32768}$, $X=2^{4096}$ and $d=4$. Since $0.5N^{1/4} \sim 2^{8192}$ we can apply the Coppersmith Method. Luckily, this is already implemented in sage with the function small_roots, so we don’t need to worry about that. The final code is:
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
from sage.all import *
# Input values
ps = ...
S = ...
# Lists for the coefficients of fi
c0, c1, c2, c3, c4 = [], [], [], [], []
for i in range(len(S)):
Ki = Zmod(ps[i])
P = PolynomialRing(Ki, implementation='NTL', names=('x',));
(x,) = P._first_ngens(1)
# For each i compute fi
x1,x2,x3,x4 = S[i]
fi = (x - x1)*(x - x2)*(x - x3)*(x - x4)
n0, n1, n2, n3, n4 = fi.int_list()
c0.append(n0); c1.append(n1); c2.append(n2); c3.append(n3); c4.append(n4);
print('CRT')
# Coefficients of the final f
c0 = CRT(c0, ps); c1 = CRT(c1, ps); c2 = CRT(c2, ps); c3 = CRT(c3, ps); c4 = CRT(c4, ps);
P = product(ps)
K = Zmod(P)
R = PolynomialRing(K, implementation='NTL', names=('x',));
(x,) = R._first_ngens(1)
f = c0 + c1*x + c2*x**2 + c3*x**3 + c4*x**4
print(f'Computing Small roots')
B = 2**4096
s_roots = f.small_roots(X = B, beta=0.5)
print(f'{s_roots}')
Step 3 - Really Loud Revenge
Like before, the difference between Loud Revenge and Really Loud Revenge is only in the parameters. This is the source code for Really Loud Revenge:
1
2
3
4
5
6
7
8
9
B = 2^4096
flag = randint(1, B) # recover this value, wrap the answer in Dead{}
m = 4
n = 20
ps = [getPrime(256) for _ in range(n)]
S = [[randint(0, ps[i] - 1) for __ in range(m - 1)] + [int(flag % ps[i])] for i in range(n)]
for Si in S:
random.shuffle(Si)
This time, we only have $20$ reminders of 256 bits each. If we apply the above idea, we get $N \sim 2^{5120}$, and $X = 2^{4096}$. Since $d = 4$, we can no longer apply Coppersmith Method, at least not in this way (actually, for it to work we would need $d=1$).
I failed to solve this part during the CTF. I thank UnknownError235 and vishiswoz (the author of the challenge) for suggesting me the correct solution afterwards. It consists in solving the Noisy Chinese Remaindering problem as described in this paper. Using a direct lattice reduction, instead of passing through Coppersmith Method, can result in solutions with better bounds. Of course the same lattice also works for Loud Revenge.