CPCTF 2024 writup

1. はじめに

　4/20-21、今年も東工大デジタル創作同好会 traP さんが主宰する「CPCTF 2024」に「EdwowMath」で参加しました。

▼開催案内 trap.jp

▼東工大デジタル創作同好会traPさんのTwitter

4/20日(土)~4/21日(日)に、競プロとCTFの大会であるCPCTFを開催します！

初心者から上級者まで楽しめる問題を準備しております。
新入生で上位の成績を取られた方にはささやかながら賞品も準備しておりますので、ぜひご参加ください！

詳細は以下のブログをご覧ください。 https://t.co/wD3rg7nJtV

— 東工大デジタル創作同好会traP (@traPtitech) 2024年4月18日

twitter.com

　昨年よりも少しだけ多くプレイ時間は確保できましたが、Crypto と Forensics などを数問解くだけで終わってしまいました。実はこの時期に楽しげな CTF イベント*1があることは予測していて、「4/21 は IPA の試験日だから、CTF 開催があるとすれば 4/27 か 28 だろう」と Guess したのですがハズレ*2でした。

　ちなみに、ランキングは 52 位でした。合成数ですが平方因子を取り除けば*3、素数だ（苦しい）！

　以下、Forensics と Crypto から 1問ずつ（いずれも難易度 Medium）の writeup を記します。

2. Writeup

2.1. which is true flag (Forensics)

設問

メールでflagを受け取れるサービスに登録したんだけど、どれが本物かわからないや。助けて～。

　10000個 の emlファイルが入った zip アーカイブが与えられます。

　どのメールもクーポン ID の部分がフラグ文字列になっており、一見しただけでは真贋は判然としません。

検討

　雑にサイズで比較し、一番大きいか小さいものではないかと Guess しましたがハズレでした*4。

　そこで、糸口を探るためフラグ文字列以外で各メールにある差異を確認します（*の部分が各メールで異なる点）。

Delivered-To: [deprecated]
Received: by [deprecated] with SMTP;
        Wed, 10 Apr 2024 **:**:** -0700
Return-Path: flagProvider@trap.jp
Received: from flagProvider@trap.jp ([*.*.*.*])
        for <[deprecated]>
        (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128);
        Wed, 10 Apr 2024 **:**:** -0700
Date: Wed, 10 Apr 2024 **:**:** +0000
Message-ID: <1711280279.71604854bdb2@trap.jp>
From: "FlagProvider" <flagProvider@trap.jp>
Precedence: list
To: [deprecated]
Subject: this is Flag
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="CaZbzhBcFLIbRm4oHyaTGmRS10UXycIAgvlMBxvY"
Content-Transfer-Encoding: 8bit
（後略）

　いくつか選んで雑に比較してみると、相違点はメールヘッダの「日時」と「Received の IP アドレス」のようです。

解法

　IP アドレスが「trap.jp」にまつわるものであればホンモノ、と推測し、まずは雑に nslookup した結果で Grep しても出てきません。

　そこで、ViewDNS info（https://viewdns.info/）で 「trap.jp」の DNS Report を取り、「MX レコード」を確認します。

　「60.243.212.49.in-addr.arpa <--> www3550.sakura.ne.jp.」という記載があるので、「49.212.243.60」で Grepすると、アタリを引けました。

フラグ

CPCTF{bzMpKzAMmJPYcwSIzPcJ}

2.2. AAAA (Crypto)

設問

traP専用のssh-key鍵を作りました. 秘密鍵ファイルなので見せられないですがなんとTOKYO+INSTITUTE+OF+TECHNOLOGY+DIGITAL+CREATORS+CLUB+TRAPAAAA をファイルに含ませることに成功しました(下のコードブロック参照)! 余計なAAAAついてる原因はたぶんBluetoothキーボードの電池が途中で切れて最後の入力文字を入力し続けたせいです(知らんけど). チェックコードとログ渡すのでうまく行ってるか確認して欲しいな.

-----BEGIN OPENSSH PRIVATE KEY-----
****************************************************************************
****************************************************************************
****************************************************************************
****************************************************************************
****************************************************************************
****************************************************************************
****************************************************************************
****************************************************************************
****************************************************************************
****************************************************************************
****************************************************************************
****************************************************************************
****************TOKYO+INSTITUTE+OF+TECHNOLOGY+DIGITAL+CREATORS+CLUB+TRAPAAAA
****************************************************************************
****************************************************************************
****************************************************************************
************************************************************
-----END OPENSSH PRIVATE KEY-----

　「チェックコードとログ」として、以下の python スクリプト、出力データ、公開鍵情報が与えられます。

「check.py」

from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.backends import default_backend
from flag import flag
from Crypto.Util.number import bytes_to_long

with open("id_original_rsa", "rb") as key_file:
    private_key = serialization.load_ssh_private_key(key_file.read(), password=None, backend=default_backend())


d = private_key.private_numbers().d
p = private_key.private_numbers().p
q = private_key.private_numbers().q
e = private_key.private_numbers().public_numbers.e

# write above to log
with open("log.txt", "w") as f:
    # should be 1?
    f.write(f"check:{d * e // ((p - 1) * (q - 1))}")


with open("id_original_rsa.pub", "rb") as key_file:
    public_key = serialization.load_ssh_public_key(key_file.read(), backend=default_backend())

e = public_key.public_numbers().e
n = public_key.public_numbers().n

# ecrypt flag
c = pow(bytes_to_long(flag), e, n)

with open("log.txt", "a") as f:
    f.write(f"\ncipher_txt:{c}")

「log.txt」

check:664970535868760471861569536340291069667883992376028708769845457783613660265052576839423273653848019325779003789765689843558710301491594080036941832108949705955593516764818937279323965091627546748674211266507786466008632121410963708374997250619464487575615405705625432462121329034121265811768509604395398
cipher_txt:91909831605657069445845285327703537320564411834583437474685559300515808097121545408912830638788814887579525882344139171811485832485059084283941124305156610689962166410078761970967400765774729703472221849202068624455203268518779280481613556790751660833883720545638508961571818018544412339125981301492301611155

「id_original_rsa.pub」

ssh-rsa AAAAB3NzaC1yc2EAAACASBVCRibRXqtqQZlDX+GlC3v3WayWucdYlXlrM1WuIcJR4uxBbmUABbcxLmUrygPqfgAmW6vPywE2xNHiJ5DE07/ES38GT4Dw9ZE5ojD9jGvzHD9sebqviVGMfxzZFvJQBoJanrD0DmXx3Jb22K0EuGA1F/Mfkf0fGxax/Gno7s8AAACBAK+3xKv8Z1BAoY5L8qQ1jkErc50LQiPz6sMNMHL6VzMTEbZlmsqv/OJrXZrpGe0IbtJ/h72XUvb5wv8/9RzovM7SILPiPdxS7fNqNk6rtuauymyAVJeI452EWz/ydti4lsGtQB2RgRoMv+J06d2DXoeW43duXqZAGRc/n8Sei97T

検討

　チェックコードから、秘密鍵 d は概ね 1024bit であることと、上位ビット（全体の半分くらい）は判明します。が、Coppersmith で算出するには未知の部分が大きすぎます。

　公開鍵のうちリークしている部分をよく見ると、d の下位 336 ビット分と考えられるため*5、これらを合わせれば d を算出できます。

解法

　複数未知数に効く、例の「defund/coppersmith」の助けを借りました*6。

　実際には対話型で計算しながらやりましたが、まとめると以下のようなソルバになります。

「solve.sage」

from Crypto.Util.number import *
import itertools

#from https://github.com/defund/coppersmith
def small_roots(f, bounds, m=1, d=None):
  if not d:
    d = f.degree()

  if isinstance(f, Polynomial):
    x, = polygens(f.base_ring(), f.variable_name(), 1)
    f = f(x)

  R = f.base_ring()
  N = R.cardinality()
  
  f /= f.coefficients().pop(0)
  f = f.change_ring(ZZ)

  G = Sequence([], f.parent())
  for i in range(m+1):
    base = N^(m-i) * f^i
    for shifts in itertools.product(range(d), repeat=f.nvariables()):
      g = base * prod(map(power, f.variables(), shifts))
      G.append(g)

  #B, monomials = G.coefficient_matrix()
  B, monomials = G.coefficients_monomials()
  monomials = vector(monomials)

  factors = [monomial(*bounds) for monomial in monomials]
  for i, factor in enumerate(factors):
    B.rescale_col(i, factor)

  B = B.dense_matrix().LLL()

  B = B.change_ring(QQ)
  for i, factor in enumerate(factors):
    B.rescale_col(i, 1/factor)

  H = Sequence([], f.parent().change_ring(QQ))
  for h in filter(None, B*monomials):
    H.append(h)
    I = H.ideal()
    if I.dimension() == -1:
      H.pop()
    elif I.dimension() == 0:
      roots = []
      for root in I.variety(ring=ZZ):
        root = tuple(R(root[var]) for var in f.variables())
        roots.append(root)
      return roots

  return []

check = 664970535868760471861569536340291069667883992376028708769845457783613660265052576839423273653848019325779003789765689843558710301491594080036941832108949705955593516764818937279323965091627546748674211266507786466008632121410963708374997250619464487575615405705625432462121329034121265811768509604395398
cipher_txt = 91909831605657069445845285327703537320564411834583437474685559300515808097121545408912830638788814887579525882344139171811485832485059084283941124305156610689962166410078761970967400765774729703472221849202068624455203268518779280481613556790751660833883720545638508961571818018544412339125981301492301611155

#from cryptography.hazmat.primitives import serialization
#from cryptography.hazmat.primitives.asymmetric import rsa
#from cryptography.hazmat.backends import default_backend
#with open("id_original_rsa.pub", "rb") as pubkey_file:
#  public_key = serialization.load_ssh_public_key(pubkey_file.read(),backend=default_backend())
#e = public_key.public_numbers().e
e= 50618433852658748379043300943454705578640059546418608667534588435517890985399798108491679178955555911923406334739318656389639710389456285931259335434222801093593078698699166819597977524166255300639767424325935155600622100054669838107915117515970781609068507655428974834627111173507712406777016056768683896527
#n = public_key.public_numbers().n
n = 123393266848753774793988537953180028539115250856106025537216773380958628152562100672118606928463978436011165444467480532772417083604480800733710941324873110091771811088565570080174630816085848424528561607402232783421513798645607303961634498411528751498617746292710162722858597500115435758238375018411049344723

#e * d - 1 = check * phi 
approx_d = ((check * n // e)//2**512)*2**512

#from leaked private key
lower_d = 0x4ce2983be20d49321351313e385f931021cd38b38663e0c81884c02fe0911004ce452f822d407e4d100f

PR.<x,y> = PolynomialRing(Zmod(n))
bounds = (2**(512-336), 2**512)
f = (approx_d + x*2**336 + lower_d) * e - 1 - check * (-y+1)
r = small_roots(f, bounds, m=4, d=2)
 
d = int(approx_d + r[0][0]*2**336 + lower_d)
print(long_to_bytes(pow(cipher_txt,d,n)))

2024/04/22 17:30 追記：

　e と check は互いに素なので、Coppersmith を持ち出すまでもなく、

p_plus_q = (n + 1 + pow(check,-1, e)) % e

で p+q が算出できてしまいますね。

フラグ

CPCTF{sh0rt_pu61ic_k3y_e_w4s_difficu1t_t0_g3n}

3. 感想

　今回も少ししかできていませんが、程よくパンチが効いた問題があって面白かったです。

　また、昨年に引き続き全て競プロ問題をスルーしてしまった点と、日程 Guess で失敗した点を反省＆懺悔しています。

　次回はガッツリ参加したいと思います。

*1:CPCTF のほか、Ricerca CTF、Wani CTF などの開催があり得ると想定していました。

*2:まぁ私の Guessing 能力はこの程度なのですよ。

*3:二次体が大好きな数学徒なので、ついやってしまいがちなのです。

*4:CPCTF でそんなクソ問が出るはずもなく、大変失礼なことをしてしまったと反省。

*5:openssh で RSA 秘密鍵を作成し、e のサイズと AAAA の場所から推測しました。

*6:ただし、手許の SageMath（10.3）に怒られたので「coefficient_matrix」を「coefficient_monomial」に修正。