crypto (952 points, 2 solves)

This challenge consisted of breaking a subset-product problem. Only two teams managed to solve the task during the CTF: we came in second after MSLC, who also got first blood on all other crypto tasks.

The full source code of the task is rather short:

from Cryptodome.Util.number import bytes_to_long, getPrime
import random
import hashlib

sr = random.SystemRandom()
p = getPrime(120)
num = [sr.randint(1,p-1) for i in range(90)]
secret = sr.randint(0, 2**90)
r = 1
for i in range(90):
    if (secret >> i) & 1:
        r *= num[i]
        r %= p

flag = open("flag.txt","rb").read()
h = hashlib.sha256(str(secret).encode('utf-8')).digest()

print(p)
print(num)
print(r)
print(bytes_to_long(h)^bytes_to_long(flag))

So, we are given a product $r$ of a subset of known integers $x_1,…,x_n$, modulo a prime $p$, and the goal is to figure out what that subset was.

The obvious approach to solving this problem was to reduce it to a subset-sum problem, which are well-studied in computer science. We can convert the product into a sum by taking logarithms: Here, since everything is modulo $p$, this means computing the discrete logarithms in $(\mathbb Z/p)^\times$ of the product $r$ and all the elements $x_1,…,x_n$ with respect to some primitive element $g\in(\mathbb Z/p)^\times$. Note that we can make sure these logarithms are efficient by reconnecting to the server a few times until we get an instance where $p{-}1$ is sufficiently smooth.

Write $b:=\log_g r$ and $a_i:=\log_g x_i$; these integers are defined modulo $p{-}1$. Hence, we are looking for a subset $S\subseteq\{1,…,n\}$ such that \[ \label{modsum}\tag{$\ast$} b \equiv \sum_{i\in S} a_i \pmod{p{-}1} \,\text. \]

First, let us apply a standard trick to get rid of the modulo and obtain a subset-sum problem over $\mathbb Z$: If every $a_i\leq B$, then the modular congruence $\eqref{modsum}$ is equivalent to the integer equation \[ \label{intsum}\tag{$\dagger$} b = \Big(\sum_{i\in S} a_i\Big) - u(p{-}1) \] where $u\leq nB$. We decompose $u$ as $u=\sum_{j=0}^{\ell-1} 2^ju_j$, where $2^\ell > nB$. Thus, equation $\eqref{intsum}$ now describes a new subset-sum problem over $\mathbb Z$: Letting \[ n’:=n+\ell \,\text, \qquad\qquad a_i’:=\begin{cases} a_i & 1\leq i\leq n \,\text; \
-2^j(p{-}1) & i=n{+}1{+}j>n \,\text, \end{cases} \] we are looking for a subset $S’$ of $\{1,…,n’\}$ such that $\sum_{i\in S’} a_i’ = b$. In our particular case, we have $a_i<p{-}1<2^{120}$ and $n=90$, so we may choose $\ell=7$.

It is known that the feasibility of subset-sum problems depends on the density of the problem, defined as \[ d := n’ / \log_2\max\lvert a_i’\rvert \,\text. \]

Generally, the problem becomes easier as the density drops significantly below one.

In our case, the largest $\lvert a_i’\rvert$ is $2^{\ell-1}(p{-}1)$, so the density is approximately \[ d = \tfrac{n+\ell}{\log_2(2^{\ell-1}(p{-}1))} \approx \tfrac{90+7}{6+120} \approx 0.77 \ll 1 \,\text. \] Thus, we can attempt to solve the problem using BKZ, as described on page 2 of this paper, in particular using the lattice shown in equation (1) — and indeed, this solves the challenge within a few minutes on a laptop!

---

Final attack script (written in sage):

#!/usr/bin/env sage
import socket, ast, hashlib
from Crypto.Util.number import bytes_to_long, long_to_bytes

proof.all(False)

def get(smooth=None):

    while True:

        sock = socket.socket()
        sock.connect(('124.156.133.6', 22298))

        r = b''
        while r.count(b'\n') < 4:
            tmp = sock.recv(0x100)
            assert tmp
            r += tmp

        p, num, r, cipher = r.decode().strip().split('\n')
        p, r, cipher = map(ZZ, (p, r, cipher))
        num = ast.literal_eval(num)

        print(f'p-1 = {factor(p-1)}...'); sys.stdout.flush()

        if smooth is None or all(v < smooth for v,_ in factor(p-1)):
            return p, num, r, cipher

def fl0g(secret):
    h = hashlib.sha256(str(ZZ(secret)).encode()).digest()
    flag = bytes_to_long(h) ^^ cipher
    print(hex(flag))
    print(f'--> \x1b[32m{long_to_bytes(flag)}\x1b[0m')
    exit()

########################################

p, num, r, cipher = get(2**40)

print()
print(f'p = {p}')
print(f'num = {num}')
print(f'r = {r}')
print(f'cipher = {cipher}')
print('_'*40 + '\n')

F = GF(p)
gen = F.multiplicative_generator()

logr = F(r).log(gen)
logs = []
for i,a in enumerate(num):
    print(f'doing log {i+1}/{len(num)}')
    logs.append(F(a).log(gen))
print()

########################################

A = logs + [- 2**i * (p-1) for i in range(7)]
b = logr
n = len(A)
N = ceil(sqrt(n))+5

print('density:', RR(n / log(max(map(abs, A)),2)))

lat = []
for i,a in enumerate(A):
    lat.append([0] + [2*(j==i) for j in range(n)] + [a])
lat.append([1] + [1]*n + [logr])

lat = matrix(lat)
S = [1] + [1]*n + [N]
lat = lat*diagonal_matrix(S)

def chk(lat):
    for row in lat.rows():
        if abs(row[0]) != S[0]: continue
        print(RR(row.norm()))
        assert row[1:][n] == 0
        sol = [abs(r - row[0]//S[0]) // 2 for r in row[1:][:len(logs)]]
        if all(s in (0,1) for s in sol):
            if sum(s*l for s,l in zip(sol,logs)) % (p-1) == logr:  # yay!
                secret = sum(s << i for i,s in enumerate(sol[:len(logs)]))
                print(secret)
                fl0g(secret)

lat = matrix(row for row in lat.LLL().rows() if row)

for blksz in (2,4,8,16,32,40,48,56,64):
    print(f'\n{blksz}')
    lat = lat.BKZ(block_size=blksz)
    chk(lat)

Output:

p-1 = 2 * 3 * 13^2 * 67 * 942651349373 * 10681598664886220317...
p-1 = 2 * 121229 * 578453 * 83890981 * 77344055269928087...
p-1 = 2 * 3 * 8656691 * 12606777067 * 1107674989700835271...
p-1 = 2^6 * 1943867 * 3992446807 * 2002929681291537497...
p-1 = 2^3 * 13 * 17 * 47 * 4663 * 437480317009 * 6572229116332553...
p-1 = 2^2 * 3 * 11 * 179 * 1279 * 461889255847 * 52374450589955089...
p-1 = 2^2 * 3 * 181 * 211 * 263 * 1181 * 16889 * 330487157334737955469...
p-1 = 2^2 * 3 * 188477141 * 307904289809824860346344443...
p-1 = 2^2 * 37 * 5088733549450992411938759889789907...
p-1 = 2^2 * 2861 * 11131027 * 2874156541 * 2429047311268901...
p-1 = 2^2 * 5 * 443 * 149418779 * 659264112376728136490567...
p-1 = 2^4 * 1867 * 45677 * 908244249129367943975265299...
p-1 = 2 * 5 * 11 * 1789 * 8863 * 82373 * 99961 * 120383 * 692795402813...

p = 1197758907768081485534724803560741991
num = [652627644838437141346745483171095432, 816228107784050572229698743837731169, 305740989542405312179370845813817149, 333740769277741821697291394135160253, 948062843613027157315150822985348694, 720432623797675942231544413918191660, 1132190516284667454369792358128851900, 730522261047905820936971367552840960, 531133956498204023090040478802643085, 506371809624690428173988885858839625, 651629867298647640423075458977493545, 1086002067314375280066225297793233473, 707489687283583955535500187527173794, 368742942452147897544042437997997249, 696254430786930709721399633533577578, 667833664698484218724622354497819679, 676373238243231725396400950959513544, 288323927700862108224828582470568866, 839463567985236548864964242998317197, 1000334774921048061094775318374863922, 64987320061568590355316459771318627, 15001896279465327768100170418877199, 775099586400725696985845253837868152, 883446404586096988208960588094042061, 58670718816420058717987657173277263, 1137966185683154432211604353624187956, 850024024710717673943277180457695307, 851436039687804772293883964577372119, 1184865864896507799883260389870014457, 382217171263558688266637280927454443, 557626222323217644909715978500779344, 863951738351482238758538317942403907, 616757813628093548028988910802704872, 833424548735834950713966597386637361, 327195708098875749521277499827981600, 251112915928303607119717028965931684, 709692888253613335946993163149183589, 853201699147311370164349464356211552, 62487144802269994483194910140802345, 197194747222628759990750306840628289, 22924150923917449384520517782131651, 143524887117164769116161710200128544, 464977632577708464599755867081514436, 52846615296432221391383726123269519, 710468025630219777201339629797450644, 1120398371628666751485960518237777709, 1076390367892901634873961673512317266, 619867113482597309977909404182470093, 941935067992299435070092369146546813, 160248335188575387542030068412618586, 321906919796853200483176639874479352, 632724816281321417330839465830425205, 839861135987351051304197907051261624, 907314464877794057162372574646925156, 99676936823514909971733436465594516, 457011894566048411245221616321835145, 117962865677750898066232852859223408, 1129875241424599603965411242897153911, 999888661227542075322263868600495697, 457017665710723521492644481365179299, 126239870851677743115881029200088712, 760858628224324229389403171251672017, 72650585718893583329000596402140956, 736838549234633942813280242326690653, 717357867076168368714141429955447006, 978046382744238689073422016435516158, 1192492907656810230532225751577116758, 63517707226252082035029321548002021, 778566385205279753188730120833579121, 269103109530908201273747657759384955, 309615619528561810808906608041599606, 1016283562031684952826264149726296268, 66850332407769576548583424672622583, 161517621211793616293083399736011757, 96919534984063614744487266108970917, 82757721253166973597550096999088208, 897511652725635357267513948487835370, 494441818978744463663477306288446875, 60830916556122244227899659349694672, 713416869602422839359056183593044682, 462603926516811740689791612465722061, 1036424284904189395971523716103140587, 332316121980296344629007220775426050, 41863440681559278941443531226223501, 489644420257490788747360329362527531, 295386977979505562570599680600172615, 232743751782954317306103490872741690, 23400572585244596514519592334130125, 498945800502542425865960947545395955, 645656803407473606238838078777064199]
r = 745151308593019743122849208361601056
cipher = 624256992453213884781850750761373830058640464064778126471334846995566516287664575819
________________________________________

doing log 1/90
doing log 2/90
doing log 3/90
doing log 4/90
doing log 5/90
doing log 6/90
doing log 7/90
doing log 8/90
doing log 9/90
doing log 10/90
doing log 11/90
doing log 12/90
doing log 13/90
doing log 14/90
doing log 15/90
doing log 16/90
doing log 17/90
doing log 18/90
doing log 19/90
doing log 20/90
doing log 21/90
doing log 22/90
doing log 23/90
doing log 24/90
doing log 25/90
doing log 26/90
doing log 27/90
doing log 28/90
doing log 29/90
doing log 30/90
doing log 31/90
doing log 32/90
doing log 33/90
doing log 34/90
doing log 35/90
doing log 36/90
doing log 37/90
doing log 38/90
doing log 39/90
doing log 40/90
doing log 41/90
doing log 42/90
doing log 43/90
doing log 44/90
doing log 45/90
doing log 46/90
doing log 47/90
doing log 48/90
doing log 49/90
doing log 50/90
doing log 51/90
doing log 52/90
doing log 53/90
doing log 54/90
doing log 55/90
doing log 56/90
doing log 57/90
doing log 58/90
doing log 59/90
doing log 60/90
doing log 61/90
doing log 62/90
doing log 63/90
doing log 64/90
doing log 65/90
doing log 66/90
doing log 67/90
doing log 68/90
doing log 69/90
doing log 70/90
doing log 71/90
doing log 72/90
doing log 73/90
doing log 74/90
doing log 75/90
doing log 76/90
doing log 77/90
doing log 78/90
doing log 79/90
doing log 80/90
doing log 81/90
doing log 82/90
doing log 83/90
doing log 84/90
doing log 85/90
doing log 86/90
doing log 87/90
doing log 88/90
doing log 89/90
doing log 90/90

density: 0.770760377374606

2
31.4006369362152
27.0185121722126
29.0172362570938
31.5277655408689
31.6543835826888

4
31.4006369362152
27.0185121722126
29.0172362570938
31.5277655408689
31.6543835826888

8
26.1151297144012
27.8926513619627
25.0199920063936
26.2678510731274
26.4196896272458

16
24.6981780704569
20.6397674405503
22.6715680975093
24.8596057893121
25.0199920063936

32
21.7715410570772
19.2353840616713
22.6715680975093
21.9544984001001
22.1359436211787

40
18.1659021245849
19.0262975904404
21.7715410570772
18.3847763108502
18.6010752377383

48
21.0237960416286
18.8148877222268
21.0237960416286
21.2132034355964
21.4009345590327

56
16.0623784042090
18.1659021245849
18.1659021245849
20.2484567313166
17.4928556845359
17.7200451466693
20.6397674405503
18.1659021245849
18.8148877222268
18.8148877222268
17.7200451466693
17.7200451466693
20.0499376557634
17.4928556845359
18.8148877222268
18.8148877222268
19.2353840616713
18.3847763108502
18.3847763108502
19.8494332412792
21.0237960416286
17.9443584449264
20.0499376557634
18.8148877222268
20.6397674405503
20.8326666559997
19.8494332412792
18.1659021245849
21.2132034355964
21.0237960416286
20.4450483002609
17.0293863659264
18.1659021245849
19.4422220952236

64
9.89949493661167
479242466236242008324207712
0x524354467b4d3474685f30665f4d754c4c4c7469706c69636174696f6e5f323333337d
--> b'RCTF{M4th_0f_MuLLLtiplication_2333}'