从做题到出题再到做题三部曲-RC4

xuenixiang

前言　　总感觉自己半吊子出家，尤其是遇到算法的问题，总是会磨蹭很久，哪怕拿到key和enc也总要花费很多时间在解这种公开算法上面，不希望以后也应该杜绝此类事情的发生，再加上自己也遇到过不少考察算法的题目了，因此想更深层的了解各种算法它的数据到底是如何流动的，也就有了这一系列的文章。

　　第一篇就拿比较简单的RC4算法来进行学习，

原理介绍

　　相关的原理网上有很多，不过为了文章的完整性，还是在此说明一二。

　　在密码学中，RC4（来自Rivest Cipher 4的缩写）是一种流加密算法，密钥长度可变。它加解密使用相同的密钥，因此也属于对称加密算法。RC4是有线等效加密（WEP）中采用的加密算法，也曾经是TLS可采用的算法之一。
　　RC4算法的原理非常简单，包括初始化算法（KSA）和伪随机子密码生成算法（PRGA)两大部分。
　　一.初始化算法：
[pre]1. 1-256初始化S-Box
2. 依据用户输入的秘钥产生临时数组K
3. 根据K将S-Box乱序[/pre]　　二.伪随机自密码生成算法：
[pre]1. 将S-Box经过伪随机子密码生成算法得到子密钥序列
2. 将子密钥序列同明文进行异或得到密文[/pre]一、做题　　首先从一个很简单的rc4题目入手。
直接丢入IDA中，整个程序逻辑一目了然。

从做题到出题再到做题三部曲-RC4

　　先获取用户输入，然后对固定数组进行异或，根据用户输入进行某种加解密运算，最后输出flag.
　　那么如何知道这是何种加密方式呢，ida中有findcrypto插件进行加密算法的识别，不过使用局限性很大，更多的还是得靠人来识别。

从做题到出题再到做题三部曲-RC4

　　如果对RC4加密算法比较熟悉，应该很容易根据一些特征可以看出该算法为RC4，更何况IDA已经将算法的逻辑毫无保留的展示出来了。
　　查看sub_400736函数

从做题到出题再到做题三部曲-RC4

　　首先第一个循环体初始化了S-Box，并且根据key初始化了数组K。
第二个循环体根据K生成V8然后对S-Box进行乱序(交换)
　　而后查看sub_4008F3函数

从做题到出题再到做题三部曲-RC4

　　首先生成下标V7和V8，然后对S-Box[V7]和S-Box[V8]进行交换，然后得到一个新的下标，也就是一个子密钥序列，最后将子密钥序列同明文进行异或，得到密文。
　　基本上和RC4的源码一摸一样，这完全得益于IDA的强大功能，但是这并不能提高我们的逆向能力，更无法体会到逆向的乐趣！
二、出题　　RC4算法用C语言很容易实现，以下便是这道题目的源代码,大家可以拿去参考。
[pre]#include<stdio.h>
#include<stdint.h>
#include<stdbool.h>
#include<stdlib.h>
#include <stdio.h>
#include <string.h>


void rc4_init(uint8_t *s, uint8_t *key, uint16_t Len) //初始化函数
{
int i =0, j = 0;
char k[256] = {0};
uint8_t tmp = 0;
for (i=0;i<256;i++) {
s = i;
k = key[i%Len];
}
for (i=0; i<256; i++) {
j=(j+s+k)%256;
tmp = s;
s = s[j]; //交换s和s[j]
s[j] = tmp;
}
}

void rc4_crypt(uint8_t *s, uint8_t *Data, uint16_t Len) //加解密
{
int i = 0, j = 0, t = 0;
uint16_t k = 0;
uint8_t tmp;
for(k=0;k<Len;k++) {
i=(i+1)%256;
j=(j+s)%256;
tmp = s;
s = s[j]; //交换s[x]和s[y]
s[j] = tmp;
t=(s+s[j])%256;
Data[k] ^= s[t];
}
}

void Hex2Str( const char *sSrc,  char *sDest, int nSrcLen )  
{  
int  i;  
char szTmp[3];  

for( i = 0; i < nSrcLen; i++ )  
{  
sprintf( szTmp, "%02X", (unsigned char) sSrc );  
memcpy( &sDest[i * 2], szTmp, 2 );  
}  
return ;  
}  

int getStr(char *buffer,int maxLen){
char c;  // 读取到的一个字符
int len = 0;  // 当前输入的字符串的长度
// 一次读取一个字符，保存到buffer
// 直到遇到换行符(\n)，或者长度超过maxLen时，停止读取
while( (c=getchar()) != '\n' ){
buffer[len++]=c;  // 将读取到的字符保存到buffer
if(len>=maxLen){
break;
}
}
buffer[len]='\0';  // 读取结束，在末尾手动添加字符串结束标志
fflush(stdin);  // 刷新输入缓冲区
return len;
}

int main(int argc,char ** argv){

char enc[23]  = {232, 86, 8, 28, 69, 57, 192, 153, 1, 33, 226, 253, 141, 89, 30, 212, 29, 94, 84, 46, 230, 190, 249};
uint8_t s[256] = {0}; //S-box
uint8_t keyLen = 0,i;
char key[9];
// uint8_t flag[] = "flag{test_flag_for_rc4}";
printf("Please input you flag:\n");
keyLen = getStr(key,8);
for(i=0;i<23;i++){
enc = enc^(i+0x31);
}
rc4_init(s,(uint8_t *)key, strlen(key)); //初始化密钥
rc4_crypt(s,(uint8_t *)enc,strlen(enc));//解密
// Hex2Str( (const char *)flag,  sDest, keyLen );
printf("flag is :%s\n",enc);

}
[/pre]
　　编译makefile文件如下:
[pre]# modify CC to your own obfuscator-llvm location!

CC := /home/***/Desktop/llvm-4.0/build/bin/clang
CFLAGS := -s -mllvm -fla -mllvm -sub -mllvm -bcf
OUT := rc4-level-1
SRC := main.c

# default: $(OUT)
.PHONY:build
build: $(SRC)
$(CC) $(CFLAGS) $^ -o $@

.PHONY:clean
clean:  *.o
rm -rf *.o
[/pre]
三、做题　　我感觉逆向的乐趣在于面对着一堆汇编指令甚至是字节码能看出程序的运行逻辑，而不是简单的丢到工具中，然后对着伪代码进行分析，为了更详细的看清数据的流动，我采用了ollvm混淆，这也仅仅是为了不让ida轻易的将逻辑展示出来。
关于ollvm混淆可以参考ollvm。
关于ollvm的特点我就不详细了，这里直接在每个分支最后的基本块下断点，配置好环境后，我们便可以开始动态调试了。

从做题到出题再到做题三部曲-RC4

　　通过源代码我们可以知道程序大概的验证逻辑，接下来我们就直奔主题——注意数据是如何流动的。在sub_4018B0函数处我们随便输入一个key,不过呢通常为了更好的表征数据我习惯性的会输入12345678或是其他有某种含义的数据，接下来便是不断的F9运行到我们事先设置好的断点处。

从做题到出题再到做题三部曲-RC4

　　很快的，我们可以分析出每个分支的功能，比如说loc_402012分支，是在准备进入循环体，关键的一条指令cmp     edx, 17h,也就对应着源码里的for(i=0;i<23;i++),其他也都是类似，只需要抓住关键的几条指令即可。
loc_402034分支对应的是i+0x31

从做题到出题再到做题三部曲-RC4

　　接下来会来到loc_402278这个分支里我们会遇到rc4_init和rc4_crypt.
　　sub_4006B0函数和先前类似的方法下断，可以知道
[rbp+var_42]是长度len;
[rbp+var_48]为i;
[r8+r9]为S-Box;
[rbp+r8+s]为k

从做题到出题再到做题三部曲-RC4

　　接下来我们同时打开两个数据窗口观察数据的变化。很快的两个数组的初始化便完成了。

从做题到出题再到做题三部曲-RC4

从做题到出题再到做题三部曲-RC4

　　如果不看代码，仅从这个数组中的变化中也能知道程序做了何事。接下来我们需要时刻关注代码对数据的引用。经过一次循环，发现01和31互换了位置

从做题到出题再到做题三部曲-RC4

　　下一个循环也是类似将02和S-Box中的某个数据互换了位置，我们大可不必关心具体的两个位置是如何变换的，只要能抽象出该变换的特征，我们便可以知道此为何种加密算法。经过这两个循环的观察可知这段代码正在进行交换（乱序）操作。
　　而后我们便会进入sub_400E70函数,

从做题到出题再到做题三部曲-RC4

　　这部分是一个mod操作,当运行完loc_4010E2分支后，可观察到S-Box发生了变化，并且从最后几条指令中，发现经过了xor运算，查看一下[rsi+rdi]的值。

从做题到出题再到做题三部曲-RC4

　　其所对应就是enc，继续往后走，注意观察enc和S-Box的数据。

从做题到出题再到做题三部曲-RC4

　　发现大致操作是对S-Box做某种变化，然后取值同enc进行异或，此函数也就是做了此操作。之后便输出解密之后的flag.
　　现在让我们来整理下数据变化的特征：

• 有一个大小为256的S-Box，初始化，根据key进行乱序
• 同样的对S-Box进行乱序，然后同enc进行异或
  

　　然后我们便可以很容易的确定这部分为RC4算法。那么对于整个程序的功能也能有一个预测，完毕。
题解？　　这道题不需要题解，因为只需爆破key就可以了。==阴险
总结　　总的来说RC4比较的简单，涉及到的变换少之又少，不过要想快速的确定算法，还是需要一定的经验，有时候逆向就是预测/验证的过程。
有关RC4的源代码可以参考

游客，如果您要查看本帖隐藏内容请回复

---