　4月20～25日にangstromCTFが開催されてました．チームzer0ptsで参加し、3730点で8位でした．僕個人は、MiscとCryptoしかやってないです．

　今回は結構たくさんの問題を解くことができたので、うれしいです． Miscの簡単な問題を除いて以下に、Writeupを書いていきます．

チームメンバーのWriteup

theoldmoon0602 : ångstromCTF 2019 writeup - ふるつき

ptr-yudai : angstromCTF 2019 Writeup - CTFするぞ

st98 : ~~ちょいまち~~ angstromCTF 2019 の write-up - st98 の日記帳

[Misc 40] Paper bin

defund accidentally deleted all of his math papers! Help recover them from his computer's raw data.

　paper_bin.datというファイルが渡されます．

　recoverしてくれと言われているので、拡張子をpdfに変更してみます．普通にpdfが見れるのですが、pdfの中を検索してもフラグが一向に見つかりません．しかし、foremostをするとpdfの中に20個ほどpdfが隠されていることがわかりました．

$ foremost paper_bin.dat　　（pdfからでも取れます）
Processing: paper_bin.dat
|*|
$ cd output/pdf/
$ evince *

　雑にpdfを開けて、1つずつactfで検索するとフラグが取れます．

actf{proof_by_triviality}

　この問題は、10ページのpdfに対してサイズがやけに大きいことに感づくべきで、初めは全然気づかなかったです．実ははじめforemostをpdfに対してしたけど、cd output/を見てpdf以外なんもないじゃんって放置してました... 気づくまで、ddとかで空白を消したりしてました（ddコマンドの練習にはなった...）．

[Misc 60] Lithp

My friend gave me this program but I couldn't understand what he was saying - what was he trying to tell me?

　lithp.lispというファイルが渡されます．

;LITHP

(defparameter *encrypted* '(8930 15006 8930 10302 11772 13806 13340 11556 12432 13340 10712 10100 11556 12432 9312 10712 10100 10100 8930 10920 8930 5256 9312 9702 8930 10712 15500 9312))
(defparameter *flag* '(redacted))
(defparameter *reorder* '(19 4 14 3 10 17 24 22 8 2 5 11 7 26 0 25 18 6 21 23 9 13 16 1 12 15 27 20))

(defun enc (plain)
    (setf uwuth (multh plain))
    (setf uwuth (owo uwuth))
    (setf out nil)
    (dotimes (ind (length plain) out)
        (setq out (append out (list (/ (nth ind uwuth) -1))))))
    
(defun multh (plain)
    (cond
        ((null plain) nil)
        (t (cons (whats-this (- 1 (car plain)) (car plain)) (multh (cdr plain))))))

(defun owo (inpth)
    (setf out nil)
    (do ((redth *reorder* (cdr redth)))
        ((null redth) out)
        (setq out (append out (list (nth (car redth) inpth))))))

(defun whats-this (x y)
    (cond
        ((equal y 0) 0)
        (t (+ (whats-this x (- y 1)) x))))

;flag was encrypted with (enc *flag*) to give *encrypted*

　僕はlispわからないマンなので、condとかをググりながら読み解きます．すると．whats-thisがただ単にx * yをしてるだけだったり、owoがreorderの順に並び変えているだけだということがわかります．

　ここまでわかったので、自分の書きやすい言語で調べていきます（僕はpython）． owoを日本語でうまく説明できないですが（すいません）、

for i in range(len(encrypted)):
    encrypted[reorder.index(i)]

こんな感じで、encryptedを参照すると元の位置のものがわかります．

　ここで、encryptedが何か（lisp読むと平文っぽい）がwhats-thisに入っているのを思い出します．そのため、encryptedは平文actf{と何かを掛けたものだと考えられます．やってみると、

f = 'actf{'
for i, c in enumerate(f):
    a = encrypted[reorder.index(i)] / ord(c)
    print(a)

96.0          <- * ord('a')
98.0          <- * ord('c')
115.0        <- * ord('t')
101.0        <- * ord('f')
122.0        <- * ord('{')

きれいに割れてます．ord('a') = 97であることを考えると、1引いたものだとわかります（lispをきちんと読むとわかる）．

　となると、encryptedに格納されている数字はフラグの文字 * (フラグの文字 - 1)とわかります．ここまでわかると、1文字ずつ全探索をするとフラグが得られます．

import string

encrypted = [8930, 15006, 8930, 10302, 11772, 13806, 13340, 11556, 12432, 13340, 10712, 10100, 11556, 12432, 9312, 10712, 10100, 10100, 8930, 10920, 8930, 5256, 9312, 9702, 8930, 10712, 15500, 9312]
reorder = [19, 4, 14, 3, 10, 17, 24, 22, 8, 2, 5, 11, 7, 26, 0, 25, 18, 6, 21, 23, 9, 13, 16, 1, 12, 15, 27, 20]

attack = string.printable

flag = ''
for i in range(len(encrypted)):
    for c in attack:
        if encrypted[reorder.index(i)] == ord(c)*(ord(c)-1):
            print('[+]find : {}'.format(c))
            flag += c

print('[!]flag : {}'.format(flag))

actf{help_me_I_have_a_lithp}

　lispを軽く理解して、あとはエスパー？で補って解いていく感じが楽しかったです． lispを完璧に読むとこんなに手順を踏まなくてもいいですが、CTF感があって楽しかったです．

[Misc 60] Just Letters

Hope you’ve learned the alphabet!

AlphaBeta - Esolang こういう頭がおかしくなる系の言語っぽいです．

$ nc 54.159.113.26 19600
Welcome to the AlphaBeta interpreter! The flag is at the start of memory. You get one line:
>

　メモリのはじめにフラグがあるみたいです．いろいろ遊んでると、outputの命令を呼ぶとregister3にある値が参照されるっぽいです．なのでこの辺りを使います．

C sets register 3 to the value of register 1
G sets register 1 to the memory at the memory pointer
L outputs a character to the screen
S adds 1 to the register
Y sets the register to 0

　YGCLを送るとaが返ってきます．次の文字からはSGCLで求められます．フラグの長さはわからないので、YGCLSGCLSGCLSGCLSGCL...とSGCLをたくさん繰り返したものを送るとフラグを得られます．

actf{esolangs_sure_are_fun!}

[Crypto 50] Half and Half

Mm, coffee. Best served with half and half!

　フラグを半分にしたものをxorしただけです．

from secret import flag

def xor(x, y):
    o = ''
    for i in range(len(x)):
        o += chr(ord(x[i])^ord(y[i]))
    return o

assert len(flag) % 2 == 0

half = len(flag)//2
milk = flag[:half]
cream = flag[half:]

assert xor(milk, cream) == '\x15\x02\x07\x12\x1e\x100\x01\t\n\x01"'

　フラグの形式からmilkの初めがactf{であるので、creamの5文字がtasteであることがわかります．しかしこれでは

milk  = actf{xxxxxx_
cream = tastexxxxxx}

　ここで、残りの文字をエスパーします．

import string

def xor(x, y):
    o = ''
    for i in range(len(x)):
        o += chr(ord(x[i]) ^ ord(y[i]))
    return o

a = '\x15\x02\x07\x12\x1e\x100\x01\t\n\x01"'

b = 'coffee'
for i in range(len(a)):
    print(xor(b, a[i:i+len(b)]))

　これお行儀の悪いプログラムなので、当然怒られますが、bの文字列がいい感じの文字になるか調べられます．初めはbにmilkとかcreamとかを適当に入れてみますが駄目でした．問題文よりcoffeeを入れてみると、

vmat{u
ahtxuU
d}xvUd
qqvVdl
}Vglo
s_good
SnoldG
おこ

s_goodがいい感じなので、フラグが

milk  = actf{coffee_
cream = tastes_good}

だとわかります．

[Crypto 150] Lattice ZKP

I tried to make a zero knowledge proof, but something isn't right.

　ncすると、なにやら大きな値のA*r + eが得られます．そのあとに、rかr + sのどちらかを選べる想定の問題だと思います．しかし、複数回ncしても毎回A*r + eの値は変わりません．そのため、rとr + sを得ることができるので、鍵であるs（各自プログラムをよんでほしい）を簡単に求めることができます．

　あとは、暗号文を平文に戻すことを考えるだけです．といっても、sのハッシュとxorしているだけなので、同じことをします．注意点としては、行列で値を持っていて、それをpackしたものが見えているので、packを戻すこと（unpack）を考えなければならないです．さらにもう一つ注意することがあって、Cryptoモジュールはpycryptoではなくpycryptodomeのものを使いましょう（ややこしい）．

from Crypto.Util.strxor import strxor
from Crypto.Hash import SHAKE256
from Crypto.Util.asn1 import DerSequence
import binascii
import numpy as np


pack = lambda x: binascii.hexlify(DerSequence(x.tolist()).encode())
unpack = lambda x: np.array(DerSequence().decode(binascii.unhexlify(x)))

def sub(x, y):
    return np.mod(x-y, q)

with open('./r.txt') as f:
    r = f.read().strip()

with open('./r_plus_s.txt') as f:
    r_plus_s = f.read().strip()

q = 1 << 15
s = sub(unpack(r_plus_s), unpack(r))

print('[+]s : {}'.format(s))

with open('./flag.enc', 'rb') as f:
    enc_flag = f.read().strip()

raw = bytes(np.mod(s, 256).tolist())
shake = SHAKE256.new()
shake.update(raw)
pad = shake.read(len(enc_flag))
flag = strxor(enc_flag, pad)
print('[!]flag : {}'.format(flag))

actf{deep_into_that_darkness_learning_with_errors_goes}

　僕が手を動かして書いていたのですが、theoldmoon0602にunpack等の助言を得ながら解きました．ややこしいところすべてtheoldmoon0602によって解決したので、ほとんど彼が解いた感じです...

[Crypto 200] Powerball

Introducing ångstromCTF Powerball, where the Grand Prize is a flag! All you need to do is guess 6 ball values, ranging from 0 to 4095. But don't worry, we'll give one for free!

　ptr-yudaiからOblivious TransferでRSAっぽいからやってみて！と言われてやってみた問題です．申し訳ないですけど、Oblivious Transferが何なのかよく知らないです... が、あふれる想像力でなんとかしました（嘘です）．

　nとeが渡されています．ランダムで生成された6つのxが毎回見れます．次に好きな数vを入力することができ、各i=0, 1, ... ,6について

$k = (v - x_i)^{d} \bmod{n}$

$m_i = balls_i + k$

によって、mが計算され、表示されます．

　これらの情報から、ballsを6つ予想し、すべて合えばフラグが得られるいう問題でした．

　これはRSAが元ということを考えるとうまく解けます． kを求める際、RSAっぽさを感じないですか？？感じれば勝ちです．つまり、

$v - x_i = k^{e} \bmod n$

が成り立ちそうです．ここで $m_i = balls_i + k$ より $k = balls_i - m_i$ なので上式に代入すると、

$v - x_i = (m_i - balls_i)^{e} \bmod n$

この式で、わからないのはballsだけなので、全探索します（ballsは0~4095の値でしかない）．

for m, x in zip(ms, xs):
    for i in range(4096):
        if (max_x - x) == pow(m - i, e, n):
            print('[!]find bull : {}'.format(i))

　vの値として、xの中で一番大きい値を選んでいます（特にこれといった理由はないが、よさそうな感じがしたので...）．

　実は、僕がしたのはここまでで、ncでやり取り云々はptr-yudaiに任せました．（僕はすぐに書けないので、pwnで手慣れている彼に投げた．）ここには、自分でやり取りする部分も書いて載せようと思ったのですが、こんなに長いWriteupを書くのは初？？なので疲れてしまいました．回復したら、更新するかもしれないです（しないやつ）．

actf{no_more_free_oblivious_transfers}