解码小实验

Oct. 18th, 2016


汇编 栈布局

今天系统级程序设计实验课上布置了这么一个实验,要求通过对函数运行时堆栈的分析解码一段信息,蛮有意思,头一次做这种分析。原问题在这里, 我再简要地重复一下。

问题重述

给出了一串以十六进制表示的字符,且给出了解码这段字符的程序,但是发现程序运行需要四个参数 key1-key4,已知解码出来的前五个字符为From:,要求通过求出四个参数的值,解码出完整的信息。另外要求先求出key1和key2,会得到提示信息,再求解key3和key4。

求解key1key2

首先将程序的主函数main中所有有关key3key4的语句都忽略掉,可以更清楚地看到程序的作用:

int main (int argc, char *argv[]) {
    int dummy = 1;
    int start, stride;
    int key1, key2;
    char * msg1;
    key1 = strtol(argv[1], NULL, 0);
    key2 = strtol(argv[2], NULL, 0);
    process_keys12(&key1, &key2);
    start = (int)(*(((char *) &dummy)));
    stride = (int)(*(((char *) &dummy) + 1));
    msg1 = extract_message1(start, stride);
    printf("%s\n", msg1);
}

可以看出,变量startstride是解码的关键,而这两个值又与dummy有关,如果将dummy看作是长度为4的字符数组,那么start为数组的第0个元素,stride为数组的第1个元素。对于初始的dummy=0x 00 00 00 01,如果程序运行的机器为小端字节序,那么这个数组可以看做是[0x01,0x00,0x00,0x00] (如果是大端序则正好反过来)。此时有start=1stride=0,接下来进入函数extract_message1(),我们期望这个函数能够解码出正确的信息,并保存到字符串msg1里。

char * extract_message1(int start, int stride) {
    int i, j, k;
    int done = 0;
    for (i = 0, j = start + 1; ! done; j++) {
        for (k = 1; k < stride; k++, j++, i++) {
            if (*(((char *) data) + j) == '\0') {
                done = 1;
                break;
            }        
            message[i] = *(((char *) data) + j);
        }
    }
    message[i] = '\0';
    return message;
}

将相应的两个参数带入会发现,内层循环永远不会执行,函数陷入死循环。我们需要做的就是正确的选择两个参数的值,来使函数能够正确处理data数组里的字符,从而得到正确的字符串。

我们已经知道,解码出的前五个字符是From:,通过查ASCII码表,得到这五个字符的十六进制表示为[0x46,0x72,0x6f,0x6d,0x3a]。这里同样把data看做一个字节数组,因此也受到机器字节序的影响,这里使用小端序来分析。

进一步分析这个函数,两层循环表示从第start+1个字节开始,连续地取出stride-1个字节后隔过去一个字节,再连续取出stride-1个字节,直到取到字节0x00,函数返回。

根据已知的字符,我们开始到data中寻找合理的startstride值,方便起见,这里直接将data表示成字符数组的形式。

data [] = {
    63 63 63 63, 63 63 63 63, 63 46 46 72, 72 6F 6D 6F,
        3A 02 6D 46, 72 3A 69 65, 20 6E 64 43, 0A 54 54 6F,
        ...
};

可以发现,0x46所在的位置索引为9,10,19(省略部分不存在合理的索引),这些是可能的起始索引。接下来依次分析这三个索引:

对于索引9,字符0x72在索引11,那么说明连续取出一个字节后就隔过去一个字节,那么再取出的字符为0x6f0x6f,第四个字符出错,该索引错误。

对于索引10,取索引1011的字符0x72均合理,假设先取索引10的该字符,那么下一个字符0x6f在索引12,说明连续取出两个字节后就隔过去一个字节,依照这个规则,接下来取出0x6d0x3a,满足前五个字符的要求,该索引正确。

对于索引10的另一种情况和索引19,可以用类似的方法证明不可行。

因此我们发现从第10个字节开始取,连续取2个字节可以满足要求,也就是说

start = 9; stride = 3;

再回过头看main函数,思路就很清晰了,我们需要更改dummy的值为0x ?? ?? 03 09,其中?表示的值可以任取,不影响最终结果。但是dummy在前面已经赋值过了,怎么修改呢?一个直接的想法就是通过processkeys_12来修改。接下来分析函数process_keys12:

void process_keys12 (int * key1, int * key2) {
    *((int *) (key1 + *key1)) = *key2;
}

这个函数将地址为key1 + *key1处的值变成了*key2的值(注意这里的key1key2是地址),我们希望将dummy所在的位置的值改为777(假设高位全为0)。

通过阅读程序产生的汇编代码(32位机器上,64位机器可以用命令gcc -m32 -S *.cpp来产生相应32位的*.s汇编代码),发现运行到调用该函数的指令call前的一条指令时,栈的布局如下图左所示:

可以看到,dummykey1地址多了4,但是由于指针在加减时会自动根据所指向的类型进行扩展(比如对于int型指针,指针加1相当于其值加4),所以上面函数中*key1=1, *key2=777,也就是输入的参数

key1=1    key2=777

我们将这两个参数带入程序中运行得到如下消息:

From: Friend
To: You
Good! Now try choosing keys3,4 to force a call to extract2 and avoid the call to extract1

求解key3key4

根据上面的提示,我们需要避免调用函数extract_message1,而是调用下面main函数里的if语句中的extract_message2。然而extract_message1并不是条件分支,如果程序顺序执行,一定会执行到这条语句,也就是说函数process_key34更改了执行顺序,直接跳转到下面的if语句里执行了。

int main (int argc, char *argv[])
{
    ...
    if (key3 != 0 && key4 != 0) {
        process_keys34(&key3, &key4);
    }
    msg1 = extract_message1(start, stride);
    if (*msg1 == '\0') {
        process_keys34(&key3, &key4);
        msg2 = extract_message2(start, stride);
        printf("%s\n", msg2);
    }
    else {
        printf("%s\n", msg1);
    }
}

具体来说,就是将第一个process_keys34返回后的下一条指令的起始地址(PC值)更改为第二个process_keys34返回后的下一条指令的起始地址。

使用objdump反汇编,可以得到如下的汇编代码:

27d:   e8 cd fd ff ff      call   4f <__Z14process_keys34PiS_>
282:   8b 44 24 38         mov    0x38(%esp),%eax
...
2bd:   89 04 24            mov    %eax,(%esp)
2c0:   e8 8a fd ff ff      call   4f <__Z14process_keys34PiS_>
2c5:   8b 44 24 38         mov    0x38(%esp),%eax
...

也就是将0x282改为0x2c5,增加了67。(不同机器,不同编译器该值差别较大) 接下来就考虑如何更改这个值了,对process_keys34进行分析:

void process_keys34 (int * key3, int * key4) {
    *(((int *)&key3) + *key3) += *key4;
}

这个函数将&key3 + *key3地址处的值增加了*key4的值,它在执行时的栈布局如上图右所示(还是要注意这里的key3key4是地址),我们需要将返回地址处的值增加67,而返回地址处的地址恰好比key3的地址少4,考虑到指针的类型扩展,*key3=-1,而*key4=67,对应到输入的参数上,即:

key3=-1;    key4=67;

将这四个参数均代入程序中,得到最终结果:

From: CTE
To: You
Excellent!You got everything!

小结

需要注意的是,这些值与机器有着很大的关系,包括32位或64位,大端字节序或小端字节序,以及使用的系统和编译的环境,所以还是要从栈的分析入手,以应对不同机器的变化。