Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Boston Key Party CTF 2015 Writeup -- Wellington (RE 250)

Author: xiaohuajiao

描述

1
2
3
4
5
6
7
8
Wellington
orange : 250

If you had the code, you\'d see that the program is calling

decrypt("[QeZag^VQZShWQgeWVQSe]ZW^^Q[`efWSV", X). 

Unfortunately, you don\'t have it, HAHAHAHAHAHA. Ho, and by the way, the flag ends with a dot.

这是个带有prolog解释器的64位ELF. 如描述所说,解密下面这段密文,就能拿到flag

1
[QeZag^VQZShWQgeWVQSe]ZW^^Q[`efWSV

解法

题目文件非常大,500+K。

信息收集

ida里发现了很多编译时候留下来的字符串,比如

1
2
3
4
5
.rodata:000000000046A3E7 00000029 C /home/diaz/GP/src/src/BipsPl/debugger.pl
.rodata:000000000046A41A 00000016 C All spypoints removed                   
.rodata:000000000046A430 0000000E C Alternatives:                           
.rodata:000000000046A43E 0000000B C Ancestors:                              
.rodata:000000000046A449 00000007 C Call:                                   

源码文件名被编译进来了,用到了gprolog (GNU Prolog) 的开源工具,其中有个gplc,能把prolog源码编译成一个可执行程序,所以这应该是把所有Prolog的运行环境都编译进来了,才能保证原来的prolog程序能够正常执行。

根据字符串,同样很容易就定位到了主逻辑初始化函数在403420这个位置,可是所有函数都被strip过,随便翻了几个函数看看,恩,还是想想其他办法吧。

特征识别

可以自己编译一个prolog程序,并且可以控制我们自己编译出来的这个程序是没有strip的,这样至少就能保留大部分prolog库中的符号信息,大大减少逆向的工作量和难度。

gplc 的 -v选项能输出编译时的详细信息,通过这些信息发现gcc编译时会把下面几个静态库链接到程序里来。

1
2
3
4
5
/usr/lib/gprolog-iso/libbips_fd.a 
/usr/lib/gprolog-iso/libengine_fd.a 
/usr/lib/gprolog-iso/libbips_pl.a 
/usr/lib/gprolog-iso/libengine_pl.a 
/usr/lib/gprolog-iso/liblinedit.a 

flair只能针对库文件生成相应的sig特征,所以前面的思路要稍微改动一下,对上面这5个静态库生成相应的特征,在ida里对程序应用这几个sig,发现自动帮助我们识别出了大量函数。

出题人源码编译出来的函数地址范围基本集中在402000~404000,搞了半天,看来还是得看看。

关键点

容易定位到verify函数,但是其中有几十行的if-else

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
int __usercall verify@<eax>(__int64 a1@<r12>)
{
  __int64 v1; // rbx@1
  signed __int64 v2; // rdi@1
  __int64 v3; // rax@1
  __int64 v4; // rax@3
  __int64 v5; // rax@5
  __int64 v6; // rax@7
  __int64 v7; // rax@9
  __int64 v8; // rax@11
  __int64 v9; // rax@13
  __int64 v10; // rax@15
  __int64 v11; // rax@17
  __int64 v12; // rax@19
  __int64 v13; // rax@21
  __int64 v14; // rax@23
  __int64 v15; // rax@25
  __int64 v16; // rax@27
  __int64 v17; // rax@29
  __int64 v18; // rax@31
  __int64 v19; // rax@33
  __int64 v20; // rax@35
  __int64 v21; // rax@37
  __int64 v22; // rax@39
  __int64 v23; // rax@41
  __int64 v24; // rax@43
  __int64 v25; // rax@45
  __int64 v26; // rax@47
  __int64 v27; // rax@49
  __int64 v28; // rax@51
  __int64 v29; // rax@53
  __int64 v30; // rax@55
  __int64 v31; // rax@57
  __int64 v32; // rax@59
  __int64 v33; // rax@61
  __int64 v34; // rax@63
  __int64 v35; // rax@65
  __int64 v36; // rax@67
  __int64 v37; // rax@68
  __int64 v38; // rax@69
  int result; // eax@69

  Load_Cut_Level((_QWORD *)(a1 + 8));
  Create_Choice_Point2((__int64)print_lose);
  Allocate(3LL);
  v1 = *(_QWORD *)(a1 + 2088);
  *(_QWORD *)(v1 - 32) = *(_QWORD *)a1;
  *(_QWORD *)(v1 - 40) = *(_QWORD *)(a1 + 8);
  *(_QWORD *)a1 = Put_List();
  v2 = 0x2DFLL;
  LODWORD(v3) = Unify_Integer_Tagged(0x2DFLL);
  if ( v3
    && Unify_List()
    && (v2 = 0x28FLL, LODWORD(v4) = Unify_Integer_Tagged(0x28FLL), v4)
    && Unify_List()
    && (v2 = 0x32FLL, LODWORD(v5) = Unify_Integer_Tagged(0x32FLL), v5)
    && Unify_List()
    && (v2 = 0x2D7LL, LODWORD(v6) = Unify_Integer_Tagged(0x2D7LL), v6)
    && Unify_List()
    && (v2 = 0x30FLL, LODWORD(v7) = Unify_Integer_Tagged(0x30FLL), v7)
    && Unify_List()
    && (v2 = 0x33FLL, LODWORD(v8) = Unify_Integer_Tagged(0x33FLL), v8)
    && Unify_List()
    && (v2 = 0x2F7LL, LODWORD(v9) = Unify_Integer_Tagged(0x2F7LL), v9)
    && Unify_List()
    && (v2 = 0x2B7LL, LODWORD(v10) = Unify_Integer_Tagged(0x2B7LL), v10)
    && Unify_List()
    && (v2 = 0x28FLL, LODWORD(v11) = Unify_Integer_Tagged(0x28FLL), v11)
    && Unify_List()
    && (v2 = 0x2D7LL, LODWORD(v12) = Unify_Integer_Tagged(0x2D7LL), v12)
    && Unify_List()
    && (v2 = 0x29FLL, LODWORD(v13) = Unify_Integer_Tagged(0x29FLL), v13)
    && Unify_List()
    && (v2 = 839LL, LODWORD(v14) = Unify_Integer_Tagged(839LL), v14)
    && Unify_List()
    && (v2 = 703LL, LODWORD(v15) = Unify_Integer_Tagged(703LL), v15)
    && Unify_List()
    && (v2 = 655LL, LODWORD(v16) = Unify_Integer_Tagged(655LL), v16)
    && Unify_List()
    && (v2 = 831LL, LODWORD(v17) = Unify_Integer_Tagged(831LL), v17)
    && Unify_List()
    && (v2 = 815LL, LODWORD(v18) = Unify_Integer_Tagged(815LL), v18)
    && Unify_List()
    && (v2 = 703LL, LODWORD(v19) = Unify_Integer_Tagged(703LL), v19)
    && Unify_List()
    && (v2 = 695LL, LODWORD(v20) = Unify_Integer_Tagged(695LL), v20)
    && Unify_List()
    && (v2 = 655LL, LODWORD(v21) = Unify_Integer_Tagged(655LL), v21)
    && Unify_List()
    && (v2 = 671LL, LODWORD(v22) = Unify_Integer_Tagged(671LL), v22)
    && Unify_List()
    && (v2 = 815LL, LODWORD(v23) = Unify_Integer_Tagged(815LL), v23)
    && Unify_List()
    && (v2 = 751LL, LODWORD(v24) = Unify_Integer_Tagged(751LL), v24)
    && Unify_List()
    && (v2 = 727LL, LODWORD(v25) = Unify_Integer_Tagged(727LL), v25)
    && Unify_List()
    && (v2 = 703LL, LODWORD(v26) = Unify_Integer_Tagged(703LL), v26)
    && Unify_List()
    && (v2 = 759LL, LODWORD(v27) = Unify_Integer_Tagged(759LL), v27)
    && Unify_List()
    && (v2 = 759LL, LODWORD(v28) = Unify_Integer_Tagged(759LL), v28)
    && Unify_List()
    && (v2 = 655LL, LODWORD(v29) = Unify_Integer_Tagged(655LL), v29)
    && Unify_List()
    && (v2 = 735LL, LODWORD(v30) = Unify_Integer_Tagged(735LL), v30)
    && Unify_List()
    && (v2 = 775LL, LODWORD(v31) = Unify_Integer_Tagged(775LL), v31)
    && Unify_List()
    && (v2 = 815LL, LODWORD(v32) = Unify_Integer_Tagged(815LL), v32)
    && Unify_List()
    && (v2 = 823LL, LODWORD(v33) = Unify_Integer_Tagged(823LL), v33)
    && Unify_List()
    && (v2 = 703LL, LODWORD(v34) = Unify_Integer_Tagged(703LL), v34)
    && Unify_List()
    && (v2 = 671LL, LODWORD(v35) = Unify_Integer_Tagged(671LL), v35)
    && Unify_List()
    && (v2 = 695LL, LODWORD(v36) = Unify_Integer_Tagged(695LL), v36)
    && (LODWORD(v37) = Unify_Nil(695LL), v37) )
  {
    LODWORD(v38) = Put_Y_Variable(v1 - 48);
    *(_QWORD *)(a1 + 8) = v38;
    *(_QWORD *)(a1 + 2080) = jump_win;
    result = decrypt(a1);
  }
  else
  {
    result = (*(int (__fastcall **)(signed __int64))(*(_QWORD *)(a1 + 2056) - 8LL))(v2);
  }
  return result;
}

其实最后肯定会进到if里,因为所有&&连接起来的条件都是真,随后就是decrypt。 可惜再往后就超出理解的能力范围了,各种跟进也没看出个名堂。

无意中随意点进了函数Unify_Integer发现了其中整数的编码方式

1
2
3
4
5
Unify_Integer   
.text:0000000000460BD0            shl     rdi, 3
.text:0000000000460BD4            or      rdi, 7
.text:0000000000460BD8            jmp   Unify_Integer_Tagged
.text:0000000000460BD8            Unify_Integer   endp

整数左移了3个bit,然后或上了7.

这也就解释了为什么verify里那几十行的&&条件中,整数的十六进制表示都是F7结尾。

回去试着翻译了一下verify中的整数常数,发现正好是要decrypt的这串字符

1
[QeZag^VQZShWQgeWVQSe]ZW^^Q[`efWSV

所以这里仅仅是在做初始化字符串而已

跟进decrypt,发现在402cd1的有个加常量的加法操作

1
2
3
Math_Fast_Load_Value(*(_QWORD **)(a1 + 16), (_QWORD *)(a1 + 16));
  *(_QWORD *)(a1 + 32) = Put_Integer_Tagged(0x77LL);
  LODWORD(v3) = Fct_Fast_Add(*(_QWORD *)(a1 + 16), *(_QWORD *)(a1 + 32));

这里(0x77 & 0xf8) >> 3 == 14,所以应该是做了一个+14的运算。

试着解密,发现真就翻译出了一串flag

1
2
3
4
def dec(s):
    print ''.join(map(chr, map(lambda x: x+14, map(ord, s))))
dec("[QeZag^VQZShWQgeWVQSe]ZW^^Q[`efWSV")
## output: i_should_have_used_askhell_instead

flag 就是i_should_have_used_askhell_instead

Tricky的解法

比赛结束后,IRC上有人放出了他用ltrace的解法

1
echo -e "X.\n" | ltrace -s 64 ./troll_log 2> foo3.txt && tail foo3.txt

RTFM.

Acknowledgements

感谢RomanGolhen在解题过程中的讨论和帮助。

Appendix

源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
decrypt([], []) :- !.
decrypt([X|Y], [X1|Y1]):- X1 is X + 14, decrypt(Y, Y1).

verify(X) :-
  decrypt("[QeZag^VQZShWQgeWVQSe]ZW^^Q[`efWSV", D),
  atom_codes(X, D),
  !,
  write('WiN'), nl.

verify(_) :- write('LOSE'), nl.

main :-
  write('BKP 2015 - Troll_log'), nl,
  write('Password: '),
  read(X),
  verify(X),
  halt.

:- initialization(main).

Reference

WAM instruction set prolog dictionary