面白かった 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, bnn を求める
    • Gx,GyG_x, G_y を求める
    • giftnn から 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_jrandint(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_ix,yx, y 座標をそれぞれ xi,yix_i, y_i とすると、 xi3+axi+b=yi2modn2x_i^3 + ax_i + b = y_i^2 \mod n^2 となります。 この式の添字が0のものと ii のもので差をとると bb が消去できて、 x03xi3+a(x0xi)=y02yi2modn2x_0^3 - x_i^3 + a(x_0 - x_i) = y_0^2 - y_i^2 \mod n^2 が得られます。 さらにこの式の添字が i,ji, j の2式で aa を消すと (x0xj)×(y02yi2x03+xi3)=(x0xi)×(y02yj2x03+xj3)modn2(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_ya,b,na, b, n と比べて十分小さいことから LLL で求められます。

    具体的には Gy2Gx2G_y^2 - G_x^227682^{768} bits 程度、 GxG_x22562^{256} bits 程度なので以下のような格子を考えます。

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

    この行列に左から (Gx,1,k)(G_x, 1, k) (kkn2n^2 で割ったときの商) をかけることで (Gx,1,Gy2Gx3)(G_x, 1, G_y^2 - G_x^3) となりますが、このベクトルのノルムは行列よりも小さいことが期待されるので LLL で求まります。 実際に計算するときは (Gx,1,k)(G_x, 1, k) をかけたときの各要素のサイズが同程度の大きさになるように、↑の行列の1列目に 2(768256)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 が未定義となる (?) ことを利用するみたいです。 このような llgifted の約数であることが必要なため、 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 から乗り換えるいい機会になるかもしれない。