Preliminary

As far as I’m concerned crypto involves a bunch of maths. After painstakingly but successfully solving 3 out of the 8 challenges in this category in time (which is low as hell), I can imagine the amount of maths one has to know in order to solve many of these.

I’ll attempt to go through all 8 challenges, in detail.

The Challenges

crypto/rot727

That name reminds us of ROT13, a rotation cipher. We know every flag starts with osu{, so to make it quick, just put the string in CyberChef. Set amount to 14 and the challenge is solved.

crypto/beyond-wood

First of all, I completely forgot about this challenge while solving one of the later ones. But the most embarrasing part of all is I forgot how to solve this one during the contest.

Anyway, back to the solve. The archive contains an altered image named output.png and an encryptor written in Python. Our challange is to recover flag.png.

1
from PIL import Image
2
import random
3

4
FLAG = Image.open("flag.png")
5
width, height = FLAG.size
6

7
key = [random.randrange(0, 256) for _ in range(width+height+3)]
8

9
out = FLAG.copy()
10
for i in range(width):
11
  for j in range(height):
12
    pixel = FLAG.getpixel((i, j))
13
    pixel = tuple(x ^ k for x, k in zip(pixel, key))
14
    newi, newj = (2134266 + i * 727) % width, (4501511 + j * 727) % height
15
    out.putpixel((newi, newj), pixel)
16

17
out.save("output.png")

Let’s make some observations.

This encryptor has two layers to it:

• The first being an XOR color layer, per-pixel, with a tiny $key$. Only the first $C$ bytes of $key$ matter where $C \in \{3,4\}$ for RGB/RGBA (due to $zip$).
• The other being a per-axis affine map, given $W$ is width, $H$ is height, with:

Talk about the basics of XOR, let $C = P \oplus K$. Then $P = C \oplus K$, because XOR is its own inverse.

So, for the dominant plaintext color $p_\star$ and dominant ciphertext color $c_\star$:

If the original background was black, $p_\star=(0,0,0)$, so $K = c_\star$. Extend with the alpha byte if the image was RGBA.

Then about the inversion of an affine permutation. We invert

where $a^{-1}$ is the modular inverse of $a$ modulo $n$. This exists if $\gcd(a,n)=1$. Here $a=727$, so as long as $727 \nmid W$ and $727 \nmid H$, both axes are invertible.

From there we have a solve strategy to reverse what was done. For this whole segment, since we don’t see any opaque property of the encrypted image, let’s assume alpha is not present.

We can use frequency to recover the XOR key: Compute the mode color of the ciphertext RGB histogram, $c_\star$. Finding $p_\star$ is easily done with Python.

Then we try inverting the shuffle. Compute

Write $(C \oplus K)$ at $(x,y)$. The challenge is solved.

Here’s my solve script:

1
from PIL import Image
2
from collections import Counter
3

4
enc_i = Image.open("output.png")
5
width, height = enc_i.size
6

7
px = list(enc_i.getdata())
8

9
colors = Counter(px)
10
xor_key = colors.most_common(1)[0][0]
11

12
dec_img = Image.new('RGB', (width, height))
13

14
inv_w = pow(727, -1, width)
15
inv_h = pow(727, -1, height)
16

17
for i in range(width):
18
  for j in range(height):
19
    enc_px = enc_i.getpixel((i, j))
20

21
    dec_px = tuple(p ^ k for p, k in zip(enc_px, xor_key))
22

23
    org_i = ((i - 2134266) * inv_w) % width
24
    org_j = ((j - 4501511) * inv_h) % height
25

26
    dec_img.putpixel((org_i, org_j), dec_px)
27

28
dec_img.save("flag_decrypted.png")

We get a pretty funny image with the flag handwritten in it.

crypto/xnor-xnor-xnor

Looks like something about XNOR. There is a single Python script in the challenge archive.

1
import os
2

3
flag = open("flag.txt", "rb").read()
4

5
def xnor_gate(a, b):
6
  if a == 0 and b == 0:
7
    return 1
8
  elif a == 0 and b == 1:
9
    return 0
10
  elif a == 1 and b == 0:
11
    return 0
12
  else:
13
    return 1
14

15
def str_to_bits(s):
16
  bits = []
17
  for x in s:
18
    bits += [(x >> i) & 1 for i in range(8)][::-1]
19
    return bits
20

21
def bits_to_str(bits):
22
  return bytes([sum(x * 2 ** j for j, x in enumerate(bits[i:i+8][::-1])) for i in range(0, len(bits), 8)])
23

24
def xnor(pt_bits, key_bits):
25
  return [xnor_gate(pt_bit, key_bit) for pt_bit, key_bit in zip(pt_bits, key_bits)]
26

27
key = os.urandom(4) * (1 + len(flag) // 4)
28
key_bits = str_to_bits(key)
29
flag_bits = str_to_bits(flag)
30
enc_flag = xnor(xnor(xnor(flag_bits, key_bits), key_bits), key_bits)
31

32
print(bits_to_str(enc_flag).hex())
33
# 7e5fa0f2731fb9b9671fb1d62254b6e5645fe4ff2273b8f04e4ee6e5215ae6ed6c

XNOR is bitwise NOT of XOR: xnor(x,k) = ~(x ^ k). The two very useful identities we’ll be using:

• When we check the truth table, we can see xnor(x,k) is also ~(x) ^ k.
• Applying the NOT and the XOR rule gives us some interesting result:

~((~x) ^ k) = x ^ k

Now apply twice, we get:

xnor(xnor(x,k), k)
= ~(~(x ^ k) ^ k)
= x (by identity)

So two XNORs just cancel each other. The challenge Python code used three, so that means it’s just a single XNOR:

xnor(xnor(xnor(x,k), k), k) = xnor(x,k)

Therefore the encryption is just enc = ~(flag ^ key), and from that, we get key = (~enc) ^ flag. Furthermore, the challenge script repeats some 4-byte block across the message. We know the first four plaintext bytes, that’s just osu{ established by the rules of this contest.

Recover the flag by building a key stream flag = (~enc) ^ key_stream. The challenge is solved.

Here’s my solve script:

1
enc_hex = "7e5fa0f2731fb9b9671fb1d62254b6e5645fe4ff2273b8f04e4ee6e5215ae6ed6c"
2
enc = bytes.fromhex(enc_hex)
3

4
def xnor_byte(a,b): return (~(a ^ b)) & 0xFF
5

6
prefix = b"osu{"
7
k4 = bytes(xnor_byte(p,e) for p,e in zip(prefix, enc[:4]))
8

9
ks = k4 * ((len(enc)//4) + 1)
10
flag = bytes(xnor_byte(e,k) for e,k in zip(enc, ks))
11
print(flag.decode())

crypto/pls-nominate

It’s getting a little difficult, I gave up on this at the very beginning. After trying to solve this, I completely understand why I would never solve this in the given timeframe.

The challenge archive includes two files, a plaintext file containing the results of a Python script file.

1
from Crypto.Util.number import *
2

3
FLAG = open("flag.txt", "rb").read()
4
message = bytes_to_long(
5
    b"hello there can you pls nominate my map https://osu.ppy.sh/beatmapsets/2436259 :steamhappy: i can bribe you with a flag if you do: " + FLAG
6
)
7

8
ns = [getPrime(727) * getPrime(727) for _ in range(5)]
9
e = 5
10
print(len(FLAG))
11
print(ns)
12
print([pow(message, e, n) for n in ns])

The text file is the output of this script, as expected. Now let’s make a couple of observations, we’re given a script that does these things:

• It creates a plaintext msg = prefix || FLAG, FLAG is obviously unknown and prefix is,
• It then generates 5 RSA moduli $n_i = p_i \times q_i$, with each constructed by getPrime(727) * getPrime(727),
• It uses a small public exponent $e = 5$,
• Finally it prints the 5 moduli and the 5 ciphertexts $c_i = m^e \mod n_i$

Our challenge is to reverse what this does to our flag. After doing some bits of research, I found out about the RSA low-exponent setup, which is supposed to be a classic: If the same plaintext $m$ is encrypted under $e$ different moduli $n_1,...,n_e$ with the same small exponent $e$ and no padding, and if

then the Chinese Remainder Theorem lets us compute the integer

and if actually $M = m^e$ as integers, taking the integer $e$-th root of $M$ recovers $m$ exactly.

That was a mouthful, but that is Håstad’s broadcast attack in its simplest form. In our case $e = 5$ and we have exactly 5 ciphertexts, this is intended, but there is this one case where we’re bust: if $m^5 \geq N$, the Chinese Remainder Theorem will only give us $M = m^5\,(\bmod\,N)$, and the plain integer root may not exist.

Not the end of the world though. If that’s actually the case, note that there must exist a positive integer $k$ such that:

We can probably try small $k$ values and check if $M + kN$ is a perfect $e$-th power. Basically saying we’re relying on luck and the kindness of the challenge author here, lol.

Practically this might work. In theory, $k$ could be a really big number because

and if $m^e$ is several times bigger then $N$, the ratio is stupid huge. To be brutally honest if $k$ was something of the worst case I wouldn’t know how do I approach this challenge.

Here’s my solve script. That actually succeeded.

1
# paste ns and cts in, there's line wrap here and they're massive
2
# qwq
3
ns = []
4
cts = []
5
e = 5
6

7
def integer_nth_root(x: int, n: int):
8
  if x < 0:
9
    raise ValueError
10
  if x == 0:
11
    return 0, True
12
  lo, hi = 0, 1 << ((x.bit_length() + n - 1) // n)
13
  while lo <= hi:
14
    mid = (lo + hi) // 2
15
    p = mid ** n
16
    if p == x:
17
      return mid, True
18
    if p < x:
19
      lo = mid + 1
20
    else:
21
      hi = mid - 1
22
  return hi, (hi ** n == x)
23

24
def crt_combine(ns, cts):
25
  N = 1
26
  for ni in ns:
27
    N *= ni
28
  total = 0
29
  for ni, ci in zip(ns, cts):
30
    Ni = N // ni
31
    inv = pow(Ni, -1, ni)
32
    total += ci * Ni * inv
33
  total %= N
34
  return total, N
35

36
def main():
37
  M, N = crt_combine(ns, cts)
38
  root, exact = integer_nth_root(M, e)
39
  if exact:
40
    m = root
41
  else:
42
    # brute-force small k; tuned to reasonable limit for this CTF instance
43
    max_k = 1 << 20
44
    m = None
45
    for k in range(max_k):
46
      y = M + k * N
47
      root, exact = integer_nth_root(y, e)
48
      if exact:
49
        m = root
50
        break
51
    if m is None:
52
      raise SystemExit(1)
53
  msg = m.to_bytes((m.bit_length() + 7) // 8, 'big').lstrip(b'\x00')
54
  prefix = b"hello there can you pls nominate my map https://osu.ppy.sh/beatmapsets/2436259 :steamhappy: i can bribe you with a flag if you do: "
55
  if not msg.startswith(prefix):
56
    # fallback: try stripping leading zeros once more, then check
57
    msg = msg.lstrip(b'\x00')
58
    if not msg.startswith(prefix):
59
      raise SystemExit(1)
60
  flag = msg[len(prefix):]
61
  try:
62
    print(flag.decode())
63
  except Exception:
64
    print(flag.hex())
65

66
if __name__ == "__main__":
67
  main()

That map was qualified a couple of hours after this challenge airs. :steamhappy: indeed.

crypto/linear-feedback

There are several things I won’t mention again in this writeup since they’ve been mentioned (and being the good reader you are, you’ve made it halfway), but when I think the concepts should be mentioned again I will.

I also gave up at this challenge from the very beginning, mainly because I was always scared of Linear Feedback Shift Registers (LFSR). That was a nightmare for me during the times I tried to solve other CTFs alone and this concept appeared more than I initially anticipated (be reminded I am a linguistics major, LOL).

But anyway. I’ll simplify the script used in the challenge archive:

1
# Two LFSRs
2
key1 = randbits(21)
3
key2 = randbits(29)
4

5
L1 = LFSR(key1, [2, 4, 5, 1, 7, 9, 8], "{:021b}")
6
L2 = LFSR(key2, [5, 3, 5, 5, 9, 9, 7], "{:029b}")
7

8
# Output 72 bits: XNOR of the two LFSR output bits at each clock
9
bits = [xnor_gate(L1._clock(), L2._clock()) for _ in range(floor(72.7))]  # 72 bits
10
print(bits)
11

12
# Flag is XOR'd with SHA-256(str(key1)+str(key2)) repeated
13
keystream = sha256((str(key1) + str(key2)).encode()).digest() * 2
14
print(xor(FLAG, keystream).hex())

This is the instance of that script we’re given to work with:

1
bits =
2
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0]
3

4
cipherhex =
5
9f7f799ec2fb64e743d8ed06ca6be98e24724c9ca48e21013c8baefe83b5a304af3f7ad6c4cc64fa4380e854e8

Let’s make some observations.

The LFSR class is MSB-first and it outputs the initial state directly:

1
ob = self.state[0] # first bit of current state
2
self.state = self.state[1:] + [ ... ] # shift left, append feedback

That state is created through list("{:0wb}".format(key)). Because the output is state[0] before shifting, the first n outputs of an n-bit LFSR are… the n bits of the initial state. In order as well. That means if we know the first 29 outputs of L2, we know key2.

The taps. They are sum’d mod 2, with dupes: Feedback is sum(state[t] for t in taps) % 2, and duplicates matter only modulo 2. The effective L2 tap from its original [5, 3, 5, 5, 9, 9, 7] is just {3, 5, 7}.

Then we know this, because of XNOR:

So, guess key1 to generate 72 output bits of L1. If we can do that, we can deterministically derive 72 such bits of L2 as well, then use that to derive key2.

From there we have our solve strategy. First, we try to brute-force key1 since it’s small enough (just around 2m tries, that’s fine), then for each key1:

• Simulate L1 for 72 clocks
• Deduce the wanted $L2_i$ as above
• Take the first 29 bits of that L2 as its initial state, then find key2
• Verify by simulating L2 to see if it produces what we deduced
• Compute the keystream like the challenge did, then decrypt the flag.

The challenge is solved. Here’s my solve script:

1
from hashlib import sha256
2

3
# pls supply them like above qwq
4
obs = []
5
cipher = bytes.fromhex()
6

7
L1_n, L2_n = 21, 29
8
L1_taps = [2,4,5,1,7,9,8]
9
L2_taps = [5,3,5,5,9,9,7]
10
fmt1 = "{:021b}"
11
fmt2 = "{:029b}"
12
need = len(obs)
13

14
def step_bits(state, taps):
15
  # output is state[0]
16
  # feedback is sum(state[t]) % 2
17
  ob = state[0]
18
  fb = 0
19
  for t in taps: fb ^= state[t] # xor is fine (sum mod 2)
20
  return ob, state[1:] + [fb]
21

22
def run_lfsr_bits(key, fmt, taps, outlen):
23
  s = list(map(int, fmt.format(key)))
24
  out = []
25
  for _ in range(outlen):
26
    ob, s = step_bits(s, taps)
27
    out.append(ob)
28
  return out
29

30
def bits_to_int_msb(bits):
31
  v = 0
32
  for b in bits: v = (v<<1) | b
33
  return v
34

35
def solve():
36
  for k1 in range(1<<L1_n):
37
    l1 = run_lfsr_bits(k1, fmt1, L1_taps, need)
38
    # deduce L2 output stream
39
    l2_wanted = [(b if x==1 else 1-b) for b,x in zip(l1, obs)]
40
    # recover key2
41
    k2 = bits_to_int_msb(l2_wanted[:L2_n])
42
    # verify that
43
    l2 = run_lfsr_bits(k2, fmt2, L2_taps, need)
44
    if l2 != l2_wanted:
45
      continue
46
    # build keystream like chall if found
47
    ks = sha256((str(k1) + str(k2)).encode()).digest() * 2
48
    flag = bytes(c ^ k for c, k in zip(cipher, ks))
49
    try:
50
      txt = flag.decode()
51
    except:
52
      txt = None
53
    if txt and ("{" in txt and "}" in txt):
54
      print(txt)
55
      return
56

57
if __name__ == "__main__":
58
    solve()

The brute takes quite some time. For simplicity my solution is using a list, which makes it take a while, I recommend you to look into int-based LFSR! That’d make it seconds.

Also, I’ve read one other writeup of this same problem that uses Gaussian elimination, which seems to be able to get the exact initial states in a single shot, not brute-forcing like this. I think that solution is wonderful, but it has no explanation to it, which is quite sad.

Anyway, :steamhappy:, I like that song as well, being a taiko player.

crypto/ssss

So, this one. Being the third least solved challenge at the time I was about to submit the flag (it was around 50 solves, which is abysmally low compared to the actual challenges later on), I was wondering what was wrong.

The challenge archive, outside of that netcat server we’re supposed to get things, has a single script file. I’ll once again truncate it:

1
p = 2**255 - 19
2
k = 15
3
SECRET = random.randrange(0, p)
4

5
def lcg(x, a, b, p): return (a*x + b) % p
6

7
a = randrange(0,p)
8
b = randrange(0,p)
9
poly = [SECRET]
10
while len(poly) != k:
11
    poly.append(lcg(poly[-1], a, b, p))
12

13
for _ in range(k - 1):
14
    x = int(input())
15
    print(sum(c * x^i (mod p))) # that's not xor
16

17
if int(input("secret? ")) == SECRET: print(FLAG)

Checking the server’s behavior, it allows us to query $k - 1 = 14$ values of

where the unknown coeff. vector $c = (c_0,...,c_{14})$ isn’t arbitrary, but satisfies the LCG relation

with unknown $a, b \in \mathbb{F}_p$. SECRET is $c_0$.

We can draw a rough solve plan like this:

• Obviously try to probe at $x = 1,2,...,14$ to get 14 equations $A\,c = y\ (\bmod\ p)$ where $A$ is a $14 \times 15$ matrix. Interestingly this is a Vandemonde(-ish) matrix as well.
• Then we solve the linear system modulo $p$, as in a particular solution $c_\star$ plus a 1-dimensional nullspace spanned by $n$ (rank = 14, generically):

• Impose the LCG structure $c_{i+1} = ac_i + b$ to eliminate $a$ and $b$, then derive a quadratic in $t$. We’ll solve that in $\mathbb{F}_p$.
• For each $t$, try to reconstruct $c$, find $a,\ b$ and check if both conditions hold: that LCG holds for all indices and it matches the oracle evals.

Oh but where does the quadratic come from, though?

Check this derivation out: from the linear solve, for each $i$, we have

Define first differences:

Let $C_i = c_{\star, i + 1} - c_{\star, i}$ and $D_i = n_{i + 1} - n_i$, $\Delta_i(t) = C_i + tD_i$ is affine in $t$. Call that (1).

From the LCG,

When we plug $c_{i + 1}$ back in, we get:

Therefore, whenever $\Delta_i(t) \neq 0$,

Consistency over two distinct indices $i \neq j$ forces the ratios to match:

Now we plug (1) back in, cross-multiply, we get:

That’s a quadratic with term $t$.

with $\alpha = (D_{i + 1}D_j - D_{j + 1}D_i)$, $\beta = (C_{i + 1}D_j + D_{i + 1}C_j - C_{j + 1}D_i - D_{j + 1}C_i)$ and $\gamma = (C_{i + 1}C_j - C_{j + 1}C_i)$.

We solve this in $\mathbb{F}_p$ and get two $t$ candidates. Now that’s why this challenge is named like that, QuadS.

For each $t$ candidate:

• Build $c_i = c_{\star, i} + tn_i$
• Pick any $i$ with $\Delta_i \neq 0$ and set $a = \Delta_{i + 1}\ \Delta_i^{-1}$
• Try to find $b = c_1 - ac_0$
• Finally, verify if $c_{i + 1} = ac_i + b$ for all $i$, and that $f(x)$ evaluates to what we observed.

That’s our $c_0$ = SECRET. The challenge is solved.

Here’s my solve script. Note that this script does not do the nc part itself, just so I can present the math concepts without the noise:

1
p = 2**255 - 19
2
k = 15
3

4
# paste your 14 oracle outputs (f(1)..f(14)) here qwq
5
ys = []
6

7
def inv(x):  # mod inverse
8
    return pow(x % p, p-2, p)
9

10
def ts_sqrt(a):  # Tonelli–Shanks sqrt mod p
11
  a %= p
12
  if a == 0: return 0
13
  if pow(a, (p-1)//2, p) != 1: return None
14
  q, s = p-1, 0
15
  while q % 2 == 0: q //= 2; s += 1
16
  z = 2
17
  while pow(z, (p-1)//2, p) != p-1: z += 1
18
  m, c = s, pow(z, q, p)
19
  t, r = pow(a, q, p), pow(a, (q+1)//2, p)
20
  while t != 1:
21
    i, t2i = 1, pow(t, 2, p)
22
    while t2i != 1:
23
      i += 1
24
      t2i = pow(t2i, 2, p)
25
    b = pow(c, 1 << (m-i-1), p)
26
    m, c = i, (b*b) % p
27
    t, r = (t*c) % p, (r*b) % p
28
  return r
29

30
def solve_quadratic(a, b, c):  # ax^2+bx+c=0 over F_p
31
  a %= p; b %= p; c %= p
32
  if a == 0:
33
    return [] if b == 0 and c != 0 else ([(-c*inv(b))%p] if b else list())
34
  inv2 = inv(2)
35
  disc = (b*b - 4*a*c) % p
36
  s = ts_sqrt(disc)
37
  if s is None: return []
38
  x1 = ((-b + s) * inv(2*a)) % p
39
  x2 = ((-b - s) * inv(2*a)) % p
40
  return [x1] if x1 == x2 else [x1, x2]
41

42
def gauss_mod(A, b):
43
  """Solve A*c=b (mod p) with A: m x n (here 14x15).
44
  Returns particular solution 'part' and a single null vector 'null'."""
45
  m, n = len(A), len(A[0])
46
  M = [A[i][:] + [b[i]%p] for i in range(m)]
47
  row, piv = 0, []
48
  for col in range(n):
49
    if row == m: break
50
    sel = next((r for r in range(row, m) if M[r][col] % p), None)
51
    if sel is None: continue
52
    M[row], M[sel] = M[sel], M[row]
53
    iv = inv(M[row][col])
54
    for c in range(col, n+1): M[row][c] = (M[row][c]*iv) % p
55
    for r in range(m):
56
      if r != row and M[r][col] % p:
57
        f = M[r][col]
58
        for c in range(col, n+1):
59
          M[r][c] = (M[r][c] - f*M[row][c]) % p
60
    piv.append(col); row += 1
61
  part = [0]*n
62
  for r, col in enumerate(piv): part[col] = M[r][n]
63
  free = [c for c in range(n) if c not in piv]
64
  assert len(free) == 1, "expected nullspace dim 1"
65
  f = free[0]
66
  null = [0]*n; null[f] = 1
67
  for r, col in enumerate(piv): null[col] = (-M[r][f]) % p
68
  return part, null
69

70
def recover_secret(xs, ys):
71
  # build 14x15 Vandermonde-like matrix for x^0..x^14
72
  A = []
73
  for x in xs:
74
    row, powx = [], 1
75
    for _ in range(k):
76
      row.append(powx)
77
      powx = (powx * x) % p
78
    A.append(row)
79
  part, null = gauss_mod(A, ys)
80

81
  # first-difference arrays C_i, D_i for i=0..12
82
  C = [(part[i+1]-part[i]) % p for i in range(k-1)]
83
  D = [(null[i+1]-null[i]) % p   for i in range(k-1)]
84

85
  # build one quadratic in t using indices i and j=i+1
86
  # a t^2 + b t + g = 0
87
  for i in range(k-3):
88
    j = i+1
89
    alpha = (D[i+1]*D[j] - D[j+1]*D[i]) % p
90
    beta  = (C[i+1]*D[j] + D[i+1]*C[j] - C[j+1]*D[i] - D[j+1]*C[i]) % p
91
    gamma = (C[i+1]*C[j] - C[j+1]*C[i]) % p
92
    sols = solve_quadratic(alpha, beta, gamma)
93
    for t in sols:
94
      c = [(part[u] + t*null[u]) % p for u in range(k)]
95
      # derive a,b from first nonzero diff
96
      a = None
97
      for u in range(k-2):
98
          den = (c[u+1]-c[u]) % p
99
          if den: a = ((c[u+2]-c[u+1]) * inv(den)) % p; break
100
      if a is None: continue
101
      b = (c[1] - a*c[0]) % p
102
      # verify LCG
103
      if all((c[u+1] - (a*c[u]+b)) % p == 0 for u in range(k-1)):
104
        # verify evals
105
        ok = True
106
        for x,y in zip(xs, ys):
107
          val, powx = 0, 1
108
          for u in range(k):
109
            val = (val + c[u]*powx) % p
110
            powx = (powx * x) % p
111
          if val != y % p: ok = False; break
112
        if ok: return c[0]  # SECRET
113
  raise SystemExit("no solution found; check inputs")
114

115
def main():
116
  if len(ys) != k-1: raise SystemExit("need 14 values in ys")
117
  xs = list(range(1, k))  # 1..14
118
  secret = recover_secret(xs, [y % p for y in ys])
119
  print(secret)
120

121
if __name__ == "__main__":
122
  main()

Yeah this is hard. Not very :steamhappy: this time, but we got 100% accuracy, fast.

crypto/please-nominate

This challenge is one of the two 3/5s difficulty-wise, denoted by the challenge author.

The moment I see 3/5 after bugging myself at the previous challenge, which was denoted as a 2/5, prompts me immediately this has got something to do with Sage. I gave up at that point, lol.

After doing some research again since I was not equipped with the sufficient knowledge to solve the easier variant of this challenge, crypto/pls-nominate, this seems like it was another Håstad-style small-e broadcast attack with different known prefixes.

We can just see the challenge like this:

• Every ciphertext is a cube,
• Every plaintext is known_prefix || FLAG,
• Every FLAG has the same length for all three messages,
• There are three coprime moduli $n_1, n_2, n_3$,
• Recover the small unknown suffix $x$

So the entire challenge is basically a single cubic congruence modulo $N = n_1n_2n_3$ with a small root, then we run a univariate Coppersmith to pull that root out.

Let $L$ be the number of FLAG bytes. For each BN in ["Plus4j", "Mattay", "Dailycore"], define its prefix string $p_i =$ “hi there {BN}, ”, then turn these prefixes into integers:

with $f$ a bytes_to_long function.

Why the $256^L$ though? Now, that’s because concatenation in base-256 is

Let the FLAG, as an integer, be $x = f(\text{FLAG})$, so each message is

Since the challenge uses $e = 3$, each ciphertext is

with pairwise coprime $n_i$, each a product of two 727-bit primes.

Now we turn the three congruences into one cubic modulo $N$. Expand $(A_i + x)^3$ and move $c_i$ to the left, we get:

For each coeff. position we know its residue mod $n_i$. Then, we build the global coeffs. modulo $N = n_1n_2n_3$ using the Chinese Remainder Theorem coeff. wise:

• $C_2 = 3A_i\quad (\bmod\ n_i)$,
• $C_1 = 3A^2_i\quad (\bmod\ n_i)$,
• $C_0 = A^3_i - c_i\quad (\bmod\ n_i)$.

We get integers $C_2, C_1, C_0$ with

Any $x$ that solves the three original congruences will satisfy that.

Our last work is to just briefly check over the small-root condition. Bitlengths:

• Each $n_i$ is $\approx$ 1454 bits
• $N = n_1n_2n_3 \approx 3 \times 1454 \approx 4362$ bits.
• $N^{1/3} \approx 2^{1454}$.

The FLAG has $L = 147$ bytes, so $x < 256^{147} = 2^{1176} < N^{1/3}$, we’re good.

Finally, recover $x$ with univariate Coppersmith. The challenge is solved.

Here’s my solve script:

1
from sage.all import *
2
from Crypto.Util.number import bytes_to_long, long_to_bytes
3

4
L = 147
5

6
# paste them in qwq
7
data = [
8
  ("Plus4j", Integer(), Integer()),
9
  ("Mattay", Integer(), Integer()),
10
  ("Dailycore", Integer(), Integer()),
11
]
12

13
N = Integer(1)
14
for _, n, _ in data:
15
  N *= n
16

17
P.<x> = PolynomialRing(Zmod(N))
18
f = 0
19
const = 0
20
shift = 2**(8*L)  # 256^L
21

22
# cubic via CRT weighting (same thing as coeff-wise CRT)
23
for name, n, c in data:
24
  A = Integer(bytes_to_long(f"hi there {name}, ".encode())) * shift
25
  w = N // n
26
  f += w * (x**3 + 3*A*x**2 + 3*(A*A % n)*x)
27
  const += w * (c - pow(A, 3, n))
28

29
f = (f - const).monic()
30

31
# find small root x < 256^L (the flag as integer)
32
for i in range(1, 101):
33
  roots = f.small_roots(X=shift, beta=i/100)
34
  if roots:
35
    print(long_to_bytes(int(roots[0])))
36
    break

crypto/ssssp

The following challenge is rated 3/5 by the challenge author.

Now, I’ve seen some, supposedly, 4/5, crypto challenges. I obviously can solve none of them, and I know for sure two days aren’t going to cut it for those challenges for many, many teams. The general idea around these very difficult challenges is we get away with several tricks in our sleeves, this is no exception to that.

By the time I’m writing this (October 29), I haven’t seen any writeup for this challenge posted. I can’t fact-check my maths and tricks, given this is the hardest crypto challenge of this contest, some of these might convey the wrong idea.

Now back to the challenge. The only script file in the challenge archive looks awfully similar to QuadS, but this time we have to deal with a hidden modulus $pp$.

Summarizing the challenge, we once again need to find $c_0$, our SECRET. The server:

• Has this evaluation field $p = 2^{255} - 19$
• Has this hidden modulus $pp$ that’s a random 256-bit prime
• Has the coeffs. $\{ c_i \}^{k - 1}_{i = 0}$, $k = 15$, generated by an LCG modulo $pp$:

• Has an oracle that returns $f(x) = \sum_{i = 0}^{14}c_ix^i\ (\bmod\ p)$ for our chosen $x$.

Here comes the tricks.

Isolating the odd coeffs. mod p with symmetry

Query in pairs $(x,\ p - x)$. Modulo $p$, we have $p - x = -x$, then: