はじめに

こんにちは、LLUUIIGGEEです。主にPwnをやっていて、Reversingはその延長でちょこっと触れた程度なので、まだ初心者です。

最近（というか昨日）ブログを開設したところで色々記事を書きたいな～と思っており、この問題のWriteupがまだ上がってなかったので、それなら書いてしまおうということで書きました。

問題概要

アセンブリを読もう！
フラグは Alpaca{challenge関数の返り値} として送信してください。

配布されたファイルを展開すると、challenge関数のアセンブリが書かれたテキストファイルが得られます。中身はこのようになっています。

0000000000000840 <challenge>:
 840:   52800000        mov     w0, #0x0                        // #0
 844:   52800001        mov     w1, #0x0                        // #0
 848:   52800024        mov     w4, #0x1                        // #1
 84c:   52800002        mov     w2, #0x0                        // #0
 850:   14000005        b       864 <challenge+0x24>
 854:   0b030000        add     w0, w0, w3
 858:   11000421        add     w1, w1, #0x1
 85c:   2a0203e4        mov     w4, w2
 860:   2a0303e2        mov     w2, w3
 864:   0b040043        add     w3, w2, w4
 868:   3607ff61        tbz     w1, #0, 854 <challenge+0x14>
 86c:   11000421        add     w1, w1, #0x1
 870:   7100a03f        cmp     w1, #0x28
 874:   54ffff41        b.ne    85c <challenge+0x1c>  // b.any
 878:   d65f03c0        ret

tbzという見慣れない命令があるのでこれを調べてみると、どうやらArmアーキテクチャのアセンブリのようです。tbz r, imm, labelという命令は、レジスタrの値の、下からimmビット目(0-origin)が0ならば、labelにジャンプするという命令です。

ちなみに、ほかの命令の意味は以下のようになります。

mov a, b: bをaに代入する
add a, b, c: bとcの和をaに代入する
b label: labelに無条件でジャンプ
cmp a, b; b.ne label: aとbが等しくないならばlabelにジャンプ
ret: w0を返り値として関数リターン

解法

アセンブリの動作が大まかに分かったところで、Pythonでこのアセンブリを再現してみましょう。

変数としてw0~w4に加え、次に実行する命令のアドレスpcも保持するようにし、ループを回します。分かりやすいように、元のアセンブリを、分岐・合流のない基本ブロックに分けておきます。

0000000000000840 <challenge>:
 840:   52800000        mov     w0, #0x0                        // #0
 844:   52800001        mov     w1, #0x0                        // #0
 848:   52800024        mov     w4, #0x1                        // #1
 84c:   52800002        mov     w2, #0x0                        // #0
 850:   14000005        b       864 <challenge+0x24>

 854:   0b030000        add     w0, w0, w3
 858:   11000421        add     w1, w1, #0x1

 85c:   2a0203e4        mov     w4, w2
 860:   2a0303e2        mov     w2, w3

 864:   0b040043        add     w3, w2, w4
 868:   3607ff61        tbz     w1, #0, 854 <challenge+0x14>

 86c:   11000421        add     w1, w1, #0x1
 870:   7100a03f        cmp     w1, #0x28
 874:   54ffff41        b.ne    85c <challenge+0x1c>  // b.any

 878:   d65f03c0        ret

再現したPythonプログラムは以下のようになります。

w0 = 0
w1 = 0
w4 = 1
w2 = 0
pc = 0x864 # jump to 0x864

while True:
    if pc == 0x854:
        w0 += w3
        w1 += 1
        pc = 0x85c

    if pc == 0x85c:
        w4 = w2
        w2 = w3
        pc = 0x864

    if pc == 0x864:
        w3 = w2 + w4
        if w1 & 1 == 0:
            pc = 0x854
            continue

        w1 += 1
        if w1 != 0x28:
            pc = 0x85c
            continue
        break

# w0が返り値
print(w0)

ところでこのプログラム、情報論理の授業でやった、whileプログラムの正規化みたいですよね

このプログラムを実行すると102334155が出力されます。つまり、このchallenge関数の返り値は102334155ということなので、フラグはAlpaca{102334155}です。

おまけ

102334155という数字を見てぴんときた方もいるかもしれませんが、この関数はフィボナッチ数列の0x28=40番目の数を求める関数になっています。Pythonコードの0x28の部分を色々な数に変えると、さまざまなフィボナッチ数を計算することができます。（ただし、奇数にすると無限ループに陥るので気を付けてくださいね）

CTFのReversingという分野は、このような簡単なプログラムに難読化を施すことによって、プログラムの意味を分かりにくくする意地悪な問題が多いです。そういったコードを、一行一行丁寧に追っていって、動作を解き明かしていくのが醍醐味なのかなと思っています。