# zer0pts CTF 2020 writeup
* 原文 (日本語) はこちら The original Japanese version is here:
* https://hackmd.io/@hakatashi/Syck8VfSL
## ROR (Crypto, 260pts)
* `len(m)` count of RSA ciphertexts are given, which is the result of encryption of the `i`-bit-right-rotate-shifted values of plaintext $m$.
* $N=2^{n_1}3^{n_2}7^{n_3},e$ is unknown
### Solution
* $N$ is the even number, so the evens will be encrypted to the evens and the odds be the odds
`zer0pts{0h_1t_l34ks_th3_l34st_s1gn1f1c4nt_b1t}`
{%gist hakatashi/fac3ce50f0e7febc4db7f5d7768246d9 %}
## nibelung (Crypto, 525pts)
* A common key cryptosystem is defined by the operations on the general linear group of 6th-degree $GL_6(F_p)$ on $F_p$ ($p$: 512bit)
* $p$ is reset to the random primes per connection.
* $U$ as the secret key, $U\cdot X\cdot U^{-1}$ is encryption and $U^{-1}\cdot X\cdot U$ is depcyption.
* We can encrypt/decrypt any value $X$ with all the elements is less than 256.
* The encrypted flag value is given.
### Solution
* General linear group is obviously linear as its name suggests, so I can retrieve the result of encryption of unit vector for all the elements in the matrix and solve it with linear modular equation.
`zer0pts{r1ng_h0m0m0rph1sm_1s_c00l}`
{%gist hakatashi/de69225d17617a0fd8c75c484d3ca6af %}
## diysig (Crypto, 394pts)
* RSA and the mysterious hash function is implemented
* We can encrypt any data and get its hash
* We can get hash of the result of the decryption of any data
* $N,e$ is known. $N$: 1024bit, $e=65537$
* The hash function is as follows:
```python
def _hash(self, m):
""" DIY Hash Function """
H = 0xcafebabe
M = m
# Stage 1
while M > 0:
H = (((H << 5) + H) + (M & 0xFFFFFFFF)) & 0xFFFFFFFF
M >>= 32
# Stage 2
M = H
while M > 0:
H = ((M & 0xFF) + (H << 6) + (H << 16) - H) & 0xFFFFFFFF
M >>= 8
# Stage 3
H = H | 1 if m & 1 else H & 0xfffffffe
return H
```
### Solution
* The hash funciton is somewhat tricky, but the awful thing is that they repaint the LSB of the hash value with the one of the input $m$.
* So we can know the LSB of the result of decryption of any data.
* **LSB Decryption Oracle Attack** can be applied
`zer0pts{n3v3r_r3v34l_7h3_LSB}`
{%gist hakatashi/0c30ac59b88927a452903f94d5a6f490 %}
I connect on the server 1024 times and worried if I may be banned :)
## dirty laundary (Crypto, 636pts)
* Shamir's Secret Sharing Scheme and Paillier cryptosystem combined
* The quadratic polynomial $f(x)$ on $F_p$ is randomly generated and the result of $y = f(x)$ is calculated for each $x=1\sim5$. All shares are given so we should decrypt SSSS immediately but funky noises are added to $y$ and it's encrypted with Paillier cryptosystem, so we cannot decrypt it.
* The following values are random-generated among encryption:
* The coefficients $a,b,c$ in the polynomial of SSSS and modulus $p$ (all with 1024bits, c is the flag)
$f(x)=ax^2+bx+c\bmod p$
* The noises added to secret shares, $e_i$ (256bit)
$y_i=f(x_i)+e_i\:(x_i=1,2,3,4,5)$
* The prime factors $p_i,q_i$ (1024bit, 512bit) of the modulus $N_i$ in the Paillier cryptosystem
$N_i=p_iq_i\:(p_i\approx p+e_i)$
* The coefficients $k_i$ (256bit) of Paillier cryptosystem
$g_i=1+k_iN_i\bmod N_i^2$
* The random value $r_i$ (256bit) introduced in Paillier cryptosystem
$c_i=g_i^{y_i}r_i^{N_i}\bmod N_i^2$
* $N_i,g_i,c_i$ are given
### Solution
On closer inspection, $e_i$: 256bit is a bit small compared to $p$: 1024bit which satisfies $p_i\approx p+e_i$. Thus about 75% of the highest bits of the five $N_i$ are shared. It smells like lattice-y :sunglasses:
I dunno the appliable method for this situation, but I googled some and found [this paper](https://hal.archives-ouvertes.fr/hal-01288914/document) that can hint me (this is paper in 2010. cool)
According to the paper, when the size of $q$ is $\alpha$ bits and the $t$ bits of LSB of $p$ is shared for $k$ RSA public keys, it should satisfy
$$t\geqq\frac{k}{k-1}\alpha$$
to be broken with lattices. In this challenge the coefficients are $t=768,\alpha=512,k=5$ so the constraint is satisfied.
We consider the following lattice (with row vectors) reffering to the paper:
$$
\mathcal{L}=\left[\begin{array}{ccccccccccccccc}
K & 0 & 0 & 0 & 0 & N_{2} & N_{3} & N_{4} & N_{5} & 0 & 0 & 0 & 0 & 0 & 0\\
0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & 0 & N_{3} & N_{4} & N_{5} & 0 & 0 & 0\\
0 & 0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & -N_{2} & 0 & 0 & N_{4} & N_{5} & 0\\
0 & 0 & 0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & -N_{2} & 0 & -N_{3} & 0 & N_{5}\\
0 & 0 & 0 & 0 & K & 0 & 0 & 0 & -N_{1} & 0 & 0 & -N_{2} & 0 & -N_{3} & -N_{4}
\end{array}\right]
$$
where $K$ is $K=2^{n-t}$ with $n$ as the size of $N$. Then the coefficients of base vectors of the shortest vector will become $q_1,\cdots,q_5$, and $N_i$ can be factorized. This can be achieved by applying LLL and solve SVP, and inspect the leading 5 elements of the shortest vector.
Now we have prime factors of $N_i$. Then Paillier cryptosystem can be decrypted ($k_i$ can be retrieved from the basis of $g_i=1+k_iN_i$) so we also have $y_i$.
By denoting $p_i$ as $p_i=p+e_i+\delta_i\:(\delta_i<\text{approx 1000})$ and organizing the equations around $f(x)$, we get:
$$
\begin{aligned}
f\left(1\right)-\delta_{1} &=y_{1}-p_{1}\bmod p\\
f\left(2\right)-\delta_{2} &=y_{2}-p_{2}\bmod p\\
f\left(3\right)-\delta_{3} &=y_{3}-p_{3}\bmod p\\
f\left(4\right)-\delta_{4} &=y_{4}-p_{4}\bmod p\\
f\left(5\right)-\delta_{5} &=y_{5}-p_{5}\bmod p\\
\end{aligned}
$$
By the way the following is satisfied:
$$
\begin{aligned}
f\left(1\right)-3f\left(2\right)+3f\left(3\right)-f\left(4\right)=&\left(a+b+c\right)-3\left(4a+2b+c\right)\\
&+3\left(9a+3b+c\right)-\left(16a+4b+c\right)\\
=&0
\end{aligned}
$$
so if we define $d_i$ as $d_i:=y_i-p_i$:
$$
d_1-3d_2+3d_3-d_4=kp-\delta_1+3\delta_2-3\delta_3+\delta_4\:(k\in\mathbb{Z})
$$
we can get the good approximate value of the small multiple of $p$. Actually, $k$ was $1$ in this chal.
And also:
$$
\begin{aligned}
3f\left(1\right)-3f\left(2\right)+f\left(3\right)=&3\left(a+b+c\right)-3\left(4a+2b+c\right)\\
&+\left(9a+3b+c\right)\\
=&c
\end{aligned}
$$
then if we calculate the following:
$$
3d_1-3d_2+d_3\bmod p=c-3\delta_1+3\delta_2-\delta_3
$$
with the approximate value of $p$ above, we can get
```
c = 20713161535193761558784128809506534938870667474516138291919014014508231236559472271196444472147718083977745751388526121905625505
```
as the approximate solution of $c$. Convert it to string and we get:
```
"zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!\x19\xA1"
```
Guess its some least bits and the flag is:
`zer0pts{excellent_w0rk!y0u_are_a_master_0f_crypt0!!!}`
{%gist hakatashi/0fce3ea3e73c4ef1615108594ed46b2e %}