Writeups
  • UMASS CTF 2024
    • Crypto-Brutal Mogging
    • Crypto - Shuffling as a Service
  • GPN CTF 2024
    • Crypto-Boombox
  • WANICTF 2024
    • Crypto - Replacement
    • Crypto - Easy Calc
    • Crypto - dance
    • Crypto - speedy
    • Crypto - Many Xor Shift
    • Crypto - uf
  • UIUCTF 2024
    • Crypto-Without a Trace
    • Crypto-Determined
    • Crypto-Naptime
    • Crypto-Snore Signatures
    • Crypto-Groups
  • DeadSec CTF 2024
    • Crypto - Raul Rosas
    • Crypto - SSP
    • Crypto - Password Guesser
  • corCTF 2024
    • Crypto - Steps
    • Crypto - Monkfish
    • Crypto - Anglerfish
  • LITCTF 2024
    • Crypto- Symmetric RSA
    • Crypto -Truly Symmetric RSA
  • IrisCTF 2025
    • Crypto - knutsacque
  • UofTCTF 2025
    • Misc - Simple Signing
  • HTB CyberApocalypse
    • Crypto - Copperbox
  • BreachCTF 2025
    • Crypto - Taaffeite Encryption
    • Crypto - Big Stuff
Powered by GitBook
On this page
  • Full Implementation
  • Challenge
  • Exploit
  1. DeadSec CTF 2024

Crypto - SSP

Sometimes it requires GPU to compute huge amount of operation... like O(2^100)..? Nah, you'll use better algorithm, O(2^50) seems fair huh? - __readfsqword

PreviousCrypto - Raul RosasNextCrypto - Password Guesser

Last updated 10 months ago

Challenge

MAX_N = 100
RAND_MAX = 10 ** 200 # You can't even solve with knapsack method
from random import randrange
for n in range(1, MAX_N + 1):
    print(f"Stage {n}")
    arr = [ randrange(0, RAND_MAX) for _ in range(n) ]
    counts = randrange(0, n + 1)
    used = set()
    while True:
        idx = randrange(0, n)
        used.add(idx)
        if len(used) >= counts:
            break
    s = 0
    for idx in used:
        s += arr[idx]
    for a in arr:
        print(a, end=' ')
    print(s)
    answer = list(map(int, input().split()))
    user_sum = 0
    for i in answer:
        user_sum += arr[i]

Another knapsack question, although the question states that it is exponential in time, we use a lattice reduction method that solves it in polynomial time

To do this, we refer to this paper

Exploit

from pwn import *
load(flatter.sage)
def solve(arr,s):
    M = identity_matrix(QQ, len(arr))
    M = M.augment(vector(arr))
    M = M.stack(vector([-1/2 for _ in range(len(arr))] + [-s]))
    try:
        M1= flatter(M)
        row = M1[0][:-1]
        ans=[]
        for cnt,i in enumerate(row):
            if i==1:
                ans.append(cnt)
        return ans
    except:
        M1 = M.LLL()
        for row in M.LLL():
         for row in (row, -row):
            if row[-1] == 0:
                subset = [i for i, x in enumerate(row[:-1]) if x+1/2==1]
                return subset
r.close()
r = remote("35.224.11.111",32054)
r.sendline("0")
r.recv()
r.recvline()
for i in range(99):
 arr=r.recvuntil(b"\n")[:-1].decode()
 arr = arr.split(" ")
 arr = [int(i) for i in arr]
 s= arr[-1]
 arr = arr[:-1]
 ans=solve(arr,s)
 a1=str(ans)[1:-1].replace(','," ")
 r.sendline(a1)
r.recvline()
b'DEAD{T00_B1g_Number_Causes_Pr0blem...}\n'

To speed up the lattice reduction for large lattices, we use . Unfortunately, flatter doesn't work for very short lattices so we use sage's built in LLL method as a fallback and the knapsack solve code from

Full Implementation
flatter
here
752KB
cjloss.pdf
pdf
Pg 18, A Gentle Tutorial for Lattice-Based Cryptanalysis