My-Public-CTF-Challenges

This is the repository of some CTF challenges I made, maybe including the source code and solution.

ToC

• AliyunCTF 2024
  • BabyDH 1
  • BabyDH 2
  • Doctored Dobbertin v2
• 0CTF/TCTF 2023
  • Double RSA 0/1/2/3
  • blocky-4.5 lite
  • blocky-4.5
  • Isolate
• AliyunCTF 2023
  • BabyPRNG
  • BabyAuth
• 0CTF/TCTF 2022
  • real magic dlog
  • Leopard
  • ezRSA++
  • Login
  • Chimera
• 0CTF/TCTF 2021 Finals
  • ezMat
  • ezHash
  • ezRSA
  • ezRSA+
  • halfhalf
• 0CTF/TCTF 2021 Quals
  • zer0lfsr-
  • zer0lfsr+
  • zer0lfsr++

AliyunCTF 2024

BabyDH 1

Category: Crypto
Difficulty: ★★
Solved: 8 / 94
Tag: Diffie–Hellman, Elliptic Curve, Coppersmith

Details

Source

Solution

中文 English

BabyDH 2

Category: Crypto
Difficulty: ★★★
Solved: 5 / 94
Tag: Diffie–Hellman, Elliptic Curve, ECHNP, Coppersmith

Details

Source

Solution

中文 English

Doctored Dobbertin v2

Category: Crypto
Difficulty: ★★☆
Solved: 2 / 94
Tag: Tweakable Block Cipher, AES, Backdoor

Details

Source

Solution

中文 English

0CTF/TCTF 2023

Double RSA 0/1/2/3

Category: Crypto
Difficulty: ★/★★/★★★/★★☆
Solved: (28/10/1/0) / 63
Tag: Smoothness, DLP, Lattice, HNP, EHNP, RSA
Hint released: Orthogonal lattice attack (for Double RSA 2)

Details

Source

The Double RSA series consists of 4 challenges. At first glance, the problem seems somewhat complex. So I highly recommend that you can read the code first, to better understand the following content.

In brief, the server will randomly generate a 1024-bit RSA key pair for Alice. And the client, namely, the player, can send Bob's RSA key (only the primes $p$ and $q$) to the server. Note that both the public exponents of Alice and Bob are random 329-bit prime numbers. There is also a multiple recursive generator with degree 6 in all challenges, $o=\sum_{i=0}^{5}a_is_i+b \mod p$ is the output.

Each challenge contains the following 4 phases:

• Encryption Query: Player can send any plaintext $m$ to the server, it will be encrypted, as $(m^{e_{a}'⊕\text{lcg.next()} }\mod n_{a})^{e_{b}'⊕ \text{lcg.next()}} \mod n_{b}$. Here $e_a'$ and $e_b'$ mean the updated public exponents of Alice and Bob respectively. Each time before the power-mod operation, the public exponents will be updated by XOR with the least 329 bits of the next output of lcg.
• Secret Query and Refresh: The server computes $(\text{secret}^{e_{a}} \mod n_{a})^{e_{b}'⊕ \text{lcg.next()}}\mod n_{b}$, and send it to client. Then the lcg will be refreshed, $a,b,s,p$ are changed, $e_b$ are also changed.
• Decryption Query: Player can send any non-repeating ciphertext $c$ to the server, it will be decrypted as $(c^{d_{a}}\mod n_{a})^{e_{b}'⊕ \text{lcg.next()}}\mod n_{b}$.
• Guess Secret: Player guess the value of secret, if correct, he will get the flag.

Solution

For Double RSA 0, $(a,s,b,p)$ and $(n_a,e_a)$ are known. So player just need to recover the value of $e_b$, then he can predict everything. The idea is to send two smooth primes (that is, $p-1$ and $q-1$ are products of small primes) to the server, so the descrete logarithm problem (DLP) over $Z_{n_b}$ is easy. For each ciphertext, we can get a equation like $m'^x\mod n_{b} =c$, where $m'$ can be computed, by solving the DLP, one can get $x$. Since $x={e_{b}'⊕\text{lcg.next()}}$, the value of current $e_{b}'$ is recovered. And one can predict the next updated value. The remaining part is trivial, as the params of refreshed lcg are also known.

For Double RSA 1, all $(a,s,b,p)$ are 512-bit numbers, $(a,b,p)$ are known. First, send -1 as the plaintext, with probability 1/2, we can get $C=(n_{a}-1)^{e_{b}'⊕\text{lcg.next()}}\mod n_{b}$. Pick a generator $g$ of $Z_{n_{b}}$, with probability $\frac{\lambda(p_{b}-1,q_{b}-1)}{n_{b}}$, $n_{a}-1$ can be represented as a element in the group generated by $g$, i.e., $g^{x}$, where $x$ is unknown. Once this condition holds, we can also rewrite $C$ as $g^{y}$ for some known $y$ by solving DLP. Note that the lcg only outputs 512-bit numbers, just regard the exponent part as a small unknown number $u$. Now, we have $g^{xu_i} = g^{y_i}\mod n_{b}$, which can be reduced to $u_i=y_ix'\mod \lambda$. Each $y_i$ is known, and each $u_i$ is small enough compared with the modulus, this is a standard hidden number problem (HNP), we can recover all $u_i$ and $x$ with the LLL algorithm, then we can also recover $n_{a}$. Note that each $u_i$ reveals the most significant bits (MSB) of the corresponding output of lcg, that's, $u_i=l_i+e_i$, $l_i$ is the lcg output, $e_i$ is an 329-bit small term. We can represent the initial state of the lcg as 6 variables $(s_0,\dots,s_5)$, then each $l_i$ can be rewrite as a linear combination of them, added with a constant, by constructing the corresponding lattice, the initial state of lcg can be recovered. Now we can predict the updated $e_{b}'$ and partially decrypt the encryped secret to get $S=\text{secret}^{e_{a}}\mod n_{a}$. Suppose secret is also in the group generated by $g$, we have $\text{secret}=g^z\mod n_{b}$. During the decryption query phase, just send $S,S^{3},S^{5}$ as the bit size of secret is only 64, we may get $g^{zv_0}=g^{w_0},g^{3zv_1}=g^{w_1},g^{5zv_2}=g^{w_2}$ for some small $v_i$, it is another instance of HNP, thus we can recover $z$ and then the secret.

For Double RSA 2, all $(a,s,b,p)$ are 1024-bit numbers, $(a,b,p)$ are known. In the first step, we can not reduce the recovery of $n_{a}-1$ to solving an HNP problem, since each $u_i$ is not small enough compared with the modulus in this case. The core lies in the first part, namely, recover the initial state of the lcg. And there are at least 3 different methods to solve this.

• My solution is the orthogonal lattice attack. From the previous analysis, we can learn each $l_i$ is a known linear combination of $s_j$ (0<=$j$<=5) added with a constant $b_i$, suppose the coefficient of each $s_j$ is $c_i^j$. Consider the matrix $\textbf{M}$ where each row is in the form of $(c_i^0,c_i^1,c_i^2,c_i^3,c_i^4,c_i^5,b_i)$, we can compute some short enough vectors $\textbf{v}_k$ which are orthogonal to each column by running the LLL algorithm. Note that we have $u_i=l_i+e_i\mod \lambda$, and $xu_i=y_i\mod \lambda$. Expand it and get $x(c_i^0s_0+c_i^1s_1+c_i^2s_2+c_i^3s_3+c_i^4s_4+c_i^5s_5+b_i+e_i-t_ip)=y_i\mod \lambda$, let $\textbf{y}=(y_0,y_1,\dots,y_i)$, for each $\textbf{v}_k$, compute $w_k=\langle \textbf{v}_k, \textbf{y} \rangle$, the coefficient of each $s_j$ will be annihilated, so we get an equation like $w_k=x(e'_k+t'_kp)\mod \lambda$, rewrite it as $w_kx'-t'_kp=e'_k\mod \lambda$, if $\textbf{y}_k$ is short enough, $e_k',t_k'$ will be small, so this is an instance of extended hidden number problem with two holes ($x'$ and $t'_k$), one can solve it via lattice reduction. The recovery of initial state is simialr as Double RSA 1.
• The second approach is provided by @PhiQuadro and @Genni from Team mhackeroni. In my method, I assume $n_a-1=g^x$ for some $x$, but what if $n_a-1$ is exactly a generator of $Z_{n_b}$? In this case, we have $x=1$, so the equation becomes $(c_i^0s_0+c_i^1s_1+c_i^2s_2+c_i^3s_3+c_i^4s_4+c_i^5s_5+b_i+e_i)\mod p =y_i \mod \lambda $, where all $s_i$, $y_i$, $e_i$ are unknown. First, we can remove the $\lambda$ in the rhs by replacing $y_i \mod \lambda$ with $Y_i$, to get an equation modulo $p$ with 8 variables, and then store all these equations. Then, we can extract some extra information about each $Y_i$ from the ciphertexts $C_i$. Specifically, we can solve the DLP between $C_0$ and $C_i$ ($1&lt;=i$), if $C_0^{w_i}=C_i\mod n_{b}$, then $Y_0w_i-Y_i=0\mod \lambda$, and we can store these equations as well. Now we can construct a lattice where each column corresponds to a stored equation, and run the LLL algorithm to recover all variables.
• The third approach is provided by @Neobeo from Team Friendly Maltese Citizens. The lattice he constructed is [[A,B,B],[0,C,C],[0,0,D]], where A is an identity matrix, B is the matrix whose columns are the coefficients vectors $(c_i^0,c_i^1,c_i^2,c_i^3,c_i^4,c_i^5,b_i)$, C is an diagonal matrix whose diagonal entries are $p$, and D is the matrix constructed from the above equations $Y_0w_i-Y_i=0\mod \lambda$ (namely, the first row is $(1,w_1,w_2,\dots,w_i)$, the second row is $(0,\lambda,0,\dots,0)$, the last row is $(0,\dots,0,\lambda)$). To make the size of each entry in the target vector balanced, one should also multiply each column with the corresponding weight.

During the decryption phase, each ciphertext can only be sent once, and secret is 512 bit this time, we can not just send $S,S^3,S^5$, as the decryption results exceed the modulus $n_{a}$. Instead, we need to obtain the encryption result of some value $f$ under Alice's key, denoted as $F=f^{e_{a}}\mod n_{a}$, so we can send $SF,SF^3,SF^5...$. To get $F$, just send $f$ repeatedly during the first phase, each time, we partially decrypt the result, and get an equation $f^{e_{a}⊕r_i}=m'i\mod n{a}$, where only $e_{a}$ is unkown. We can rewrite each term $r_i$ in binary digits and find a linear combination of them which yields a small value, then we can recover $F$ ($e_{a}$ can also be recovered, by not necessary), one may refer to the writeup of the challenge in TetCTF 2022 by @hellman for details. Finally, during the decryption query phase, we can obtain the params of refreshed lcg as well as the MSBs of its outputs, it is easy to recover the state and the secret.

For Double RSA 3, as no one has solved it Team Kalmarunionen solved this about 4 hours after the end of the competition, directly revealing the answer would take away much of the fun. So I just release a hint here, you may read the paper [1].

Epilogue

I underestimated the difficulty of this series of tasks. I originally thought Double RSA 1 is an easy task, but only 11 teams solved it. And for Double RSA 2/3, I expected that 4-5 teams could solve them. Personally, I favor Double RSA 2 the most. As far as I know, there are no prior works that have studied the similar problems. It feels great to solve such an challenge on your own.

Reference
[1] YU, Hanbing, and ZHENG Qunxiong. "A Lattice-Based Method for Recovering the Unknown Parameters of Truncated Multiple Recursive Generators with Constant." Chinese Journal of Electronics 33 (2023): 1-10.

blocky-4.5 lite

Category: Crypto
Difficulty: ★★
Solved: 9 / 63
Tag: SPN, AES, Square Attack

Details

Source

This task is based on the challenge blocky-5 (and blocky-4) in pbctf 2023. I removed the mixcolumn operation of the last two rounds, that's why the new cipher is named blocky-4.5. This task is the easier version. The remote server will create an instance of this cipher with unknown master key, you are allowed to perform at most 132 operations of chosen-plaintext encryption or chosen-ciphertext decryption, then you need to recover the master key within 133s to get the flag.

Solution

The solution is not unique. One can still break this cipher using the square attack, you may refer to the solution for Arsenal in 0CTF 2016 Quals.

blocky-4.5

Category: Crypto
Difficulty: ★★★★
Solved: 2 / 63
Tag: SPN, AES, Differential Cryptanalysis

Details

Source

This task is similar to the previous one. But this time, we are only allowed to perform at most 12 operations of either known-plaintext encryption or chosen-ciphertext decryption. And we need to recover the master key within 13s.

Solution

The solution of this challenge is not unique, but it basically relies on the differential cryptanalysis. As the server only allows chosen-ciphertext decryption, we need to launch the differential attack from the backward direction. Two teams solved this task with similar methods.

• The first method is proposed by @RBTree and @JOHNKRAM from Team Blue Water. The cipher can be decomposed as E2 ○ E1, where E1 is the first 1.5 rounds (full round 1 + round 2 ARK + round 2 SB) and E2 is the remaining part. One can construct a pair of ciphertexts C1/C2 that only differ on bytes 0/4/8, and get the corresponding decrypted plaintexts P1/P2. Now, consider the partially decrypted results of C1/C2, namely, C1'=E2_inv(C1) and C2'=E2_inv(C2), one can find the difference of C1' and C2' will be D=[[a*x1,b*x2,c*x3],[a*x3,b*x1,c*x2],[a*x2,b*x3,c*x1]], where a=86, b=222, c=148. Next, one can bruteforce subkey[0][0], subkey[0][4], subkey[0][8] to get C1'[0] and C2'[0] from the encryption direction, since subkey[1][0] only depends on subkey[0][0] and subkey[0][8]. For each guess, one can find a corresponding x1. Similarly, bruteforce subkey[0][1], subkey[0][6], subkey[0][7], subkeys[1][4], then one can get C1'[4] and C2'[4], thus can find another candidate for x1. For the correct guess, the two values must be the same. With enough plaintext/ciphertext pairs, one can filter out the wrong answers and obtain the correct key.
• The second method is proposed by @hellman from Team More Smoked Leet Chicken. He used a second-order differential cryptanalysis. The cipher can be decomposed as E2 ○ E1, where E1 is the first 1.5 rounds (full round 1 + round 2 AK + round2 SB) and E2 is the remaining part. Then, construct four ciphertexts C1/C2/C3/C4, where C1 and C2 have the difference a at byte 0, C1/C3 have the difference b at byte 1, C1/C4 have the difference a at byte 0 and the difference b at byte 1. We can get the decryption results, denoted as P1/P2/P3/P4. Consider the partially decrypted results of the ciphertexts, namely, C'= E2_inv(C), for each byte at position i, we have C4'[i]-C3'[i]-C2'[i]+C1'[i]=0. Thus one can bruteforce 3 bytes of the first round key and then 1 byte of the second round key which makes the previous condition hold can be determined, note that the candidate may not be unique. With enough plaintext and ciphertext pairs, one can find the correct answer.

Isolate

Category: Crypto
Difficulty: ★★★☆
Solved: 2 / 63
Tag: Isogeny, SIDH

Details

Source

This task is based on the challenge S1DH in starCTF 2023. The SageMath script performs a standard supersingular isogeny key exchange (SIDH) between Alice and Bob over a non-standard curve, namely, it sets a=147, b=94, p=2^a*3^b-1. Our goal is to recover both the secret keys of Alice and Bob from the standard transcript data in SIDH.

Solution

To recover Bob's secret key, one can directly follow the solution of the original task.

The main challenge lies in recovering Alice's secret key, which requires us to compute a (3-3) isogeny chain. Fortunately, Thomas and Sabrina have already proposed an efficient computation of this [1], and a MAGMA implementation of this attack has been provided. Thus, you need to understand the attack procedure, and tweak some parameters. In fact, you can just regard Thomas and Sabrina's algorithm as a black box, and you only need to find the proper input. First, we need to find a suitable a', b' and d, which makes the endomorphism of the starting curve with degree c=3^(b-b')-d*2^(a-a') can be efficiently computed. One may set a',b',das 3,0,10 (my solution) or 2,0,5 (choosed by Team organizer and Kalmarunionen). Both settings require us to guess a' steps of Alice’s isogeny, and there seems to be some issues in the function IsogenyFromKernel in MAGMA, so all of us implement this part in SageMath. Then, you can follow the idea in [2] (Algorithm 2), to recover the auxiliary information. Finally, recover a generator of the kernel of Alice's isogeny using the MAGMA script.

Reference
[1] DECRU Thomas, and KUNZWEILER Sabrina. "Efficient computation of $(3^ n, 3^ n) $-isogenies." Cryptology ePrint Archive (2023).

[1] MAINO, Luciano, CHLOE Martindale, PANNY Lorenz, POPE Giacomo, and WESOLOWSKI Benjamin. "A direct key recovery attack on SIDH." In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 448-471. Cham: Springer Nature Switzerland, 2023.

AliyunCTF 2023

BabyPRNG

Category: Crypto
Difficulty: ★★★
Solved: 2 / 109
Tag: PRNG, Elliptic Curve, Lattice

Details

Source

Solution

中文 English

BabyAuth

Category: Crypto
Difficulty: ★★★☆
Solved: 4 / 109
Tag: CBC, DSA, Lattice

Details

Source

Solution

中文 English

0CTF/TCTF 2022

real-magic-dlog

Category: Crypto
Difficulty: ★
Solved: 66 / 158
Tag: Smoothness, Coppersmith

Details

Source

This challenge is based on HITCON CTF 2021 magic dlog, but we add a 60-seconds limit this time. According to its author @lyc, the intended solution is [1]. But many players solved it with simple brute-force attack, i.e., randomly generating numbers and hope it is smooth enough.

Solution

I underestimate the success rate of the original brute-force method, so it also works for this challenge. The intended solution is to implement the algorithm in [1]. But in our case, it can not guarantee the full smoothness of the output number, the number always contains one or two large factors. So, we hope these factors are not too large, then the DLP can be solved within 1 minute. Another trick is the parameter setting, the algorithm works better if we set S (for details, see [1]) as the product of first 45 primes, I don't know why.

Reference
[1] Boneh, Dan. "Finding smooth integers in short intervals using CRT decoding." Proceedings of the thirty-second annual ACM symposium on Theory of computing. 2000.

Leopard

Category: Crypto
Difficulty: ★★☆
Solved: 6 / 158
Tag: AEAD, Algebraic Attack

Details

Source

This challenge implements a homemade AEAD scheme named Leopard, which is inspired from an AEAD scheme called Panther [1]. Note that Panther suffers from a straightforward attack [2], while Leopard has been patched. And in this challenge, we are asked to apply the differential fault analysis on Leopard. Specifically, given a fixed plaintext, its ciphertext as well as a fault ciphertext, one should recover the secret key and IV within 300s.

Solution

There are at least three methods to solve this task.

• Approach 1 (team More Smoked Leet Chicken): This is an algebraic attack, and it is the intended solution. The SBOX of Leopard is not generated in the same way as the SBOX of AES. One can check this wiki page, note that the linear transform is done over $\mathbb{F}{2}^8$. But in this challenge, one can figure out the linear transform is actually done over $\mathbb{F}{2^8}$, it can be represented as SBOX[x]=55/x+186. Now consider the internal state of the cipher just before the fault will be injected, partial state are known to us since they are equal to the ciphertext bytes, so we can treat the remaining unknown state bytes as variables over $\mathbb{F}_{2^8}$, then simulate the state update function locally. And we can get several equations in the form as 55/f(x_0,x_1,...)+186=ct[i]+pt[i], SageMath keeps these equations in fraction form, but we can extract the numerator part of the fraction, which yields a multivariate equation. After collecting enough equations, we can find the roots with Gröbner basis. The fault is used to providing more equations.
• Approach 2 (team perfect r00t): This is a SAT-based solution, one can check here.
• Approach 3 (other teams): This is a guess-and-determine attack, which exploits the internal state update function. Several players shared their codes in Discord channel, but there are no detailed writeups now. If you have a detailed analysis, please contact me :)

Reference
[1] Bhargavi, K. V. L., Chungath Srinivasan, and K. V. Lakshmy. "Panther: A Sponge Based Lightweight Authenticated Encryption Scheme." International Conference on Cryptology in India. Springer, Cham, 2021.
[2] Boura, Christina, Rachelle Heim Boissier, and Yann Rotella. "Breaking Panther." Cryptology ePrint Archive (2022).

ezRSA++

Category: Crypto
Difficulty: ★★★☆
Solved: 4 / 158
Tag: RSA, Coppersmith

Details

Source

This challenge is based on 0CTF/TCTF 2021 Finals ezRSA+. We are given an CRT-RSA public key where N and e are around 2000 bits. We also know both dp and dq are 105 bits, and we are given 55 LSBs of them.

Solution

• Approach 1 (team idek): This is the intended solution, just implement the algorithm in the paper [1]. @gripingberry has released his neat [code] (https://gist.github.com/willfisher/79292934bf2a08cc41174619ae69a70c).
• Approach 2 (team Super Guesser and team Straw Hat): Please read rkm's writeup.

Reference
[1] May, Alexander, Julian Nowakowski, and Santanu Sarkar. "Partial Key Exposure Attack on Short Secret Exponent CRT-RSA.

Login

Category: Crypto
Difficulty: ★★☆
Solved: 2 / 158
Tag: Lattice, RLWE, IPFE

Details

Source

This challenge implements an RLWE-based inner-product functional encryption scheme. You have to login as player at first then login as admin to get flag. The scheme is modified from [1].

Solution

The original scheme encodes a l-dimension vector to l polynomials, and this is provably secure. But in this task, both the vectors x and y are treated as one polynomial X and Y, it is possible to recover y from the coefficients of the result X*Y with some linear algebra when x is known. One may refer to perfect r00t 's writeup for detials

Reference
[1] Mera, Jose Maria Bermudo, et al. "Efficient lattice-based inner-product functional encryption." IACR International Conference on Public-Key Cryptography. Springer, Cham, 2022.

Chimera

Category: Crypto
Difficulty: ★★★★☆
Solved: 0 / 158
Tag: Feistel, SPN, Boomerang Attack

Details

Source

This challenge implements a homemade block cipher named Chimera. The 16-bytes plain text will be encrypted by two parallel 4-rounds DES-like cipher, then permutated, and finally encrypted by a 4-rounds (without shift rows in first round) AES-like cipher. One can set one byte among the master keys of three components to a specified byte of flag. And the server provide an encryption oracle as well as a decryption oracle. The time limit is 300 seconds, and one can call encryption/decryption oracles for 16-bytes input plaintext at most 8192 times.

Solution

The intended solution is a combination of differential cryptanalysis of the Feistel cipher [1] and Yoyo tricks with the SPN [2], which can be regarded as a retracing boomerang attack [3]. The basic idea is to find a differential path of one of the Feistel cipher such that the non-zero bytes in the output differential after the permutation are placed in one column of the input to SPN, then the condition of Yoyo tricks will be satisfied. And one may hope when decryption, the input difference of another Feistel cipher are exactly zero, thus the right half of two plaintexts are the same. Once this happens, the differential path of the first Feistel cipher is likely activated, and we can extract some bytes of the first round key, since the input as well as the difference of the output of first round function are known. Detailed writeup is coming soon...

Reference
[1] Biham, Eli, and Adi Shamir. Differential cryptanalysis of the data encryption standard. Springer Science & Business Media, 2012.
[2] Rønjom, Sondre, Navid Ghaedi Bardeh, and Tor Helleseth. "Yoyo tricks with AES." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2017.
[3] Dunkelman, Orr, et al. "The retracing boomerang attack." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2020.

0CTF/TCTF 2021 Finals

ezMat

Category: Crypto
Difficulty: ★
Solved: 12 / 12
Tag: Matrix, Linear Algebra

Details

Source

This task is inspired from the challenge Onclude in Crypto CTF 2021. The ciphertext computes as E = L_inv * S * X = U * X = U * (A + R), we know E and R, need to recover A. And U is the LU decomposition of a secret matrix, A is a matrix which contains most of zero and flag bytes. We are also given a sha256 digest of flag.

Solution

Notice that U is a triangular matrix, and there are lots of zero elements in A, thus we may solve linear equations to recover most elements in A, then bruteforce the remaining bytes according to the given sha256 digest.

ezHash

Category: Crypto
Difficulty: ★★★☆
Solved: 3 / 12
Tag: Matrix, LPS Graph

Details

Source

The script implements an algorithm involves 2x2 matrix multiplication over Fp. Our input will be converted to base 5 sequence, then each time choose one of the six generator matrix multiple to the result according to the sequence. The server will generate a random matrix X per connection, we have 10 seconds to find an input which yields a matrix Y, where Y ≡ aX (mod p) for some a ∈ Fp.

Solution

In fact, the algorithm is a hash function based on LPS graph. This paper [1] describes a preimage attack, just implement it.

Reference
[1] Petit, Christophe, Kristin Lauter, and Jean-Jacques Quisquater. "Full cryptanalysis of LPS and Morgenstern hash functions." International Conference on Security and Cryptography for Networks. Springer, Berlin, Heidelberg, 2008.

ezRSA

Category: Crypto
Difficulty: ★★
Solved: 11 / 12
Tag: RSA, Hint

Details

Source

The script generates a CRT-RSA key pair, where n is 2000 bits, e is 1000 bits, dp, dq, k, l are only 60 bits, then encrypt the flag. We are given the public key, encrypted flag and the lowest 10 bits of both dp dq as well as a magic number m = 1337 * k ** 4 + 7331 * l ** 3 + 73331 * k ** 2 + 13337 * l ** 2 + 7 * k * l + 2 * k + l.

Solution

Take 4th root of m // 1337 may get an approximation of k, then search in a small range, for each candidate k_bar, take 3th root of (m - 1337 * k_bar ** 4) // 7331 to get an approximation of l, then search again and use m to determine l and k. As k * p - k = e * dp - 1, we can recover p, then decrypt flag.

ezRSA+

Category: Crypto
Difficulty: ★★☆
Solved: 6 / 12
Tag: RSA, Lattice, Continued Fraction

Details

Source

Same as ezRSA, but no magic numebr m, and we get the lowest 12 bits of both dp dq.

Solution

• Approach 1: After some arithmetic, we have e * e * X + e * Y + Z = W * n, where X = dp * dq,Y = dp * (l - 1) + dq * (k - 1), Z = (k - 1) * (l - 1), W = k * l. Notice that X, Y, Z, W are small enough, so we can construct a lattice where the first column is [n, -e^2, -e], then apply LLL to get k and l, which leads to factor n.
• Approach 2: Notice dp and dq are small enough, we may apply Wiener's attack, to get X = dp * dq (for data in this task, X = dp * dq // 3) from the continued fraction of e * e / N. Then we may guess dp from the factors of X, and recover p via GCD(pow(pow(2, e, n), dp, n) - 2, n) .
• Approach 3: Both the above methods are unintended, intended solution involves a Partial Key Exposure attack on CRT-RSA [1] or a small CRT-Exponent attack (slower) [2].

Reference
[1] May, Alexander, Julian Nowakowski, and Santanu Sarkar. "Partial Key Exposure Attack on Short Secret Exponent CRT-RSA.
[2] Takayasu, Atsushi, Yao Lu, and Liqiang Peng. "Small CRT-exponent RSA revisited." Journal of Cryptology 32.4 (2019): 1337-1382.

halfhalf

Category: Reverse
Difficulty: ★★☆
Solved: 7 / 12
Tag: Rust, Jacobi Symbol

Details

Source

We are given a Rust ELF file. It requires you solve a PoW, then input a magic word, next the server will generate a RSA key and a secret number. You can interact with server, there are five options: Get the RSA modulus; Guess the secret; Reset secret; Get flag; Exit. Each time you input a guess, the server may encrypt9x^2 or 18x^2 for some random x, which depends whether your guess is greater than the secret. And if your guess is same as the secret you may get the flag. Note that all the number should be encoded with emoji.

Solution

The PoW requires us to find a 4-byte phrase whose sha256 digest match the given value for the last 3 bytes. And it is easy to find the magic word, which are a series of emoji. To distinguish 9x^2 and 18x^2, we can compute its Jacobi symbol, so a binary search can determine the secret and get the flag.

Issues

• I deployed this challenge with xinetd, due to a mistake in the wrapper, the program is executed under root directory, so it can't read the flag from file. Thanks @FORMALIN for pointing out this.
• @RBTree tells me the 60s time limitation is too tight, and he asks to increase it. But the source code of this challenge is lost, due to a VM broken, so the only way is to patch the binary. And he quickly finds the location of the corresponding parameters, then I patch it from 60s to 200s. Thanks RBTree's help.

0CTF/TCTF 2021 Quals

zer0lfsr-

Category: Crypto
Difficulty: ★★
Solved: 35 / 198
Tag: LFSR, NFSR, Z3

Details

Source

There are three generators composed of LFSR or NFSR.

• Generator1 contains a 48-bit NFSR and a 16-bit LFSR

• Generator2 contains a 16-bit NFSR and a 48-bit LFSR

• Generator3 contains a 64-bit LFSR

The output functions of each generator are filted, which are not linear from its internal state. We are asked to recover the initial state of any two generators within 50 seconds after obtained its consecutive 5000-byte output and the hash digest of its initial state.

Solution

Most teams choose to attack Generator1 and Generator3.

• Approach 1: Use z3
• Approach 2: See rkm's writeup for details

zer0lfsr+

Category: Crypto
Difficulty: ★★★★
Solved: 2 / 198
Tag: LFSR, NFSR, FCA

Details

Source

The three generators remain unchanged. But we are given 20000 bytes from the majority function of the output of three generators, and are required to recover all the initial states within 100s. The initial state of Generator2 is derived from Generator1 with KDF function, the initial state of Generator3 is derived from Generator2 with KDF function.

Solution

Please check rkm's writeup for details.

zer0lfsr++

Category: Crypto
Difficulty: ★★★★★
Solved: 1 / 198
Tag: LFSR, NFSR, FCA

Details

Source

Same as zer0lfsr+, but there are no KDF, three initial states are independent. And we have a hint, can get the highest 16 bits of one of the three state.

Solution

• FCA attack recover full state of Generator3.
• FCA attack recover the LFSR state of Generator2 and use the hint to get the NFSR state of Generator2.
• Similar attack in [1] to recover full state of Generator1.

Reference
[1] Berbain, Côme, Henri Gilbert, and Alexander Maximov. "Cryptanalysis of grain." International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, 2006.