TSGCTF 2021 Writeup

Tue Oct 05 2021

10/2-3 で開催していた TSGCTF2021 にチーム WreckTheLine で参加しました。結果は 22nd/775 (得点のあるチームのみカウント) でした。

見てくれは簡単そうなのにいざ解こうとすると意外と解けない、というものが多く感じました。いい問題ですね。Crypto 全部解いた後は pwn の Coffee と cHeap にずっと取り掛かっていたのですが解けなくて悲しい…

以下 Crypto 問の writeup です。

Crypto

This is DSA

9 solves

server.py
# 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')}")

requirements.txt
git+https://github.com/tsg-ut/[email protected]#egg=pycryptodome

DSA の問題。 $q$ が与えられる中、こちら側で $p, h$ を指定します。すると $y$ が返ってくるので b"flag" というメッセージに対して署名を作ることができればフラグが手に入ります。

普通の DSA っぽいなあと思って困り requirements.txt を見てみると、どうやら自前のレポジトリから pycryptodome をインストールしているみたいです。このレポジトリの commit 履歴を見てみると、以下のような diff がありました。

457d456
<         fmt_error |= ((p - 1) % q) != 0
523d521
<         fmt_error |= ((key.p - 1) % key.q) != 0

DSA に与える値のチェックがいくつかあるのですが、そのうち $p - 1 \equiv 0 \mod q$ というチェックがされないようになっています。

残ったチェックは以下だけとなります (fmt_error が True でエラーです)を。

        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
        if hasattr(key, 'x'):
            fmt_error |= key.x <= 0 or key.x >= key.q
            fmt_error |= pow(key.g, key.x, key.p) != key.y

問題の性質上、求められるのは性質のいい $p$ を見つけることです。性質のいいというのは、例えば

$h^{\lfloor(p-1)/q\rfloor q} = 1 \mod p$ となる $h$ が存在する
2048bits
- これは fips-186-3 による制約
DLP が解けるような $p$ を探す
- $y$ から $x$ を求められる

のような $p$ です。このような $p$ を見つけることができれば $x$ が既知となるので署名を作ることができます。

自分は上記方法でいけないかを考えていたのですが、いい方法が思いつきませんでした (実際には存在するし他の方はこの方法で解いていることが多そうでした。自分があほだった…この方法については後述)。なので別のアプローチとして、

$h^{\lfloor(p-1)/q\rfloor q} = 1 \mod p$ となる $h$ が存在する
2048bits
DSA の verification でいかなるメッセージ (ハッシュ) であっても $r$ が必ず同じ値 (自明な値) になる
- 特に、今回は $r = 1$ を目指した

で考えたところ、上手くできました。

まず、自明に $g^q = 1 \mod p$ なる $g$ が存在することを保証するために、 $p$ を $kq + 1$ ( $k$ は $kq + 1$ が素数となるように選ばれた自然数) の倍数としました。こうすると $\phi(p)$ は $q$ の倍数となり、適当に探索させれば $g$ が求まります。

しかしこのままでは自明な署名とはなりません。自明な署名を作るには $r = (g^k \mod p) \mod q$ の部分を $k$ の値に関わらず必ず1にしてあげるとよさそう。そこで $g = 1 \mod q$ かつ $p$ は $q$ の倍数としてあげます。 $1^q = 1 \mod p$ は必ず成り立つので CRT を使えばこのような $g$ は見つかりますし、 $r$ を計算する部分で $\mod p$ を取った後 $\mod q$ を取るので必ず $r = 1$ となります。

以上を踏まえ、 $p = 2^{\mathrm{pad}} (kq + 1)q$ (pad は $p$ が2048bits にするため) とします。 DSA の verification では $(g^{u_1}y^{u_2} \mod p) \mod q$ という計算がされますが、 $y = g^x \mod p$ なので結局この値は1となります。つまり署名 $(r, s)$ のうち $r$ が1でさえあればいかなるメッセージに対しても必ず署名は通ることとなります。

solve.sage
from base64 import b64encode

from pwn import context, remote

context.log_level = "DEBUG"

io = remote("34.146.212.53", 61234)


def recvafter(prefix: bytes) -> bytes:
    io.recvuntil(prefix)
    return io.recvline().strip()


q = int(recvafter(b"q = "))

i = 1
while True:
    tmp = i * q + 1
    if is_prime(tmp):
        p = tmp
        break
    i += 1
p *= q
p = p * 2**(2048-p.nbits())
g = crt([int(Zmod(p//q)(1).nth_root(q)), 1], [p//q, q])
h = crt([int(Zmod(p//q)(g).nth_root((p-1)//q)), int(Zmod(q)(g).nth_root((p-1)//q))], [p//q, q])

# r = 1, t != 0 であればなんでも通る
sign = b"\x00" * 31 + b"\x01" + b"\x00" * 31 + b"\x01"

io.sendlineafter(b"p? ", str(p).encode())
io.sendlineafter(b"h? ", str(h).encode())
assert int(recvafter(b"g = ")) == g
io.sendlineafter(b"sign? ", b64encode(sign))

io.recvall()

TSGCTF{WOW_AMAZING_DSA_IS_TOTALLY_BROKEN}

競技時間中は上記のようなお気持ちで解きましたが、競技終了後に writeup 漁っていたら大体の人は $p = q^8$ ( $q$ が十分大きく生成されていれば $p$ は2048bits になる) でやっていたっぽいです。こうすると $g = q^7 + 1$ で $g^q = (q^7 + 1)^q = 1 \mod p$ となり、 DLP を考えたときも $y = g^x = xq^7 + 1 \mod p$ となるので DLP が解けます。DLP が解ければ当然署名も作れます。

なるほどなあ、自分は DLP が解けるようにするために pohlig-hellman が使えるような $p$ を作ろうとしてたけど、もっとシンプルに考えればよかった…

ところで実は $p = q^8$ のときも $g = 1 \mod q$ となっているので、実は必ず $r = 1$ となっていて、自分の解き方と同様に DLP を解く必要はなさそうな気がしますね。というか $p = kq^2$ みたいな形式でも必ず $r = 1$ になりそう。考察しがいがあるなあ。

Flag is Win

10 solves

flag_is_win.rb
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 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.'

ruby で書かれた ECDSA 問題。 "Baba" というメッセージに対する署名を4個まで得られ、残りの1回で "Flag" というメッセージに対する署名を作る必要があります。

なんで ruby なんだろう、と思っていたところ、昔参加した CTF でも同じ気持ちになったことを思い出しました。SECCON 2020 の This is RSA ですね (昔自分が書いた writeup)。過去問と同様、 $k$ の生成部分で乱数を文字列で表したものを16進数表示してしまっており、 $k$ は 0x(3[0-9])+ という形になっています。適当に ruby で $k$ を生成させてみると、 3?3?... というのが25-26回繰り返されています。とりあえず26回繰り返されているとすると、 $k = \sum_{i=0}^{25} 3 \times 16^{2i+1} + \sum_{i=0}^{25} k_i \times 16^{2i}$ という式が成り立つことがわかります。

ECDSA の署名の計算式から、 $H(m)s^{-1} + ds^{-1} - k$ ( $d$ は秘密鍵) が成り立つので、これらの式から格子を作って CVP で $d$ を求め、署名を生成することができます。 CVP の部分は rkm-san の Inequality_Solving_with_CVP を使いました。 $d$ を求めるのに署名は2つで十分でした。

solve.sage
from pwn import remote, context
from hashlib import sha256
from Crypto.Util.number import bytes_to_long


context.log_level = "DEBUG"

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

EC = EllipticCurve(GF(p), [a, b])
G = EC(Gx, Gy)


io = remote("34.146.212.53", 35719)


def sign():
    io.sendlineafter(b"choice? ", b"1")
    io.recvuntil(b"x = ")
    x = int(io.recvline().strip())
    io.recvuntil(b"s = ")
    s = int(io.recvline().strip())
    return x, s


x_list = []
s_list = []
for _ in range(2):
    x, s = sign()
    x_list.append(x)
    s_list.append(s)

k_base = sum([16**i * 3 for i in range(1, 52, 2)])
Hm = bytes_to_long(sha256(b"Baba").digest())

# use https://github.com/rkm0959/Inequality_Solving_with_CVP/blob/main/solver.sage
M = len(x_list)
mat = matrix(ZZ, 26*M+M+2, 26*M+M+2)
for i in range(26*M):
    mat[i, i] = 1
for i in range(M):
    for j in range(26):
        mat[i*26+j, 26*M+i] = 256**j
    mat[26*M+i, 26*M+i] = -n
    mat[26*M+M, 26*M+i] = -int(pow(s_list[i], -1, n) * x_list[i] % n)
    mat[26*M+M+1, 26*M+i] = int((k_base - Hm * int(pow(s_list[i], -1, n))) % n)
mat[26*M+M, 26*M+M] = 1
mat[26*M+M+1, 26*M+M+1] = 1
lb = [0] * 26*M + [0] * M + [0] + [1]
ub = [9] * 26*M + [0] * M + [2**256] + [1]
res = solve(mat, lb, ub)


d = int(res[2][-2])
k = 2
x = (k * G).xy()[0]
s = (bytes_to_long(sha256(b"Flag").digest()) + int(x) * d) * int(pow(k, -1, n)) % n

io.sendlineafter(b"choice? ", b"2")
io.sendlineafter(b"know? ", b"Flag")
io.sendlineafter(b"x? ", str(x).encode())
io.sendlineafter(b"s? ", str(s).encode())
print(io.recvall())
io.close()

TSGCTF{CRYPTO_IS_LOCK._KEY_IS_OPEN._CTF_IS_FUN!}

Baba is Flag

34 solves

時系列的には Flag is Win の前に出た問題で、それよりも簡単な問題になっています。 diff はこちら。

34,35c34,36
<     # We should discourage every evil hacks
<     s = (z + x * @d) * inv(k) % @n
---
>     # We all like hacks, ain't we?
>     # s = (z + x * @d) * inv(k) % @n
>     s = (z + @d) * inv(k) % @n
45c46,47
<     x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
---
>     # x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
>     x2, y2 = (@G * (z * inv(s)) + @Q * inv(s)).xy

Flag is Win とほぼ全く同じ解き方をしました。格子をつくるところで $x$ をかけなくするだけです。コードは省略します。

TSGCTF{CRYPTO_IS_LOCK._KEY_IS_OPEN._CTF_IS_FUN!}

Minimalist's Private

49 solves

encrypt.py
from Crypto.Util.number import isPrime
from random import randrange
from secret import p, q, L, e, d

class RSA:
    def __init__(self, p, q, L, e, d):
        assert(isPrime(p) and isPrime(q))
        self.N = p * q
        self.L = L
        self.e = e
        self.d = d

        # these are the normal RSA conditions
        for _ in range(100):
            assert(pow(randrange(1, self.N), self.L, self.N) == 1)
        assert(self.e * self.d % self.L == 1)

        # minimal is the best
        assert(self.L * self.L <= 10000 * self.N)

    def gen_private_key(self):
        return (self.N, self.d)

    def gen_public_key(self):
        return (self.N, self.e)

    def encrypt(self, msg):
        return pow(msg, self.e, self.N)

    def decrypt(self, c):
        return pow(c, self.d, self.N)

flag = open('flag.txt', 'rb').read()
msg = int.from_bytes(flag, byteorder='big')
assert(msg < p * q)

rsa = RSA(p, q, L, e, d)
encrypted = rsa.encrypt(msg)
assert(rsa.decrypt(encrypted) == msg)

print(f'N, e = {rsa.gen_public_key()}')
print(f'c = {encrypted}')

RSA の問題ですが、謎のパラメータ $L$ が使われています。この $L$ についての情報をまとめると、

$\mathrm{rand}^{L} = 1 \mod N$
$L^2 \le 10000 N$

となっています。したがって $N$ についてカーマイケルの定理を考えると、 $L = \mathrm{lcm}(p-1, q-1) = (p-1)(q-1)/\gcd(p-1, q-1)$ が非常に小さい数字になっていることが期待されます。

そこで $p = iG + 1, q = jG + 1$ とおきます。 $G = \gcd(p-1, q-1)$ です。 $L = ijG$ となるので、

(ij)^2 G^2 \le 10000 (ijG^2 + (i+j)G + 1) < 10001 ij G^2

\therefore ij < 10001

が成立します。また、 $jp - iq = j - i$ です。 $(jp)(iq) = (ij)N$ で $i, j$ が小さい (すなわち $j - i$ が小さい) ことを考えると $iq \approx jp \approx \sqrt{ijN}$ となります。

以上を踏まえ、 $ij$ の値について全探索させ、 $\gcd(N, \lceil\sqrt{ij N}\rceil + k)$ が十分大きくなる $k$ を探索させました (このときに gcd の結果が p または q になる)。

競プロだったら TLE ですが、これは CTF。

solve.sage
from Crypto.Util.number import long_to_bytes


N, e = (1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151, 65537)
c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426

for ij in range(1, 10**5+2):
    tmp = ceil(sqrt(ij * N))
    for k in range(1000):
        G = gcd(tmp + k, N)
        if G.nbits() > 300:
            print(G)  # 見つかったら Ctrl+C

G = 5293956253947009870401417007695694880120669942943370772882122022200933137261970150546718751594723858094466011384272699668015027900382760667694940922283
p = G
q = N // p
phi = (p - 1) * (q - 1)
d = int(pow(e, -1, phi))
print(long_to_bytes(pow(c, d, N)))

TSGCTF{Roll_Safe:_You_c4n't_be_exploited_1f_you_are_a_minimali5t_enough_and_y0u_don't_have_any_s3crets_in_your_mind}

Beginner's Crypto 2021

126 solves

beginners_crypto_2021.py
from secret import e
from Crypto.Util.number import getStrongPrime, isPrime

p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q
phi = (p - 1) * (q - 1)

with open('flag.txt', 'rb') as f:
    flag = int.from_bytes(f.read(), 'big')

assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))

e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)
e3 = pow(e + 4, 0x10001, phi)

c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)

print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')

RSA の $p, q$ が与えられている代わりに $e$ の値が既知ではありません。しかし assert(isPrime(e + i)) ( $i = 0, 2, 4$ ) の意味を真剣に考えてみると、 $e = 3$ が確定します (∵ $e, e+2, e+4$ のどれかは必ず3の倍数になる)。

$e$ がわかれば $e_1, e_2, e_3$ もわかるので RSA の復号をやるだけに見えますが、 $\gcd(e_i, \phi) \ne 1$ となり秘密鍵を求めることができません。仕方がないので前書いたこれを参考に復号しました。

solve.sage
from Crypto.Util.number import long_to_bytes


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

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

e = 3
e1 = int(pow(e, 0x10001, phi))
e2 = int(pow(e + 2, 0x10001, phi))
e3 = int(pow(e + 4, 0x10001, phi))

l = lcm(p - 1, q - 1)

k = 3
L = pow(k, l // 3, N)
while True:
    if L != 1:
        assert L ** 3 == 1
        break
    k += 1

d1 = int(pow(e1, -1, l // 3))
for i in range(3):
    print(long_to_bytes(pow(c1, d1, N) * L**i))

TSGCTF{You are intuitively understanding the distribution of prime numbers! Bonus: You can solve this challenge w/ N instead of p and q!}