TSGCTF 2021 Writeup

Tue Oct 05 2021

    10/2-3 で開催していた TSGCTF2021 にチーム WreckTheLine で参加しました。結果は 22nd/775 (得点のあるチームのみカウント) でした。

    見てくれは簡単そうなのにいざ解こうとすると意外と解けない、というものが多く感じました。いい問題ですね。Crypto 全部解いた後は pwn の Coffee と cHeap にずっと取り掛かっていたのですが解けなくて悲しい…

    以下 Crypto 問の writeup です。

    Crypto

    This is DSA

    9 solves

    server.py
    # See also https://github.com/tsg-ut/pycryptodome
    from Crypto.PublicKey import DSA
    from Crypto.Signature import DSS
    from Crypto.Hash import SHA256
    from Crypto.Util.number import getPrime
    from Crypto.Random.random import randrange
    from base64 import b64decode
    from signal import alarm
    import os
    
    alarm(15)
    
    q = getPrime(256)
    print(f'q = {q}')
    
    p = int(input('p? '))
    h = int(input('h? '))
    
    g = pow(h, (p - 1) // q, p)
    x = randrange(q)
    y = pow(g, x, p)
    
    print(f'g = {g}')
    print(f'y = {y}')
    
    dsa = DSA.construct((y, g, p, q, x))
    dss = DSS.new(dsa, 'fips-186-3')
    
    print('Thank you for helping me with DSA! Now give me the base64-encoded signature of sha256("flag")')
    sign = b64decode(input('sign? '))
    
    dss.verify(SHA256.new(b'flag'), sign)
    print(f"Awesome! {os.environ.get('FLAG')}")
    requirements.txt
    git+https://github.com/tsg-ut/[email protected]#egg=pycryptodome

    DSA の問題。 qq が与えられる中、こちら側で p,hp, h を指定します。すると yy が返ってくるので b"flag" というメッセージに対して署名を作ることができればフラグが手に入ります。

    普通の DSA っぽいなあと思って困り requirements.txt を見てみると、どうやら自前のレポジトリから pycryptodome をインストールしているみたいです。このレポジトリの commit 履歴を見てみると、以下のような diff がありました。

    457d456
    <         fmt_error |= ((p - 1) % q) != 0
    523d521
    <         fmt_error |= ((key.p - 1) % key.q) != 0

    DSA に与える値のチェックがいくつかあるのですが、そのうち p10modqp - 1 \equiv 0 \mod q というチェックがされないようになっています。

    残ったチェックは以下だけとなります (fmt_error が True でエラーです)を。

            fmt_error |= key.g <= 1 or key.g >= key.p
            fmt_error |= pow(key.g, key.q, key.p) != 1
            # Public key
            fmt_error |= key.y <= 0 or key.y >= key.p
            if hasattr(key, 'x'):
                fmt_error |= key.x <= 0 or key.x >= key.q
                fmt_error |= pow(key.g, key.x, key.p) != key.y

    問題の性質上、求められるのは性質のいい pp を見つけることです。性質のいいというのは、例えば

    • h(p1)/qq=1modph^{\lfloor(p-1)/q\rfloor q} = 1 \mod p となる hh が存在する
    • 2048bits
      • これは fips-186-3 による制約
    • DLP が解けるような pp を探す
      • yy から xx を求められる

    のような pp です。このような pp を見つけることができれば xx が既知となるので署名を作ることができます。

    自分は上記方法でいけないかを考えていたのですが、いい方法が思いつきませんでした (実際には存在するし他の方はこの方法で解いていることが多そうでした。自分があほだった…この方法については後述)。なので別のアプローチとして、

    • h(p1)/qq=1modph^{\lfloor(p-1)/q\rfloor q} = 1 \mod p となる hh が存在する
    • 2048bits
    • DSA の verification でいかなるメッセージ (ハッシュ) であっても rr が必ず同じ値 (自明な値) になる
      • 特に、今回は r=1r = 1 を目指した

    で考えたところ、上手くできました。

    まず、自明に gq=1modpg^q = 1 \mod p なる gg が存在することを保証するために、 ppkq+1kq + 1 (kkkq+1kq + 1 が素数となるように選ばれた自然数) の倍数としました。こうすると ϕ(p)\phi(p)qq の倍数となり、適当に探索させれば gg が求まります。

    しかしこのままでは自明な署名とはなりません。自明な署名を作るには r=(gkmodp)modqr = (g^k \mod p) \mod q の部分を kk の値に関わらず必ず1にしてあげるとよさそう。そこで g=1modqg = 1 \mod q かつ ppqq の倍数としてあげます。 1q=1modp1^q = 1 \mod p は必ず成り立つので CRT を使えばこのような gg は見つかりますし、 rr を計算する部分で modp\mod p を取った後 modq\mod q を取るので必ず r=1r = 1 となります。

    以上を踏まえ、 p=2pad(kq+1)qp = 2^{\mathrm{pad}} (kq + 1)q (pad は pp が2048bits にするため) とします。 DSA の verification では (gu1yu2modp)modq(g^{u_1}y^{u_2} \mod p) \mod q という計算がされますが、 y=gxmodpy = g^x \mod p なので結局この値は1となります。つまり署名 (r,s)(r, s) のうち rr が1でさえあればいかなるメッセージに対しても必ず署名は通ることとなります。

    solve.sage
    from base64 import b64encode
    
    from pwn import context, remote
    
    context.log_level = "DEBUG"
    
    io = remote("34.146.212.53", 61234)
    
    
    def recvafter(prefix: bytes) -> bytes:
        io.recvuntil(prefix)
        return io.recvline().strip()
    
    
    q = int(recvafter(b"q = "))
    
    i = 1
    while True:
        tmp = i * q + 1
        if is_prime(tmp):
            p = tmp
            break
        i += 1
    p *= q
    p = p * 2**(2048-p.nbits())
    g = crt([int(Zmod(p//q)(1).nth_root(q)), 1], [p//q, q])
    h = crt([int(Zmod(p//q)(g).nth_root((p-1)//q)), int(Zmod(q)(g).nth_root((p-1)//q))], [p//q, q])
    
    # r = 1, t != 0 であればなんでも通る
    sign = b"\x00" * 31 + b"\x01" + b"\x00" * 31 + b"\x01"
    
    io.sendlineafter(b"p? ", str(p).encode())
    io.sendlineafter(b"h? ", str(h).encode())
    assert int(recvafter(b"g = ")) == g
    io.sendlineafter(b"sign? ", b64encode(sign))
    
    io.recvall()

    TSGCTF{WOW_AMAZING_DSA_IS_TOTALLY_BROKEN}


    競技時間中は上記のようなお気持ちで解きましたが、競技終了後に writeup 漁っていたら大体の人は p=q8p = q^8 (qq が十分大きく生成されていれば pp は2048bits になる) でやっていたっぽいです。 こうすると g=q7+1g = q^7 + 1gq=(q7+1)q=1modpg^q = (q^7 + 1)^q = 1 \mod p となり、 DLP を考えたときも y=gx=xq7+1modpy = g^x = xq^7 + 1 \mod p となるので DLP が解けます。DLP が解ければ当然署名も作れます。

    なるほどなあ、自分は DLP が解けるようにするために pohlig-hellman が使えるような pp を作ろうとしてたけど、もっとシンプルに考えればよかった…

    ところで実は p=q8p = q^8 のときも g=1modqg = 1 \mod q となっているので、実は必ず r=1r = 1 となっていて、自分の解き方と同様に DLP を解く必要はなさそうな気がしますね。というか p=kq2p = kq^2 みたいな形式でも必ず r=1r = 1 になりそう。考察しがいがあるなあ。

    Flag is Win

    10 solves

    flag_is_win.rb
    require 'openssl'
    require 'digest'
    
    STDOUT.sync = true
    
    class OpenSSL::PKey::EC::Point
      def xy
        n = to_bn(:uncompressed).to_i
        mask = (1 << group.degree) - 1
        return (n >> group.degree) & mask, n & mask
      end
      alias_method :+, :add
      alias_method :*, :mul
    end
    
    class ECDSA
      def initialize
        @curve = OpenSSL::PKey::EC::Group.new('secp256k1')
        @G = @curve.generator
        @n = @curve.order.to_i
        @d = OpenSSL::BN.rand(@curve.degree).to_i
        @Q = @G * @d
      end
    
      def inv(x)
        x.pow(@n - 2, @n)
      end
    
      def sign(msg)
        z = Digest::SHA256.hexdigest(msg).hex
        k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex
        x, y = (@G * k).xy
    
        # We should discourage every evil hacks
        s = (z + x * @d) * inv(k) % @n
    
        return x, s
      end
    
      def verify(msg, x, s)
        return false if x % @n == 0 || s % @n == 0
        z = Digest::SHA256.hexdigest(msg).hex
    
        # ditto
        x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
    
        return x == x2
      end
    end
    
    ecdsa = ECDSA.new
    
    5.times do
      puts <<~EOS
        1. Sign
        2. Find rule
        3. Exit
      EOS
    
      print 'choice? '
    
      case gets.chomp
      when '1'
        x, s = ecdsa.sign('Baba')
        puts 'Baba is:'
        puts "x = #{x}"
        puts "s = #{s}"
      when '2'
        print 'Which rule do you want to know? '; msg = gets.chomp
        print 'x? '; x = gets.to_i
        print 's? '; s = gets.to_i
    
        if ecdsa.verify(msg, x, s)
          if msg == 'Baba'
            puts 'Baba is you'
          elsif msg == 'Flag'
            puts "Flag is #{ENV['FLAG']}"
          else
            puts 'Not Found :('
          end
        else
          puts 'Invalid :('
        end
      else
        exit
      end
    end
    
    puts 'You is defeat.'

    ruby で書かれた ECDSA 問題。 "Baba" というメッセージに対する署名を4個まで得られ、残りの1回で "Flag" というメッセージに対する署名を作る必要があります。

    なんで ruby なんだろう、と思っていたところ、昔参加した CTF でも同じ気持ちになったことを思い出しました。SECCON 2020 の This is RSA ですね (昔自分が書いた writeup)。 過去問と同様、 kk の生成部分で乱数を文字列で表したものを16進数表示してしまっており、 kk0x(3[0-9])+ という形になっています。適当に ruby で kk を生成させてみると、 3?3?... というのが25-26回繰り返されています。 とりあえず26回繰り返されているとすると、 k=i=0253×162i+1+i=025ki×162ik = \sum_{i=0}^{25} 3 \times 16^{2i+1} + \sum_{i=0}^{25} k_i \times 16^{2i} という式が成り立つことがわかります。

    ECDSA の署名の計算式から、 H(m)s1+ds1kH(m)s^{-1} + ds^{-1} - k (dd は秘密鍵) が成り立つので、これらの式から格子を作って CVP で dd を求め、署名を生成することができます。 CVP の部分は rkm-san の Inequality_Solving_with_CVP を使いました。dd を求めるのに署名は2つで十分でした。

    solve.sage
    from pwn import remote, context
    from hashlib import sha256
    from Crypto.Util.number import bytes_to_long
    
    
    context.log_level = "DEBUG"
    
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
    a = 0
    b = 7
    Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
    Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
    n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
    
    EC = EllipticCurve(GF(p), [a, b])
    G = EC(Gx, Gy)
    
    
    io = remote("34.146.212.53", 35719)
    
    
    def sign():
        io.sendlineafter(b"choice? ", b"1")
        io.recvuntil(b"x = ")
        x = int(io.recvline().strip())
        io.recvuntil(b"s = ")
        s = int(io.recvline().strip())
        return x, s
    
    
    x_list = []
    s_list = []
    for _ in range(2):
        x, s = sign()
        x_list.append(x)
        s_list.append(s)
    
    k_base = sum([16**i * 3 for i in range(1, 52, 2)])
    Hm = bytes_to_long(sha256(b"Baba").digest())
    
    # use https://github.com/rkm0959/Inequality_Solving_with_CVP/blob/main/solver.sage
    M = len(x_list)
    mat = matrix(ZZ, 26*M+M+2, 26*M+M+2)
    for i in range(26*M):
        mat[i, i] = 1
    for i in range(M):
        for j in range(26):
            mat[i*26+j, 26*M+i] = 256**j
        mat[26*M+i, 26*M+i] = -n
        mat[26*M+M, 26*M+i] = -int(pow(s_list[i], -1, n) * x_list[i] % n)
        mat[26*M+M+1, 26*M+i] = int((k_base - Hm * int(pow(s_list[i], -1, n))) % n)
    mat[26*M+M, 26*M+M] = 1
    mat[26*M+M+1, 26*M+M+1] = 1
    lb = [0] * 26*M + [0] * M + [0] + [1]
    ub = [9] * 26*M + [0] * M + [2**256] + [1]
    res = solve(mat, lb, ub)
    
    
    d = int(res[2][-2])
    k = 2
    x = (k * G).xy()[0]
    s = (bytes_to_long(sha256(b"Flag").digest()) + int(x) * d) * int(pow(k, -1, n)) % n
    
    io.sendlineafter(b"choice? ", b"2")
    io.sendlineafter(b"know? ", b"Flag")
    io.sendlineafter(b"x? ", str(x).encode())
    io.sendlineafter(b"s? ", str(s).encode())
    print(io.recvall())
    io.close()

    TSGCTF{CRYPTO_IS_LOCK._KEY_IS_OPEN._CTF_IS_FUN!}

    Baba is Flag

    34 solves

    時系列的には Flag is Win の前に出た問題で、それよりも簡単な問題になっています。 diff はこちら。

    34,35c34,36
    <     # We should discourage every evil hacks
    <     s = (z + x * @d) * inv(k) % @n
    ---
    >     # We all like hacks, ain't we?
    >     # s = (z + x * @d) * inv(k) % @n
    >     s = (z + @d) * inv(k) % @n
    45c46,47
    <     x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
    ---
    >     # x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
    >     x2, y2 = (@G * (z * inv(s)) + @Q * inv(s)).xy

    Flag is Win とほぼ全く同じ解き方をしました。格子をつくるところで xx をかけなくするだけです。コードは省略します。

    TSGCTF{CRYPTO_IS_LOCK._KEY_IS_OPEN._CTF_IS_FUN!}

    Minimalist's Private

    49 solves

    encrypt.py
    from Crypto.Util.number import isPrime
    from random import randrange
    from secret import p, q, L, e, d
    
    class RSA:
        def __init__(self, p, q, L, e, d):
            assert(isPrime(p) and isPrime(q))
            self.N = p * q
            self.L = L
            self.e = e
            self.d = d
    
            # these are the normal RSA conditions
            for _ in range(100):
                assert(pow(randrange(1, self.N), self.L, self.N) == 1)
            assert(self.e * self.d % self.L == 1)
    
            # minimal is the best
            assert(self.L * self.L <= 10000 * self.N)
    
        def gen_private_key(self):
            return (self.N, self.d)
    
        def gen_public_key(self):
            return (self.N, self.e)
    
        def encrypt(self, msg):
            return pow(msg, self.e, self.N)
    
        def decrypt(self, c):
            return pow(c, self.d, self.N)
    
    flag = open('flag.txt', 'rb').read()
    msg = int.from_bytes(flag, byteorder='big')
    assert(msg < p * q)
    
    rsa = RSA(p, q, L, e, d)
    encrypted = rsa.encrypt(msg)
    assert(rsa.decrypt(encrypted) == msg)
    
    print(f'N, e = {rsa.gen_public_key()}')
    print(f'c = {encrypted}')

    RSA の問題ですが、謎のパラメータ LL が使われています。この LL についての情報をまとめると、

    • randL=1modN\mathrm{rand}^{L} = 1 \mod N
    • L210000NL^2 \le 10000 N

    となっています。したがって NN についてカーマイケルの定理を考えると、 L=lcm(p1,q1)=(p1)(q1)/gcd(p1,q1)L = \mathrm{lcm}(p-1, q-1) = (p-1)(q-1)/\gcd(p-1, q-1) が非常に小さい数字になっていることが期待されます。

    そこで p=iG+1,q=jG+1p = iG + 1, q = jG + 1 とおきます。G=gcd(p1,q1)G = \gcd(p-1, q-1) です。 L=ijGL = ijG となるので、

    (ij)2G210000(ijG2+(i+j)G+1)<10001ijG2(ij)^2 G^2 \le 10000 (ijG^2 + (i+j)G + 1) < 10001 ij G^2
    ij<10001\therefore ij < 10001

    が成立します。また、 jpiq=jijp - iq = j - i です。 (jp)(iq)=(ij)N(jp)(iq) = (ij)Ni,ji, j が小さい (すなわち jij - i が小さい) ことを考えると iqjpijNiq \approx jp \approx \sqrt{ijN} となります。

    以上を踏まえ、 ijij の値について全探索させ、 gcd(N,ijN+k)\gcd(N, \lceil\sqrt{ij N}\rceil + k) が十分大きくなる kk を探索させました (このときに gcd の結果が p または q になる)。

    競プロだったら TLE ですが、これは CTF。

    solve.sage
    from Crypto.Util.number import long_to_bytes
    
    
    N, e = (1108103848370322618250236235096737547381026108763302516499816051432801216813681568375319595638932562835292256776016949573972732881586209527824393027428125964599378845347154409633878436868422905300799413838645686430352484534761305185938956589612889463246508935994301443576781452904666072122465831585156151, 65537)
    c = 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426
    
    for ij in range(1, 10**5+2):
        tmp = ceil(sqrt(ij * N))
        for k in range(1000):
            G = gcd(tmp + k, N)
            if G.nbits() > 300:
                print(G)  # 見つかったら Ctrl+C
    
    G = 5293956253947009870401417007695694880120669942943370772882122022200933137261970150546718751594723858094466011384272699668015027900382760667694940922283
    p = G
    q = N // p
    phi = (p - 1) * (q - 1)
    d = int(pow(e, -1, phi))
    print(long_to_bytes(pow(c, d, N)))

    TSGCTF{Roll_Safe:_You_c4n't_be_exploited_1f_you_are_a_minimali5t_enough_and_y0u_don't_have_any_s3crets_in_your_mind}

    Beginner's Crypto 2021

    126 solves

    beginners_crypto_2021.py
    from secret import e
    from Crypto.Util.number import getStrongPrime, isPrime
    
    p = getStrongPrime(1024)
    q = getStrongPrime(1024)
    N = p * q
    phi = (p - 1) * (q - 1)
    
    with open('flag.txt', 'rb') as f:
        flag = int.from_bytes(f.read(), 'big')
    
    assert(isPrime(e))
    assert(isPrime(e + 2))
    assert(isPrime(e + 4))
    
    e1 = pow(e, 0x10001, phi)
    e2 = pow(e + 2, 0x10001, phi)
    e3 = pow(e + 4, 0x10001, phi)
    
    c1 = pow(flag, e1, N)
    c2 = pow(flag, e2, N)
    c3 = pow(flag, e3, N)
    
    print(f'p = {p}')
    print(f'q = {q}')
    print(f'c1 = {c1}')
    print(f'c2 = {c2}')
    print(f'c3 = {c3}')

    RSA の p,qp, q が与えられている代わりに ee の値が既知ではありません。しかし assert(isPrime(e + i)) (i=0,2,4i = 0, 2, 4) の意味を真剣に考えてみると、 e=3e = 3 が確定します (∵ e,e+2,e+4e, e+2, e+4 のどれかは必ず3の倍数になる)。

    ee がわかれば e1,e2,e3e_1, e_2, e_3 もわかるので RSA の復号をやるだけに見えますが、gcd(ei,ϕ)1\gcd(e_i, \phi) \ne 1 となり秘密鍵を求めることができません。仕方がないので 前書いたこれ を参考に復号しました。

    solve.sage
    from Crypto.Util.number import long_to_bytes
    
    
    p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
    q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
    c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
    c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
    c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837
    
    N = p * q
    phi = (p - 1) * (q - 1)
    
    e = 3
    e1 = int(pow(e, 0x10001, phi))
    e2 = int(pow(e + 2, 0x10001, phi))
    e3 = int(pow(e + 4, 0x10001, phi))
    
    l = lcm(p - 1, q - 1)
    
    k = 3
    L = pow(k, l // 3, N)
    while True:
        if L != 1:
            assert L ** 3 == 1
            break
        k += 1
    
    d1 = int(pow(e1, -1, l // 3))
    for i in range(3):
        print(long_to_bytes(pow(c1, d1, N) * L**i))

    TSGCTF{You are intuitively understanding the distribution of prime numbers! Bonus: You can solve this challenge w/ N instead of p and q!}