y011d4.log

面白かった Crypto 問 2022

Tue Dec 06 2022

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

前回の記事は ptr-yudai さん による Best Pwnable Challenges 2022 でした。難しかった…

はじめに

去年に引き続き自分が解いた中で2022年の面白かった Crypto 問を紹介したいと思います。去年は参加した CTF の Crpto 問をリストアップするところまでやったのですが、今年は スプラトゥーンのせいで 時間がないため、割愛します。 以下では問題の紹介とともに一部解説を行っているので、ネタバレを踏みたくない人は問題名だけ目次で見てググってください。

ちなみに参加した CTF 一覧はこちら。厳密には問題だけダウンロードしたものも含んでいると思います。今年はあまり CTF やっていないなという感覚だったのですが、毎週何かしら問題解いているペースでドン引きです。

 1月  9  2022 tetctf
 1月 19  2022 rctf
 1月 19  2022 tastelessctf
 1月 23  2022 real_world_ctf
 1月 29  2022 insomni
 2月  6  2022 dicectf
 2月 12  2022 defcamp
 2月 27  2022 codegate
 2月 28  2022 tsjctf
 3月 12  2022 intigriti
 3月 24  2022 zer0ptsctf
 3月 24  2022 picoctf
 3月 28  2022 linectf
 4月  3  2022 midnightsun
 4月 10  2022 securinets_yosen
 4月 17  2022 crewctf
 4月 24  2022 b01lers
 4月 29  2022 nahamcon
 4月 30  2022 angstrom
 5月  1  2022 cpctf
 5月  5  2022 fcsc
 5月  8  2022 sdctf
 5月 11  2022 securinets
 5月 14  2022 tsglive
 5月 14  2022 m0lecon
 5月 18  2022 cyber_apocalypse
 5月 29  2022 defcon
 6月  5  2022 ctf4b
 6月  7 23:16 hsctf
 6月 12 19:08 wectf
 6月 12 23:59 justctf
 6月 25 23:09 aaa
 7月  3 22:47 googlectf
 7月 16 11:38 cryptoctf
 7月 17 14:27 nazotokictf
 7月 31 12:00 uiuctf
 8月  7 21:27 corctf
 8月 13 05:39 defcon_final
 8月 21 09:08 boeisho
 8月 27 21:52 maplectf
 9月  3 22:55 cakectf
 9月 10 10:01 csaw
 9月 25 17:08 ductf
10月  1 01:11 blackhat
10月  1 22:52 project_sekai
10月  9 21:46 cyber_security_rumble
10月 15 20:56 asis
10月 22 17:39 tsukuctf
10月 24 21:24 hacktheboo
11月  7 09:01 n1ctf
11月 12 22:30 seccon
11月 19 15:29 tsglive-11
11月 27 16:54 hitcon

面白かった Crypto 問

HITCON CTF 2022: Chimera

この問題はソースコードが非常に短くシンプルなのに、解くためにはそこそこ難しいテクニックを多量に要する、芸術点がかなり高い問題です。それぞれのテクニック単体は過去問で見たことがあるものですが、このソースコードの量で詰め込めるのは本当にすごい。本来自分は見慣れた手法を使った問題に対してあまり感動を覚えないのですが、この問題については別でした。

この問題については自分で writeup を書いたことがないので、ついでにここで書きます。

公式 writeup は こちら。

chall.sage
import os
from Crypto.Util.number import bytes_to_long, getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from secret import flag


p = getPrime(384)
q = getPrime(384)
n = p * q
Gx = bytes_to_long(os.urandom(32))
Gy = bytes_to_long(os.urandom(32))
a = randint(1, n**2)
b = (Gy**2 - (Gx**3 + a * Gx)) % (n**2)

E = EllipticCurve(Zmod(n), [a, b])
gift = int(E.change_ring(GF(p)).order() * E.change_ring(GF(q)).order())
assert gift * E(Gx, Gy) == E(0, 1, 0)
print(f"{gift = }")

E = EllipticCurve(Zmod(n**2), [a, b])
lion_head = E(Gx, Gy)
goat_body = [randint(1, n) * lion_head for _ in range(16)]
snake_tail = [os.urandom(16) for _ in range(64)]
chimera = [sum([x * y for x, y in zip(tail, goat_body)]) for tail in snake_tail]
print("chimera =", [P.xy() for P in chimera])

key = sha256(str(sum(goat_body).xy()[0]).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, b"\0" * 16)
flagct = cipher.encrypt(pad(flag, 16))
print(f"{flagct = }")

解くための流れは大きく分けると以下の6ステップに分かれます。

  • 楕円曲線のパラメータ a,ba, b と nn を求める
  • Gx,GyG_x, G_y を求める
  • gift と nn から nn を素因数分解する (Gx,GyG_x, G_y を求めるのとどっちが先でもよい)
  • G=E(Gx,Gy),Ci=chimeraiG = E(Gx, Gy), C_i = \mathrm{chimera}_i として、 kiG=Cik_i G = C_i となる kik_i を求める
  • hjh_j を randint(1, n) で生成された整数、 xijx_{ij} を os.urandom(16) で生成された整数として、 xijhj=kix_{ij} h_j = k_i となる xij,hjx_{ij}, h_j を求める
  • フラグを求める

a, b, n を求める

これは比較的簡単で、60 solves ぐらいの難易度じゃないでしょうか。楕円曲線 E(Z/n2Z)E(\Z / n^2 \Z) 上の点 CiC_i が64個既知なことを利用して求めていきます。

CiC_i の x,yx, y 座標をそれぞれ xi,yix_i, y_i とすると、 xi3+axi+b=yi2mod  n2x_i^3 + ax_i + b = y_i^2 \mod n^2 となります。 この式の添字が0のものと ii のもので差をとると bb が消去できて、 x03−xi3+a(x0−xi)=y02−yi2mod  n2x_0^3 - x_i^3 + a(x_0 - x_i) = y_0^2 - y_i^2 \mod n^2 が得られます。 さらにこの式の添字が i,ji, j の2式で aa を消すと (x0−xj)×(y02−yi2−x03+xi3)=(x0−xi)×(y02−yj2−x03+xj3)mod  n2(x_0 - x_j) \times (y_0^2 - y_i^2 - x_0^3 + x_i^3) = (x_0 - x_i) \times (y_0^2 - y_j^2 - x_0^3 + x_j^3) \mod n^2 が得られます。 左辺と右辺の値はどちらも計算可能で、これの差が n2n^2 の倍数であることから、複数の i,ji, j のケースでこの差を求めて GCD を計算することで n2n^2 が求まります。

LCG の問題でパラメータが未知のときの解き方と似てますね。

Gx, Gy を求める

このあたりは LLL の典型っぽい問題なので 20 solves ぐらいの難易度ですかね。 a,b,na, b, n が既知なこと、 Gx,GyG_x, G_y が a,b,na, b, n と比べて十分小さいことから LLL で求められます。

具体的には Gy2−Gx2G_y^2 - G_x^2 が 27682^{768} bits 程度、 GxG_x が 22562^{256} bits 程度なので以下のような格子を考えます。

(10a01b00−n2)\left( \begin{array}{ccc} 1 & 0 & a \\ 0 & 1 & b \\ 0 & 0 & -n^2 \end{array} \right)

この行列に左から (Gx,1,k)(G_x, 1, k) (kk は n2n^2 で割ったときの商) をかけることで (Gx,1,Gy2−Gx3)(G_x, 1, G_y^2 - G_x^3) となりますが、このベクトルのノルムは行列よりも小さいことが期待されるので LLL で求まります。 実際に計算するときは (Gx,1,k)(G_x, 1, k) をかけたときの各要素のサイズが同程度の大きさになるように、↑の行列の1列目に 2(768−256)2^{(768-256)}, 2列目に 27682^{768} をかけておきます。このとき格子行列の行列式の 1/31/3 乗は938bits程度となり、 768<938768 < 938 なので求まることが期待されます。詳しくは昔書いた LLL アルゴリズムの Crypto 問への適用 や各所の LLL 紹介記事をご覧ください。

n を素因数分解する

ここからかなり難易度が上がります。単体で 10 solves ぐらいの難易度？これは解き方がわからなくて公式 writeup を見ました。 ある楕円曲線 E(Z/nZ)E(\Z / n \Z) 上の点 XX について、 E(Z/pZ)E(\Z / p \Z) 上では lXl X が無限遠点となるが E(Z/qZ)E(\Z / q \Z) 上では lXl X が無限遠点とならないような ll について、 lXl X が未定義となる (?) ことを利用するみたいです。 このような ll は gifted の約数であることが必要なため、 gift を適当に割り算していくことで条件を満たす ll を求めていきます。

この手法は前に出た CTF でも見覚えがありましたが、原理が深くは理解できていないので忘れてしまってました…

ki を求める

ここまででようやく半分ぐらいです。これ単体だと 10 solves ぐらいの難易度ですかね。楕円曲線 E(Z/p2Z)E(\Z / p^2 \Z) や E(Z/q2Z)E(\Z / q^2 \Z) 上では、解が p,qp, q 以下の場合、実は簡単に離散対数問題が解けてしまうよという話です。 といっても自分はアルゴリズムの理解はできていないのでここで紹介できることはありません… (理解して書こうと思ったが、投稿日に間に合わなかったです) zer0pts 2021 の pure division が似た問題なので、原理的な話は これの公式 writeup を参照してください。投げやりですみません。

hi, xij を求める

これでほぼ終わりです。これ単体だと 10 solves ぐらいだと思います。

これはいわゆる hidden subset sum problem になっており、Nguyen-Stern algorithm で解くことができます。 zer0pts 2022 の Karen が似た問題になっています。 自分の writeup でアルゴリズムのお気持ちを整理しているのでそちらをご参照ください。 注意点として、 Karen では 0 or 1 のベクトルを作っているところを、今回の問題では 0-255 の範囲のベクトルを探す必要があります。

こう振り返ってみると、 Chimera の 1/3 ぐらいは zer0pts でできていますね。

フラグを求める

あとはやるだけです。 上記で求めた hih_i の順番は不定なのですが、 key に使われているのは ∑ihi\sum_i h_i なので問題なしです。 長かった…

hitcon{literally_mixing_everything_together}

Google CTF 2022: Custom Protocol

この問題は Crypto 問には珍しくロジック的なバグが巧妙に隠されていていました。多くの人はバグの存在にすら気づかなかったのではないでしょうか。バグに気づいてもそれの利用の仕方は非自明なところも高評価です。protobuf を使っている関係で無駄にソースコードが長くなっているのがマイナスポイントですが、それでもかなり面白いと思います。

公式 solver は こちら。

server.py
#!/usr/bin/python3.9

# Copyright 2022 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

import enum
import gmpy2
import hashlib
import hmac
import msgs_pb2 
import os
import time
import typing

debug = True  # We can set it to False when in production.
flag = open('flag.txt', 'rb').read().strip()

class DataType(enum.Enum):
  RSA_ENC = 1
  RSA_SIG = 2

version = "My crypto protocol v0.0.1"
enc_oid = ('For this encryption oid I am not sure, but I would guess something '
           'in between 1.2.840.113549.2.7 and 1.2.840.113549.1.1.5 plus nonce '
           ':).')
sig_oid = ('For this signing oid I am not sure, but I would guess something '
           'in between 1.2.840.113549.2.7 and 1.2.840.113549.1.1.5 plus nonce '
           ':).')
enc_algorithm = ('For this encryption algorithm I am not sure, but I would '
                 'guess something in between hmacWithSHA1 and '
                 'sha1WithRSAEncryption plus nonce :).')
sig_algorithm = ('For this signing algorithm I am not sure, but I would guess '
                 'something in between hmacWithSHA1 and '
                 'sha1-with-rsa-signature plus nonce :).')

def pad(data_to_pad: bytes, block_size: int) -> bytes:
    #Apply ISO/IEC 7816-4 padding.
    padding_len = block_size - len(data_to_pad) % block_size
    padding = b'\x80' + b'\x00'*(padding_len - 1)
    return data_to_pad + padding

def unpad(padded_data: bytes, block_size: int) -> bytes:
    #Remove ISO/IEC 7816-4 padding.
    pdata_len = len(padded_data)
    padding_len = pdata_len - padded_data.rfind(b'\x80')
    return padded_data[:-padding_len]

def bytes2int(bytes_val: bytes) -> int:
  return int.from_bytes(bytes_val, 'big')

def int2bytes(int_val: int) -> bytes:
  int_val = int(int_val)
  return int_val.to_bytes((int_val.bit_length() + 7) // 8, 'big')


class RSA:

  def __init__(self):
    self.e = 65537
    self.p = gmpy2.next_prime(bytes2int(os.urandom(256)) | 2**2047 | 2**2046)
    self.q = gmpy2.next_prime(bytes2int(os.urandom(256)) | 2**2047 | 2**2046)
    self.dp = gmpy2.invert(self.e, self.p-1)
    self.dq = gmpy2.invert(self.e, self.q-1)
    self.qInv = gmpy2.invert(self.q, self.p)
    self.n = self.p*self.q
    self.bl = self.n.bit_length()//8

  def parse(self, msg: bytes, hmac_key: bytes, data_type: DataType) -> int:
    if data_type == DataType.RSA_ENC:
      data = msgs_pb2.RSAEncryptionData()
      data.plaintext = msg
      data.oid = enc_oid
      data.algorithm_name = enc_algorithm
    elif data_type == DataType.RSA_SIG:
      data = msgs_pb2.RSASignatureData()
      data.oid = sig_oid
      data.algorithm_name = sig_algorithm
    else:
      raise ValueError('Unknown Data Type.')
    data.version = version
    data.hmac_key = hmac_key
    data.nonce = hmac.digest(hmac_key, int2bytes(time.time()), hashlib.sha1)
    data.digest_message = hmac.digest(hmac_key, msg, hashlib.sha1)
    m = bytes2int(pad(data.SerializeToString(), self.bl))
    if not m < self.n:
      raise ValueError('Message is too long.')
    return m

  def unparse(self, m: int,
              data_type: DataType) -> typing.Union[msgs_pb2.RSAEncryptionData,
                                                   msgs_pb2.RSAEncryptionData]:
    if data_type == DataType.RSA_ENC:
      data = msgs_pb2.RSAEncryptionData()
    elif data_type == DataType.RSA_SIG:
      data = msgs_pb2.RSASignatureData()
    else:
      raise ValueError('Unknown Data Type.')
    data.ParseFromString(unpad(int2bytes(m), self.bl))
    return data

  def encrypt(self, msg: bytes, hmac_key: bytes) -> int:
    return pow(self.parse(msg, hmac_key, DataType.RSA_ENC), self.e, self.n)

  def decrypt(self, enc: int) -> bytes:
    mp = pow(enc, self.dp, self.p)
    mq = pow(enc, self.dq, self.q)
    h = self.qInv*(mp - mq) % self.p
    m = mq + h*self.q
    data = self.unparse(m, DataType.RSA_ENC)
    digest_message = hmac.digest(data.hmac_key,
                                 data.plaintext,
                                 hashlib.sha1)
    if digest_message != data.digest_message:
      raise ValueError('Can\'t decrypt. Integrity check failed.')
    return data.plaintext

  def sign(self, msg: bytes, hmac_key: bytes) -> int:
    sp = pow(self.parse(msg, hmac_key, DataType.RSA_SIG), self.dp, self.p)
    sq = pow(self.parse(msg, hmac_key, DataType.RSA_SIG), self.dq, self.q)
    h = self.qInv*(sp - sq) % self.p
    s = sq + h*self.q
    return s

  def verify(self, msg: bytes, sig: int) -> bool:
    m = pow(sig, self.e, self.n)
    data = self.unparse(m, DataType.RSA_SIG)
    digest_message = hmac.digest(data.hmac_key, msg, hashlib.sha1)
    return digest_message == data.digest_message

def menu() -> int:
  print("")
  print("[1] Get Public key")
  print("[2] Get Encrypted flag")
  print("[3] Decrypt flag")
  print("[4] Get signed flag")
  print("[5] Verify signed flag")
  print("[6] Exit")
  op = int(input(">>> "))
  return op
 
def operation_loop(rsa):
  while True:
    op = menu()
    if op == 1:
      print('e =', hex(rsa.e))
      print('n =', hex(rsa.n))
    elif op == 2:
      hmac_key = os.urandom(16)
      enc = rsa.encrypt(flag, hmac_key)
      print('enc =', hex(enc))
      if debug:
        assert rsa.decrypt(enc) == flag
    elif op == 3:
      enc = int(input("enc (hex)? "), 16)
      try:
        res = rsa.decrypt(enc)
      except:
        res = None
      if res == flag:
        print("Flag decrypted with success :-)")
      else:
        print("Something went wrong. Incorrect ciphertext?")
    elif op == 4:
      hmac_key = os.urandom(16)
      sig = rsa.sign(flag, hmac_key)
      print('sig =', hex(sig))
      if debug:
        assert rsa.verify(flag, sig)
    elif op == 5:
      sig = int(input("sig (hex)? "), 16)
      try:
        res = rsa.verify(flag, sig)
      except:
        res = None
      if res:
        print("Signed flag verified with success :-)")
      else:
        print("Something went wrong. Incorrect signature?")
    elif op == 6:
      print("Bye!")
      break

if __name__ == "__main__":
  print("\nWelcome to my Crypto box. Tell me what operation you want.")
  while True:
    rsa = RSA()
    try:
      operation_loop(rsa)
      break
    except:
      pass

これの writeup は以前自分も書いたので そちら を参照してください。

SECCON CTF 2022: janken vs kurenaif

この問題は一見すると解くのが不可能そうな問題設定 (randint(0, 2) でじゃんけんを模していて、666回連続でじゃんけんに勝てるような seed を求める) なのに頑張れば解くことができ、驚きがとても強かったです。他にも問題名が janken vs yoshiking の続編感 (実際には全然関係ない問題) があることや、フラグで見られるおまけ動画の存在など、遊び心が感じられて楽しめました。

公式 writeup はまだ存在していない？自分の writeup は こちら。

server.py
import os
import signal
import random
import secrets

FLAG = os.getenv("FLAG", "fake{cast a special spell}")


def janken(a, b):
    return (a - b + 3) % 3


signal.alarm(1000)
print("kurenaif: Hi, I'm a crypto witch. Let's a spell battle with me.")

witch_spell = secrets.token_hex(16)
witch_rand = random.Random()
witch_rand.seed(int(witch_spell, 16))
print(f"kurenaif: My spell is {witch_spell}. What about your spell?")

your_spell = input("your spell: ")
your_random = random.Random()
your_random.seed(int(your_spell, 16))

for _ in range(666):
    witch_hand = witch_rand.randint(0, 2)
    your_hand = your_random.randint(0, 2)

    if janken(your_hand, witch_hand) != 1:
        print("kurenaif: Could you come here the day before yesterday?")
        quit()

print("kurenaif: Amazing! Your spell is very powerful!!")
print(f"kurenaif: OK. The flag is here. {FLAG}")

おわりに

この記事では個人的に面白いと感じた問題を紹介しました。

2年近く Crypto をやってると、真新しいと感じる問題はだいぶ減ってきているなあという印象を受けました。寂しいね…あと2022年上半期の記憶が失われており、今回紹介したやつは最近のものばかりになってしまった気がします。 以上のような理由でかなり偏った評価になってしまっていそうなので、他にも面白いのあるぞという人はぜひアドカレに登録して教えてくれると嬉しいです。12/7時点では4日ほど空いてます。

次回は予定の変更がなければ12/8の bata_24 さん による「bata24/gefの機能紹介とか」です。 pwndbg から乗り換えるいい機会になるかもしれない。