CTF日本語サイト : DEF CON CTF Qualifier 2016 writeup baby-re

baby-re

Baby's First, 50 points

Get to reversing.

baby-re

fileコマンドでダウンロードしたファイルのファイルタイプを確認します。Linuxの64bit実行ファイルです。

$ file baby-re
baby-re: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=5d5783d23d78bf70b80d658bccbce365f7448693, not stripped

objdumpコマンドで逆アセンブルし動作を解析します。

$ objdump -s -D baby-re > aaa.txt

<main>関数の中でVar[0]～Var[12]の入力を要求してきます。すべて入力されたら、<CheckSolution>関数を呼び出して入力値をチェックしています。正しい場合は、入力された値を文字コードとする文字列を出力して、それがフラグになります。
まず、以下の箇所でVar[0]へ入力しています。

00000000004025e7 <main>:
(略)
402605: bf 08 2a 40 00 mov $0x402a08,%edi #Var[0]:
40260a: b8 00 00 00 00 mov $0x0,%eax
40260f: e8 6c df ff ff callq 400580 <printf@plt> #Var[0]を出力
(略)
402623: 48 8d 45 a0 lea -0x60(%rbp),%rax
402627: 48 89 c6 mov %rax,%rsi
40262a: bf 11 2a 40 00 mov $0x402a11,%edi #%d
40262f: b8 00 00 00 00 mov $0x0,%eax
402634: e8 77 df ff ff callq 4005b0 <__isoc99_scanf@plt> #数値としてVar[0](-0x60(%rbp))に入力

次にVar[1]へ入力しています。

402639: bf 14 2a 40 00 mov $0x402a14,%edi #Var[1]:
40263e: b8 00 00 00 00 mov $0x0,%eax
402643: e8 38 df ff ff callq 400580 <printf@plt>
(略)
402657: 48 8d 45 a0 lea -0x60(%rbp),%rax
40265b: 48 83 c0 04 add $0x4,%rax #+4
40265f: 48 89 c6 mov %rax,%rsi
402662: bf 11 2a 40 00 mov $0x402a11,%edi #%d
402667: b8 00 00 00 00 mov $0x0,%eax
40266c: e8 3f df ff ff callq 4005b0 <__isoc99_scanf@plt> #Var[1](-0x60+0x4(%rbp)に入力

同様に、Var[2]～Var[12]まで入力します。
そして、<CheckSolution>関数で入力値のチェックをし、戻り値が0の場合はWrongと出力、そうでない(正しい)場合は、フラグが表示されます。

4028e0: e8 e1 dd ff ff callq 4006c6 <CheckSolution> #入力値のチェック
4028e5: 84 c0 test %al,%al
4028e7: 74 58 je 402941 <main+0x35a> #al=0の場合
(略)
40292c: bf 88 2a 40 00 mov $0x402a88,%edi #The flag is: %c%c%c%c%c%c%c%c%c%c%c%c%c.
402931: b8 00 00 00 00 mov $0x0,%eax
402936: e8 45 dc ff ff callq 400580 <printf@plt>
(略)
402941: bf b1 2a 40 00 mov $0x402ab1,%edi #Wrong
402946: e8 15 dc ff ff callq 400560 <puts@plt>

次に<CheckSolution>関数を見てみます。<CheckSolution>関数では、入力されたVar[0]～Var[12]を使って計算を行いある値と比較しています。これを計13回異なる計算を行っています。つまり、この13個の式を十三元一次方程式として解けば良いということになります。
まず、1つ目の方程式が以下になります。

00000000004006c6 <CheckSolution>:
(略)
401558: 8b 95 50 fd ff ff mov -0x2b0(%rbp),%edx #37485
40155e: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
401565: 8b 00 mov (%rax),%eax
401567: 0f af d0 imul %eax,%edx #Var[0]*37485->edx
40156a: 8b 8d 54 fd ff ff mov -0x2ac(%rbp),%ecx #21621
401570: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
401577: 48 83 c0 04 add $0x4,%rax #Var[1]:
40157b: 8b 00 mov (%rax),%eax
40157d: 0f af c1 imul %ecx,%eax #21621*Var[1]->eax
401580: 89 d1 mov %edx,%ecx
401582: 29 c1 sub %eax,%ecx #Var[0]*37485-21621*Var[1]->ecx
401584: 8b 95 58 fd ff ff mov -0x2a8(%rbp),%edx #1874
40158a: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
401591: 48 83 c0 08 add $0x8,%rax #Var[2]:
401595: 8b 00 mov (%rax),%eax
401597: 0f af c2 imul %edx,%eax #1874*Var[2]->eax
40159a: 29 c1 sub %eax,%ecx #Var[0]*37485-21621*Var[1]-1874*Var[2]->ecx
40159c: 8b 95 5c fd ff ff mov -0x2a4(%rbp),%edx #46273
4015a2: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
4015a9: 48 83 c0 0c add $0xc,%rax #Var[3]:
4015ad: 8b 00 mov (%rax),%eax
4015af: 0f af c2 imul %edx,%eax #46273*Var[3]->eax
4015b2: 29 c1 sub %eax,%ecx #Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]->ecx
4015b4: 8b 95 60 fd ff ff mov -0x2a0(%rbp),%edx #50633
4015ba: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
4015c1: 48 83 c0 10 add $0x10,%rax #Var[4]:
4015c5: 8b 00 mov (%rax),%eax
4015c7: 0f af c2 imul %edx,%eax #50633*Var[4]->eax
4015ca: 01 c1 add %eax,%ecx #Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]+50633*Var[4]->ecx
4015cc: 8b 95 64 fd ff ff mov -0x29c(%rbp),%edx #43166
4015d2: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
4015d9: 48 83 c0 14 add $0x14,%rax #Var[5]:
4015dd: 8b 00 mov (%rax),%eax
4015df: 0f af c2 imul %edx,%eax #43166*Var[5]->eax
4015e2: 01 c1 add %eax,%ecx #Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]+50633*Var[4]+43166*Var[5]->ecx
4015e4: 8b 95 68 fd ff ff mov -0x298(%rbp),%edx #29554
4015ea: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
4015f1: 48 83 c0 18 add $0x18,%rax #Var[6]:
4015f5: 8b 00 mov (%rax),%eax
4015f7: 0f af c2 imul %edx,%eax #29554*Var[6]->eax
4015fa: 01 c1 add %eax,%ecx #Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]+50633*Var[4]+43166*Var[5]+29554*Var[6]->ecx
4015fc: 8b 95 6c fd ff ff mov -0x294(%rbp),%edx #16388
401602: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
401609: 48 83 c0 1c add $0x1c,%rax #Var[7]:
40160d: 8b 00 mov (%rax),%eax
40160f: 0f af c2 imul %edx,%eax #16388*Var[7]->eax
401612: 01 c1 add %eax,%ecx #Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]+50633*Var[4]+43166*Var[5]+29554*Var[6]+16388*Var[7]->ecx
401614: 8b 95 70 fd ff ff mov -0x290(%rbp),%edx #57693
40161a: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
401621: 48 83 c0 20 add $0x20,%rax #Var[8]:
401625: 8b 00 mov (%rax),%eax
401627: 0f af c2 imul %edx,%eax #57693*Var[8]->eax
40162a: 01 c1 add %eax,%ecx #Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]+50633*Var[4]+43166*Var[5]+29554*Var[6]+16388*Var[7]+57693*Var[8]->ecx
40162c: 8b 95 74 fd ff ff mov -0x28c(%rbp),%edx #14626
401632: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
401639: 48 83 c0 24 add $0x24,%rax #Var[9]:
40163d: 8b 00 mov (%rax),%eax
40163f: 0f af c2 imul %edx,%eax #14626*Var[9]->eax
401642: 01 c1 add %eax,%ecx #Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]+50633*Var[4]+43166*Var[5]+29554*Var[6]+16388*Var[7]+57693*Var[8]+14626*Var[9]->ecx
401644: 8b 95 78 fd ff ff mov -0x288(%rbp),%edx #21090
40164a: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
401651: 48 83 c0 28 add $0x28,%rax #Var[10]:
401655: 8b 00 mov (%rax),%eax
401657: 0f af c2 imul %edx,%eax #21090*Var[10]->eax
40165a: 01 c1 add %eax,%ecx #Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]+50633*Var[4]+43166*Var[5]+29554*Var[6]+16388*Var[7]+57693*Var[8]+14626*Var[9]+21090*Var[10]->ecx
40165c: 8b 95 7c fd ff ff mov -0x284(%rbp),%edx #39342
401662: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
401669: 48 83 c0 2c add $0x2c,%rax #Var[11]:
40166d: 8b 00 mov (%rax),%eax
40166f: 0f af c2 imul %edx,%eax #39342*Var[11]->eax
401672: 01 c1 add %eax,%ecx #Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]+50633*Var[4]+43166*Var[5]+29554*Var[6]+16388*Var[7]+57693*Var[8]+14626*Var[9]+21090*Var[10]+39342*Var[11]->ecx
401674: 8b 95 80 fd ff ff mov -0x280(%rbp),%edx #54757
40167a: 48 8b 85 48 fd ff ff mov -0x2b8(%rbp),%rax #Var[0]:
401681: 48 83 c0 30 add $0x30,%rax #Var[12]:
401685: 8b 00 mov (%rax),%eax
401687: 0f af c2 imul %edx,%eax #54757*Var[12]->eax
40168a: 01 c8 add %ecx,%eax #Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]+50633*Var[4]+43166*Var[5]+29554*Var[6]+16388*Var[7]+57693*Var[8]+14626*Var[9]+21090*Var[10]+39342*Var[11]+54757*Var[12]->eax
40168c: 3d 53 87 46 01 cmp $0x1468753,%eax
####0x1468753=21399379=Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]+50633*Var[4]+43166*Var[5]+29554*Var[6]+16388*Var[7]+57693*Var[8]+14626*Var[9]+21090*Var[10]+39342*Var[11]+54757*Var[12]
401691: 74 0e je 4016a1 <CheckSolution+0xfdb>
401693: eb 02 jmp 401697 <CheckSolution+0xfd1>
401695: d0 96 b8 00 00 00 rclb 0xb8(%rsi)
40169b: 00 e9 add %ch,%cl
40169d: 30 0f xor %cl,(%rdi)
40169f: 00 00 add %al,(%rax)

1つ目の方程式は次のようになります。

21399379=Var[0]*37485-21621*Var[1]-1874*Var[2]-46273*Var[3]+50633*Var[4]+43166*Var[5]+29554*Var[6]+16388*Var[7]+57693*Var[8]+14626*Var[9]+21090*Var[10]+39342*Var[11]+54757*Var[12]

以下、同様にしていくと、13個の方程式が得られます。

21399379==v0*37485-21621*v1-1874*v2-46273*v3+50633*v4+43166*v5+29554*v6+16388*v7+57693*v8+14626*v9+21090*v10+39342*v11+54757*v12
1453872==v0*50936+4809*v1-6019*v2+38962*v3+14794*v4+22599*v5-837*v6-36727*v7-50592*v8-11829*v9-20046*v10-9256*v11+53228*v12
-5074020==-38730*v0+52943*v1-16882*v2+26907*v3-44446*v4-18601*v5-65221*v6-47543*v7+17702*v8-33910*v9+42654*v10+5371*v11+11469*v12
-5467933==v0*57747-23889*v1-26016*v2-25170*v3+54317*v4-32337*v5+10649*v6+34805*v7-9171*v8-22855*v9+8621*v10-634*v11-11864*v12
7787144==-14005*v0+16323*v1+43964*v2+34670*v3+54889*v4-6141*v5-35427*v6-61977*v7+28134*v8+43186*v9-59676*v10+15578*v11+50082*v12
-8863847==-40760*v0-22014*v1+13608*v2-4946*v3-26750*v4-31708*v5+39603*v6+13602*v7-59055*v8-32738*v9+29341*v10+10305*v11-15650*v12
-747805==-47499*v0+57856*v1+13477*v2-10219*v3-5032*v4-21039*v5-29607*v6+55241*v7-6065*v8+16047*v9-4554*v10-2262*v11+18903*v12
-11379056==-65419*v0+17175*v1-9410*v2-22514*v3-52377*v4-9235*v5+53309*v6+47909*v7-59111*v8-41289*v9-24422*v10+41178*v11-23447*v12
-166140==1805*v0+4135*v1-16900*v2+33381*v3+46767*v4+58551*v5-34118*v6-44920*v7-11933*v8-20530*v9+15699*v10-36597*v11+18231*v12
9010363==-42941*v0+61056*v1-45169*v2+41284*v3-1722*v4-26423*v5+47052*v6+42363*v7+15033*v8+18975*v9+10788*v10-33319*v11+63680*v12
-4169825==-37085*v0-51590*v1-17798*v2-10127*v3-52388*v4+12746*v5+12587*v6+58786*v7-8269*v8+22613*v9+30753*v10-20853*v11+32216*v12
4081505==36650*v0+47566*v1-33282*v2-59180*v3+65196*v4+9228*v5-59599*v6-62888*v7+48719*v8+47348*v9-37592*v10+57612*v11+40510*v12
1788229==51735*v0+35879*v1-63890*v2+4102*v3+59511*v4-21386*v5-20769*v6+26517*v7+28153*v8+25252*v9-43789*v10+25633*v11+7314*v12

SageMathCloudでこの連立方程式を解きます。SageMathに次の通り入力して実行します。

sage: v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12 = var('v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12')
sage: solve([
21399379==v0*37485-21621*v1-1874*v2-46273*v3+50633*v4+43166*v5+29554*v6+16388*v7+57693*v8+14626*v9+21090*v10+39342*v11+54757*v12,
1453872==v0*50936+4809*v1-6019*v2+38962*v3+14794*v4+22599*v5-837*v6-36727*v7-50592*v8-11829*v9-20046*v10-9256*v11+53228*v12,
-5074020==-38730*v0+52943*v1-16882*v2+26907*v3-44446*v4-18601*v5-65221*v6-47543*v7+17702*v8-33910*v9+42654*v10+5371*v11+11469*v12,
-5467933==v0*57747-23889*v1-26016*v2-25170*v3+54317*v4-32337*v5+10649*v6+34805*v7-9171*v8-22855*v9+8621*v10-634*v11-11864*v12,
7787144==-14005*v0+16323*v1+43964*v2+34670*v3+54889*v4-6141*v5-35427*v6-61977*v7+28134*v8+43186*v9-59676*v10+15578*v11+50082*v12,
-8863847==-40760*v0-22014*v1+13608*v2-4946*v3-26750*v4-31708*v5+39603*v6+13602*v7-59055*v8-32738*v9+29341*v10+10305*v11-15650*v12,
-747805==-47499*v0+57856*v1+13477*v2-10219*v3-5032*v4-21039*v5-29607*v6+55241*v7-6065*v8+16047*v9-4554*v10-2262*v11+18903*v12,
-11379056==-65419*v0+17175*v1-9410*v2-22514*v3-52377*v4-9235*v5+53309*v6+47909*v7-59111*v8-41289*v9-24422*v10+41178*v11-23447*v12,
-166140==1805*v0+4135*v1-16900*v2+33381*v3+46767*v4+58551*v5-34118*v6-44920*v7-11933*v8-20530*v9+15699*v10-36597*v11+18231*v12,
9010363==-42941*v0+61056*v1-45169*v2+41284*v3-1722*v4-26423*v5+47052*v6+42363*v7+15033*v8+18975*v9+10788*v10-33319*v11+63680*v12,
-4169825==-37085*v0-51590*v1-17798*v2-10127*v3-52388*v4+12746*v5+12587*v6+58786*v7-8269*v8+22613*v9+30753*v10-20853*v11+32216*v12,
4081505==36650*v0+47566*v1-33282*v2-59180*v3+65196*v4+9228*v5-59599*v6-62888*v7+48719*v8+47348*v9-37592*v10+57612*v11+40510*v12,
1788229==51735*v0+35879*v1-63890*v2+4102*v3+59511*v4-21386*v5-20769*v6+26517*v7+28153*v8+25252*v9-43789*v10+25633*v11+7314*v12
],v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12)

次のとおり、解が得られます。

[[v0 == 77, v1 == 97, v2 == 116, v3 == 104, v4 == 32, v5 == 105, v6 == 115, v7 == 32, v8 == 104, v9 == 97, v10 == 114, v11 == 100, v12 == 33]]

実行ファイルを実行して、得られた解を入力するとフラグが表示されます。

$ ./baby-re
Var[0]: 77
Var[1]: 97
Var[2]: 116
Var[3]: 104
Var[4]: 32
Var[5]: 105
Var[6]: 115
Var[7]: 32
Var[8]: 104
Var[9]: 97
Var[10]: 114
Var[11]: 100
Var[12]: 33
The flag is: Math is hard!

フラグは、