Pythonで鍵生成 - Keygen | はじめてのリバースエンジニアリング#7

鍵生成プログラムKeygenをPythonで作成します。 まずはradare2を用いてパスワード認証アルゴリズムを解析し、それを開くことができるKeygenを作成しました。



Introduction

前回は、ごく簡単な暗号アルゴリズムを用いてパスワード認証プログラム"your_pass_2"を作成しました。

www.bioerrorlog.work

今回は、このバイナリコードを自らリバースエンジニアリングして仕様を解析し、パスワード認証を通過できる鍵を生成する"Keygen"をPythonで作成します。

なお、内容はこのLiveOverflow氏の動画を参考に、自分で少し改変を加えつつ流れを再現するという形になります。

youtu.be


Material

Ubuntu18.04.1 LTS を
Windows10の上に、VMwareによって構築した仮想環境で起動しています。
www.bioerrorlog.work


Results

radare2でアルゴリズムを解析する

radare2でバイナリコード"your_pass_2"を逆アセンブルし、パスワード認証のアルゴリズムを解析します。 まずは、ビジュアルモードで着目すべき場所を探します。

なお、radare2の使い方については過去記事に詳しく記録しました。

www.bioerrorlog.work

それでは、さっそくradare2のビジュアルモードでmain関数を解析します。

$ r2 your_pass_2
~
> aaa
~
> s sym.main
> VV
Rendering graph...

ビジュアルモードの結果を入念に見ると、一箇所だけループ構造が発生していました(Fig. 1)。 ここを詳しく解析してみます。

f:id:BioErrorLog:20190223232422p:plain
Fig. 1 main関数で見られたループ部分のアセンブラコード構造

forループの特定

ループ構造として、まずはforループを疑ってみます。 これが典型的なforループならば、ループに入る前に0にセットされ、ループのたびに1ずつ増える変数(ループカウンタ" i ")があるはずです。 探してみると、ループ前に0にセットされている変数が2つありました(Fig. 1, ➀ブロック)。

mov dword [local_18h], 0 
mov dword [local_14h], 0

この2つの変数dword [local_18h]dword [local_14h]の行く末を見てみると、dword [local_14h]はループごとに1が加算されているのがわかります(Fig. 1, ➂ブロック)。

add dword [local_14h], 1 

ここからdword [local_14h]がループカウンタ" i "である期待が高まります。

つぎに、dword [local_14h]がループカウンタであれば、forループの終了条件に絡んでいるはずです。 そこでforループの分岐条件を辿ってみると(Fig. 1, ➁)、

mov eax, dword [local_14h]
~
movsxd rbx, eax
~
cmp rbx, rax
jb 0x723

dword [local_14h]eaxrbxと、分岐条件cmp rbx, raxに繋がっていました。

以上のことから、このループ構造はdword [local_14h]をループカウンタ" i "としたforループであると判断しました。

forループの処理を解析する

次に、forループ内の処理(Fig. 1, ➂ブロック)を解析しました。 とても複雑で難解なので、Cで書かれたソースコード1を書き置きます。

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

int main(int argc, char *argv[]) {
        if(argc==2) {
                printf("Checking Your Pass: %s\n", argv[1]);
                int sum = 0;
                for (int i=0; i<strlen(argv[1]); i++) {
                        sum += (int)argv[1][i];
                }
                if(sum==5345) {
                        printf("Hello, Master.\n");
                } else {
                        printf("Access Denied.\n");
                }

        } else {
                printf("Access Denied.\n");
        }
        return 0;
}

このソースコードによると、forループ内では、入力された文字argv[1]を一文字ずつint値として変数sumに加算していることがわかります。 この処理を、radare2で逆アセンブルしたコードから読み解きます。

forループ内(Fig. 1, ➂ブロック)は、

mov rax, qword [s]  
add rax, 8  
mov rdx, qword [rax] 
mov eax, dword [local_14h]
cdqe  
add rax, rdx   
movzx eax, byte [rax]    
movsx eax, al   
add dword [local_18h], eax
add dword [local_14h], 1

となっています。 最初から順に読み解いていきます


まず最初の2行に着目しました。

mov rax, qword [s]  
add rax, 8

レジスタraxに値が格納された後、8が加算されている点に注目します。 これは、raxが配列のアドレスを格納していることを示唆しています。

通常、64 bitコンピュータではメモリが8 byteずつに分割されています。 よって、1行目でraxに何かの配列のアドレスが格納された場合、2つ目の配列要素にアクセスしたいときにはraxに8を加算すればよい、というわけです。

ここで「2つ目の配列要素にアクセス」ということから考えられるのは、入力文字argv[1]でしょう。 argv[]配列は、プログラムの実行時に渡される引数を格納しています。 たとえばこのプログラム"your_pass_2"を、"Wrong-Pass"という文字列を渡して実行した場合、

$ ./your_pass_2 Wrong-Pass

argv[]配列は次のように格納されています。

./your_pass_2 Wrong-Pass
argv[0] argv[1]

よって、上記の2行は次のように解釈できそうです。

アセンブラコード レジスタの解釈
mov rax, qword [s] rax: argv[0]のアドレス
add rax, 8 rax: argv[1]のアドレス


では、次のコードに移ります

mov rdx, qword [rax] 
mov eax, dword [local_14h]
cdqe  
add rax, rdx   

前述の通り、raxargv[1]のアドレスを示しているので、1行目でrdxに格納されたのはargv[1]の中身を指すアドレスでしょう。 通常、先頭が指定されます。

アセンブラコード レジスタの解釈
mov rdx, qword [rax] rdx: argv[1]の中身の先頭を指すアドレス


次の行mov eax, dword [local_14h]では、dword [local_14h]が登場します。 これは、上述したようにforループで1ずつ増えるループカウンタです。 よってループカウンタの値がeaxに格納されるわけです。

その次の行cdqeは、eaxraxに設定する操作です2。 よって最後のadd rax, rdxは、先頭を指すアドレスrdxに、ループカウンタの値raxを足して、raxに格納しています。 ここまでをまとめると、

アセンブラコード レジスタの解釈
mov eax, dword [local_14h] eax: ループカウンタの値
cdqe rax: ループカウンタの値
add rax, rdx rax: 先頭アドレス+ループカウンタ


それでは最後の部分です。

movzx eax, byte [rax]    
movsx eax, al   
add dword [local_18h], eax

まずmovzx eax, byte [rax]で、raxの指し示すアドレスから1バイトを読み込んでいます。 この値はまさに入力文字のASCII値であると考えられます。 例えば、入力文字が"Wrong-Pass"で、ループカウンタが2の場合、

入力文字: W r o n g
ASCII値: 0x57 0x72 0x6F 0x6E 0x67
rax(rdx+ループカウンタ): rdx+1 rdx+2 rdx+3 rdx+4 rdx+5

eaxには"r"のASCII値0x72が格納されるというわけです。

次の行movsx eax, alでは、eaxの下位8ビット部分がeaxに再格納されています。 というのも、aleaxの下位8ビットを示すレジスタだからです3

そして最後には、add dword [local_18h], eaxeaxの値がdword [local_18h]に加算されています。 ここで、先に述べたようにdword [local_18h]は0で初期化された変数です。 つまり、ループごとにdword [local_18h]に入力文字が加算され、最後には入力文字の合計ASCII値の総和が格納されている、ということになります。


かなり長く複雑な解析をしてきました。 ここまでわかったforループの処理をまとめます。

アセンブラコード レジスタの解釈
mov rax, qword [s] rax: argv[0]のアドレス
add rax, 8 rax: argv[1]のアドレス
mov rdx, qword [rax] rdx: argv[1]の中身の先頭を指すアドレス
mov eax, dword [local_14h] eax: ループカウンタの値
cdqe rax: ループカウンタの値
add rax, rdx rax: 先頭アドレス+ループカウンタ
movzx eax, byte [rax] eax: 入力文字のASCII値
movsx eax, al eax: 下位8ビットを再格納
add dword [local_18h], eax dword [local_18h]: 入力文字ASCII値の総和


アクセス可否の判定条件

ここまで、forループ内で入力文字の総和dword [local_18h]が計算されていることを明らかにしました。 つぎは、この処理結果がどのようにしてアクセス可否の判定に使われているかを調べます。

これは簡単に分かりました。 forループ終了後の処理を見ると(Fig. 1, ➃)、次のようになっています。

cmp dword [local_18h], 0x14e1 
jne 0x778

つまり、入力文字の総和dword [local_18h]が0x14e1であるかどうかを判定し、プログラムが分岐しているわけです。

ついに、このプログラムの挙動が明らかになりました。 各入力文字ASCII値の総和が0x14e1であればアクセス承認、そうでなければアクセス拒否です。


Pythonで鍵生成 - Keygen

このパスワード認証プログラムの仕組みがわかったので、これを破るためのKeygenを作成します。 仕様は単純です。 ASCII値の総和が0x14e1となる文字列を自動生成するプログラムを、Pythonで書きます4

import random

#文字列keyの合計ASCII値を算出する関数
def check_key(key):
    char_sum = 0
    for c in key:
        char_sum += ord(c)
    return char_sum

#合計ASCII値が5345(0x14e1)である文字列を無限ループで生成
key = ""
while True:
    key += random.choice("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_")
    s = check_key(key)
    if s > 5345:
        key = ""
    elif s == 5345:
        print ("Key: {0}".format(key))

さっそくこのPythonプログラム"keygen_your_pass_2.py"実行してみます。

$ python3 keygen_your_pass_2.py 
Key: 3beg-iCw2Xg7OP7E1xkn-HEaxai-KRl43pj5OkJuViZJnIozP9-q-XKOG7v0vWy6
Key: kI_MoMol9yqM6gImi2lyfVhNn6npOo7eRXxelQ4VHh88_BIfb5NtKvsyVHF1
Key: 9qFkJQVe74CTJz5EpF8h6E6bukw1XFYJ7YhndKM58SlymLooMra30RfgUUFUN5kK
Key: PLySl4Mu_eDoOaDQ7BV09K6WGrtOZFLP--pojSBFq8GPxIsgIxX_I0YkNQmBb8f7
Key: ui-IAbPFU2cR20ZMCMYSbyMqbuNpUqNutqwtll-YxeZx83KcI--u-PJF5B3RuAO
Key: ZL6AZgMIlphS0spzgWEsy_sFKusCS_46ahjGm2T7PQBf7h3ifrmytkX89s5z
Key: LfX9lEUp5vGDTVOlo2O7NyJQR_yne6Dd8BBTCQxfBleMmIz8RJPYYa9JuGpfdg
Key: 9yMjf2YKivb84KuhF6iLdvTssguiQne6kVKyjJvAvlV13qskhNgfLOHQBy6
Key: 5tzqUevjCYFoZ1lEnJWoIJJOHD4OMTv3qB5A3W2SBlHlhuXThrqksLV8FuHc-j
Key: _mcHUIbIM5QEAyGQOTqvpY-5TKsVBJEdGuT86fLcP3KrqAUH_fD1s0fR2JNqVS0NL
Key: 6t0pv0F3SbtKXwEjsp47xrfnC9zr2VjtqTOrTEYGcmwoRvpkdBT2bj_T6dO
Key: BjOLf49V_xPvaONmPyiyKoQAP0WYc3PNrq7VD-UQqT8I3otgILvmADOrGo3sDf
Key: nNBYpcTZAXdx8aXA5EUwSgXsKT2lcQpaH7JnuEuvmO2bvvXKNkSdwVPlkIm
Key: YnvH_JbZsDwKmJg7_fA4xnrn-UwM_d_N_G-xQS47wsOI5q12Cwc9hVIx_m3C3D
#以下略

即座に大量の鍵が生成されました。 ちなみに無限ループなので、処理を終了するには"Ctrl+c"を押す必要があります。

それでは、はたしてこれらの鍵でこのプログラム"your_pass_2"のアクセス承認が引き出せるのかを確かめます。

$ ./your_pass_2 A2viBkKm4IU-I_pEGF6-7YKONqAEk1Vl6KIAAg88fHKjFMN2DAqBjBvlwaqib-_xe5
Checking Your Pass: A2viBkKm4IU-I_pEGF6-7YKONqAEk1Vl6KIAAg88fHKjFMN2DAqBjBvlwaqib-_xe5
Hello, Master.

"Hello, Master."
見事、アクセス承認を引き出すことができました。


Discussion

今回は、radare2を用いてパスワード認証アルゴリズムを解析し、それに基づいてPythonで鍵生成プログラムKeygenを作成しました。

以前のようにデバッグ上でレジスタを操作する5のでなく、完全に外側からアクセスを開くのはなかなか趣深いものでした。

今回はソースコードを知っている状態で、かつ極めて簡単な暗号アルゴリズムをリバースしましたが、自分が知らないプログラムの解析にも挑戦してみたいです。 そういうことをするための安全なコミュニティがネット上にはたくさんある6ようなので、今後手を出していけたらと思っています。

See also

前↓

www.bioerrorlog.work


  1. パスワード認証の暗号化 | はじめてのリバースエンジニアリング#6 - 生物系がゼロから始めるIT技術

  2. Assembly Programming on x86-64 Linux (07)

  3. プログラミングノート - x86より、"eax は rax の下位 32 ビット部分を指す。 また ax は eax の下位 16 ビット部分を指す。 さらに ax は上下 2 つの 8 ビットレジスタ ah, al に分割して使うことができる。"

  4. GitHub - LiveOverflow/liveoverflow_youtube: Material for the YouTube seriesを参考にしています。

  5. レジスタ操作でアクセス承認を引き出す - gdb | はじめてのリバースエンジニアリング#3 - 生物系がゼロから始めるIT技術

  6. 逆に、禁じられているソフトウェアを解析することは違法ですから、そこの一線は絶対に超えてはなりません。