Union CTF 2021 writeup - ふるつき

Mordel Primes
- 感想
committee
- 感想

Mordel Primes

from Crypto.Util.number import bytes_to_long
from secrets import k, FLAG

assert k < 2^128
assert FLAG.startswith(b'union{')

E = EllipticCurve(QQ,[0,1,0,78,-16])
P = E(1,8)
Q = k*P
R = (k+1)*P

p = Q[0].numerator()
q = R[0].numerator()

assert is_prime(p)
assert is_prime(q)

e = 0x10001
N = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,N)

print(f'N = {N}')
print(f'c = {c}')

RSAの秘密鍵 $p, q$ を有理数体上の楕円曲線 $E$ 上の2点 $Q, R$ のx座標の分子から生成しています。少し実験すると、有理数体上では $k$ が大きくなればなるほどその座標の値も大きくなっていることがわかります。これは結構なスピードで大きくなるので、 $k$ の値を全探索すれば適切な $Q, R$ が見つかりそうに思えます。

E = EllipticCurve(QQ,[0,1,0,78,-16])
P = E(1,8)

N = ...
c = ...

for k in range(2, 1000):
    Q = k*P
    R = (k+1)*P

    M = Q[0].numerator() * R[0].numerator()
    if N == M:
        p, q = (Q[0].numerator(), R[0].numerator())
        break
else:
    quit()

e = 0x10001
N = p*q
phi = (p-1)*(q-1)
d = inverse_mod(e, phi)

m = pow(c, d, N)
print(bytes.fromhex(hex(m)[2:]))

感想

要素が無限にある有理数体上の楕円曲線なのだから、値がどんどん大きくなるのはそれはそうだよなぁと思った。そこにたどり着くまでに色々机上の空論をこねくり回してはうまく行かないと頭を抱えていましたが、実験するとすぐだったので実験は大事ですね。

committee

flag.txt というファイルだけが存在する git リポジトリと、そのコミットログが渡されます。リポジトリ自体のログは最初の2コミット分しか記録されていません。また、flag.txt の中身は union{*******3*********_************r****d**********} となっています。

...

commit cb18d2984f9e99e69044d18fd3786c2bf6425733
Author: Peter G. Anderson <pepega@legal.committee>
Date:   Tue Apr 14 12:00:00 2020 +0000

    Proceedings of the flag-deciding committee: 32, 33, 34

commit dca4ca5150b82e541e2f5c42d00493ba8d4aa84a
Author: Christopher L. Hatch <crisscross.the.hatch@legal.committee>
Date:   Mon Mar 23 12:30:00 2020 +0000

    Proceedings of the flag-deciding committee: 8, 31, 36

commit c3e6c8ea777d50595a8b288cbbbd7a675c43b5df
Author: Pamela W. Mathews <pammy.emm@legal.committee>
Date:   Fri Mar 13 12:30:00 2020 +0000

    Proceedings of the flag-deciding committee: 18

commit 08e1f0dd3b9d710b1eea81f6b8f76c455f634e87
Author: Robert J. Lawful <boblaw@legal.committee>
Date:   Wed Mar 4 12:00:00 2020 +0000

    Initial formation of the flag-deciding committee.

与えられた情報から、この問題はコミットログを頼りにフラグのi文字目の値を探索し、ログに残されたコミットハッシュと一致しているかを調べていくことで解けそうです。このためには、gitのコミットハッシュがどのように決まるのかを知る必要があります。これには Gitのコミットハッシュ値は何を元にどうやって生成されているのか | メルカリエンジニアリングというブログ記事が参考になりました。 .git/objects 以下に存在するファイルと照らし合わせながら処理をかいて、最終的に次のようなプログラムで解くことができました。

import re
from datetime import datetime
import zlib
from hashlib import sha1
from typing import List
from ptrlib import brute_force_attack, brute_force_pattern

def get_indices(s: str):
    xs = re.findall(r"\d+", s)
    return [int(x) for x in xs]

class Commit():
    def __init__(self):
        self.binsha = b""
        self.author = ""
        self.date = 0
        self.message = ""

    def __repr__(self):
        return "commit {}\nAuthor: {}\nDate:   {}\n{}".format(self.binsha.hex(), self.author, datetime.fromtimestamp(self.date).strftime("%c +0000"), self.message)

    def get_hash(self, flag, parent):
        blob = "blob {}\0{}".format(len(flag), flag)

        treecontent = b"100644 flag.txt\0" + sha1(blob.encode()).digest()[:20]
        tree = b"tree " + str(len(treecontent)).encode() + b"\0" + treecontent
        treehash = sha1(tree).digest()[:20]

        obj = "tree {}\nparent {}\nauthor {} {} +0000\ncommitter {} {} +0000\n{}".format(treehash.hex(), parent.hex(), self.author, self.date, "Flag-deciding Committee <committee@legal.committee>", self.date, self.message)
        target = b"commit " + str(len(obj)).encode() + b"\0" + obj.encode()
        # return repr(target)
        return sha1(target).hexdigest()


with open("log.txt") as f:
    lines = f.read().strip().split("\n")
    commits = [] # type: List[Commit]
    commit = Commit()
    for i in range(len(lines)):
        if lines[i].startswith("commit "):
            if commit.binsha:
                commit.message = commit.message[:-1]
                commits.append(commit)
                commit = Commit()

            commit.binsha = bytes.fromhex(lines[i][len("commit "):])

        elif lines[i].startswith("Author: "):
            commit.author = lines[i][len("Author: "):]

        elif lines[i].startswith("Date:   "):
            commit.date = int(datetime.strptime(lines[i][len("Date:   "):], "%c %z").timestamp())

        else:
            commit.message += lines[i].lstrip() + "\n"
    commits.append(commit)

flagstr = "union{*******3*********_************r****d**********}\n"
offset = 5
commits = commits[:-2][::-1]
for i in range(1, len(commits)):
    indices = get_indices(commits[i].message)

    for b in brute_force_attack(len(indices)):
        p = brute_force_pattern(b)
        flag2 = list(flagstr)
        for j, k in enumerate(indices):
            flag2[offset + k] = p[j]

        h = commits[i].get_hash("".join(flag2), commits[i-1].binsha)
        if h == commits[i].binsha.hex():
            flagstr = "".join(flag2)
            print(flagstr)
            break
    else:
        raise Exception()

感想

gitのコミットハッシュに関する問題はどう出題したものかと思っていましたが、とてもきれいな出題がなされていてすごいと思いました。そして勉強になった。最初の2コミットが残されていて、自分の書いたプログラムが正しいかどうかをそれで検証できる用になっているのがとても親切だと思います