2021年の CTF Crypto 問を振り返る

Thu Dec 16 2021

    この記事は CTF Advent Calendar 2021 17日目の記事です。

    前回の記事は DiKO さん による LLL入門してみた! でした。 LLL は「何も分からん (文字通りの意味)」と「完全に理解した (完全に理解したの意味)」のギャップが結構大きいのですが、上記記事ではそのギャップが埋められている感じがあって読みがいがありました。

    はじめに

    今年は CTF の中でも Crypto に特化するぞという目標があったため、この1年間大量の Crypto の問題を見てきました (解いたとは言っていない)。そのおかげで何か問題を解くときに「これ〇〇で見た問題だ!」となることが増えてきました。いいことです。

    そんな中、今年も12月と終わりを迎え、あるモチベーションが高まってきました。「今まで見てきた問題をリストアップしたほうがいいのではないか」と。 こう思い至った理由は主に3つあり、

    • 人間の記憶力には限界があるため、ある程度検索可能な形でまとめたい
    • 問題を見て即そっ閉じした問題も多々あり (特に2021年初頭の頃)、学びの機会を大きく損失してしまっている
    • 自分の得意不得意を可視化することで今後の勉強の方向性を定めたい

    といった感じです。

    似たコンセプトのものとして mystiz さんCrypto in CTF があります。これこそ顧客が本当に必要だったものです。これでいいでは? ですが、こういうのは自分で作ることに意義があるのでは?と自分に言い聞かせながら自己満オレオレ問題リストを 作りました 作っている途中です (こういう作業はコツコツやるべきです、常識ですね)。せっかくなので共有したいと思います。

    またこれを共有するだけだと URL ドンッで終わってしまうため、この記事ではリストアップ作業の中で「ああ、これ面白かったなあ」と感じた問題をいくつか取り上げようと思います。

    1年間の Crypto まとめ

    まず自分が参加した CTF を https://note.y011d4.com/ctf-list にまとめました。つまり今回まとめた問題は基本的にこれらの CTF で出題された問題に限ります。 これらの CTF のうち、過去の自分の Writeup やプロのブログ等を辿り Crypto の問題をリストアップしました。Crypto 問は https://note.y011d4.com/crypto-list にまとめてあります。 この作業の中で、 solves 数のメモが手元にないものについては CTF-rating を参考にさせていただきました。ありがとうございます。

    ⚠️⚠️⚠️以下注意点⚠️⚠️⚠️

    • 2021年になった頃はまだ楕円曲線も格子も知らない状況でしたので見て見ぬふりをした問題が結構あります。なので特にリストの序盤 (2021年1-2月頃) は問題の抜け漏れが多いかと思います。
    • タグが解法のネタバレになっていたり、いくつかの問題では解法を直で書いていたりします。ネタバレには注意してください。
    • このまとめは notion で書いています。自分が使うぶんには便利なのですが、他人の編集を無許可にしているせいでソートができなかったりといろいろ使い勝手が悪そうです。もしかすると URL もろとも別のフレームワークに移行するかもしれませんがそのときはこの記事に追記します。
      • こういう view で見たいというのがあればご連絡ください。取り急ぎ view を作ります。
    • タグ付けがガバガバです🙇🙇🙇

    ⚠️⚠️⚠️以上注意点⚠️⚠️⚠️

    まとめてみた結果、リストアップをやろうと思った理由の2つ目3つ目は解決できていそうです。すなわち自分が復習できていなかった問題に再度挑戦できましたし、自分の不得意な分野が浮き彫りになりました。みなさんもまとめてみるといいかもしれません。 一方で検索可能な形にするのはまだできていないです。タグである程度は検索できますが、コレジャナイ感が…アイディア募集中です。

    残念ながら本日 (2021/12/17) 時点ではごく少数の問題についてしか問題・解法が記入できておらず、本当にただのリストアップになってしまっています。ちょっとずつ追記していきます。何かご要望があれば twitter で @y011d4 宛にご連絡いただければと思います。

    印象に残った Crypto 問

    それではリストアップした問題のうち、印象に残っていたものについて簡単に紹介したいと思います。時系列順に並べました。 解法についてはあまり深く取り上げず、他の Writeup に委ねます。

    corCTF: leave_it_to_chance

    source.py
    from Crypto.Util.number import getPrime
    from random import randrange, shuffle
    from private import flag
    
    class Game():
    	KEY_LEN = 32
    
    	def __init__(self):
    		self.p = getPrime(256)
    		while self.p % 4 == 3:
    			self.p = getPrime(256)
    		x = randrange(self.p)
    		while pow(x, (self.p-1)//2, self.p) == 1:
    			x = randrange(self.p)
    		self.a = pow(x, (self.p-1)//4, self.p)
    		self.privgen()
    		self.signed = []
    
    	def privgen(self):
    		self.priv = [randrange(self.p) for _ in range(self.KEY_LEN)]
    
    	def sign(self, m):
    		s = 0
    		for i in range(len(self.priv)):
    			s += (pow(m, i, self.p) * self.priv[i]) % self.p
    		return s
    
    	def verify(self, m, s):
    		c = self.sign(m)
    		return c**4 % self.p == s
    
    def getSig():
    	m = int(input("Enter the message you would like to sign, in hex> "), 16) % game.p
    	if m not in game.signed:
    		s = game.sign(m)
    		game.signed.append(m)
    		print(f"Signature: {hex(s**4 % game.p)[2:]}")
    		hints = [-s % game.p, s*game.a % game.p, -s*game.a % game.p]
    		shuffle(hints)
    		guess = int(input("Enter a guess for s, in hex> "), 16)
    		if guess in hints:
    			hints.remove(guess)
    		print(f"Hints: {hints[0]} {hints[1]}")
    	else:
    		print("You already signed that.")
    
    def verifyPair():
    	m = int(input("Enter m, in hex> "), 16)
    	s = int(input("Enter s, in hex> "), 16)
    	if game.verify(m, s):
    		print("Valid signature.")
    	else:
    		print("Invalid signature.")
    
    def guessPriv():
    	inp = input("Enter the private key as a list of space-separated numbers> ")
    	guess = [int(n) for n in inp.split(" ")]
    	if guess == game.priv:
    		print(f"Nice. Here's the flag: {flag}")
    	else:
    		print("No, that's wrong.")
    	exit()
    
    def menu():
    	print("Enter your choice:")
    	print("[1] Get a signature")
    	print("[2] Verify a message")
    	print("[3] Guess the private key")
    	print("[4] Exit")
    	options = [getSig, verifyPair, guessPriv, exit]
    	choice = int(input("Choice> "))
    	if choice - 1 in range(len(options)):
    		options[choice - 1]()
    	else:
    		print("Please enter a valid choice.")
    
    game = Game()
    welcome = f"""Welcome.
    I will let you sign as many messages as you want.
    If you can guess the private key, the flag is yours.
    But you only have one chance. Make it count.
    p = {game.p}
    """
    print(welcome)
    while True:
    	menu()

    32個の秘密鍵 did_i を使い s=i=031dimimodps = \sum_{i=0}^{31} d_i m^i \mod p を計算し、メッセージ mm の署名として s4s^4 が使われます。署名 ss' の検証時には、 s=(i=031dimi)4s' = \left(\sum_{i=0}^{31} d_im^i \right)^4 であるかをチェックします。 この問題の肝としてヒントシステムがあります。

    		print(f"Signature: {hex(s**4 % game.p)[2:]}")
    		hints = [-s % game.p, s*game.a % game.p, -s*game.a % game.p]
    		shuffle(hints)
    		guess = int(input("Enter a guess for s, in hex> "), 16)
    		if guess in hints:
    			hints.remove(guess)
    		print(f"Hints: {hints[0]} {hints[1]}")

    s4s^4 の4乗根は s,s,sa,sas, -s, sa, -sa (aaa4=1modpa^4 = 1 \mod p を満たす整数) の4種類が存在します。署名のたびに4乗根1つを選択することができて、それが {s,sa,sa}\{-s, sa, -sa\} の集合に含まれていたらそれ以外の2つが、含まれていなければランダムに2つが与えられます。 これらの情報をもとに秘密鍵32個を特定できればフラグが手に入ります。 ソースコードに書かれていない制約として、サーバーの待機時間的に100-200個程度しか署名を得ることができません。数字はうろ覚えです…

    仮に s=i=031dimis = \sum_{i=0}^{31} d_im^i が32個得られれば、連立方程式を解くことで did_i が求まります。しかしこの問題では ss が特定できないので工夫が必要となります。

    自分が観測した限りでは2種類の解法があります。

    前者の解法 (これが公式 writeup です) はあまり見ない手法で、このような不確定性のある問題に対してこういうアプローチがあるのか!と感動しました。ご存知でない方は一度読んでみるといいかと思います。

    Zh3r0 CTF: Real Mersenne

    challenge.py
    import random
    from secret import flag
    from fractions import Fraction
    
    def score(a,b):
        if abs(a-b)<1/2**10:
            # capping score to 1024 so you dont get extra lucky
            return Fraction(2**10)
        return Fraction(2**53,int(2**53*a)-int(2**53*b))
    
    total_score = 0
    for _ in range(2000):
        try:
            x = random.random()
            y = float(input('enter your guess:\n'))
            round_score = score(x,y)
            total_score+=float(round_score)
            print('total score: {:0.2f}, round score: {}'.format(
                total_score,round_score))
            if total_score>10**6:
                print(flag)
                exit(0)
        except:
            print('Error, exiting')
            exit(1)
    else:
        print('Maybe better luck next time')

    random.random() で生成される [0, 1] の乱数を予測する問題です。乱数を xx, 入力値を yy とすると min(210,1/(xy))\min(2^{10}, 1 / (x - y))score が計算され、 2000回以内で 10610^6 に達成する必要があります。 106/210100010^6 / 2^{10} \simeq 1000 なので、1000回程度は Mersenne Twister の状態復元に使うことができます。

    連続した624個の random.getrandbits(32) を得られれば Mersenne Twister の出力を予測できることは比較的有名な話ですが、 random.random() では32bitで生成した乱数の一部を切り捨てており、 state 復元の難易度が上がります。それでも解けるんだなあというところに面白さを感じました。 自分の解法は https://blog.y011d4.com/20210606-zh3r0-ctf-writeup/#real-mersenne にて書きましたので解き方が気になる方はそちらをご覧ください。

    0CTF/TCTF: zer0lfsr+

    task.py
    #!/usr/bin/env python3
    
    import random
    import signal
    import socketserver
    import string
    from hashlib import sha256
    from os import urandom
    from secret import flag
    
    def _prod(L):
        p = 1
        for x in L:
            p *= x
        return p
    
    def _sum(L):
        s = 0
        for x in L:
            s ^= x
        return s
    
    def b2n(x):
        return int.from_bytes(x, 'big')
    
    def n2l(x, l):
        return list(map(int, '{{0:0{}b}}'.format(l).format(x)))
    
    def split(x, n, l):
        return [(x >> (i * l)) % 2**l for i in range(n)][::-1]
    
    def combine(x, n, l):
        return sum([x[i] << (l * (n - i - 1)) for i in range(n)])
    
    class Generator1:
        def __init__(self, key: list):
            assert len(key) == 64
            self.NFSR = key[: 48]
            self.LFSR = key[48: ]
            self.TAP = [0, 1, 12, 15]
            self.TAP2 = [[2], [5], [9], [15], [22], [26], [39], [26, 30], [5, 9], [15, 22, 26], [15, 22, 39], [9, 22, 26, 39]]
            self.h_IN = [2, 4, 7, 15, 27]
            self.h_OUT = [[1], [3], [0, 3], [0, 1, 2], [0, 2, 3], [0, 2, 4], [0, 1, 2, 4]]
    
        def g(self):
            x = self.NFSR
            return _sum(_prod(x[i] for i in j) for j in self.TAP2)
    
        def h(self):
            x = [self.LFSR[i] for i in self.h_IN[:-1]] + [self.NFSR[self.h_IN[-1]]]
            return _sum(_prod(x[i] for i in j) for j in self.h_OUT)
    
        def f(self):
            return _sum([self.NFSR[0], self.h()])
    
        def clock(self):
            o = self.f()
            self.NFSR = self.NFSR[1: ] + [self.LFSR[0] ^ self.g()]
            self.LFSR = self.LFSR[1: ] + [_sum(self.LFSR[i] for i in self.TAP)]
            return o
    
    class Generator2:
        def __init__(self, key):
            assert len(key) == 64
            self.NFSR = key[: 16]
            self.LFSR = key[16: ]
            self.TAP = [0, 35]
            self.f_IN = [0, 10, 20, 30, 40, 47]
            self.f_OUT = [[0, 1, 2, 3], [0, 1, 2, 4, 5], [0, 1, 2, 5], [0, 1, 2], [0, 1, 3, 4, 5], [0, 1, 3, 5], [0, 1, 3], [0, 1, 4], [0, 1, 5], [0, 2, 3, 4, 5], [
                0, 2, 3], [0, 3, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4], [1, 2, 3, 5], [1, 2], [1, 3, 5], [1, 3], [1, 4], [1], [2, 4, 5], [2, 4], [2], [3, 4], [4, 5], [4], [5]]
            self.TAP2 = [[0, 3, 7], [1, 11, 13, 15], [2, 9]]
            self.h_IN = [0, 2, 4, 6, 8, 13, 14]
            self.h_OUT = [[0, 1, 2, 3, 4, 5], [0, 1, 2, 4, 6], [1, 3, 4]]
    
        def f(self):
            x = [self.LFSR[i] for i in self.f_IN]
            return _sum(_prod(x[i] for i in j) for j in self.f_OUT)
    
        def h(self):
            x = [self.NFSR[i] for i in self.h_IN]
            return _sum(_prod(x[i] for i in j) for j in self.h_OUT)        
    
        def g(self):
            x = self.NFSR
            return _sum(_prod(x[i] for i in j) for j in self.TAP2)  
    
        def clock(self):
            self.LFSR = self.LFSR[1: ] + [_sum(self.LFSR[i] for i in self.TAP)]
            self.NFSR = self.NFSR[1: ] + [self.LFSR[1] ^ self.g()]
            return self.f() ^ self.h()
    
    class Generator3:
        def __init__(self, key: list):
            assert len(key) == 64
            self.LFSR = key
            self.TAP = [0, 55]
            self.f_IN = [0, 8, 16, 24, 32, 40, 63]
            self.f_OUT = [[1], [6], [0, 1, 2, 3, 4, 5], [0, 1, 2, 4, 6]]
    
        def f(self):
            x = [self.LFSR[i] for i in self.f_IN]
            return _sum(_prod(x[i] for i in j) for j in self.f_OUT)
    
        def clock(self):
            self.LFSR = self.LFSR[1: ] + [_sum(self.LFSR[i] for i in self.TAP)]
            return self.f()
    
    class KDF:
        def __init__(self, key: int):
            self.msk = key
            self.SBOX = [12, 5, 1, 2, 7, 15, 9, 3, 0, 13, 14, 6, 8, 10, 4, 11]
            self.idx = [[0, 3], [0, 1], [2, 3], [0, 3]]
    
        def substitue(self, x):
            return [self.SBOX[i] for i in x]
    
        def expand(self):
            h = sha256(str(self.msk).encode()).digest()
            rnd_key = [h[: 2], h[2: 4], h[2: 4], h[4: 6]]
            rnd_key = list(map(b2n, rnd_key))
            chunk = split(self.msk, 4, 16)
            sub_key = [combine(self.substitue(split(chunk[self.idx[i][0]] ^ chunk[self.idx[i][1]] , 4, 4)), 4, 4) for i in range(4)]
            final_key = [rnd_key[i] ^ sub_key[i] for i in range(4)]
            return combine(final_key, 4, 16)
    
    class zer0lfsr:
        def __init__(self, msk: int):
            self.key = []
            for i in range(3):
                msk = KDF(msk).expand()
                self.key.append(msk)
            self.g1 = Generator1(n2l(self.key[0], 64))
            self.g2 = Generator2(n2l(self.key[1], 64))
            self.g3 = Generator3(n2l(self.key[2], 64))
    
        def next(self):
            o1 = self.g1.clock()
            o2 = self.g2.clock()
            o2 = self.g2.clock()
            o3 = self.g3.clock()
            o3 = self.g3.clock()
            o3 = self.g3.clock()
            o = (o1 * o2) ^ (o2 * o3) ^ (o1 * o3)
            return o
    
    class Task(socketserver.BaseRequestHandler):
        def __init__(self, *args, **kargs):
            super().__init__(*args, **kargs)
    
        def proof_of_work(self):
            random.seed(urandom(8))
            proof = ''.join([random.choice(string.ascii_letters + string.digits + '!#$%&*-?') for _ in range(20)])
            digest = sha256(proof.encode()).hexdigest()
            self.dosend('sha256(XXXX + {}) == {}'.format(proof[4: ], digest))
            self.dosend('Give me XXXX:')
            x = self.request.recv(10)
            x = (x.strip()).decode('utf-8') 
            if len(x) != 4 or sha256((x + proof[4: ]).encode()).hexdigest() != digest: 
                return False
            return True
    
        def dosend(self, msg):
            try:
                self.request.sendall(msg.encode('latin-1') + b'\n')
            except:
                pass
    
        def timeout_handler(self, signum, frame):
            raise TimeoutError
    
        def handle(self):
            try:
                signal.signal(signal.SIGALRM, self.timeout_handler)
                signal.alarm(30)
                if not self.proof_of_work():
                    self.dosend('You must pass the PoW!')
                    return
                lfsr = zer0lfsr(random.getrandbits(64))
                for i in range(20):
                    keystream = ''
                    for j in range(1000):
                        b = 0
                        for k in range(8):
                            b = (b << 1) + lfsr.next()
                        keystream += chr(b)
                    self.dosend('start:::' + keystream + ':::end')
                signal.alarm(100)
                self.dosend('k1: ')
                k1 = int(self.request.recv(100).strip())
                self.dosend('k2: ')
                k2 = int(self.request.recv(100).strip())
                self.dosend('k3: ')
                k3 = int(self.request.recv(100).strip())
                if lfsr.key == [k1, k2, k3]:
                    self.dosend(flag)
                else:
                    self.dosend('Wrong ;(')
            except TimeoutError:
                self.dosend('Timeout!')
                self.request.close()
            except:
                self.dosend('Wtf?')
                self.request.close()
    
    class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
        pass
    
    if __name__ == "__main__":
        HOST, PORT = '0.0.0.0', 13337
        server = ThreadedServer((HOST, PORT), Task)
        server.allow_reuse_address = True
        server.serve_forever()

    3種類の LFSR を非線形に組み合わせたストリーム暗号の問題です。

    ストリーム暗号はよく出題されるジャンルの1つだと思いますが、この問題はその中でも最も難しかったのではないでしょうか。 紹介しておいてなんですが自分はこの問題を解くことができなかったし今もまだ解けてないです。しかしこの問題を解くときに調べた知識を使って別の問題が解けたという経験があるので、挑戦する価値はあると思います。ただ、この問題はしんどすぎるかも…

    ちなむとこの問題の easier 版として zer0lfsr- という問題も出題されていました。そちらは3種類の LFSR のうち2つを crack する問題でした。 zer0lfsr+ との難易度の差が激しい… また、この問題には非想定解が存在していたらしく、それを修正した zer0lfsr++ という問題も出題されています。 zer0lfsr+ のフラグが配布ファイルの password になっていたため自分は zer0lfsr++ の中身をまだ見れていません。

    rkm さん がこの問題の writeup を公開しています。 https://rkm0959.tistory.com/229

    TSGCTF: This is DSA

    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
    https://github.com/tsg-ut/pycryptodome/commit/22388c5fec4607e8e255926c3e95724a2f070e76
    457d456
    <         fmt_error |= ((p - 1) % q) != 0
    523d521
    <         fmt_error |= ((key.p - 1) % key.q) != 0

    DSA で p1=0modqp - 1 = 0 \mod q という制約が消えたとき、どのような p,hp, h を与えると DSA を破壊できるか、という問題です。

    制約が消えるとどのような不都合があるのかということが知れるのと、意外と簡単には破壊できないというところが面白かったです。 自分の解法は https://blog.y011d4.com/20211005-tsgctf-writeup/#this-is-dsa にて書きましたので解き方が気になる方はそちらをご覧ください。

    pbctf: Seed Me

    Main.java
    import java.nio.file.Files;
    import java.nio.file.Path;
    import java.io.IOException;
    import java.util.Random;
    import java.util.Scanner;
    
    class Main {
    
        private static void printFlag() {
            try {
                System.out.println(Files.readString(Path.of("flag.txt")));
            }
            catch(IOException e) {
                System.out.println("Flag file is missing, please contact admins");
            }
        }
    
        public static void main(String[] args) {
            int unlucky = 03777;
            int success = 0;
            int correct = 16;
    
            System.out.println("Welcome to the 'Lucky Crystal Game'!");
            System.out.println("Please provide a lucky seed:");
            Scanner scr = new Scanner(System.in);
            long seed = scr.nextLong();
            Random rng = new Random(seed);
    
            for(int i=0; i<correct; i++) {
                /* Throw away the unlucky numbers */
                for(int j=0; j<unlucky; j++) {
                    rng.nextFloat();
                }
    
                /* Do you feel lucky? */
                if (rng.nextFloat() >= (7.331f*.1337f)) {
                    success++;
                }
            }
    
            if (success == correct) {
                printFlag();
            }
            else {
                System.out.println("Unlucky!");
            }
        }
    }

    2048回ごとに rng.nextFloat() >= (7.331f*.1337f) (約0.98) となる乱数を生成するような seed を指定することができればフラグが得られます。

    一度解けてしまうと自明な感じがしてしまうのですが、このような seed が存在するのって結構非直観的な気がしませんか? 自分の解法は https://blog.y011d4.com/20211011-pbctf-writeup/#seed-me にて書きましたので解き方が気になる方はそちらをご覧ください。

    BSides Ahmedabed CTF: They Were Eleven

    task.py
    import os
    from Crypto.Util.number import getPrime, getRandomRange
    
    with open("flag.txt", "rb") as f:
        m = f.read().strip()
        m += os.urandom(111 - len(m))
        m = int.from_bytes(m, "big")
    
    xs = []
    for i in range(11):
        p = getPrime(512)
        q = getPrime(512)
        n = p  * q
    
        c = m**11 * getRandomRange(0, 2**11) % n
    
        xs.append((c, n))
    
    print(xs)

    11種類の (ri,ni)(r_i, n_i) を用いてフラグ mmci=rim11modnic_i = r_i m^{11} \mod n_i で暗号化しています。 (ci,ni)(c_i, n_i) が与えられます。 rir_i2122^{12} 以下の小さい乱数です。

    ぱっとみは LLL が使えそうな問題なのですが、なかなか式を線形に表すことができません。結局は LLL で解くのが想定解で、式変形の過程が面白かったです。

    作問者の ふるつきさん による writeup がこちらです。 https://furutsuki.hatenablog.com/entry/2021/12/07/020611

    Balsn CTF: trinity

    server.py
    #!/usr/local/bin/python3 -u
    import signal
    from blake3 import blake3
    
    
    signal.alarm(15)
    
    key = b'wikipedia.org/wiki/Trinity'.ljust(32)
    
    God = bytes.fromhex(input('God >'))
    GOd = bytes.fromhex(input('GOd >'))
    GOD = bytes.fromhex(input('GOD >'))
    
    trinity = {God, GOd, GOD}
    
    assert 3 == len(trinity)
    assert 1 == len({blake3(x, key=key).digest(8) for x in trinity})
    
    with open('/flag.txt') as f:
        print(f.read())

    BLAKE3 でハッシュ化したときに上位8bytesが一致する3つの入力を求められればフラグが手に入ります。

    現段階では BLAKE3 に脆弱性は発見されていないため、純粋に探索する問題となります。いかに高速に探索させるかがポイントとなります。 このような脳筋問題はあまり CTF では好まれない傾向がありますが、個人的にはこういう問題にも興味があります。暗号という観点では重要な技術だと思います。 この問題の想定解法は Pollard's Lambda Algorithm を GPU で並列化させる方法です。著者実装で1時間程度で見つかります。1時間で見つかるんだから驚きです。

    公式 writeup はこちらとなります。 https://sasdf.github.io/ctf/tasks/2021/BalsnCTF/crypto/trinity/

    CryptoHack: Bruce Schneier's Password

    Part 1 と Part 2 があります。自分が推したいのは Part 2 です。

    import numpy as np
    import random
    import re
    from Crypto.Util.number import isPrime
    from utils import listener
    
    
    FLAG = "crypto{??????????????????}"
    SCHNEIER_FACTS = [
        "Bruce Schneier can write a recursive program that proves the Riemann Hypothesis. In Malbolge.",
        "The halting problem doesn't apply to Bruce Schneier. Loops terminate when he tells them to.",
        "Bruce Schneier knows Chuck Norris' private key.",
        "Bruce Schneier reads the 'Voynich Manuscript' as a bedtime story.",
        "Bruce Schneier never gets a speeding ticket because the camera manufacturers don't want to have to show him their source code in court.",
        "Hashes collide because they're swerving to avoid Bruce Schneier.",
        "Bruce Schneier has a set of SSH Bump Keys.",
        "Bruce Schneier can read captchas.",
        "Bruce Schneier is the root of all certificates.",
        "To describe the difficulty of cracking Bruce Schneier's cryptosystem, mathematicians use the term 'NP-Awesome'.",
    ]
    
    
    def check(password):
        if not re.fullmatch(r"\w*", password, flags=re.ASCII):
            return "Password contains invalid characters."
        if not re.search(r"\d", password):
            return "Password should have at least one digit."
        if not re.search(r"[A-Z]", password):
            return "Password should have at least one upper case letter."
        if not re.search(r"[a-z]", password):
            return "Password should have at least one lower case letter."
    
        array = np.array(list(map(ord, password)))
        if isPrime(int(array.sum())) and array.sum() == array.prod():
            return FLAG
        else:
            return f"Wrong password, sum was {array.sum()} and product was {array.prod()}"
    
    
    class Challenge():
        def __init__(self):
            self.before_input = f"{random.choice(SCHNEIER_FACTS)}\n"
    
        def challenge(self, message):
            if not "password" in message:
                self.exit = True
                return {"error": "Please send Bruce's password to the server."}
    
            password = message["password"]
            return {"msg": check(password)}
    
    
    listener.start_server(port=13401)

    こちらは常設 CTF の問題ですので解法に関する話は控えますが、ぜひ解いてみて欲しいです。 個人的にはこの問題は数ヶ月間ずっと悩まされた問題で、解けたときの感動が忘れられません。解いてる過程でいろいろと勉強になりました (ネタバレになるのでふわふわしたことしか言えない)。

    おわりに

    この記事では Crypto 問のリストを共有し、個人的に面白いと感じた問題を一部紹介しました。 リストやこの記事を見てみなさんが「へーこんな手法があるのか」というのを発見をできたり「面白そうな問題だな、やっていき」の気持ちになれたりしたら幸いです。 特にここで紹介した問題は何かしら得られるものがある問題だと思うので、解いたことのない人はぜひ挑戦してみてください。

    余談になりますが、問題リストを作るの結構大変な作業で12月は結構それに疲弊してしまいました。今後はコツコツ作っていきます。絶対に。 解き残している問題が可視化されたのは大きなメリットで、年末はそれらを消化して楽しむことができそうです。

    次回は予定の変更がなければ12/20の Edwow Math さん による「弱小プレーヤーがムズめのCTFに立ち向かった記録」です。数学に強い Crypto player というイメージを勝手ながら持っていますが、はたしてどんな記録になるのでしょうか。

      ;