# 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 %}