这道题目是去年ISG初赛的一道ARM逆向题，当时的知识储备还不足以解决。但其实稍微了解了下ARM汇编之后就可以做了，虽然说还不熟练，花了较久时间。
我是开始想用IDA的反编译的，但不知怎么回事，对thumb代码的处理总有问题；继而无奈用hopper，然而hopper得到的伪代码还是比较简陋的，而且发现居然会把本应是*ptr+=1这样的反编译为*ptr=1，这个错误太大了……于是最后基本还是通过读汇编代码，理解分析后得到伪代码如下
struct sNode {
char value;
struct sNode *left;
struct sNode *right;
};
typedef struct sNode Node;
struct sInfo {
Node *node;
int height;
int value2;
}
typedef struct sInfo Info;
int record[128]; //record=0x11258
int index; //&index=0x116f8
int infoCount; //&infoCount=0x116fc
Info *infoStack[]; //infoStack=0x11058
function setup { //sub_8610
memset(0x11058, 0x0, 0x200);
}
function buildTree(char *str, Node **nodeAddr) { //sub_86d4
char ch; //&ch=r7+0xf
ch = str[index];
if(ch == 0)
return;
index++;
if(ch == ' ')
return;
Node *newNode = malloc(sizeof(Node));
*nodeAddr = newNode;
newNode->value = ch;
buildTree(str, &(newNode->left));
buildTree(str, &(newNode->right));
return;
}
function push(Info *info) { //sub_8634
if (infoCount <= 0x7e) {
infoStack[infoCount++] = info;
}
return;
}
function pop { //sub_867c
if (infoCount > 0) {
return infoStack[--infoCount];
}
else
return NULL;
}
function traverse(Node *node) { //sub_8790
push(NULL);
Node *current = node; //*current=r7+8
int height = 0; //&height=r7+0xc
int someVal = 0; //&someVal=r7+0x10
Info *info; //*info = r7+0x14
while(current != NULL) {
if(record[current->value] != 0) {
record[current->value] = someVal;
}
if(current->right != NULL) {
info = malloc(sizeof(Info));
info->node = current->right;
info->height = height + 1;
info->value2 = 49*(height+1) + someVal;
push(info);
}
if(current->left != NULL) {
height++;
someVal += 48*height;
current = current->left;
}
else {
info = pop();
if(info != NULL) {
current = info->node;
height = info->height;
someVal = info->value2;
free(info);
}
else
current = NULL;
}
}
return;
}
function check(char *str, size_t len) {
int buf[0xa0/4]; //buf=r7+0x10
int i = 0; //&i=r7+0xc
memset(buf, 0x0, 0xa0);
while (i < len) {
buf[i] = record[str[i]];
i++;
}
doCheck(buf, len);
}
function doCheck(int *buf, size_t len) {
if(len == 0x22 && buf == {0xc6b, 0xa59, 0x2d9, 0x30, 0x1e7, 0xc75,
0x881, 0xa5a, 0x169d, 0x111c, 0x870, 0x546,
0x169d, 0x6c8, 0x90, 0x870, 0x1129, 0x3f6,
0x13be, 0xeab, 0x31, 0x169d, 0x2d4, 0x13cb,
0x1990, 0x870, 0xc75, 0x2d4, 0x870, 0x1110,
0x6cf, 0x2d0, 0x3f0, !0x125})
puts("correct");
else
puts("wrong");
}
function destroyTree (Node *node){
if (node != NULL) {
destroyTree(node->left);
destroyTree(node->right);
free(node);
}
return;
}
function main { //sub_88d4
Node *node; //&node=r7;
char buf[40]; //buf=r7+0xc
setup();
printf("Password:");
fgets(buf, 0x28, stdin);
size_t len = strlen(buf); //&len = r7+8
len--;
buf[len] = 0; //'\n' => '\0'
int i = 0; //&i = r7+4
while (i < len) {
record[buf[i]] = 1;
i++ ;
}
char *string = "g{3q9OLNZ_bVWCyJk l sh c ax r d6 A MY t Iv P 4u i TS Q eB n Xz o R7 H U2 p F5 G Km 8 Dw } Ej f "; //string = 0x8c10
buildTree(string, &node);
traverse(node);
check(buf, len);
destroyTree(node);
return 0;
}可以看到，首先通过一个给定的字符串构造了一个二叉树，字符串中的连续两个空格就使左右子树均为空；然后进行深度优先搜索，对每个节点的字符计算了一个数；最后由前面生成的对应，检查输入字符串的每个字符。
为了找到正确的输入，我是依照树的构造方式和DFS，先找到每个字符对应的值，然后反过来查输入的各个字符应该为什么。
下面是我的python代码，二叉树构造那里写的很别扭……
#!/usr/bin/env python2
class Node(object):
value, left, right = 0, None, None
def __init__(self, v):
self.value = v
class Tree(object):
def __init__(self, string):
self.string = string
self.root = None
self.index = 0
self.height = 0
self.someVal = 0
self.stack = []
self.record = {}
def addNode(self):
ch = self.string[self.index]
self.index += 1
if ch == " ":
return None
else:
return Node(ch)
def build(self, root):
if root == None or self.index>=len(self.string):
return None
node = self.addNode()
root.left = self.build(node)
node = self.addNode()
root.right = self.build(node)
return root
def traverse(self, node):
current = node
while not current == None:
#print "%s:%s" % (current.value, hex(self.someVal))
self.record[self.someVal] = current.value
if not current.right == None:
self.stack.append((current.right, self.height+1, 49*(self.height+1)+self.someVal))
if not current.left == None:
self.height += 1
self.someVal += 48*self.height
current = current.left
else:
try:
info = self.stack.pop(-1)
current = info[0]
self.height = info[1]
self.someVal = info[2]
except IndexError:
current = None
if __name__ == "__main__":
string = "g{3q9OLNZ_bVWCyJk l sh c ax r d6 A MY t Iv P 4u i TS Q eB n Xz o R7 H U2 p F5 G Km 8 Dw } Ej f "
tree = Tree(string)
root = tree.build(tree.addNode())
tree.traverse(root)
res = []
code = (0xc6b, 0xa59, 0x2d9, 0x30, 0x1e7, 0xc75,0x881, 0xa5a, 0x169d, 0x111c, 0x870, 0x546, 0x169d, 0x6c8, 0x90, 0x870, 0x1129, 0x3f6, 0x13be, 0xeab, 0x31, 0x169d, 0x2d4, 0x13cb, 0x1990, 0x870, 0xc75, 0x2d4, 0x870, 0x1110, 0x6cf, 0x2d0, 0x3f0)
for x in code:
res.append(tree.record[x])
print ''.join(res)运行得到除最后一个字符外，输入应该为ISG{8in4rY_7re3_tRavEr5Al_i5_CoOL。虽然检查时只要求最后一个字符对应的数不是0x125，但我们显然知道应该是右花括号}