Related CTF Challenges

[hyunsikjeong]

If there're any related CTF challenges, feel free to left comments here.

• No wargame-site challenges!
• Only past, limited-hour CTF challenges are allowed.

[soreatu]

Here is 2 related CTF challenges: WMCTF 2020 babySum && Sum. The former is a instance of 120-n low-density (d = 0.8) subset-sum problem, and the latter is a 180-n one.

You can find the challenges and writeup here. 😄

Some Notes:

• Both of the two challenges are made by me, inspired by the National Crypto-Math Challenge in China.
• Lattice reduction algorithm is indeed a powerful tool to solve such low-density knapsack problem. It works well in low dimension (<100). However, when the dimension increases, it takes more time to find the right solution.
• It takes about 30 minutes to solve the 120-n instance, and hundreds of hours to solve the 180-n one, by using lattice reduction.
• During the 48-hour WMCTF 2020, 4 teams solve the 180-n one, by renting cloud computing servers, equipped with nearly a hundred of CPU cores, and running the BKZ algorithms for several hours.

I am not a professor in this area and just made the two challenges for fun 😭, if you find any mistake, please feel free to contact me via [email protected]

[hyunsikjeong]

Thank you for sharing, @soreatu !
I love the idea of the challenge "Sum".

[rkm0959]

Breaking DSA with LCG nonces is a known application of LLL, and appeared in some CTFs
DEFCON 2019 Quals: https://github.com/pcw109550/write-up/tree/master/2019/DEFCON/tania

Two Hidden Number Problems have appeared in DownUnderCTF, but both are relatively straightforward
writeups: https://rkm0959.tistory.com/162

[hyunsikjeong]

HDP: https://github.com/pcw109550/my-ctf-challenges/tree/master/codegate2020/Final/Sculptor

[rkm0959]

N1CTF 2019 : guess_ex - kinda like a hidden number problem
https://github.com/Nu1LCTF/n1ctf-2019/tree/master/CRYPTO/guess_ex
SECCON 2020 sharsable -lattice construction using number theory bounds
https://rkm0959.tistory.com/165