In this competition, NeSE solved all the reversing , misc , crypto challenges and won the championship. Here are the detailed writeups of three crypto challenges.
brandnew check-in
Source Code
1 | from Crypto.Util.number import * |
Solution
By the description : cakectf brand_new_crypto
, I went for Google to browse the writeup and found this one : CakeCTF 2022 Writeup. We can use the extended Euclid algorithm to obtain x,y such that : . Therefore, , we can brute force to recover the and use the to verify the original equations : . By this method, we can recover all the and if .
Now, we have recovered the encrypted flag : . Notice that is generated with getrandbits(1024)
, we can fully recover MT19937 state and then backtrack to find parameters or even . Here, parameter is easy to locate because it is exactly the previous 1024 bits of . The most important point of recovering MT state is that our recovered . Therefore, each has 2~3 possible values and we need 20 consecutive parameters to reconstruct MT state and another 20 consecutive parameters to verify (if not verified, there might be multiple solutions). I found the minimal brute-forcing space is .
After we recovered , . Therefore, we can obtain and derive the private key to decrypt .
EXP
1 | from ast import literal_eval |
MT Cracker (offset = 48, the brute-forcing space is minimal, 12 cores multi-process, time cost : 6 minutes):
1 | # Initialise rng (random.getrandbits) |
1 | [+] Brute forcing space 7962624 23 |
1 | data = res_list # results from above MT state |
ezdlp
Source Code
1 | from Crypto.Util.number import * |
Solution
Use lattice and gcd to recover the correct modulo . Since has a semi-smooth order prime () , we can use Pollard p-1 algorithm to factorize and Pohlig-Hellman algorithm to compute the discrete logarithm to obtain flag.
Recover modulo N
The first step to recover the modulo N. Since the exponent is too large to be computed in Integer Ring, we can construct a lattice to narrow down the exponents. The lattice is as follows:
Apply LLL algorithm to M: . Denoting as the ith row of , we have the following equations :
In (2), if , place it on the left side; if , place it on the right side. Now every parameter is positive, and we exponentiate both sides of the equation with base = 0x10001
and then subtract them to get integer multiples of modulo . We can compute and then filter all the small factors to recover the real modulo (about 1034 bits).
Semi-Smooth Factorization and Discrete Logarithm
If we simply run Pollard’s p-1 algorithm on , it costs about 10 hours in sage with time complexity . This TCC paper explains the concept of semi-smooth and related factorization attacks. Yafu
implements such factorization. Assume the two bounds for semi-smooth order prime are : , the time complexity is . In the challenge, the time complexity is .
For yafu
, the max bound is and for , the upper bound should be . If you find that with correct you can’t obtain the factorization, you can increase the bound a little and run again.
The yafu
documentation of pm1
:
[pm1]
usage: pm1(expression)description:
New in version 1.28: uses GMP-ECM exclusively. Stage 1 bound is configurable using
the POLLARD_STG1_MAX parameter. The default is 100000. Stage 2 bound is also
configurable using the POLLARD_STG2_MAX parameter.To use the default B2 with gmp-ecm, simply do not specify the B2ecm or B2pp1 or B2pm1
flags in the .ini file or in the command line arguments.
Specifying B2 as well will cause the default value to be overridden.command line flags affecting pm1:
-B1pm1
B1 bound in the pm1 method
-B2pm1B2 bound in the pm1 method
Crack our modulo in this challenge, a few seconds:
1 | C:\yafu-1.34>yafu-x64.exe -B1pm1 33554432 -B2pm1 4294967296 |
After factorization, just use discrete_log
of sage to obtain the flag.
EXP
Lattice to compute
1 | from ast import literal_eval |
Factorization by yafu
, then compute discrete logarithm:
1 | from Crypto.Util.number import * |
babyecc
Source Code
1 | from Crypto.Util.number import * |
Solution
First use the point doubling formula to construct an equation () for every set of . Combine these polynomials with CRT to derive a new polynomial . Finally we can get the small root of (coppersmith method) and recover the flag.
Construct Polynomial
Point doubling formula of Weierstrass normal form ECC :
Consider the double point with x-coordinate= , from (1), , multiply both sides with :
The ECC polynomial :
Denote k, c as :
Combine (2), (3) :
Now we have constructed a polynomial modulo and .
SMUPE-problem
In this section, we focus on solving Systems of Modular Univariate Polynomial Equations (SMUPE).
A straight forward method : combine all the polynomials with CRT and we can obtain a new polynomial which coppersmith method can be applied to. Let the max degree of is and every is about , the upper bound of common root is . In this challenge, we have 7 polynomials; the degree of all is 12; the bits of is 1024. Therefore, the upper bound of for the above idea is . Our flag length is 344 bits. F(x).small_roots(X=2^400,epsilon= 1/40,beta = 4/7)
is enough to extract the small root .
EXP
1 | from ast import literal_eval |