zer0pts CTF 2023 参戦記

1. はじめに

　2023/7/15（土）12:00 JST ～ 7/16（日）12:00 JST に開催された「zer0pts CTF 2023」にチーム「N30Z30N」(ソロチーム）で参加しました。これはその参戦記です。

• 2023/7/18 7:05 誤脱字等修正

　なお、結果は Crypto のみ Warmup を含む 3 問 を解いて 551 pts（得点のあったチーム 476 チーム中 85位）でした。去年は「Warmupを含めて 2 問」だったので、少しは進歩したということでしょう（？）。

2. 作戦立案

　前週の CryptoCTF （7/7 23:00～）は当日に休暇をとらず仮眠もとれなかったので、かなり肉体疲労に苦しみました*1。その反省をもとに、今回は次のようなゲームの組み立てを行うことにしました。

• 開始まで極力休養をとる。「エナジー満タン」の感触がなければ、競技前の Warmup も取りやめ。
• 開始後は解きやすそうな Crypto 問題から着手し、波に乗るとことから。
• 方向性としては、「全分野の Warmup 」ではなく、Crypto を埋める方向で進めることを想定*2。
• Crypto を全完するか行き詰った場合*3、他分野の解きやすそうな問題（この段階である程度競技は進んでいるので、solve 数も考慮）を着手。
• 途中、疲労や体調不良の兆候が見られたら、迷わず睡眠（最低 3 時間）をとる。
• 楽しめれば勝ち。

3. 参戦状況（Timeline + Writeup）

3.1 競技前～競技開始まで

【11:15】早めの昼食

　「腹が減っては戦はできぬ」という諺に忠実に従う。スタートダッシュ感を出すため、普段の朝食メニューを昼食とした。

【11:45】パソコン起動、着席

　準備OK。部屋が暑い。

【11:55】腹痛

　おいおい、このタイミングでかよ！（トイレへダッシュ）

【12:01】復帰、競技開始

　始まってるぞ！いざ参戦！

3.2 競技開始～仮眠まで

【12:02頃】「Welcome」（Discord）フラグゲット

　Sanity Check ヨシ！

【12:05頃】「Square_RNG」着手

　サーバのスクリプトを眺めるも、頭に入ってこない。というか、パソコン周辺が暑いので涼しい場所で思考できるようスクリプトを印字。

【12:15頃】虚無りタイム

　印字したスクリプトを眺めながら虚無る。

【13:15頃】「easy_factoring」着手

　とりあえず、オープンされている問題の handout データを DL して印字。easy_factoring が一番やりやすそうだったので、パソコンの前に戻り着手。

【14:00頃】「easy factoring」試行錯誤

　一応「数論屋」なので、 型の数は の元のノルム、というお気持ちを常に持っており、「 だから、N を で素因数分解し、その結果を（Conjugateはいずれか一方を選ぶようにして）組み合わせゆき、 と がともに素数になるものを見つければいいんじゃね？」という方針は割と早く決まった。

　しかし、実装力がカスでプログラムがあちこちバグってしまい、つまらんところで時間を溶かしてしまった。

【15:15頃】「easy_factoring」フラグゲット

　telnetlib とか pwntools とかで接続するプログラムを書くのが面倒だったので、N の値をコピペすると答えを出力する以下のスクリプトを SageMath のコンソールで実行させながら解いた。例によってプログラムが洗練されていない点はご容赦いただきたい。

hand out script：「server.py」

import os
import signal
from Crypto.Util.number import *

flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")

def main():
    p = getPrime(128)
    q = getPrime(128)
    n = p * q

    N = pow(p, 2) + pow(q, 2)

    print("Let's factoring !")
    print("N:", N)

    p = int(input("p: "))
    q = int(input("q: "))

    if isPrime(p) and isPrime(q) and n == p * q:
        print("yey!")
        print("Here you are")
        print(flag)
    else:
        print("omg")

def timeout(signum, frame):
    print("Timed out...")
    signal.alarm(0)
    exit(0)

if __name__ == "__main__":
    signal.signal(signal.SIGALRM, timeout)
    signal.alarm(30)
    main()
    signal.alarm(0)

ソルバ：「solve.sage」

from Crypto.Util.number import *

def isEquiv(z, z0):
  return z == z0 or z == -z0 or z == z0.conjugate() or z == -z0.conjugate() or z == I * z0 or z == I * -z0 or z == I * z0.conjugate() or z == -I * z0.conjugate()

def ZI_factor(N):
  R = ZZ[I]
  _facs = R(N).factor()
  facs = []
  for fac in _facs:
    if isEquiv(fac[0],I+1):
      continue
    else:
      OK = 1
      for z0 in facs:
        if isEquiv(fac[0], z0):
          OK = 0
          break
      if OK:
        facs.append(fac[0])
  for x in range(2**len(facs)):
    z = 1 + I
    for i in range(len(facs)):
      if (x & 2**i) >> i:
        z = z * facs[i]
      else:
        z = z * facs[i].conjugate()
    p = int(abs(z[0]))
    q = int(abs(z[1]))
    if isPrime(p) and isPrime(q) and p^2+q^2==N:
      #print(p,q)
      return(p,q)
  return None

print(ZI_factor(int(input("N= "))))

zer0pts{piyopiyo_Fermat's_Sum_of_Square_meow!!}

【15:30頃】「SquareRNG」再考

　1 問解けたので、虚無るのをやめて、スクリプトをちゃんと読むことにした。

　こちらで指定できる値はsb1とsb2で、これらをうまく決めるというところなのだが、「0」は禁止されている。次に映るのが1とか-1なのだが、どうやらこのあたりでうまくいきそうな感じである。

【17:20頃】「SquareRNG」フラグゲット

　サーバの「int」の処理で、初期値 s=0 だと勘違いしていてハマっていた。ちゃんと見直して s=1 に気づいてからは話は簡単で、sb1=1 をセットすると欲しい情報は「がで平方数かどうか」。ここで「Random 1」を32bitと見た時の先頭ビットから「がで平方数か否か」は得られるので sb2に-1をセットすれば「Random 2」の末尾ビットから「がで平方数か否か」が得られ、case closed となった。

hand out script：「server.py」

#!/usr/bin/env python3
import os
from Crypto.Util.number import getPrime, getRandomRange

def isSquare(a, p):
    return pow(a, (p-1)//2, p) != p-1

class SquareRNG(object):
    def __init__(self, p, sa, sb):
        assert sa != 0 and sb != 0
        (self.p, self.sa, self.sb) = (p, sa, sb)
        self.x = 0

    def int(self, nbits):
        v, s = 0, 1
        for _ in range(nbits):
            self.x = (self.x + 1) % p
            s += pow(self.sa, self.x, self.p) * pow(self.sb, self.x, self.p)
            s %= self.p
            v = (v << 1) | int(isSquare(s, self.p))
        return v

    def bool(self):
        self.x = (self.x + 1) % self.p
        t = (pow(self.sa, self.x, self.p) + pow(self.sb, self.x, self.p))
        t %= self.p
        return isSquare(t, self.p)

p = getPrime(256)

sb1 = int(input("Bob's seed 1: ")) % p
sb2 = int(input("Bob's seed 2: ")) % p
for _ in range(77):
    sa = getRandomRange(1, p)
    r1 = SquareRNG(p, sa, sb1)
    print("Random 1:", hex(r1.int(32)))
    r2 = SquareRNG(p, sa, sb2)
    print("Random 2:", hex(r2.int(32)))

    guess = int(input("Guess next bool [0 or 1]: "))
    if guess == int(r1.bool()):
        print("OK!")
    else:
        print("NG...")
        break
else:
    print("Congratz!")
    print(os.getenv("FLAG", "nek0pts{*** REDACTED ***}"))

ソルバ：「solve.py」

from Crypto.Util.number import *
import telnetlib

HOST = "crypto.2023.zer0pts.com"
PORT = 10666

def readline():
  return tn.read_until(b"\n")

def readuntil(s):
  return tn.read_until(s.encode())

def sendline(s):
  return tn.write(s.encode() + b"\n")

############################################################
def guess(r1,r2):
  R1 =  '0' * (32 - len(bin(r1)[2:])) + bin(r1)[2:]
  R2 =  '0' * (32 - len(bin(r2)[2:])) + bin(r2)[2:]
  res = (int(R1[0]) + int(R2[31])) % 2
  return str(res^1)

times = 77
tn = telnetlib.Telnet(HOST, PORT)

readuntil("Bob's seed 1: ")
sendline("1")
readuntil("Bob's seed 2: ")
sendline("-1")

#Question : x^33 - 1 is Square
#x^33 + 1 = (x + 1) * (x^32 - ... - x + 1)
#R1[0] :  x + 1 is square
#R2[31] : x^32 - ... - x + 1is square

for i in range(times):
  r1 = int(readline().strip().decode().replace("Random 1:", ""), 16)
  r2 = int(readline().strip().decode().replace("Random 2:", ""), 16)
  readuntil("Guess next bool [0 or 1]: ")
  sendline(guess(r1,r2))
  print(readline())
print(readline())
print(readline())

tn.close()

zer0pts{L(a)L(b)=L(ab)}

【17:30頃】仕切り直し

　次に着手する問題を決める。とりあえず、「Elliptic Ring RSA」に着手することに。ちなみに決めた理由はこれ。

• Elliptic、私の好きな言葉です。
• Ring、私の好きな言葉です。
• RSA、私の好きな言葉です。

【18:00】名探偵コナン視聴

　今年の劇場版を観たせいか、無意識のうちに灰原哀に執着してしまっている。つまり、思考回路がジンに近づいていてヤバい。

【18:45頃】ディナー

　赤いきつね（焼うどん）だったような気がするが、疲労が溜まってきたせいか記憶が薄い。

【19:30頃】「Elliptic Ring RSA」着手

　とりあえずスクリプトを読みはじめ、いろいろいじってみることにする。

【23:00頃】「Elliptic Ring RSA」を継続

　テストプログラムを動かして、環の構造を体感。とりあえず、環の（半群の）order が分かれば P の（半群の元としての）order はその約数で、d = inverse(e, order) が求まれば ER.pow(C,d)でPを復元できそうな感じである。

　それと、楕円曲線がからんでいるせいか、計算コストは高めである。

　しかし、眠くなってきたので、とりあえず d を求めるプログラムを雑に書き、寝ている間に計算させることにした。

【25:45頃】就寝

　プログラムがなかなか書けず、だいぶ時間を溶かしてしまった。

3.3 起床～競技終了まで

【5:00頃】起床＆朝飯

　目覚ましで起きる。とりあえずメシ、否、プログラムの実行結果。

　order の計算を勘違いしているっぽい（ちゃんと考えず、(p-1)*(E.order())とかいろいろやっていた）。この環は t := E.order、 としたとき、実質 だから、orderはp^t-1（の約数）でよいはず！

　修正＆再稼働。

　しかし朝飯を食べた後、意識が飛んで前方タイムリープ。

【8:00頃】再起床＆事故

　意識回復。パソコンを見ると、計算がうまくいっているっぽい。

　ポチっ。

　ん？

　あれ、SageMathのコンソールWindowsが消えた！

　やっちまった。(>_<)

　気を取り直して8:30頃～再計算開始。終わるのか？

　無理っぽいけど、このパソコンは伊達じゃない！

【11:25頃】「Elliptic Ring RSA」フラグゲット

　計算終わった！よっしゃ！見せてやったぜ、わが軍の新しいパソコンの性能とやらを！

hand out script「q.sage」

import string
import random

flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")

class EllipticRingElement:
    point = None
    def __init__(self, point):
        self.point = point
    
    def __add__(self, other):
        if self.point == dict():
            return other
        if other.point == dict():
            return self
        res = self.point.copy()
        for k in other.point.keys():
            if k in res:
                res[k] += other.point[k]
                if res[k] == 0:
                    res.pop(k)
            else:
                res[k] = other.point[k]
                if res[k] == 0:
                    res.pop(k)
        return EllipticRingElement(res)
    
    def __mul__(self, other):
        if self.point == dict() or other.point == dict():
            return self.point()
        res = dict()
        for k1 in other.point.keys():
            for k2 in self.point.keys():
                E = k1 + k2
                k = other.point[k1] * self.point[k2]
                if E in res:
                    res[E] += k
                    if res[E] == 0:
                        res.pop(E)
                else:
                    res[E] = k
                    if res[E] == 0:
                        res.pop(E)
        return EllipticRingElement(res)
    
    def __repr__(self):
        st = ""
        for k in self.point.keys():
            st += f"{self.point[k]}*({k[0]}, {k[1]}) + "
        return st[:-3]
    
class EllipticRing:
    E = None
    Base = None
    def __init__(self, E):
        self.E = E
        self.Base = E.base()

    def __call__(self, pt):
        for P in pt:
            pt[P] = self.Base(pt[P])
        return EllipticRingElement(pt)
    
    def zero(self):
        return EllipticRingElement(dict())
    
    def one(self):
        return EllipticRingElement({E(0): self.Base(1)})
    
    def pow(self, x, n):
        res = self.one()
        while n:
            if (n & 1):
                res = res * x
            x = x * x
            n >>= 1
        return res
    
    def encode(self, m, length):
        left = random.randint(0, length - len(m))
        pad1 = "".join(random.choices(string.ascii_letters, k=left)).encode("utf-8")
        pad2 = "".join(random.choices(string.ascii_letters, k=length-len(m)-left)).encode("utf-8")
        m = pad1 + m + pad2

        Ps = []
        while len(Ps) < length:
            PP = self.E.random_element()
            if PP not in Ps:
                Ps.append(PP)
        Ps = sorted(Ps)

        M = dict()
        for coef, pt in zip(m, Ps):
            M[pt] = self.Base(coef)
        return EllipticRingElement(M)
    
def random_prime_bits(nbits):
    return random_prime(2^nbits-1, false, 2^(nbits-1))

nbits = 8
p = random_prime_bits(nbits)
Fp = GF(p)

a = Fp.random_element()
b = Fp.random_element()
E = EllipticCurve(Fp, [a, b])

ER = EllipticRing(E)

P = ER.encode(flag, 30)

e = 13
C = ER.pow(P, e)

print(f"p: {p}")
print(f"C: {C}")
print(f"a: {a}")
print(f"b: {b}")
print(f"e: {e}")

「output.txt」 （省略）

ソルバ：「solve.sage」

from Crypto.Util.number import *
p = 211 # from output.txt
Fp = GF(p)
a = 201 # from output.txt
b = 102 # from output.txt
E = EllipticCurve(Fp, [a, b])
ord_ER = p**E.order()-1
e = 13 # from output.txt
d = inverse(e, ord_ER//13)

assert e*d % (ord_ER//13) == 1

C_ = "182*(91, 45) + 147*(3, 164) + 85*(62, 60) + 53*(77, 59) + 99*(77, 152) + 18*(137, 59) + 106*(169, 101) + 147*(127, 127) + 154*(152, 163) + 121*(43, 73) + 155*(110, 160) + 202*(116, 45) + 195*(1, 84) + 106*(71, 162) + 33*(209, 122) + 112*(134, 164) + 186*(1, 127) + 72*(183, 116) + 141*(141, 39) + 72*(83, 127) + 157*(197, 175) + 6*(178, 24) + 106*(71, 49) + 114*(57, 201) + 95*(181, 58) + 1*(174, 44) + 193*(202, 27) + 182*(121, 95) + 52*(167, 179) + 109*(184, 177) + 110*(21, 162) + 101*(126, 170) + 208*(47, 102) + 168*(129, 105) + 209*(179, 123) + 210*(160, 70) + 10*(13, 103) + 159*(76, 55) + 165*(31, 26) + 31*(44, 119) + 47*(6, 70) + 150*(74, 47) + 117*(30, 65) + 3*(108, 69) + 61*(43, 138) + 151*(72, 209) + 122*(110, 51) + 127*(44, 92) + 64*(191, 113) + 61*(45, 70) + 155*(91, 166) + 175*(95, 194) + 97*(21, 49) + 210*(66, 191) + 129*(129, 106) + 210*(80, 7) + 157*(174, 167) + 45*(141, 172) + 189*(155, 78) + 160*(194, 1) + 209*(82, 28) + 142*(164, 136) + 135*(199, 155) + 166*(118, 95) + 100*(123, 14) + 203*(121, 116) + 22*(36, 20) + 33*(65, 58) + 196*(189, 60) + 75*(137, 152) + 22*(125, 4) + 45*(119, 162) + 59*(47, 109) + 102*(177, 157) + 196*(109, 20) + 112*(192, 94) + 97*(209, 89) + 67*(95, 17) + 129*(75, 55) + 34*(134, 47) + 156*(60, 156) + 135*(127, 84) + 11*(148, 147) + 194*(202, 184) + 27*(45, 141) + 131*(4, 166) + 166*(148, 64) + 183*(164, 75) + 177*(130, 145) + 128*(107, 8) + 204*(156, 40) + 131*(17, 25) + 99*(177, 54) + 122*(82, 183) + 52*(178, 187) + 130*(168, 19) + 14*(150, 150) + 173*(167, 32) + 82*(184, 34) + 172*(72, 2) + 144*(169, 110) + 7*(118, 116) + 96*(181, 153) + 34*(133, 5) + 97*(207, 17) + 24*(78, 161) + 54*(57, 10) + 90*(143, 188) + 172*(130, 66) + 179*(146, 65) + 38*(55, 202) + 170*(63, 31) + 99*(35, 65) + 162*(150, 61) + 56*(74, 164) + 146*(144, 85) + 196*(133, 206) + 164*(152, 48) + 139*(176, 153) + 92*(125, 207) + 124*(31, 185) + 136*(0, 1) + 118*(107, 203) + 28*(24, 56) + 66*(171, 151) + 127*(76, 156) + 63*(208, 59) + 187*(146, 146) + 138*(85, 0) + 195*(19, 190) + 115*(60, 55) + 87*(171, 60) + 194*(17, 186) + 79*(75, 156) + 181*(27, 37) + 38*(192, 117) + 168*(13, 108) + 41*(143, 23) + 167*(199, 56) + 177*(86, 71) + 160*(35, 146) + 165*(189, 151) + 130*(32, 30) + 39*(108, 142) + 197*(36, 191) + 176*(120, 17) + 180*(194, 210) + 204*(19, 21) + 160*(6, 141) + 195*(109, 191) + 194*(155, 133) + 62*(65, 153) + 6*(138, 107) + 12*(201, 62) + 43*(180, 43) + 178*(208, 152) + 86*(180, 168) + 135*(55, 9) + 5*(138, 104) + 118*(207, 194) + 58*(160, 141) + 173*(66, 20) + 16*(179, 88) + 181*(61, 131) + 3*(80, 204) + 137*(119, 49) + 106*(126, 41) + 127*(176, 58) + 64*(144, 126) + 96*(30, 146) + 165*(168, 192) + 104*(27, 174) + 64*(63, 180) + 35*(123, 197) + 111*(86, 140) + 141*(197, 36) + 83*(116, 166) + 159*(4, 45) + 165*(62, 151) + 94*(183, 95) + 133*(3, 47) + 58*(83, 84) + 149*(201, 149) + 96*(20, 112) + 141*(191, 98) + 113*(24, 155) + 139*(61, 80) + 73*(120, 194) + 116*(78, 50) + 68*(156, 171) + 31*(32, 181)" # from output.txt
C_ = C_.split(" + ")

C = dict()
for c in C_:
  v, k = c.split("*")
  pt = eval(k)
  if pt == (0,1):
    pt = [0,1,0]
  C[E(pt)] = E.base()(v)

class EllipticRingElement:
  point = None
  def __init__(self, point):
    self.point = point
  def __add__(self, other):
    if self.point == dict():
      return other
    if other.point == dict():
      return self
    res = self.point.copy()
    for k in other.point.keys():
      if k in res:
        res[k] += other.point[k]
        if res[k] == 0:
          res.pop(k)
      else:
        res[k] = other.point[k]
        if res[k] == 0:
          res.pop(k)
    return EllipticRingElement(res)
  def __mul__(self, other):
    if self.point == dict() or other.point == dict():
      return self.point()
    res = dict()
    for k1 in other.point.keys():
      for k2 in self.point.keys():
        E = k1 + k2
        k = other.point[k1] * self.point[k2]
        if E in res:
          res[E] += k
          if res[E] == 0:
            res.pop(E)
        else:
          res[E] = k
          if res[E] == 0:
            res.pop(E)
    return EllipticRingElement(res)
  def __repr__(self):
    st = ""
    for k in self.point.keys():
      st += f"{self.point[k]}*({k[0]}, {k[1]}) + "
    return st[:-3]

class EllipticRing:
  E = None
  Base = None
  def __init__(self, E):
    self.E = E
    self.Base = E.base()
  def __call__(self, pt):
    for P in pt:
      pt[P] = self.Base(pt[P])
    return EllipticRingElement(pt)
  def zero(self):
    return EllipticRingElement(dict())
  def one(self):
    return EllipticRingElement({E(0): self.Base(1)})
  def pow(self, x, n):
    res = self.one()
    while n:
      if (n & 1):
        res = res * x
      x = x * x
      n >>= 1
    return res
  def encode(self, m, length):
    left = random.randint(0, length - len(m))
    pad1 = "".join(random.choices(string.ascii_letters, k=left)).encode("utf-8")
    pad2 = "".join(random.choices(string.ascii_letters, k=length-len(m)-left)).encode("utf-8")
    m = pad1 + m + pad2
    Ps = []
    while len(Ps) < length:
      PP = self.E.random_element()
      if PP not in Ps:
        Ps.append(PP)
    Ps = sorted(Ps)
    M = dict()
    for coef, pt in zip(m, Ps):
      M[pt] = self.Base(coef)
    return EllipticRingElement(M)

ER = EllipticRing(E)
CC = EllipticRingElement(C)
P = ER.pow(CC,d)

P0_ = str(P)

P0_ = P0_.split(" + ")
P0 = dict()
for c in P0_:
  v, k = c.split("*")
  pt = eval(k)
  P0[pt] = v

SK = []
for k in P0.keys():
  SK.append(k)

SK = sorted(SK)
VS = []
for k in SK:
  VS.append(chr(int(P0[k])))

flag = "".join(VS)
print(flag)

zer0pts{Gr0up_r1ng_meow!!!}

4. 解けなかった問題

　競技中に解けた問題は上のもので全てです。

　なお、チャレンジして解けなかったのは以下の 4 つです。

• moduhash 　Elliptic Ring RSA の次にやろうと思っていたのですが、時間切れ。

• Unlimited Braid Work 　Braid 群知らなかったので不戦敗。

• RSALCG2 　作者が Keymoon さんであることは、server.py を見ただけでピンときました。サーバスクリプト中の 「^」 見て心折れました。

• decompile me 　雑に key と enc を取り出して RC4 復号やってみたけどうまくいかなかった。雑すぎて失敗。

※UpsolveはTBD。

5. おわりに（振り返りと謝辞）

• Good：無理だと思ってあきらめかけた問題を通せた。
• Bad：虚無っていた時間があまりに多かった。
• Next：暗号関連の数学知識（引き出し）を増やす、Project Eular への参戦。

最後になりましたが、今年も楽しい大会を開催をしてくださった zer0pts の皆様、対戦してくださった参加者の皆様、ありがとうございました。

*1:開始後 6 時間くらいでグロッギーとなり、リポＤスーパーとチョコレートの投与でどうにか復帰しました。

*2:実際には、その時のお気持ち次第。すべての決定権が自分にあるのが「ソロチーム」の利点ですので。

*3:ガチ問題が出ることが予想されるので、実質的には行き詰ることを想定しています。