Too Many Leaks - GCC CTF 2024

Challenge:

#!/usr/bin/env python3

from Crypto.Util.number import getStrongPrime
import hashlib
from secret import flag
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

def encrypt_flag(secret_key):
    sha1 = hashlib.sha1()
    sha1.update(str(secret_key).encode('ascii'))
    key = sha1.digest()[:16]
    iv = os.urandom(16)

    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(flag,16))
    print("{ ciphertext : " + ciphertext.hex() + ", iv : " + iv.hex() + "}")

    return ciphertext, iv


# Generate parameters

p = getStrongPrime(512)
print(f"{p=}")
g = 2

# Alice calculates the public key A
a = getStrongPrime(512)
A = pow(g,a,p)
print(f"{A=}")

# Bob calculates the public key B
b = getStrongPrime(512)
B = pow(g,b,p)
print(f"{B=}")

# Calculate the secret key
s = pow(B,a,p)

# What ?!
mask = ((1 << 256) - 1 << 256) + (1 << 255)
r1 = s & mask
print(f"{r1=}")

# Charlie arrives and sync with Alice and Bob
c = getStrongPrime(512)
print(f"{c=}")
AC = pow(g,a+c,p)
s2 = pow(AC,b,p)
print(f"{AC=}")
r2 = s2 & mask
print(f"{r2=}")

encrypt_flag(s)

Output:

p=12659765344651740648724763467724826993725936263366951091039118416195292099370631377712042960634433459603684366298668316118798753725083109726606307230709481
A=3301451331273103822833339817189898484477574460332521541023442766617163003861277567173209945681794302860954824946103841799431004692332025577336344394695314
B=4585794959794770660643739179463936175470737153250504109915159478661133411133496952267060123069524419032124459912888910847574766484421490926652243218962165
r1=2568748433813321161874639775621008976218176085243148442053880160521563872123950485879781803171876295709491228751046125319137014580919198982132588104122368
c=13305825506775525477695274133373660177357107668926266252207560823721404224069651345842091298405541700114875323083835571095924844005731356668708175418706451
AC=7245241643057289361660908682282370311759108862519890618466911853745311287850476739612486696335989486506224784314474292337315512082870292214611222140900864
r2=3829741721947473719324421527352078984331611168371079834096760630101921404398331513243772077101441758022492336098369985623504441570880895898971858238701568
{ ciphertext : 89c372210be2a7b313366206f7426f941157009493d00fcb18b467250139413b6ea1ada6302e1916b6c02a6f935f4ed4, iv : c7d192fb72b529acf7b57d488c182466}

Solve:

Looking at the mask, we can see that we’re given the MSBs:

>>> mask = ((1 << 256) - 1 << 256) + (1 << 255)
>>> bin(mask)
'0b11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
>>> 

s = pow(B,a,p)
AC = pow(g,a+c,p)
s2 = pow(AC,b,p)

We can get a relation between s and s2:

\[s \equiv B^a\] \[s_2 \equiv {(g^{a+c})}^b \equiv (g^b)^{a+c} \equiv B^{a+c} \equiv B^a \cdot B^c \equiv s \cdot B^c\]

assert s2 == (s * pow(B, c, p)) % p

I’ll denote the unknown LSBs x1 and x2, so that:

s = r1 + x1
s2 = r2 + x2

Now we can solve this equation with bivariate coppersmith.

I’ve created 2 scripts for convenience:

https://github.com/Connor-McCartney/coppersmith

https://gist.github.com/Connor-McCartney/31387d1b32cf0d5f2d06f86f2e1c112c

You only need 1 implementation but I’ll showcase all 3:

# output
p=12659765344651740648724763467724826993725936263366951091039118416195292099370631377712042960634433459603684366298668316118798753725083109726606307230709481
B=4585794959794770660643739179463936175470737153250504109915159478661133411133496952267060123069524419032124459912888910847574766484421490926652243218962165
c=13305825506775525477695274133373660177357107668926266252207560823721404224069651345842091298405541700114875323083835571095924844005731356668708175418706451
r1=2568748433813321161874639775621008976218176085243148442053880160521563872123950485879781803171876295709491228751046125319137014580919198982132588104122368
r2=3829741721947473719324421527352078984331611168371079834096760630101921404398331513243772077101441758022492336098369985623504441570880895898971858238701568

load('https://gist.githubusercontent.com/Connor-McCartney/31387d1b32cf0d5f2d06f86f2e1c112c/raw/e879b7afd6076b5d4a2de466ac6caa89081da5bb/kionacoppersmith.sage')
load('https://raw.githubusercontent.com/Connor-McCartney/coppersmith/main/coppersmith.sage')

PR.<x1, x2> = PolynomialRing(GF(p), 2)
f = (r1+x1) * pow(B, c, p) - (r2+x2)
bounds = (2**255, 2**255)

# rbtree's (Herrmann-May)
print(multivariate(f, bounds, m=1, t=1, implementation="herrmann_may", algorithm="jacobian"))

# defund/Joseph (shift-polys)
print(multivariate(f, bounds, m=1, d=1, implementation="shift_polynomials", algorithm="jacobian"))

# Kiona's (shift-polys)
print(coppersmith_multivariate_direct(f, bounds, t=2, d=1))

[~/Desktop] 
$ sage c.sage 
LLL...
LLL done
 33%|█████████                  | 1/3 [00:00<00:00,  9.70it/s]
[[16398029187545116410379158779174289772216017281301637621417139570711691284296, 41036197941114149842214882116707031982582245609637689544867914273576525805038]]
LLL...
LLL done
 33%|████████▋                 | 1/3 [00:00<00:00, 138.21it/s]
[[16398029187545116410379158779174289772216017281301637621417139570711691284296, 41036197941114149842214882116707031982582245609637689544867914273576525805038]]
trying param: t=2, d=1, lm=x1
LLL start...
LLL done
 33%|█████████                  | 1/3 [00:00<00:00,  3.34it/s]
[[16398029187545116410379158779174289772216017281301637621417139570711691284296, 41036197941114149842214882116707031982582245609637689544867914273576525805038]]

They all found the same roots. Now we can take x1, calculate s, and decrypt:

from Crypto.Cipher import AES
from hashlib import sha1

ciphertext = bytes.fromhex('89c372210be2a7b313366206f7426f941157009493d00fcb18b467250139413b6ea1ada6302e1916b6c02a6f935f4ed4')
iv = bytes.fromhex('c7d192fb72b529acf7b57d488c182466')
r1 = 2568748433813321161874639775621008976218176085243148442053880160521563872123950485879781803171876295709491228751046125319137014580919198982132588104122368
x1 = 16398029187545116410379158779174289772216017281301637621417139570711691284296
s = r1 + x1
key = sha1(str(s).encode()).digest()[:16]
print(AES.new(key, AES.MODE_CBC, iv).decrypt(ciphertext).decode())
# GCC{D1ff13_H3llm4n_L34k_15_FUn!!}