# RCTF Official Writeup - Crypto Part

We will complete the official writeups of all crypto challenges of RCTF2022 within a few days. If
still have doubts, please email us: `contract[at]rois.io` or private message me(Thr#0040) on Discord.

**In view of the fact that many teams have given very good and detailed writeups, I will not give too much exploit code, but mainly explain the ideas of the design challenge and summarize players' ideas.**

To the team "一九九七", especially @ZM.J and @sh1kaku, we would like to express our sincerest gratitude for the support and challenges you provided for RCTF2022. Your contributions greatly enhanced the event.

## magic_sign

- solved: 16/363
- flag: `RCTF{you_w0uldn't_get_th1s_froM_@ny_other_guy}`

This challenge is about a very interesting cryptosystem **Xifrat0** and its attack. The paper [*Xifrat - Compact Public-Key Cryptosystems based on Quasigroups*](https://eprint.iacr.org/2021/444) proposed it but it was broken after half a month by [*Xifrat Cryptanalysis - Compute the Mixing Function Without the Key*](https://eprint.iacr.org/2021/487). We called the original one Xifrat0 after the [new attempt](https://eprint.iacr.org/2022/429) came out. The attack is so simple that the author only takes a few pages to present it. We can compute the `m` without the key when we have a pair of a message and it's signature.

However, considering there are already too many crypto challenges in the CTF, the challenge does not explicitly point to this paper, and the pure paper implementation challenge is a bit boring, I did not release the N=131 challenge. I found that the random number generator in the paper does not work well when N=137, so I weakened the cryptosystem to make it more suitable as a CTF challenge instead of boring search. Of course, the attack in the paper still works. It's a lot of fun and I highly recommend you read it.

### A. attack when N=137

When N=137, we will find there are very few elements in U：`{4: 51, 133: 11527, 135: 17, 11: 1, 78: 4641, 81: 17, 18: 2465, 24: 34, 26: 17}`. We can simply brute force $2^{(9*3)}$ to find valid signature. With some suitable optimizations, the time complexity can be reduced even lower. However, the attack in the paper does not have any requirements for computing performance which can be easily and instantly completed! Let's see:

### B. attack in the paper

Define this part as the e operation on R：

We can rewriting the `S = mix(H, Q)` as `e(H+Q)+Q=(e(H)+e(Q))+Q`. `e(H)`is known. Note that we don't need to find `Q` which is a computationally hard problem but only need to find out the `e(Q)` and `Q` that make the verification pass. **In fact, `e(Q)` and `Q` do not necessarily satisfy the `e`.**

We only need to guess `e(Q)` and `Q` and verify `S[i]==(e(H)[i]+e(Q)[i])+Q[i]` for 137 elements one by one. In this way, we only need to guess $137*2^6$ numbers and get the equivalent `Q` to sign the message.

## Derek

- solved: 7/363
- flag : `RCTF{3asy_backd0or_wiTh_CRC_r3ver3s1ng}`

Take a good look at the Feistel network code in `Derek.py`, it is easy to notice that there is a suspicious operation at the end of the Feistel network:

l ^= int.from_bytes(self.key[:8], 'big')
r ^= int.from_bytes(self.key[8:], 'big')

To make the analysis easier, we can use pen and paper to draw the Feistel network:


Well, thanks to **XOR-trick**, we find that if the output of M-function is $\rm{0xbaadf00ddeadbeef}$ (or $\rm{0xdeadbeefbaadf00d}$), this round of encryption does nothing. If we can reverse M-function, take the preimage as input, it will be an **One-Time-Pad**, which means we can recover the key!

It's not hard to realize that the "magic" is the **CRC(Cyclic Redundancy Check)**. Different from MD or SHA, it is very easy to find the preimage of CRC which is a well-studied problem which we can find many implementations.

Once having the key, the last thing we have to do is implement a decryption of *Derek*, which is very direct for a Feistel cipher.

**This interesting structure was inspired by [*Big Brother Is Watching You: A Closer Look at Backdoor Construction*](https://link.springer.com/chapter/10.1007/978-3-031-22829-2_5).** I replaced the hash function with CRC to make it a CTF challenge.


In this paper, **Derek** means cipher designer, which hints at the existence of a backdoor.

## S2DH

* solved: 7/363


The assumptions that SIDH relies on were cracked in 2022.

https://github.com/jack4818/Castryck-Decru-SageMath

Just copy paste challenge parament to the script, make some minor modifications, and get the flag.

Why S**2**DH?


The curve is $y^2=x^3+x$, so we have i rather than 2i for the script.

The following player writeups are perfect, I don't need to write much. 😀

https://github.com/pcw109550/write-up/tree/master/2022/RCTF/S2DH

## IS_THIS_LCG?

* solved: 12/363

This challenge is about three LCG variants. We need to complete three challenges to get three primes, and get flag.

The first challenge is a truncated LCG, just apply LLL-reduction to find the small root.

In the second challenge, we need to recover p from the known 7 points on elliptic curve. We can found this [paper](https://arxiv.org/pdf/1609.03305.pdf) to solve this problem. The trick is since N is given, we don't need to implement the paper in full, just compute the determinant, which is a multiple of p, then GCD.

Of course, since the number of variables is sufficient, simply deriving the equation and computing the Gröbner basis should be more straightforward.

The last challenge asks us to optimize the "matrix-LCG" to do fast skipping, which is similar to normal LCG. We can still transform this problem into matrix exponentiation. This idea comes from @sh1kaku.

def dec2mt(t, n, m):
    X = Matrix(Zmod(m), n, n)
    for i in range(n):
        for j in range(n):
            X[i, j] = t % m
            t = t // m
    return X
    
X0 = dec2mt(X0, n, m)
X1 = dec2mt(X1, n, m)
X2 = dec2mt(X2, n, m)
X9 = dec2mt(X9, n, m)
A = (X2-X1)*(X1-X0)^-1
B = X1-A*X0
X = A*X9 + B
vec = block_matrix(Zmod(m), [X.T, identity_matrix(n)], ncols=2)
MT1 = block_matrix(Zmod(m), [A, B], ncols=2)
MT2 = block_matrix(Zmod(m), [Matrix(n, n), identity_matrix(n)], ncols=2)
MT = block_matrix(Zmod(m), [MT1, MT2], nrows=2)
S2 = MT**(1337**1337-10) * vec.T
p3 = next_prime(mt2dec(S2, n, m))
print(p3)
assert N % p3 == 0

$\begin{bmatrix}
A & B \\
O & I
\end{bmatrix}
\begin{bmatrix}
X^T \\
I
\end{bmatrix}=
\begin{bmatrix}
AX^T+B \\
I
\end{bmatrix}$

Many players use the geometric sum formula to do this.

## Clearlove

* solved: 6/363

Thanks to @ZM.J for his contribution to this challenge.

This challenge is based on [HFCTF 2022 - RRSSAA](https://github.com/1umi3re/my_ctf_challenge/tree/main/hfctf_2022/RRSSAA), and it becomes more difficult. The intended solution needs to implement the **lineaization** in the official writeup for RRSSAA, which can make the volume of the lattice smaller. However it seems that the exploit of RRSSAA can also work. According to player feedback, it takes ~3 hours, but not particularly long for a 48-hour CTF. Some teams built the lattice themselves, but it still took hours. However the intended solution is only takes ~30min in my laptop.

> “毕竟比赛时间这么长，而且不让弄动态靶机，只能说这钵跟这些因素配合得不是很好。”
> ——ZMJ4396

The papers expected to be implemented in this challenge are: https://eprint.iacr.org/2021/1632.pdf

First step is factor N:

with open('output.txt', 'r') as f:
    s = f.read().splitlines()

n = eval(s[-2].split('=')[1])
e = eval(s[-1].split('=')[1])

alpha = 2.
beta = 0.4396
delta = 0.642

print(delta < 2 - (2 * alpha * beta) ^ 0.5)


P.<x, y, u> = PolynomialRing(ZZ)

X = floor(n^(alpha + delta - 2))
Y = floor(n^(2 * beta))
U = floor(n^(alpha + delta + 2*beta - 2))

def F(x, u):
    A = -(n-1)^2
    return u + A * x

def trans(f):
    my_tuples = f.exponents(as_ETuples=False)
    g = 0
    for my_tuple in my_tuples:
        my_list = list(my_tuple)
        mon = x ^ my_list[0] * y ^ my_list[1] * u ^ my_list[2]
        tmp = f.monomial_coefficient(mon) # take coefficient as begin
        # x*y -> u-1
        my_minus = min(my_list[0], my_list[1])
        my_list[0] -= my_minus
        my_list[1] -= my_minus
        tmp *= (u-1)^my_minus

        # rest
        tmp *= x ^ my_list[0] * y ^ my_list[1] * u ^ my_list[2]

        g += tmp
    return g

print()

m = 10

'''
m = 10: i = 0, 1, ... 85 6m48s
'''

tau = (2. - delta - 2. * beta) / (2. * beta)

t = round(tau * m)
print(f'{m = }, {t = }')

def show_lattice(L):
    L_vis = [['0' if x == 0 else 'X' for x in L_row] for L_row in L]
    L_vis = '\n'.join(' '.join(L_vis_row) for L_vis_row in L_vis)
    print(L_vis)

my_polynomials = []
my_monomials = []
for k in range(m+1):
    for i_1 in range(m-k+1):
        i_2 = 0
        i_3 = k
        g_ij = trans(e^(m-k) * x^i_1 * F(x, u)^k)
        my_polynomials.append(g_ij)
        my_monomials.append(x^i_1 * y^i_2 * u^i_3)

for i_2 in range(1, t+1):
    for k in range((m // t) * i_2, m+1):
        i_1 = 0
        i_3 = k
        h_ij = trans(e^(m-k) * y^i_2 * F(x, u)^k)
        my_polynomials.append(h_ij)
        my_monomials.append(x^i_1 * y^i_2 * u^i_3)

print(len(my_monomials))
print(my_monomials)
print(len(my_monomials))

my_nrows = len(my_polynomials)
my_ncols = len(my_monomials)

L = [[0 for j in range(my_ncols)] for i in range(my_nrows)]

for i in range(my_nrows):
    g_scale = my_polynomials[i](X * x, Y * y, U * u)
    for j in range(my_ncols):
        L[i][j] = g_scale.monomial_coefficient(my_monomials[j])

# show_lattice(L)

L = Matrix(ZZ, L)

my_nrows = L.nrows()

L = L.LLL()

# Recover
reduced_polynomials = []
for i in range(my_nrows):
    g_l = 0
    for j in range(my_ncols):
        g_l += L[i][j] // my_monomials[j](X, Y, U) * my_monomials[j]
    reduced_polynomials.append(g_l)


print()
print()
print()
# print(show_lattice(L))
# print(reduced_polynomials[0])

'''
perhaps failed...
need a docker
'''
my_ideal_list = reduced_polynomials[:85] 

# Variety
my_ideal_list = [u - (x * y + 1)] + [Hi.change_ring(QQ) for Hi in my_ideal_list]


print('Finding variety begin')
V = Ideal(my_ideal_list).variety(ring=ZZ) 
print('Finding variety end')

print(V)
with open('solution.txt', 'w') as f:
    f.write(str(V))

Then invert NTT.

from Crypto.Util.number import *

with open('output.txt', 'r') as f:
    s = f.read().splitlines()

N = eval(s[-2].split('=')[1])
e = eval(s[-1].split('=')[1])

y = 8300134433200911371454084976332034503390409169585505564996389860299079200426042224137407147310492419350999503509657918272483190349187151497714383983597615584912760668295526158952404190222826665445134832664816247898124958425909263437459015063666408210045342586629222466064
p_minus_q_square = y
p_plus_q_square = p_minus_q_square + 4 * N
p_minus_q = ZZ(p_minus_q_square.sqrt())
p_plus_q = ZZ(p_plus_q_square.sqrt())
p = (p_plus_q + p_minus_q) // 2
q = (p_plus_q - p_minus_q) // 2
d = inverse_mod(e, (p-1)*(q-1))

garbage_cipher = []
for i in range(65536):
    garbage_cipher.append(eval(s[i]))


print('decrypt RSA')
ZN = Zmod(N)
junk_cipher = [ZZ(ZN(c)^d) for c in garbage_cipher]


print('fast ntt')

p = 990367536408524906540912485167816012092796554403092639917950993714265910699138052663068131070259292593771612112016905904144038137551264432483487958987773403759866096258076571660618998739176702013853258687325567753038298889168254166361474202422033630403618955865472205722190830457928271527937
g = 745013838642250986737914025336862504661062017981819269513542907265222774830330586097756124678061002877695509685688964126565784246358161149675046363463274308162223776270434432888284419417479549219965033745142547821863438374478028783067286583042510995247992045551680383288951502770625897136683

Zp = Zmod(p)
g = Zp(g)

m_len = 65536

junk_cipher = list(map(Zp, junk_cipher))

def fast_ntt(some_list):
    if (len(some_list) == 1):
        return some_list
    
    fast_ntt_odd = fast_ntt(some_list[1::2])
    fast_ntt_even = fast_ntt(some_list[::2])
    aa = g^(m_len // len(some_list))
    trans_list = [fast_ntt_even[k] + aa^k * fast_ntt_odd[k] for k in range(len(some_list) // 2)] \
        + [fast_ntt_even[k] - aa^k * fast_ntt_odd[k] for k in range(len(some_list) // 2)]
    
    return trans_list

junk_msg = fast_ntt([junk_cipher[0]] + junk_cipher[1:][::-1])
junk_msg = [ZZ(jm / Zp(65536)) for jm in junk_msg]
junk_msg = [long_to_bytes(int(jm)) for jm in junk_msg]
print(len(junk_msg))
print(len(junk_msg[0]))
print(junk_msg[0])
print(len(junk_msg[1]))
msg = [junk_msg[i][i] for i in range(120)]
print(bytes(msg))

The script that generates the challenge data is:

...
m_len = 65536
a = g

def fast_ntt(some_list):
    if (len(some_list) == 1):
        return some_list
    
    fast_ntt_odd = fast_ntt(some_list[1::2])
    fast_ntt_even = fast_ntt(some_list[::2])
    aa = a^(m_len // len(some_list))
    trans_list = [fast_ntt_even[k] + aa^k * fast_ntt_odd[k] for k in range(len(some_list) // 2)] \
        + [fast_ntt_even[k] - aa^k * fast_ntt_odd[k] for k in range(len(some_list) // 2)]
    
    return trans_list

junk_cipher = fast_ntt(junk_msg)
junk_cipher = [ZZ(jc) for jc in junk_cipher]
...

Unintended solution: Inverse of Vandermonde Matrix

[Nepnep's solution](https://mp.weixin.qq.com/s?__biz=Mzg3NTEzOTA5Nw==&mid=2247484599&idx=1&sn=5e6d12173f562b970d2ea3725107087c&chksm=cec75dc1f9b0d4d7ab7bee851834254bda0c4e9598851e24767db97740a5467e289702051886&mpshare=1&scene=23&srcid=1214gqA5WDXloe03fUO2lcQX&sharer_sharetime=1671006648085&sharer_shareid=00bd6a7c2538caaa39f3bad1f17d776f#rd) (in Chinese)

[浅谈范德蒙德(Vandermonde)方阵的逆矩阵的求法以及快速傅里叶变换(FFT)中IDFT的原理](https://www.cnblogs.com/gzy-cjoier/p/9741950.html) (in Chinese)

## easyRSA

* solved: 22/363

For the v function, by observing and searching, you can learn that it is the [Lucas number](https://en.wikipedia.org/wiki/Lucas_number).

Further, you can find these papers:

[*A new attack on three variants of the RSA cryptosystem*](https://ro.uow.edu.au/cgi/viewcontent.cgi?article=6676&context=eispapers)
[*Cryptanalysis of RSA-type cryptosystems based on Lucas sequences, Gaussian integers and elliptic curves*
](https://www.sciencedirect.com/science/article/abs/pii/S2214212616302678)

Applying the continued fraction attack, we can obtain p and q.

The challenge actually is "Castagnos scheme", just implement the decryption in the paper. We can compute v function by matrix multiplication to avoid stack overflow.

The script that generates the challenge data is:

from random import randint
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from gmpy2 import lucasv_mod

def encrypt(m, e, N):
    c = (1 + m * N) * lucasv_mod(P, Q, e, N * N) % (N * N)
    return c

with open('flag.txt', 'rb') as f:
    flag = f.read()
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
N = p * q
d = getPrime(512)
e = inverse(d, (p * p - 1) * (q * q - 1))
#P = randint(2, N-1)
P = randint(2, 2**512)
Q = 1
c = encrypt(m, e, N)
# print(f"d = {d}")
# print(f"p = {p}")
# print(f"q = {q}")
# print(f"r = {P}")
print(f"e = {e}")
print(f"c = {c}")
print(f"N = {N}")

decrypt implementation:

from Crypto.Util.number import long_to_bytes, inverse
from gmpy2 import lucasv_mod, jacobi

def decrypt(c, p, q, N):
    ip = jacobi(c * c - 4, p)
    dp = inverse(e, p - ip)
    iq = jacobi(c * c - 4, q)
    dq = inverse(e, q - iq)
    rp = lucasv_mod(c, 1, dp, p)
    rq = lucasv_mod(c, 1, dq, q)
    p_ = inverse(p, q)
    r = (rp + p * (rp - rq) * p_) % N
    print(r)
    tp = c * inverse(lucasv_mod(r, 1, e, p * p), p * p) % (p * p)
    mp = ((tp - 1) // p) * inverse(q, p) % p
    tq = c * inverse(lucasv_mod(r, 1, e, q * q), q * q) % (q * q)
    mq = ((tq - 1) // q) * inverse(p, q) % q
    m = (mp + p * (mq - mp) * p_) % N
    return m

## super_guess

* solved: 4/363

t = randint(1, q)
u = (x * t - randint(1, q >> 2)) % q

Very difficult HNP. l is too small so we cannot recover x by common way.

We can brute-force the last few bytes of sorted key, solve HNP to find the other bytes.

One trick is *guess* that the last bytes is *Z*(with a probability of about one-third), and brute-force only 1 bytes, then we check if the characters are all in `ascii_uppercase + digits`. It can lead to a correct guess within a few tries.

from pwn import *
from ast import literal_eval
from string import ascii_uppercase, digits
from Crypto.Util.number import bytes_to_long, long_to_bytes
import time

def check(s):
    s = long_to_bytes(temp + lsb)
    for i in s:
        if i not in (ascii_uppercase.encode() + digits.encode() + b"rctf_"):
            return False
    return True

rounds = 1
find = False
while not find:
    start = time.time()
    print(f"rounds {rounds}")
    d = 90
    l = 2
    c = 56
    io = remote("190.92.233.181", 23334)
    q = Integer(io.recvline().strip().replace(b"q = ", b"").decode())
    T = literal_eval(io.recvline().strip().replace(b"T = ", b"").decode())
    U = literal_eval(io.recvline().strip().replace(b"U = ", b"").decode())
    print(f"q = {q}")
    block_B = identity_matrix(d) * 2^(l + 1) * q
    block_C = matrix(ZZ, d, 2, [0] * 2 * d)
    vector_t = matrix(ZZ, 1, d, [2^(l + 1) * T[i] for i in range(d)])
    vector_v = matrix(ZZ, 1, d, [2^(l + 1) * U[i] for i in range(d)]) + matrix(ZZ, 1, d, d * [q])
    block_D = block_matrix( [[vector_t],[vector_v]])
    block_E = matrix(ZZ, 2, 2, [2^c, 0, 0, q])
    for a in ascii_uppercase + digits:
        lsb = a + "Z_cfrt"
        lsb = Integer(bytes_to_long(lsb.encode()))
        vector_t_temp = 2^c * vector_t
        vector_v_temp = vector_v - lsb * vector_t
        block_D = block_matrix( [[vector_t_temp], [vector_v_temp]])
        block_E = matrix(ZZ, 2, 2, [2^c, 0, 0, q])
        M = block_matrix([[block_B, block_C], [block_D, block_E]])
        C = M.BKZ(block_size=20)
        for i in range(0, d + 2):
            temp = abs(floor(C[i][d]))
            if check(temp + lsb) and temp != 0:
                print(temp + lsb, long_to_bytes(temp + lsb))
                io.recvuntil(b"x = ")
                io.sendline(str(temp + lsb).encode())
                print(io.recvline())
                find = True
                break
    print(f"find: {find}")
    rounds += 1
    end = time.time()
    print(f"time: {end - start}")
    io.close()

As an aside, I noticed that we actually know more about x.



Maybe we can solve it as an EHNP problem? Please let me know if you have any progress on this!

## 花絮

10:01:02 Super Guesser got the third blood of Crypto super_guess