SSD06 Exercise01 个人解答

题目 写道

Understanding a Secret Message

You have just intercepted an encoded message. The message is a sequence of bits which reads as follows in hexadecimal:

6363636363636363724646636F6D6F72
466D203A65693A7243646E206F54540A
5920453A54756F0A6F6F470A21643A6F
594E2020206F776F797275744563200A
6F786F686E6963736C206765796C656B
2C3365737420346E20216F74726F5966
7565636F202061206C61676374206C6F
20206F74747865656561727632727463
6E617920680A64746F69766120646E69
21687467630020656C6C786178742078
6578206F727478787863617800783174

You have no idea how to decode it, but you know that your grade depends on it, so you are willing to do anything to extract the message. Fortunately, one of your many agents on the field has stolen the source code for the decoder. This agent (007) has put the code and the message in the file secret.cpp , which you can download from the laboratory of your technical staff (Q).

Q has noticed that the decoder takes four integers as arguments. Executing the decoder with various arguments seems to either crash the program or produce unintelligible output. It seems that the correct four integers have to be chosen in order for the program to produce the decoded message. These four integers are the "secret keys."

007 has been unable to find the keys, but from the desk of the encrypting personnel he was able to cunningly retrieve the first five characters of the unencoded message. These characters are:

From:

Assignment
Your assignment is to decode the message, and find the keys.
Reminders
This exercise is not extremely difficult. However, the strategy of trying things until something works will be ineffective. Try to understand the material in the course, particularly the following:

* Memory contains nothing but bits. Bits are interpreted as integers, characters, or instructions by the compiler, but they have no intrinsic type in memory.
* The compiler can be strong-armed into interpreting integers as characters, or even as instructions, and vice versa.
* Every group of 8 bits (a byte) has an address.
* A pointer in C is merely a stored memory address.
* The activation records for each function call are all together in memory, and they are organized in a stack that grows downwards and shrinks upwards on function calls and returns respectively.
* The return address of one function as well as the addresses of all of its local variables are allocated within one activation record.

Strategy
The designers of this decoder weren't very good. They made it possible for us to attack the keys in two independent parts. Try to break the first two keys first, and do not try to break the third and fourth keys until you have succeeded with the first two.

You can do the first part by specifying only two integer arguments when you execute the decoder. If you get the first and second keys right, a message that starts with From: will appear. This message is not the true message, but a decoy. It is useful, however, to let you know that you have indeed broken the first two keys.

In breaking the first two keys, realize that the function process_keys12 must be somehow changing the value of the dummy variable. This must be so, because the variables start and stride control the extraction of the message, and they are calculated from the value of dummy.

In breaking the third and fourth keys, try to get the code to invoke extract_message2 instead of extract_message1. This modification must somehow be controlled from within the function process_keys34.
Files

When you are done, write a brief report that includes at least the following:

1. The secret message.
2. The secret keys.
3. One paragraph describing, in your own prose, what process_keys12 does. For example, you might say that it modifies a specific program variable.
4. The meaning of the first two keys in terms of variables and addresses in the decoder program. For example, you might describe key2 by saying that its X-Y bits contain the value to which variable start is set. Or you might describe key1 by saying, for example, that it must be set equal to the number of memory addresses separating the address of two specific variables. These are only examples.
5. One paragraph describing, in your own prose, what process_keys34 does.
6. One paragraph describing the line of source code that is executed when the first call to process_keys34 returns.
7. The meaning of the third and fourth keys in terms of variables and addresses in the decoder program.

Be precise, clear, and brief in each of the points above. Your report should not, in any case, be longer than one page. Do not get frustrated if this takes a little longer than you expected: brief and clear text often requires more time to write than rambling prose.

Your teacher can tell you what word processors you may use to write your report. Chances are that you can write your report in a number of formats, and for simplicity's sake, you might even want to write it using Notepad.

 以下是我的具体解答：

注意 写道

这个解答主要是提供思路。由于整个程序的内存分配、指令相对位置等与实际的编译器有关，
并没有一个万全的解决方法。

 

我的系统环境 写道

Ubuntu 8.04
NetBeans 6.1
Using built-in specs.
Target: i486-linux-gnu
Configured with: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --with-gxx-include-dir=/usr/include/c++/4.2 --program-suffix=-4.2 --enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc --enable-mpfr --enable-targets=all --enable-checking=release --build=i486-linux-gnu --host=i486-linux-gnu --target=i486-linux-gnu
Thread model: posix
gcc version 4.2.4 (Ubuntu 4.2.4-1ubuntu3)

 

<1> The secret message.

 

最终结果 写道

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

 

<2> The secret keys.

密码 写道

key1 = 3
key2 = 777
key3 = -1
key4 = 49

<3>后面的几个问题，我就放在一起说明：

首先，我先贴出程序源代码：

#include <stdio.h>
#include <stdlib.h>

int prologue [] = {
	0x5920453A, 0x54756F0A, 0x6F6F470A, 0x21643A6F,
	0x6E617920, 0x680A6474, 0x6F697661, 0x20646E69,
	0x63636363, 0x63636363, 0x72464663, 0x6F6D6F72,
	0x63636363, 0x63636363, 0x72464663, 0x6F6D6F72,
	0x2C336573, 0x7420346E, 0x20216F74, 0x726F5966,
	0x7565636F, 0x20206120, 0x6C616763, 0x74206C6F,
	0x20206F74, 0x74786565, 0x65617276, 0x32727463,
	0x594E2020, 0x206F776F, 0x79727574, 0x4563200A
};

int data [] = {
	0x63636363, 0x63636363, 0x72464663, 0x6F6D6F72,
      	0x466D203A, 0x65693A72, 0x43646E20, 0x6F54540A,
      	0x5920453A, 0x54756F0A, 0x6F6F470A, 0x21643A6F,
      	0x594E2020, 0x206F776F, 0x79727574, 0x4563200A,
      	0x6F786F68, 0x6E696373, 0x6C206765, 0x796C656B,
      	0x2C336573, 0x7420346E, 0x20216F74, 0x726F5966,
      	0x7565636F, 0x20206120, 0x6C616763, 0x74206C6F,
      	0x20206F74, 0x74786565, 0x65617276, 0x32727463,
      	0x6E617920, 0x680A6474, 0x6F697661, 0x20646E69,
      	0x21687467, 0x63002065, 0x6C6C7861, 0x78742078,
      	0x6578206F, 0x72747878, 0x78636178, 0x00783174
};

int epilogue [] = {
	0x594E2020, 0x206F776F, 0x79727574, 0x4563200A,
	0x6E617920, 0x680A6474, 0x6F697661, 0x20646E69,
	0x7565636F, 0x20206120, 0x6C616763, 0x74206C6F,
	0x2C336573, 0x7420346E, 0x20216F74, 0x726F5966,
	0x20206F74, 0x74786565, 0x65617276, 0x32727463
};

char message[100];

void usage_and_exit(char * program_name) {
	fprintf(stderr, "USAGE: %s key1 key2 key3 key4\n", program_name);
	exit(1);
}

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

void process_keys34 (int * key3, int * key4) {

	*(((int *)&key3) + *key3) += *key4;
}

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;
}


char * extract_message2(int start, int stride) {
	int i, j;

	for (i = 0, j = start; 
		 *(((char *) data) + j) != '\0';
		 i++, j += stride) 
		 {
			 message[i] = *(((char *) data) + j);
		 }
	message[i] = '\0';
	return message;
}

int main (int argc, char *argv[])
{
	int dummy = 1;
	int start, stride;
	int key1, key2, key3, key4;
	char * msg1, * msg2;

	key3 = key4 = 0;
	if (argc < 3) {
		usage_and_exit(argv[0]);
	}
	key1 = strtol(argv[1], NULL, 0);
	key2 = strtol(argv[2], NULL, 0);
	if (argc > 3) key3 = strtol(argv[3], NULL, 0);
	if (argc > 4) key4 = strtol(argv[4], NULL, 0);

	process_keys12(&key1, &key2);

	start = (int)(*(((char *) &dummy)));
	stride = (int)(*(((char *) &dummy) + 1));

	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);
	}

	return 0;
}

从代码中，我们容易发现：程序的 message1的输出结果和位置由 start、 stride决定。但是我们又发现这俩个的赋值仅仅和 dummy变量有关，那么我们就需要通过处理 key1、 key2的时候去尝试修改 dummy的值。这个 process_keys12的作用就是通过相对定位来修改 dummy的值。

 

我们可以看到在主要是通过引用 key1的地址来相对定位 dummy的值，

 

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

然后用 key2的值来赋给 dummy。而 key1的位置和 dummy的位置相对距离是固定的，我们只需要通过 debug找出 key1和 dummy的距离（这个距离就是通过 *key1来赋值的）即可 。那么首先我们来确定 key1的值，从下图 中我们可以看到这两个变量的绝对地址，当然这个绝对地址是会随程序启动的实际情况而变化的。但是两者这间的距离由编译器决定是不会变化的。

key1=(0xbfa459f0 -0xbfa459e4)/4 =12/4=3

 

现在我们来确定 key2的值，这个值主要是来定位 data中间的合适位置的。这个在通常状况下，我们是需要认真分析 data的数据值和数据值之间的关系，除此之外我们还需要关心 extract_message1的细节。我这里就用了一个偷懒的办法：

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int data [] = {
    0x63636363, 0x63636363, 0x72464663, 0x6F6D6F72, 0x466D203A, 0x65693A72, 0x43646E20, 0x6F54540A,0x5920453A, 0x54756F0A, 0x6F6F470A, 0x21643A6F, 0x594E2020, 0x206F776F, 0x79727574, 0x4563200A,    0x6F786F68, 0x6E696373, 0x6C206765, 0x796C656B,    0x2C336573, 0x7420346E, 0x20216F74, 0x726F5966,    0x7565636F, 0x20206120, 0x6C616763, 0x74206C6F,
    0x20206F74, 0x74786565, 0x65617276, 0x32727463,    0x6E617920, 0x680A6474, 0x6F697661, 0x20646E69,    0x21687467, 0x63002065, 0x6C6C7861, 0x78742078,    0x6578206F, 0x72747878, 0x78636178, 0x00783174};
char message[100];
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;
}
int main(int argc, char** argv) {
    int dummy = 1;   int start, stride;
    for (dummy = 700; dummy < 800; dummy++) {
        start = (int) (*(((char *) & dummy)));
        stride = (int) (*(((char *) & dummy) + 1));
        char* msg1 = extract_message1(start, stride);
        if(strstr(msg1,"From"))printf("%d:\n%s\n",dummy,msg1);
    }
    return (EXIT_SUCCESS);
}
//搜索key2值

循环穷举出结果，从下面的输出结果中，我们便可以断定是 777了。

 

探测代码的输出结果 写道

768:
ccccccFrom: Friend
To: You
Good! Now try choosing keys3,4 to force a call to extract2 and
avoid the call to extract1
771:
ccccFrom: Friend
To: You
Good! Now try choosing keys3,4 to force a call to extract2 and
avoid the call to extract1
774:
ccFrom: Friend
To: You
Good! Now try choosing keys3,4 to force a call to extract2 and
avoid the call to extract1
777:
From: Friend
To: You
Good! Now try choosing keys3,4 to force a call to extract2 and
avoid the call to extract1

通过上面的分析我们便可以得到 key1=3, key2=777 了。

我们继续往后面看代码，并且通过提示我们了解到我们需要想办法使程序进入并执行 msg2 = extract_message2(start, stride);

但是从正常的程序逻辑上看，我们无法使 msg1为空而顺利进入到条件码中。那么我们需要考虑应该在 process_keys34中做出调整。我们能否在执行完 process_keys34后偷偷的改变 msg1的值呢？在看了这段函数的代码后，我们发现这个函数中两个变量的范围相差太大了，一个是全局变量 message（ msg1的实际指向），一个是局部变量 key3。那么我们需要换一个思路，能否让函数在返回的时候直接跳转到目标代码呢？如果要这么做，我们就需要修改程序在运行过程中的栈帧结构中的存储数据了。现在让我们来分析一下程序在调用 process_keys34之前的栈帧结构：

从汇编码中我们可以看到在调用之前整个栈帧结构中数据的存储细节。首先是将参数 key3、 key4压入栈中保存，然后在传入这些参数。然而这些参数的传递都是传地址的，所以我们在 process_keys34中可以通过 &key3的相对定位来改动调用者的栈帧数据。

在这之前让我们来想想调用时的栈帧结构：
 

我们可以看到，如果我们能够修改返回地址使它返回到我们期望的位置就可以了。那么我们现在需要确定这个返回地址相对于 key3的距离是多少，通过图我们可以看到这个地址就在 key3的下面，只需要在 key3基础上减一（这个减一是在 int下的，实际上在地址层面应该是 -4）就好了。所以我们得到了 key3的值 -1.

另外我们需要感谢出题者，他一直给我们提供充足的相对数据。在这里我们只需要在原返回地址上面加上一个合适的值就好了。

从上图 中，我们可以看到原先的返回地址和我们需要抵达的返回地址。 main+309 是原先保存在栈帧中的返回地址，而我们期望程序返回时直接到达 main+358 。这样我们就得到了 key4 的具体值：

358-309=49.

最后我们得到了 key3=-1,key4=49 .

 

 

 

 

 

评论

9 楼 crackcell 2008-11-20  

挺有启发的，看了你的，我才发现我做的时候走了弯路。

8 楼 qianjigui 2008-11-17  

  Feedback for Decoding Lab (v1.0)
Total Score: 100/100
Good work. Solution is correct.

7 楼 linuxyeshiquan 2008-10-24  

多谢，问题已解决。

6 楼 qianjigui 2008-10-24  

linuxyeshiquan 写道

还有一个地方：你是怎么知道返回地址就在key3的下面，这个返回地址是不是存在一个寄存器里面，我们可以随时查看一个函数的返回地址吗？

这个是由c语言的数据存储组织结构决定的，你可以学习一下《深入理解计算机》的第三章144面的图3.17,上面有描述。祝你好运！

5 楼 linuxyeshiquan 2008-10-24  

还有一个地方：你是怎么知道返回地址就在key3的下面，这个返回地址是不是存在一个寄存器里面，我们可以随时查看一个函数的返回地址吗？

4 楼 linuxyeshiquan 2008-10-24  

原来如此，讲的很明白。

3 楼 qianjigui 2008-10-24  

linuxyeshiquan 写道

写的太好了，看后换然大悟。还有2个地方没看懂,楼主能不能解释一下汇编代码的main+309表示什么意思,用358-309=49就得到key4的值实在是神奇。

其实在汇编代码里面是有一些0x......的定位代码的，这个main+309等数据是由netbean给出的协助调试用的相对代码。你可以反汇编执行文件看具体地址。

引用

80487b8: e8 81 fd ff ff       call   804853e <_Z14process_keys34PiS_>
80487bd: 8b 45 f0             mov    -0x10(%ebp),%eax
80487c0: 89 44 24 04          mov    %eax,0x4(%esp)
80487c4: 8b 45 f4             mov    -0xc(%ebp),%eax
80487c7: 89 04 24             mov    %eax,(%esp)
80487ca: e8 9d fd ff ff       call   804856c <_Z16extract_message1ii>
80487cf: 89 45 dc             mov    %eax,-0x24(%ebp)
80487d2: 8b 45 dc             mov    -0x24(%ebp),%eax
80487d5: 0f b6 00             movzbl (%eax),%eax
80487d8: 84 c0                test   %al,%al
80487da: 75 34                jne    8048810 <main+0x188>
80487dc: 8d 45 e0             lea    -0x20(%ebp),%eax
80487df: 89 44 24 04          mov    %eax,0x4(%esp)
80487e3: 8d 45 e4             lea    -0x1c(%ebp),%eax
80487e6: 89 04 24             mov    %eax,(%esp)
80487e9: e8 50 fd ff ff       call   804853e <_Z14process_keys34PiS_>
80487ee: 8b 45 f0             mov    -0x10(%ebp),%eax
80487f1: 89 44 24 04          mov    %eax,0x4(%esp)
80487f5: 8b 45 f4             mov    -0xc(%ebp),%eax
80487f8: 89 04 24             mov    %eax,(%esp)
80487fb: e8 fa fd ff ff       call   80485fa <_Z16extract_message2ii>

0x80487fb-0x80487ca=0x31=49

2 楼 linuxyeshiquan 2008-10-24  

写的太好了，看后换然大悟。还有2个地方没看懂,楼主能不能解释一下汇编代码的
main+309表示什么意思,用358-309=49就得到key4的值实在是神奇。

1 楼 qianjigui 2008-10-23  

总体上说，整个题目主要是考察我们对程序在内存中的位置关系以及变量、代码的存储方式。
了解程序的栈帧结构对解题是有好处的。