GreyCTF 2023 Finals Writeups

ヨミビトシラズ & /bad

Baby Feistel
Iterated Polynomials
Smart
AES confusion
OTP 2
POTP

Full solution notebooks are available here.

Baby Feistel

By ariana

I made my own custom cipher but somehow encrypting twice does nothing.

Attachment: baby_feistel.zip

11/15 solves, 300 points

The handout implements a 19-round feistel cipher $\text{encrypt}(k, m)$ . Round keys $k_i$ are derived using a degree 16 polynomial $f(x)$ modulo ${5^{55}}$ , where $k_0 = k$ is the user-provided key and $k_i = f(k_{i-1})$ . It then proves that when the flag is supplied as the key, $m = \text{encrypt}(\text{flag}, \text{encrypt}(\text{flag}, m))$ .

For a typical feistel cipher, the decryption procedure applies round keys in the reverse order. But since $\text{encrypt}(\text{flag}, m)$ works for decryption as well, we can infer that the round keys must be the same when applied in forward or reverse order, i.e. $k_0 = k_{18}, k_1 = k_{17}, \dots$ and so on. Looking specifically at $k_9 = k_{11}$ , this implies $k_9 = f(f(k_9))$ , and with more substitutions this turns into $\text{flag} = f(f(\text{flag}))$ . Expand $f(f(x))$ into a degree 256 polynomial, and the flag must then be a root of the polynomial $f(f(x)) - x$ which can be solved efficiently using Hensel lift.

(The author’s solve script operates under assumption that $f(\text{flag}) = \text{flag}$ , though I’m still not sure how this should be derived.)

Expanding f(x)sage
f_coeff = [107632798521572819694764108404904109375, 41536741957891467431472232877751864376, [...], 160013292840662875257096750676572257331, 27182818284590452353602874713526624977]
p = 5^55
Fp.<x> = Zmod(p)[]
f = Fp(f_coeff)
ff = f.subs(x=f)
solve_poly = ff - x

vector(solve_poly).change_ring(ZZ) % 10

output

(5, 5, 5, 5, 8, 7, 7, 6, 4, 1, 0, 3, 2, 5, 0, 8, [...] 1, 3, 7, 2, 6, 5, 6, 6, 6, 7)

Hensel liftsage
roots = [0]

for p_pow in range(1, 56):
    pp = 5 ^ p_pow
    Fpp.<xx> = Zmod(pp)[]
    solve_poly_pp = solve_poly.change_ring(Fpp)

    lifted_roots = []
    for a in range(0, pp, 5 ^ (p_pow - 1)):
        for root in roots:
            try_root = a + root
            if solve_poly_pp.subs(x=try_root) == 0:
                lifted_roots.append(try_root)
    print(f"Zmod 5^{p_pow} => {len(lifted_roots)} roots found", lifted_roots[:5])

    roots = lifted_roots

for root in roots:
    try:
        flag = bytes.fromhex(hex(root)[2:].zfill(32))
        flag = flag.decode()
        print(root)
        print(f"grey{{{flag}}}")
    except Exception:
        pass

output

Zmod 5^1 => 5 roots found [0, 1, 2, 3, 4]
Zmod 5^2 => 25 roots found [0, 1, 2, 3, 4]
Zmod 5^3 => 110 roots found [0, 1, 2, 3, 4]
Zmod 5^4 => 385 roots found [0, 3, 4, 5, 7]
Zmod 5^5 => 985 roots found [0, 3, 5, 7, 8]
Zmod 5^6 => 2110 roots found [0, 5, 13, 25, 30]
Zmod 5^7 => 3360 roots found [5, 25, 50, 55, 130]
Zmod 5^8 => 3360 roots found [50, 130, 400, 430, 513]
[...]
Zmod 5^51 => 3360 roots found [111682577556028427962833508437275, 125454050132363368490012975138303, 215233742379741370677956703930675, 286796871671915434641010788813880, 560551308855012470036980602748555]
Zmod 5^52 => 3360 roots found [215233742379741370677956703930675, 1981636780375212841779229137904805, 2108838093991755286764067427047388, 2418425078952215992254383591548255, 2537706269008430159124907646187082]
Zmod 5^53 => 3360 roots found [2108838093991755286764067427047388, 2418425078952215992254383591548255, 3767947421180242300033578041821300, 7230881407733365227201255650919553, 10059280878197431030158573254531025]
Zmod 5^54 => 3360 roots found [30403346210779220276624199841029805, 45586417666202440323714786633437275, 55709130260959729932588703659907630, 57058652603187756240367898110180675, 62649056773332020739508144847563047]
Zmod 5^55 => 3360 roots found [45586417666202440323714786633437275, 145876494573200279474258431557446300, 208039030150804266744405266735561055, 233344814200984776400369770554438880, 489675627516265056493167453869765400]
157458601479928338764568835668063645239
grey{vuln_f1x3d_p01n7}

Also see SECCON CTF 2022 BBB (writeup by myself), DiceCTF 2023 BBBB (writeup by pcw109550).

Iterated Polynomials

By ariana

Took me a weekend on a laptop but finally I got an output!

Attachment: iterated_polynomials.zip

3/15 solves, 460 points

Solved after the competition.

The handout descrbes a polynomial quotient ring with a fixed 17-degree modulus in a prime $n$ field. A $h$ operation on polynomials is defined as $h(f(x)) = f(x)^2 + 1$ . The handout also reveals the result of $g = h^\text{flag}(x)$ , where $\text{flag}$ is 256 bits long.

Instead of working in polynomials, we can map each polynomial to a 16-element vector and model the operation $h(f(x))$ as a matrix transformation $H$ . For generator $y$ and published result $g$ , we now have the relation $y \times H^{\text{flag}} = g$ .

Handoutpython
n = 2^32+15
F = GF(n)
R.<x> = PolynomialRing(F)
a = x^16 + 2206327570*x^15 + 764008823*x^14 + 2624308288*x^13 + [...] + 1178619281*x^3 + 124682568*x^2 + 150251198*x + 1469826103
S.<y> = R.quotient(a)

Matrix Hpython
H = []
for pos in range(16):
    hy = (y^2+1)^pos
    H.append(list(hy))
H = Matrix(F, H)

H.change_ring(ZZ) % 1000

output

[  1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  1   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0]
[  1   0   2   0   1   0   0   0   0   0   0   0   0   0   0   0]
[  1   0   3   0   3   0   1   0   0   0   0   0   0   0   0   0]
[  1   0   4   0   6   0   4   0   1   0   0   0   0   0   0   0]
[  1   0   5   0  10   0  10   0   5   0   1   0   0   0   0   0]
[  1   0   6   0  15   0  20   0  15   0   6   0   1   0   0   0]
[  1   0   7   0  21   0  35   0  35   0  21   0   7   0   1   0]
[209 113 751  30 841 341  81 378 302  72 109 731 887  23 496 741]
[392 977 353  39 549 516 934 956 491  90 155 852 709 362 107 665]
[221 562 930 200 722 845 221 414 726 233 923 952 260 375 340 140]
[980 391 990 175 741 119 957 475 500 927 361 933 309 465 629 823]
[ 53 670 872 332 398 162 484 538 921 884 312 158 638 600 997 987]
[564 704 807 191  40 628 678 429  59 993 557 601  51 857 127 494]
[225 726 730 289 672 382 657 632 639 762 235 512 716 865  52 206]
[413 277 187 758 345 240 174 366   8 283 206 762 338 545 474 913]

We can diagnonalize the matrix operation into $H = P \times J \times P^{-1}$ , where $H^x = P \times J^x \times P^{-1}$ . With some rearrangement:

\begin{align*} g &= y \times H^{\text{flag}} \\ &= y \times P \times J^{\text{flag}} \times P^{-1} \\ g \times P &= y \times P \times J^{\text{flag}} \times P^{-1} \times P \\ g \times P &= y \times P \times J^{\text{flag}} \end{align*}

$g \times P$ and $y \times P$ are vectors and $J^{\text{flag}}$ is a diagonal matrix, which means we can solve the discrete log problem for each row independently and use the chinese remainder theorem to obtain the full discrete logarithm. The orders are smooth, so the discrete logarithm completes quickly.

To allow the $H$ to be diagonalizable, we also need to work in the field extension $GF(n^{12})$ such that its characteristic polynomial is fully factorisable into 16 elements.

Diagonalize and discrete logpython
FF = GF(n^12)
J, P = H.change_ring(FF).jordan_form(transformation=True)

y_vec = vector(FF, [0] + [1] + [0] * 14)
g = 4213081404*y^15 + 3296429821*y^14 + 4211675621*y^13 + [...] + 4121679949*y^3 + 2775737979*y^2 + 1590517927*y + 1223073206
g_vec = vector(FF, list(g))

yp = y_vec * P
gp = g_vec * P

crt_a, crt_m = [], []
# for i in range(16):
for i in [1, 2, 3]:
    goal = gp[i] / yp[i]
    base = J[i][i]
    order = base.multiplicative_order()
    print(f"Row {i}, Order {order}")
    dlog = discrete_log(goal, base, ord=order)
    print(f"dlog {dlog}")

    crt_a.append(dlog)
    crt_m.append(order)

flag = CRT_list(crt_a, crt_m)
print(f"{flag=}")
flag_str = bytes.fromhex(hex(flag)[2:]).decode()
print(f"{flag_str=}")

output

Row 1, Order 79228163344367823809576701230
dlog 39659895313370669262782774899
Row 2, Order 18904576204146013290129967807464358880
dlog 160904653911627958279069599163942529
Row 3, Order 261545911121742886336251906983649969595675641752826538140
dlog 68832491842489549589549111574014464981553494769485937929
flag=25061313324495391639078071938906763925954963582764198847057562642948967133729
flag_str='7h3_FunC710N_15_4c7U4Lly_l1N34r!'

Smart

By mechfrog88

Only smart people can get the flag

nc 34.124.157.94 32521

Attachment: smart.zip

2/15 solves, 480 points

Solved after the competition.

f(v) takes in a 42-bit tuple and outputs a 42-bit tuple, and can be assumed to be non-invertible due to the nonlinearities with different moduli and the quadratic elements in the function. The hash h(v) applies f(v) 5555 to 3005555 times depending on the initial value. Given h(v), we need to find some valid v.

Approximating f(v) to be a random function, we can model it as a mapping graph comprising of tails and cycles. The expected tail and cycle lengths will be $\sqrt{2^{42} \pi / 8} \approx 1314195$ ¹, which means we can expect the target h(v) to be on some cycle. We can iterate through the cycle once to find its period and another time to check if any elements on the cycle will have an iteration count that will reach h(v).

Get targetpython
from pwn import *

# conn = remote("34.124.157.94", 32521)
conn = process(["python", "smart.py"])
conn.recvuntil(b"Target: ")
target = safeeval.expr(conn.recvline().decode().strip())
print(f"{target=}")

output

[x] Starting local process '/home/sy/miniconda3/bin/python'
[+] Starting local process '/home/sy/miniconda3/bin/python': pid 41041
target=(954, 13, 506, 838)

Find cyclepython
from numba import njit
from tqdm.auto import tqdm

p = 1657; q = 1663; r = 1049; s = 1193
@njit() # speedup!
def f(v):
    a = (5 * v[0] + 3 * v[1] + 7 * v[2] + 4 * v[3] + v[0] * v[1] + 10 * (v[2] * v[3])**2) % p
    b = (9 * v[0] + 2 * v[1] + 1 * v[2] + 1 * v[3] + v[1] * v[2] + 11 * (v[0] * v[3])**2) % q
    c = (6 * v[0] + 7 * v[1] + 3 * v[2] + 9 * v[3] + v[2] * v[3] + 12 * (v[0] * v[1])**2) % r
    d = (8 * v[0] + 5 * v[1] + 2 * v[2] + 7 * v[3] + v[3] * v[0] + 13 * (v[1] * v[2])**2) % s
    return (a,b,c,d)

def h(v):
    k = 5555 + ((v[0] * v[1] * v[2] * v[3]) % 3000000)
    for _ in range(k):
        v = f(v)
    return v

# find cycle length
ptr = target
found = False
for cycle_len in tqdm(range(1, 3_000_000)):
    ptr = f(ptr)
    if ptr == target:
        print(f"Found cycle length {cycle_len}")
        found = True
        break
assert found

# brute force for any inside the cycle with correct rep count
ptr = target
for offset in tqdm(range(1, cycle_len)):
    ptr = f(ptr)
    n_steps_left = cycle_len - offset
    n_steps_given = 5555 + ((ptr[0] * ptr[1] * ptr[2] * ptr[3]) % 3000000)
    if n_steps_left == n_steps_given:
        print(f"Found solution {ptr}")
        break
assert h(ptr) == target

output

0%|          | 0/2999999 [00:00< ?, ?it/s]
Found cycle length 1022119
0%|          | 0/1022118 [00:00< ?, ?it/s]
Found solution (396, 976, 233, 6)

Claim flagpython
conn.sendline(",".join(str(i) for i in ptr).encode())
print(conn.recvall().decode())

output

[x] Receiving all data
[x] Receiving all data: 54B
[x] Receiving all data: 113B
[+] Receiving all data: Done (113B)
[*] Process '/home/sy/miniconda3/bin/python' stopped with exit code 0 (pid 41041)
Insert the secret key (4 integers separated by comma)
Welcome admin! grey{hello_smart_admin_;D_hRkPxgxcMB7Yxk4e}

AES confusion

By ariana

I tried to implement an encrypt/decrypt service but it doesn’t work. Could you help me figure why?

nc 34.124.157.94 19522

Attachment: aes_confusion.zip

10/15 solves, 320 points

We interact with a service that has an AES-CBC encrypted flag as well as a CBC encryption oracle and ECB decryption oracle. The service will exit immediately after the flag ciphertext is revealed. At no point are any of the IVs revealed either.

The vulnerability here is that the AES key and all IVs are generated using the python PRNG. Using the encryption oracle we can clock the PRNG and using the decryption oracle we can recover the newly-clocked IV. With enough data we can then recover the python PRNG state and predict the generated key and IV used when encrypting the flag.

Collect datapython
from pwn import *
from Crypto.Util.Padding import pad
from tqdm.auto import tqdm

def bxor(a, b):
    return bytes(i ^ j for i, j in zip(a, b))

r = process(["python", "aes_confusion.py"])
# r = remote("34.124.157.94", 19522)

# each encryption reveals 4 int32 of random state
# we need 624 int32s of state to recover the PRNG
# 180 batches gets 720 int32s
n_batches = 180
dummy_pln = b"\x00" * 15
dummy_pln_pad = pad(dummy_pln, 16)

# Send dummy plaintext for encryption in one batch
r.send(
    f"1\n{dummy_pln.hex()}\n".encode() * n_batches
)
dummy_encs = []
for _ in tqdm(range(n_batches)):
    r.recvuntil(b"Ciphertext: ")
    dummy_enc = bytes.fromhex(r.recvline().strip().decode())
    dummy_encs.append(dummy_enc)

# Decrypt ciphertexts and xor with plaintext to recover the IVs
r.send("".join(
    f"2\n{dummy_enc.hex()}\n"
    for dummy_enc in dummy_encs
).encode())
ivs = []
for _ in tqdm(range(n_batches)):
    r.recvuntil(b"Plaintext: ")
    iv_raw = bytes.fromhex(r.recvline().strip().decode())
    iv = bxor(dummy_pln_pad, iv_raw)
    ivs.append(iv)

# Obtain the flag ciphertext
r.send(b"3\n")
r.recvuntil(b"Flag: ")
flag = bytes.fromhex(r.recvline().strip().decode())
print(f"{flag.hex()=}")

output

[x] Starting local process '/home/sy/miniconda3/bin/python'
[+] Starting local process '/home/sy/miniconda3/bin/python': pid 34142
    0%|          | 0/180 [00:00< ?, ?it/s]
    0%|          | 0/180 [00:00< ?, ?it/s]
flag.hex()='b0873e97866fe2f981db3d8b3f011517f2ee66e6f0aacb5daaa86a3f8b18718b'

Recover PRNGpython
from sage_army_knife import Untwister # template lib

ut = Untwister()

# clock PRNG 4 times when it generated key
for _ in range(4):
    ut.submit("?" * 32)
# clock PRNG 4 times when it generated iv
for _ in range(4):
    ut.submit("?" * 32)

# submit the data
for iv in tqdm(ivs):
    for sli in range(0, 16, 4):
        ivsl = iv[sli:sli+4]
        ivsl_int = int.from_bytes(ivsl, "little")
        ivsl_bin = bin(ivsl_int)[2:].zfill(32)
        ut.submit(ivsl_bin)

# recover the PRNG at the start
rng = ut.get_random_after_seed()

output

0%|          | 0/180 [00:00< ?, ?it/s]
sat

Decrypt flagpython
from Crypto.Cipher import AES

key = rng.randbytes(16)
iv = rng.randbytes(16)
print(f"{key.hex()}")
print(f"{iv.hex()=}")

cipher = AES.new(key, mode=AES.MODE_CBC, iv=iv)
flag_pln = cipher.decrypt(flag)
print(f"{flag_pln=}")

output

476dceea6cb2c6aff5e8e58c2ada1451
iv.hex()='f7e5a5b42a34da9c7d0371e01d9bbf67'
flag_pln=b'grey{tr4v3ll1n9_84ck_1n_t1m3}\x03\x03\x03'

OTP 2

By mechfrog88

~~Wait this service is not complete yet~~ Okay it should be complete now

nc 34.124.157.94 19622

Attachment: dist.zip

6/15 solves, 400 points

An interaction with the server proceeds as follows:

Generator $g = (5 \cdot 7)^{10}$ is a fixed constant
Server publishes a 1024-bit prime modulus $p$
Server generates 6 1024-bit secret keys $s_i$ and publishes $g^{s_i} \bmod p$
User queries 6 tokens $k_i$ (with some restrictions on bit size) and the server publishes a “token hash” $\sum^i s_ik_i$
Server generates a 1024-bit $r$ and publishes $g^r \bmod p$
Server generates 6 16-bit “otp” $\theta_i$ and publishes “otp hashes” $g^{rs_i+\theta_i} \bmod p$
User needs to recover the 6 $\theta_i$ to claim the flag

Looking at the otp hashes, we want to find some method to eliminate the $rs_i$ terms and recover the $\theta_i$ terms. The only other location where $s_i$ is known to us is in the token hash. We can try to use the token hash as an exponent and work from there.

g^{\normalsize \text{token hash}} = g^{\normalsize \sum^i s_ik_i}

Since there is the $r$ term in $g^{rs_i+\theta_i}$ and $g^r$ is known, we can use that as the base instead.

\begin{align*} (g^{\normalsize r})^{\normalsize \text{token hash}} & = (g^{\normalsize r})^{\normalsize \sum^i s_ik_i} \\ & = g^{\normalsize \sum^i rs_ik_i} & (1) \end{align*}

Given the $k_i$ term above, we can calculate exponents of the otp hashes to scale for $k_i$ and then take the product of all the otp hashes to get another equation that looks similar.

\begin{align*} \prod^i (g^{\normalsize rs_i+\theta_i})^{\normalsize k_i} & = \prod^i g^{\normalsize rs_ik_i+\theta_ik_i} \\ & = g^{\normalsize \sum^i (rs_ik_i+\theta_ik_i)} & (2) \end{align*}

Lastly, if we divide (2) by (1), we can then eliminate the $r$ and $s_i$ terms.

\begin{align*} \; & g^{\normalsize \sum^i (rs_ik_i+\theta_ik_i)} \div g^{\normalsize \sum^i rs_ik_i} \\ = \; & g^{\normalsize \sum^i (rs_ik_i+\theta_ik_i) - \sum^i rs_ik_i} \\ = \; & g^{\normalsize \sum^i (\theta_ik_i)} \\ = \; & g^{\normalsize \theta_0k_0 + \theta_1k_1 + \dots + \theta_5k_5} \end{align*}

Obtaining $\sum^i (\theta_ik_i)$ is now a discrete log problem. Assuming that we could solve this discrete log, we then need to recover the individual $\theta_i$ from the sum. To do this we can pick $k_i$ such that the sum is a radix $m$ number with each digit representing one $\theta_i$ i.e. $k_i = m^i$ using some prime $m$ larger than $2^{16}$ . To bypass the bit length check on $k_i$ we can scale all tokens by a constant $c$ larger than $2^{32}$ , finally getting $k_i = cm^i$ . To compensate for this constant term we solve the discrete log using base $g^c$ instead. This way, the sum $\sum^i (\theta_ik_i)$ (ignoring the $c$ term) will be around 97 bits long.

To actually solve the discrete log efficiently, we can first solve it in a small subgroup. Keep making connections to the challenge until the server generates some modulus $p$ where $p-1$ has small factors $f_i$ , then we can efficiently solve the discrete log modulo $q = \prod^i f_i$ . When $q$ is larger than 97 bits the discrete log modulo subgroup will be equal to the true discrete log modulo $p-1$ , or if $q$ is smaller than 97 bits we can iterate through $(g^{\normalsize c})^{\normalsize \text{DL}_{\text{q}} + a \cdot \text{q}}, a \in \mathbb{Z}$ to find the true discrete log.

Calculate tokensage
# calculate tokens
token_c = next_prime(2^32)
token_m = next_prime(2^16)
tokens = [token_c * token_m ^ i for i in range(6)]
token_str = ",".join([str(token) for token in tokens])
print(f"{token_str=}")

output

token_str='4294967311,281479272661007,18447307092384415759,1208981164913597455597583,79232998604942436447498797071,5192693029572112457459728663642127'

Connect and check subgroupsage
from pwn import *

# find size of good subgroup
def get_subgroup(x):
    fs = [1]
    for d in range(1, 25):
        while True:
            res = ecm.one_curve(x // product(fs), factor_digits=d)
            if res[0] == 1:
                break
            fs.append(res[0])
    # throw away small factors, in case the generator is
    # already in some subgroup
    fs = [f for f in fs if f == 1 or (10^2 < f < 10^14)]
    return product(fs)

while True:
    # r = remote("34.124.157.94", int(19622))
    r = process(["python", "otp2.py"])
    # i've hardcoded a good prime for local testing, in reality this takes 50-ish connections

    r.recvuntil(b"p: ")
    P = int(r.recvline().strip().decode())
    subgroup = get_subgroup(P-1)
    # make do with 70 bits of subgroup, we can recover the rest by brute force
    if subgroup.nbits() < 70:
        r.close()
        continue

    r.recvuntil(b"pub: ")
    gs = safeeval.expr(r.recvline().strip().decode())

    r.sendline(token_str.encode())

    r.recvuntil(b"Token Hash: ")
    token_hash = int(r.recvline().strip().decode())

    r.recvuntil(b"OTP Hash: ")
    otp_hash = safeeval.expr(r.recvline().strip().decode())
    break

output

[x] Starting local process '/home/sy/miniconda3/envs/sage/bin/python'
[+] Starting local process '/home/sy/miniconda3/envs/sage/bin/python': pid 29808

Rearrangement and discrete logsage
from tqdm.auto import tqdm
from itertools import count

Fp = Zmod(P)

g = Fp((5*7)^10)

gr = Fp(otp_hash[0])

grsk = gr ^ token_hash

grs_t = [Fp(x) for x in otp_hash[1:]]
grsk_tk = [x ^ token for x, token in zip(grs_t, tokens)]
grsk_tk_prod = product(grsk_tk)

gtk = grsk_tk_prod / grsk

gc = g ^ token_c
restrict = (P-1) // subgroup
subgroup_dlog = discrete_log(gtk ^ restrict, gc ^ restrict, ord=subgroup)
print(f"dlog is {subgroup_dlog} mod {subgroup} ({subgroup.nbits()} bits)")

# if the subgroup is too small to recover all of the otp sum, we brute force for
# dlogs in the form of subgroup_dlog + n*subgroup
print(f"search up to subgroup_dlog+{2^97 // subgroup}*subgroup")
acc = gc ^ subgroup_dlog
dlog = subgroup_dlog
gcs = gc ^ subgroup
for _ in tqdm(count()):
    if acc == gtk:
        break
    acc *= gcs
    dlog += subgroup

print(f"dlog is {dlog} after verification")

output

dlog is 239805411936731889614526 mod 1389727973749439726529247 (81 bits)
search up to subgroup_dlog+114019*subgroup
0it [00:00, ?it/s]
dlog is 45909903418224678097783289171 after verification

Claim flagsage
otps = [(dlog // token_m ^ i) % token_m for i in range(6)]
otp_str = ",".join(str(otp) for otp in otps)
print(f"{otp_str=}")

r.clean()
r.sendline(otp_str.encode())

flag = r.recvuntil(b"}")
print(flag.decode())

output

otp_str='29255,16961,58364,58870,57989,37972'
Welcome Admin! grey{I_forgot_to_remove_the_debug_message_qgn9fe58yMwJdMRf}

POTP

By mechfrog88

Fancier OTP service

Attachment: potp.zip

6/15 solves, 400 points

Working in $\mathbb{F}_{2^{13}}$ , there are five degree 63 polynomials, of which m1, m2, m3 have coefficients in $[20, 127)$ and otp2, otp3 have coefficients in $[0, 256)$ . The challenge publishes m1 * (otp2 + otp3), m2 * otp2 and m3 * otp3, where the flag is equal to the coefficients in m1.

The intended solution is to do a simultaneous brute force search on all 5 polynomials, solving for all $x^0$ coefficients first, then $x^1$ coefficients and so on. At each step we prune the solutions which are not in the valid ranges.

Search and prunepython
F.<x> = Zmod(2^13)[]

N = 63
m1otp1 = 491*x^126 + 5268*x^125 + 771*x^124 + 890*x^123 + [...] + 1459*x^4 + 7995*x^3 + 1397*x^2 + 2480*x + 1325
m2otp2 = 1440*x^126 + 6960*x^125 + 7242*x^124 + 2354*x^123 + [...] + 2865*x^4 + 6069*x^3 + 1091*x^2 + 646*x + 2768
m3otp3 = 3444*x^126 + 7293*x^125 + 7131*x^124 + 607*x^123  + [...] + 2380*x^4 + 1731*x^3 + 3230*x^2 + 3944*x + 7808

def remove_low_powers(pos, x, c1, c2):
    for c1_pos in range(1, pos):
        c2_pos = pos - c1_pos
        x -= c1[c1_pos] * c2[c2_pos]
    return x

def check_coeff(pos, x, c1, c1n, c2, c2n):
    if pos == 0:
        return F(c1n * c2n) == x
    else:
        return F(c1n * c2[0] + c1[0] * c2n) == x

def dfs(pos, m1, m2, m3, otp1, otp2, otp3):
    # print(m1, m2, m3, otp2, otp3)
    print(bytes(m1))
    if pos == N + 1:
        return

    # solve m2otp2 side
    m2otp2_next = []
    m2otp2_coeff = remove_low_powers(pos, m2otp2[pos], m2, otp2)
    for m2_next in range(20, 128):
        for otp2_next in range(0, 256):
            if check_coeff(pos, m2otp2_coeff, m2, m2_next, otp2, otp2_next):
                m2otp2_next.append((m2_next, otp2_next))

    # solve m3otp3 side
    m3otp3_next = []
    m3otp3_coeff = remove_low_powers(pos, m3otp3[pos], m3, otp3)
    for m3_next in range(20, 128):
        for otp3_next in range(0, 256):
            if check_coeff(pos, m3otp3_coeff, m3, m3_next, otp3, otp3_next):
                m3otp3_next.append((m3_next, otp3_next))

    # print(m2otp2_next, m3otp3_next)

    # then solve m1otp1 side
    m1otp1_coeff = remove_low_powers(pos, m1otp1[pos], m1, otp1)
    for m1_next in range(20, 128):
        for m2_next, otp2_next in m2otp2_next:
            for m3_next, otp3_next in m3otp3_next:
                otp1_next = otp2_next + otp3_next
                if check_coeff(pos, m1otp1_coeff, m1, m1_next, otp1, otp1_next):
                    # recurse
                    dfs(
                        pos + 1,
                        m1 + [m1_next], m2 + [m2_next], m3 + [m3_next],
                        otp1 + [otp1_next], otp2 + [otp2_next], otp3 + [otp3_next]
                    )

dfs(0, [], [], [], [], [], [])

output

b''
b'g'
b'g7'
b'gr'
b'gre'
b'grey'
[...]
b'grey{hFSeQZr6PP3L9Cwx_more_vulnerable_than_xor_f9xZ3tDhTMVT73b:'
b'grey{hFSeQZr6PP3L9Cwx_more_vulnerable_than_xor_f9xZ3tDhTMVT73bu'
b'grey{hFSeQZr6PP3L9Cwx_more_vulnerable_than_xor_f9xZ3tDhTMVT73bu}'
b'grey{hFSeQZr6PP3L9Cwx_more_vulnerable_than_xor_f9xZ3tDhTMVT7n'
b'grey{hFSeQZr6PP3L9Cwx_more_vulnerable_than_xor_f9xZ3t\x7f'
[...]
b'grey{hFSeQZrq'

An unintended solution exists by attempting to factorise the m1 * (otp2 + otp3) polynomial using sage. This won’t work with all possible flags and polynomials, but it did during the contest. Of the powersets of these factors, the product of one of the sets will be equal to the monic representation of m1. We can then try to recover a flag from all scalar multiples of the polynomial.

Factorize and powersetpython
from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))

F.<x> = Zmod(2^13)[]
m1otp1 = 491*x^126 + 5268*x^125 + 771*x^124 + 890*x^123 + [...] + 1459*x^4 + 7995*x^3 + 1397*x^2 + 2480*x + 1325

m1otp1_factors = m1otp1.factor()
print(m1otp1_factors)

parts = [i[0] for i in m1otp1_factors]

for i in powerset(parts):
    i = product(i)
    if len(list(i)) == 64:
        for scale in range(256):
            ii = scale * i
            try:
                print(bytes(list(ii)))
            except Exception:
                pass

output

[(x + 1035, 1),
 (x^2 + 3561*x + 1639, 1),
 (x^3 + 2087*x^2 + 3212*x + 1187, 1),
 (x^6 + 2522*x^5 + 279*x^4 + 2671*x^3 + 1958*x^2 + 1161*x + 6739, 1),
 (x^27 + 174*x^26 + 5291*x^25 + 2984*x^24 + 935*x^23 + 7722*x^22 + 5476*x^21 + 6218*x^20 + 3479*x^19 + 540*x^18 + 1246*x^17 + 344*x^16 + 5248*x^15 + 1094*x^14 + 2498*x^13 + 3635*x^12 + 5941*x^11 + 886*x^10 + 6580*x^9 + 116*x^8 + 4462*x^7 + 7647*x^6 + 4501*x^5 + 5172*x^4 + 3759*x^3 + 6653*x^2 + 8100*x + 1409,
  1),
 (x^29 + 2758*x^28 + 530*x^27 + 3940*x^26 + 1372*x^25 + 7026*x^24 + 2596*x^23 + 7799*x^22 + 7287*x^21 + 5676*x^20 + 4384*x^19 + 6507*x^18 + 2242*x^17 + 6907*x^16 + 6196*x^15 + 4690*x^14 + 5670*x^13 + 2916*x^12 + 255*x^11 + 5453*x^10 + 8132*x^9 + 4548*x^8 + 1019*x^7 + 1784*x^6 + 6114*x^5 + 7106*x^4 + 5351*x^3 + 1041*x^2 + 3532*x + 5251,
  1),
 (x^58 + 5459*x^57 + 4786*x^56 + 3607*x^55 + 4392*x^54 + 2367*x^53 + 5303*x^52 + 3204*x^51 + 4794*x^50 + 2378*x^49 + 645*x^48 + 1452*x^47 + 1933*x^46 + 6773*x^45 + 4640*x^44 + 2274*x^43 + 3891*x^42 + 1477*x^41 + 4066*x^40 + 4108*x^39 + 2913*x^38 + 5123*x^37 + 6328*x^36 + 4101*x^35 + 4998*x^34 + 450*x^33 + 4165*x^32 + 6184*x^31 + 1855*x^30 + 4687*x^29 + 6702*x^28 + 5797*x^27 + 7875*x^26 + 65*x^25 + 3543*x^24 + 8034*x^23 + 381*x^22 + 889*x^21 + 2914*x^20 + 1455*x^19 + 5673*x^18 + 2565*x^17 + 3031*x^16 + 1217*x^15 + 2249*x^14 + 151*x^13 + 962*x^12 + 208*x^11 + 3363*x^10 + 3652*x^9 + 8132*x^8 + 306*x^7 + 1076*x^6 + 7710*x^5 + 4645*x^4 + 2317*x^3 + 3637*x^2 + 7703*x + 4713,
  1)]
b''
b''
b'grey{hFSeQZr6PP3L9Cwx_more_vulnerable_than_xor_f9xZ3tDhTMVT73bu}'
b'\xce\xe4\xca\xf2\xf6\xd0\x8c\xa6\xca\xa2\xb4\xe4l\xa0\xa0f\x98r\x86\xee\xf0\xbe\xda\xde\xe4\xca\xbe\xec\xea\xd8\xdc\xca\xe4\xc2\xc4\xd8\xca\xbe\xe8\xd0\xc2\xdc\xbe\xf0\xde\xe4\xbe\xccr\xf0\xb4f\xe8\x88\xd0\xa8\x9a\xac\xa8nf\xc4\xea\xfa'

Footnotes

Menezes et al, 1996. The Handbook of Applied Cryptography, 2.37 ↩