Finished 8th in ACSC Quals 2023. Solved all cryptography challenges and warmup rev. I had a alumni meetup with NEXON Youth Programming Challenge award winners, so I went home at like 9PM with a beer and sangria inside me.
We have $n$ alongside 63 pairs of $(e, k)$ where $$ed = k \phi(n) + 1$$ The goal is to factor $n$. First, the central idea is to note that $$k \phi(n) + 1 \equiv 0 \pmod{e}$$ so we recover $$\phi(n) \equiv - k^{-1} \pmod{e}$$ Combined with CRT, this gives us $$\phi(n) \pmod{ \prod e}$$ which is around $63 * 16 = 1008$ bits of information. Meanwhile, we since $$\phi(n) = n + 1 - (p + q)$$ we have a 1025 bit range for $\phi(n)$. We can easily brute-force all possible values of $\phi(n)$, then recover $p, q$ from $n, \phi(n)$.
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
from sage.all import*
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
I overcomplicated this problem way too much - the easier solution is combining the two signature schemes via CRT then LLL.
I tried some straightforward lattices without the CRT idea, but it didn't give me the answer. Here's my solution.
Start with the equations $$ks_1 = z + r_1x + c_1q_1, \quad ks_2 = z + r_2x + c_2q_2$$ where $c_1, c_2$ each have absolute values of at most something like $2^{515}$. We'll cancel out the $k$ in the equations to get $$s_2(z + r_1x + c_1q_1) = s_1(z+ r_2x + c_2q_2)$$ or $$(s_2r_1 - s_1r_2)x = (s_1 - s_2)z + (s_1q_2) c_2 - (s_2q_1) c_1$$ This gives us a system - we want $$-2^{515} \le c_1, c_2 \le 2^{515}$$ as well as the linear equation $$(s_1q_2) c_2 \equiv (s_2q_1) c_1 + (s_2 - s_1)z \pmod{s_2r_1 - s_1r_2}$$ While there are some GCD issues like $\gcd(s_1q_2, s_2r_1 - s_1r_2) = 2 \neq 1$, in essence this is the same type of problem as $$S \le c_1 \le E, \quad L \le Ax + B \bmod{M} \le R$$ which is the exact task that the special case of my CVP repository solves. After getting $c_1, c_2$, the rest is easy linear equation.
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
def ceil(n, m): # returns ceil(n/m)
return (n + m -1) // m
def is_inside(L, R, M, val): # is L <= val <= R in mod M context?
if L <= R:
return L <= val <= R
else:
R += M
if L <= val <= R:
returnTrue
if L <= val + M <= R:
returnTrue
returnFalse
def optf(A, M, L, R): # minimum nonnegative x s.t. L <= Ax mod M <= R
if L ==0:
return0
if2* A > M:
L, R = R, L
A, L, R = M - A, M - L, M - R
cc_1 = ceil(L, A)
if A * cc_1 <= R:
return cc_1
cc_2 = optf(A - M % A, A, L % A, R % A)
return ceil(L + M * cc_2, A)
# check if L <= Ax (mod M) <= R has a solution
def sol_ex(A, M, L, R):
if L ==0or L > R:
returnTrue
g = GCD(A, M)
if (L -1) // g == R // g:
returnFalse
returnTrue
## find all solutions for L <= Ax mod M <= R, S <= x <= E:
def solve(A, M, L, R, S, E):
# this is for estimate only : if very large, might be a bad idea to run this
print("Expected Number of Solutions : ", ((E - S +1) * (R - L +1)) // M +1)
We need to recover the full PEM key. The solution is really hands-on, and it needs some grinding.
The PEM decoding algorithm is in pycryptodome - basically, it's just a DER decoding. So how does DER decoding work?
By following the DER implementation in pycryptodome alongside with some debugging, it's basically as follows.
1 byte is consumed as the octet. Not sure what this does.
Then, 1 byte is consumed as the length $l$. If $l \le 127$, then this is the final length.
If $l \ge 128$, then the next $l \pmod{128}$ bytes in big endian represent the final length.
The "final length" bytes worth of data, in big endian, is the pushed data.
However, the very first "final length" is actually the full length, so this one should be skipped.
Also, we quickly note that
By comparing lengths, it can be seen that this file is based on 2048 bit RSA.
In this case, the PEM file has a linebreak every 64 characters. Based on this, we can remove some "?" to linebreaks.
The first step is to base64 decode the lines between the first and the last ones. By randomly selecting one of 64 choices for each "?" and decoding it multple times, we can figure out which bits in the decoded data are known, and which bits in the decoded data are the ones from the "?"s. This is useful when patching important "?"s so that the length informations makes sense.
The main part is to patch everything so that the length informations makes sense. Since the datasets are $n, e, d, p, q, d_p, d_q, u$ in order, just try every patch that makes sense and does not affect the bits that are actually known. Decoding an actual 2048 bit RSA PEM helps.
In the end, we'll have the full $n, e$ and some bits of $p, q, d_p, d_q, u$. However, $u$ is not needed here.
The rest is relatively well-known - you set up an equation $$pq = n, \quad ed_p = k_p(p-1) + 1, \quad ed_q = k_q(q-1) + 1$$ and solve this equation modulo powers of 2 iteratively. To do so, you need to fix $k_p, k_q$ - it turns out that there are $\mathcal{O}(e)$ possible pairs of $(k_p, k_q)$, so you can try out all candidates. For example, see [HS09]. There is also my challenge "RSA Hex Permutation".
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
from sage.all import*
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
This is a 3-round block cipher, and a hint is given - use differential cryptanalysis.
Let's find some easy differentials. We collect the $((i \oplus j)[u], (S_i \oplus S_j)[v])$ and see how it behave - and it turns out that the bias is noticeable. We can keep track of an array $pos$, where $pos_i$ denotes the bit location where the original $i$th bit is the most correlated to it.
In the current state, there are 3 S-box applications, so the bias will decrease over those 3 S-boxes. However, if we know a key chunk, for example, the first 6 bits, then the first key addition and the S-box application can be computed directly, so in reality we are only going through 2 S-boxes. Therefore, the correlation between the state just after the first S-box and the encrypted state will be much greater.
We can now brute force all 64 possibilities for all 8 key chunks. 20K random encryptions are enough to reliably find the key.
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
from pwn import*
import os
S = [
43, 8, 57, 53, 48, 39, 15, 61,
7, 44, 33, 9, 19, 41, 3, 14,
42, 51, 6, 2, 49, 28, 55, 31,
0, 4, 30, 1, 59, 50, 35, 47,
25, 16, 37, 27, 10, 54, 26, 58,
62, 13, 18, 22, 21, 24, 12, 20,
29, 38, 23, 32, 60, 34, 5, 11,
45, 63, 40, 46, 52, 36, 17, 56
]
P = [
21, 8, 23, 6, 7, 15,
22, 13, 19, 16, 25, 28,
31, 32, 34, 36, 3, 39,
29, 26, 24, 1, 43, 35,
45, 12, 47, 17, 14, 11,
27, 37, 41, 38, 40, 20,
2, 0, 5, 4, 42, 18,
44, 30, 46, 33, 9, 10
]
def get_bit(res, w):
return (res >> (5- w)) &1
bits = [[[0, 0, 0, 0] for _ inrange(6)] for _ inrange(6)]
for i inrange(64):
for j inrange(64):
# i ^ j => Si ^ Sj
for u inrange(6):
for v inrange(6):
t1 = get_bit(i ^ j, u)
t2 = get_bit(S[i] ^ S[j], v)
bits[u][v][2* t1 + t2] +=1
mx =0
for i inrange(6):
print("[+]", i)
mx_j =0
for j inrange(6):
mx_j = max(mx_j, bits[i][j][0])
print(mx_j)
for j inrange(6):
if bits[i][j][0] == mx_j:
print(j)
sub_loc = [5, 0, 1, 1, 0, 5]
def track_sub(pos):
ret = [0] *48
for i inrange(48):
loc = pos[i] //6
md = pos[i] % 6
ret[i] =6* loc + sub_loc[md]
return ret
def track_perm(pos):
ret = [0] *48
for i inrange(48):
ret[i] = P[pos[i]]
return ret
full_enc = [i for i inrange(48)]
for i inrange(3):
full_enc = track_sub(full_enc)
full_enc = track_perm(full_enc)
part_enc = [i for i inrange(48)]
part_enc = track_perm(part_enc)
for i inrange(2):
part_enc = track_sub(part_enc)
part_enc = track_perm(part_enc)
plaintexts = [int.from_bytes(os.urandom(6), "big") for _ inrange(256*80)]
A very long story. It started when Brian Gu told me about DARK back in 2021 @theoremoon wrote the challenge "Hell" for SECCON CTF Finals 2022. It involved some hyperelliptic curves and was quite interesting. Let's look at that challenge first.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import os
flag = os.environ.get("FLAG", "neko{the_neko_must_fit_to_the_hyperelliptic}")
p = random_prime(2**512)
xv = randint(0, p-1)
yv =int(flag.encode().hex(), 16)
assert yv < p
g =2
PR.<x>= PolynomialRing(GF(p))
f = sum(randint(0, p-1)*x**i for i inrange(2*g +1+1))
Ultimately, we are given $p$ and Jacobians of $6D, 12D, 20D$. Here, we need to find the coordinates of $D$.
To solve this, first we note that for Mumford representation $(u, v)$ we must have $v^2 \equiv f \pmod{u}$.
As this is genus 2, $\deg u$ will be $2$ and $\deg f$ will be $5$. This means that we can recover $f$ via CRT.
After recovering $f$, we can compute the Mumford representation of $2D = 20D - 12D - 6D$. Here, we note that the $u(x)$ value of the Mumford representation of $2D$ will simply be $(x - xv)^2$ due to the usual formula. This recovers $xv$ and so $yv$.
So while the challenge was fun, I thought that it didn't venture through the whole "recover $D$ from $2D$" part. Another thing was that at first, I didn't realize that $(x - xv)^2$ would be the representation of $2D$. This lead me to thinking about searching for methods to actually compute the order of the Jacobian. After some quick tries, I realized that for hyperelliptic curves of genus 2 and above, the computation of orders is quite a difficult task. You can take more looks into this in papers like https://eprint.iacr.org/2020/289.pdf.
So the whole dividing by 2 shouldn't be very trivial. Let's think about genus 2. A reduced divisor would be of the form of $[P] - [O]$ or $[P] + [Q] - 2[O]$. We would be given the divisor multiplied by 2. We see that the $[P] - [O]$ case is the easy case presented in SECCON. How about the latter? In this case, $2[P] + 2[Q] - 4[O]$ would be presented to us. This is clearly not reduced, so we need to reduce.
A good explainer is presented in "Pairings For Beginners" Section 3.2. You set up a polynomial $g$ such that $g$ meets $f$ at $P$ with multiplicity $2$ and $Q$ with multiplicity $2$. This amounts to 4 constraints, so $g$ should be degree 3. Now we see something like $$g^2 - f = C (x - p)^2 (x - q)^2 (x^2 + ax + b)$$ For sake of explaining let's just say that $x^2 + ax + b$ splits and we have $$g^2 - f = (x - p)^2 (x - q)^2 (x - r) (x - s)$$ This will mean that $$2[P] + 2[Q] + [R] + [S] - 6[O]$$ is a principal divisor, so in the Jacobian, we will have $$2[P] + 2[Q] - 4[O] = 2[O] - [R] - [S]$$ which is practically now reduced. This means that $x^2 + ax + b$ will be (up to sign) the $u(x)$ of the Mumford representation of $2[P] + 2[Q] - 4[O]$, i.e. the polynomial we are already given. So basically we would be solving for something like $$g^2 - f = C (x - p)^2 (x - q)^2 u(x)$$ which looks to be relatively doable with the whole resultants and whatnot. It was, and I'll explain the further details later.
The next question for me was in dividing-by-2 in genus 3, rather than solving for dividing-by-3 in genus 2.
You actually need to reduce two times here, so following the system we have something like $$g^2 - f = C_1(x-p)^2(x-q)^2(x-r)^2 T(x)$$ $$h^2 - f = C_2T(x) u(x)$$ so something like $$(g^2 - f) u(x) = C(h^2 - f) (x-p)^2(x-q)^2(x-r)^2$$ where $g$ is degree 5 and $h$ is degree $3$. This is quite a lot of variables, so even after optimizing as hard as I can, I couldn't get the algorithm to run in SageMath at all. In the end I gave up, and decided to ask to solve for $P$ when given $5[P] - 5[O]$.
This requires a single reduction - take a $g$ of degree 4 that meets $f$ at $P$ with multiplicity 5. Then $$g^2 - f = C(x-p)^5 u(x)$$ holds, so this is a relatively manageable system that can be solved in SageMath within time. Once again, I'll explain the details later.
Before we dive into the PBCTF challenge, let's look into the whole dividing-by-2 situation in genus 3 hyperelliptic curves.
At first I thought it would just be a cool challenge, but it turned out that it had some interesting background.
It turns out that the previously noted fact that hyperelliptic curve's order is quite hard to compute had made it a candidate for a hidden order group. Hidden order groups are used in various parts of cryptography - the most common one we all know is the RSA group $\mathbb{Z}_N^\star$. There are various assumptions, (see Alin Tomescu's blog post) and various cryptographic primitives that are based on those assumptions. Some examples are VDFs (see [BBF18]) and integer-based zero knowledge proofs (see DARK [BFS19]) and so on. One popular choice for such a group is obvious - the RSA group itself, sometimes reduced to something like $QR_N / \{\pm 1\}$. However, selecting $N$ requires either a trusted third party or ridiculously large $N$ (see Sander's paper) which adds concerns. The goal now is trustless hidden order groups - and this is where class groups of imaginary quadratic fields come in. Apparently simply choosing a prime $p$ is enough - and nobody will be able to compute the order. Many papers based on hidden order groups mention class groups.
Hyperelliptic curves of genus 3 and above are mentioned as candidates in Brent's paper. It was then considered by Dobson, Galbraith, and Smith - this paper does a lot of things, such as rethinking security parameters, lowering sizes of ideal class group elements. Another thing that this paper does is to speculate that hyperelliptic curves of genus 3 actually might be a good choice - for example, the paper suggests that it may offer shorter keylengths in practice. The paper was followed by a paper by Jonathan Lee, who discusses point counting algorithms on hyperelliptic curves. Further work was done by a paper by Thakur to discuss more details, such as types of curves to avoid.
At this point, dividing-by-2 in genus 3 curves sounded like it should be impossible. After all, the RSA equivalent of this is solving a quadratic equation modulo $N$, which is straight up just equivalent to factoring. Also, if dividing-by-2 is impossible, then by definition, Strong RSA Assumption will be broken. I believed that this would immediately hinder the usage of hyperelliptic curves as hidden order groups. I didn't know if dividing-by-2 was possible in class groups as well. It is possible, and it's even mentioned in the DARK paper, oops...
Anyways, that was why I was so focused on doing the dividing-by-2 in genus 3 curves - I thought it would have a serious implication.
Back to the PBCTF challenge. The challenge I wanted was recovering $P, Q$ from $2[P] + 2[Q] - 4[O]$ in a genus 2 curve, and $R$ from $5[R] - 5[O]$ in a genus 3 curve. Since "hell" also had a part to recover the hyperelliptic curve equation, I decided that I should add this as well. I also wanted to make recovering $p$ as a part of the challenge. To do so, I added a point thanking @theoremoon for the nice SECCON challenge. To make the hyperelliptic curve formula recovery a bit more challenging, I bounded the coefficients heavily and gave less equations - so that lattice reductions are required. In the end, the challenge I submitted for PBCTF looked like this. It had 4 solves.
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
import os
flag =open("flag", "rb").read()
flag = flag.lstrip(b"pbctf{").rstrip(b"}")
assert len(flag) ==192
whileTrue:
p = random_prime(1<<513, lbound =1<<512)
coefs = [int.from_bytes(os.urandom(42), "big") for _ inrange(8)]
PR.<x>= PolynomialRing(GF(p))
g1, g2 =2, 3
f1 = sum(coefs[i] * (x ** i) for i inrange(2* g1 +2))
f2 = sum(coefs[i] * (x ** i) for i inrange(2* g2 +2))
First, the hint and the jacobian of $P_4$ immediately gives a small product of $p$ - it can be checked that the hint string converted to integers is just a little higher than $2^{512}$. By factoring that small product, you can recover $p$.
Now we move on to recovering the 8 coefficients. As in the solution of "hell", we know that $v^2 \equiv f \pmod{u}$. Since the degrees of $u$ in the three Jacobians are 2, 3, 1 respectively, this amounts to 6 linear equations on the coefficients of $f$. Therefore, the solutions will be of the form of $s + c_1 l_1 + c_2l_2$ where $c_1, c_2$ are constants and $l_1, l_2$ is in the kernel of the matrix. As the coefficients are less than $2^{336}$, a lattice reduction will find the coefficients. Notice that $336 \times 8$ is significantly less than $512 \times 6$.
We now move on to the real challenge - the first one, as mentioned is recovering $P, Q$ from $2[P] + 2[Q] - 4[O]$.
Also as mentioned before, this can be reduced to solving $$g^2 - f = C_1 (x - p)^2 (x - q)^2 u(x)$$ Let's solve for this. Set $g = A + Bx + Cx^2 + Dx^3$ to get $$(A + Bx + Cx^2 + Dx^3)^2 - f = C_1(x-p)^2(x-q)^2u(x)$$ and by comparing the leading coefficient, we see that $C_1 = D^2$ so $$(A + Bx + Cx^2 + Dx^3)^2 - f = D^2(x-p)^2(x-q)^2u(x)$$ Now, for the sake of lowering degrees (in terms of $A, B, C, D$), we change this to $$(AD^{-1} + BD^{-1} x + CD^{-1} x^2 + x^3)^2 - D^{-2} f = (x-p)^2(x-q)^2u(x)$$ and re-define the variables to get $$(A + Bx + Cx^2 + x^3)^2 - D f = (x-p)^2(x-q)^2 u(x)$$ Now we will perform long-division on the LHS by $u(x)$, and add the constrain that the remainder should be zero. This will be two polynomial constraints on $A, B, C, D$. We add the fact that the result will be of the form of $$(x^2 + ax + b)^2 = x^4 + 2ax^3 + (a^2 + 2b)x^2 + 2abx + b^2$$ Since the coefficients are polynomials of $A, B, C, D$, we add constraints that the coefficients are ones of the form shown in $(x^2 + ax + b)^2$. For example, if the division result if $x^4 + c_3x^3 + c_2x^2 + c_1x + c_0$, where $c_i$s are polynomials of $A, B, C, D$, then we could set $a = c_3 / 2$ and $b = (c_2 - a^2) / 2$ then constrain that $c_1 = 2ab$ and $c_0 = b^2$. This adds two more polynomial constraints to $A, B, C, D$. Since we have four constraints and four variables, resultants will be able to recover $A, B, C, D$ with some time.
The second challenge is recovering $R$ from $5[R] - 5[O]$. This is solving $$g^2 - f = C_1(x-r)^5 u(x)$$ Here, I actually generated the parameters so that $u$ would split into three linear factors. This made it easier to compute everything, or at least think about everything (maybe this trick works with extended fields too). For example, let's say that $t$ is a root of $u$. Then, $g$ here would actually have to pass through $(t, -v(t))$. This would make the reduction process send $5[R] - 5[O]$ to have $(t, v(t))$ in the reduced form. Therefore, we actually know 3 points that $g$ passes through, which means that we can interpolate them. Therefore, we know $g \pmod{u}$.
So let's write $g = b + C_2 u(x) (x + v)$. This makes us write $$(b + C_2u(x)(x+v))^2 - f = C_1(x - r)^5 u(x)$$ and from the leading coefficients, we know $C_2^2 = C_1$. Now we can write $$(C_2^{-1} b + u(x)(x + v))^2 - C_2^{-2} f = (x-r)^5 u(x)$$ and rewriting variables, we can just solve for $$(t b + u(x)(x+v))^2 - t^2 f = (x-r)^5 u(x)$$ so there are only two variables - $t$ and $v$. We proceed similarly - divide the LHS by $u(x)$. Here, the remainder should be $0$ already, as we set $b = g \pmod{u}$ as already known. The main part is to constrain so that the result of the division is of the form $(x-r)^5$. To do so, let the result be $x^5 + c_4x^4+ \cdots + c_0$, where $c_i$s are again polynomials of $t, v$. Then, we can set $r = -c_4/5$ and constrain $c_3 = 10r^2, c_2 = -10r^3, c_1 = 5r^4, c_0 = -r^5$. This makes it possible to solve for $t, v$.
After the CTF, @isenbaev told via twitter that divide-by-2 in genus 3 hyperelliptic curves. It happens that Magma is very strong, and can compute this kind of stuff very fast. At first, I was very surprised at the fact that divide-by-2 is possible. So what now? What does this mean??
I went over the VDF papers and DARK paper to look at exactly what assumptions they are working with.
VDFs require low order assumption or the adaptive root assumption. The latter is clearly hard, but low order assumption seemed interesing. Can we go further and consider multiplication/division by 3? I'm not sure, but it might be interesting to try. DARK paper mentions using the Strong RSA in Theorem 5. Another interesting thing was that there are papers that try to remove the Strong RSA assumption from arguments working over the integers. I still need to read that paper - it sounds very cool.
After reading more, I saw that the [DGS20] paper already had a defense in mind.
Basically, it considers the set $S$ where low-order assumption is broken, and just considers $\text{lcm}(S) G$. This is exactly the methods used to reduce the RSA group to $\mathbb{Z}_N^\star / \{\pm 1\}$ or something like that. This seems to be enough defense against low order assumption attacks.
What about the Strong RSA assumption side of things? I still thought that the whole dividing-by-2 things being possible was very bad, but as I mentioned before, I learned that even class groups have that property as well. Apparently it's fine.
I guess that not reading the detailed proof for DARK really hurt in the end. The proof is really hard, though...
Anyways, this was a really fun adventure, and I'm more motivated to study now. Thanks to everyone for the discussion.
I participated as rkm0959_test and somehow got 10th place. Initially wanted to take a brief look at the cryptography challs, ended up calling two friends and managed to clinch finals. Not sure if I'll be over there, though. Need to decide... Brief writeups, as I'm tired.
There are a lot of stuff to process. First, as $R$ is a rotation matrix, you can compute $x_1^2 + x_2^2$ and $y_1^2 + y_2^2$. However, due to the precision, only the integer value of $y_1^2 + y_2^2$ can be computed exactly, and the value of $x_1^2 + x_2^2$ has a bit of an error range. However, as we have $$(x_1^2 + x_2^2) + e (y_1^2 + y_2^2) = 2n$$ we can do some basic bounding to recover $e$ and the actual value of $x_1^2 + x_2^2$ as well.
You can also compute the rough values of $x_1y_1 + x_2y_2$ as this is the inner product of the two values, which doesn't change under rotation. Similar for $x_1y_2 - x_2y_1$. However, there are some precision issues which lead to the exact computation of these two values difficult.
To overcome this, we use the equation $$(x_1y_1+x_2y_2)^2 + (x_1y_2 - x_2y_1)^2 = (x_1^2+ x_2^2)(y_1^2+y_2^2)$$ which we know the precise value of. With this equation, some standard lattice tricks with some more bounding can recover the exact value of $x_1y_1 + x_2y_2$ and $x_1 y_2 - x_2y_1$. Now one can recover the full values of $x_1, x_2, y_1, y_2$ algebraically - I just did some resultants stuff over $\mathbb{F}_p$ for some random large $p$, but other methods will work. Now it suffices to factor $n$.
Here, we note that $$(x_1/y_1)^2 + e \equiv (x_2/y_2)^2 + e \equiv 0 \pmod{n}$$ so one can hope that $x_1/y_1$ and $x_2/y_2$ differ in one of $\pmod{p}$ and $\pmod{q}$, so usual GCD tricks work. This happens to be the case.
The clear issue here is that the decrypt function doesn't care if a solution to $x^2 - rx + c \equiv 0 \pmod{p}$ exists.
In this case, the result of $x + c / x$ would not be once again equal to $r$, which will makes things interesting.
To dive further into this, let's send enc-dec queries of $(r_0, \{-1, 1\}, \{0, 1\})$ and see the results - we are more focused on the $r$ values of the result. We would think that all the $r$ values would be $r_0$, but some experimentation shows that it isn't the case - there are sometimes a single unique $r$ value, two unique $r$ values, or four unique $r$ values. Here, we ignore the error cases (asserts) as they are not needed.
The interesting case is where there are two unique $r$ values. In this case, the intuition is that $\pmod{p}$ side of the things worked out, but $\pmod{q}$ side didn't. So while $x + c / x$ values agree each other in $\pmod{p}$, it didn't on $\pmod{q}$.
In other words, the difference of the two $r$ values would be a multiple of $p$, but not $q$, a perfect scenario for GCD ideas.
This allows us to get $n$. Try out various $r_0$ values, and if there are two unique $r$ values, collect the difference. For each pair of differences, take the GCD. If it is non-trivial, it would be a prime divisor of $n$. After enough collection we can recover both $p, q$.
Now we need to get $c$. Here, we note that even when the $x^2 - rx + c \equiv 0 \pmod{p}$ didn't work out, the two returned solutions add up to $r$. This can be used to set up a two-variable, two-equation system over $\pmod{p}$, where one variable is $a_1$ of the solve_quad and the other is $c$. This can be solved easily via various methods. Since we have $p, q, n, c$ and the encrypted flag, the rest is easy.
회사 동료분과 함께 0-day 버그를 찾은 경험이 조금 늘어났습니다. (THORChain, ChainSafe, etc)
현재 회사에서도 보안감사 일을 하고 있습니다. 아직까지는 큰 문제없이 잘하고 있는 것 같아서 다행입니다.
내년에도 계속 대회 출제를 할 수 있으면 좋겠습니다. 출제가 확실히 재밌기는 해서....
Super Guesser에서 뭔가 재밌는 일을 하게 될수도 있을 것 같은데 이것도 잘 되면 좋을 것 같아요.
Code4rena 같은 대회나 ImmuneFi 버그 헌팅도 고려는 하고 있는데 사실 고르라고 하면 암호 공부할 것 같기는 합니다.
옛날에는 pwn/web/rev를 공부하는 것에 대한 로망이 있었는데 솔직히 제가 지금 시작하는 건 별로인 것 같다는 결론을 내렸습니다.
"Macro" Timeline
1~2월: 작년 말에 좀 일이 있어서 멘탈이 날라갔는데 복구하면서 랩실 작업에 집중했습니다.
3월: 이직하기로 결정하고 갈 곳들에게 컨택하고 절차를 밟았습니다.
이직 이유는 일이 너무 어려워서 + 보안 일하는 게 재밌어보이고 적성도 맞을 것 같고 제 미래에도 도움이 될 것 같아서
여기서 어디로 이직을 할 것인지를 가지고 고민을 해야 했는데 진짜 정신나갈 것 같았습니다. 4월에 훈련소여서 시간이 없었어요.
내린 선택에 대한 후회를 한 번도 안했냐고 물으면 그건 거짓말인데, 결국 생각하고 나면 결론이 대충 "이미 선택을 했으니까 내가 그 선택을 맞는 선택으로 만들기 위해서 노력하자"여서... 병특인만큼 이제 이직을 하더라도 엄청 신중하게 해야하는 게 맞으니까요. 다양한 길이 열려있고 좋게 봐주시는 분이 계시는 건 항상 감사한 일입니다. 더 노력해야겠어요 :) 어쨌든지금은 "나만 잘하면 되는 환경"이 세팅된 상황 같아서 다행입니다.
4월: 훈련소에 갔습니다. 여기서 공부를 조금 더 열심히 했으면 좋았을 것 같지만 솔직히 그냥 끝난 게 다행입니다.
5월: Terra 사태가 터졌고 (저는 제 전재산 70%를 UST로 들고 있었는데 0.994에 다 팔았습니다) 저는 이직을 했습니다. MSI 보러 부산감.
6월: 이때부터는 Macro적인 건 특별히 없고, 그냥 회사에서 일을 했습니다 ㅋㅋㅋㅋ
7월: 이때부터 본격적으로 Security Audit 일에 들어갔습니다. 이때 Open Source Contributon도 있었습니다.
8월: DEFCON에 다녀온 게 메인 이벤트 같네요. ZK-ZK-SEL 분들도 이때 즈음에 만나서 같이 이야기하게 되었습니다.
9월: Stanford에 다녀온 게 메인 이벤트. 이때 Lookup Argument 연구를 조금 했고 회사일도 이때 재밌었어요.
10월: NSUCRYPTO도 나갔는데 이때 여러가지로 고민이 많았던 기억이 있습니다. 사실 롤드컵 보느라 인생을 삭제시켰습니다.
그거와 별개로 이때 회사 근처에 아지트를 하나 구했습니다. 디테일은 생략. 아무튼 잘 쓰고 있습니다.
11월: BlackHat MEA 다녀온 게 메인 이벤트. 근데 이때도 솔직히 약간 인생이 뇌절이긴 했어요 ㅋㅋㅋㅋㅋ;
12월: 일단 회사일이 엄청 재밌어졌습니다. 포켓몬 BDSP + 포켓몬 LA를 사서 합쳐서 90시간을 태웠습니다.
한바탕 노니까 다시 공부할 Motivation도 생겨서 지금도 그렇고 1월에도 그렇고 다시 열심히 공부할 것 같습니다
Sports & Fun
리듬게임 이야기
츄니즘은 결국 아예 접었습니다. 어떻게 된 게 대규모 업데이트가 (CHUNITHM NEW) 나왔는데 새로 나온 곡들 순회조차 안하고 접었는지는 모르겠는데, 어쨌든 접었습니다. 옛날에는 이거하는 것만을 목적으로 일본까지 가고 그랬는데 참 신기합니다. 어쨌든 츄니즘 ㅂㅂ
사볼도 제가 봤을때는 사실상 접었습니다. 비즈니스하는 사람들 골프치듯이 사볼하는 거 외에는 (ㅋㅋ) 안할 것 같아요. 점수 올릴 생각하고 사볼하러 간 다음에 기분만 망친 상태로 집으로 가는 경우가 너무 많아졌습니다. 여기서 더 올라가려면 뇌를 켜야하는데 제가 그걸 잘 못합니다.
그래서 리듬게임은 아예 접은 것 같아요. 21년 말 ~ 22년 중순까지 덕분에 잘 놀았습니다.
