# Crypto - SSP

## [Full Implementation](https://github.com/kinasant/THR34DR1PP3R/blob/main/2024/DeadSec/SSP/sol.ipynb)

## Challenge

```python
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

{% file src="<https://2017398282-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUn3m91wNDAeWCUHREmIX%2Fuploads%2F5yVyn7NUs6BB2WTxbr01%2Fcjloss.pdf?alt=media&token=35f07565-d305-4c1f-a48d-ac72b7f266f9>" %}
Pg 18, A Gentle Tutorial for Lattice-Based Cryptanalysis
{% endfile %}

## Exploit

To speed up the lattice reduction for large lattices, we use [flatter](https://github.com/keeganryan/flatter). 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 [here](https://connor-mccartney.github.io/cryptography/other/BackdoorCTF-2023-writeups)

```python
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'
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://thr34dr1pp3r.gitbook.io/ctf/deadsec-ctf-2024/crypto-ssp.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.