RC4与逆向分析

RC4算法于1987年由Ron Rivest设计，RC4现在以及成为最流行的流密码算法，广泛应用于SSL，WEP中。

加密过程和解密过程相同，使用同一个密钥就可以在密文和明文之间转化

c=RC4(key,m)
m=RC4(key,c)

RC4（Rivest Cipher 4）是一种流加密算法。流加密，是对称加密算法的一种，加密和解密双方使用相同伪随机加密数据流（pseudo-randomstream）作为密钥，明文数据每次与密钥数据流顺次对应加密，得到密文数据流。实践中数据通常是一个位（bit）并用异或（xor）操作加密。

RC4密钥长度可变。RC4是有线等效加密（WEP）中采用的加密算法，也曾经是TLS可采用的算法之一。

所谓对称加密是指：采用单钥密码系统的加密方法，同一个密钥可以同时用作信息的加密和解密，这种加密方法称为对称加密，也称为单密钥加密。

简而言之，假设我们的明文数据是N位，那么得到的密文数据也是N位，由于是xor操作，我们就可以再xor一下将密文还原成明文。

RC4算法主要有两大部分组成：初始化算法（KSA）和伪随机子密码生成算法（PRGA)

加密(解密)原理

RC4由伪随机数生成器和异或运算组成。RC4的密钥长度可变，范围是[1,255]。RC4一个字节一个字节地加解密。给定一个密钥，伪随机数生成器接受密钥并产生一个S盒。S盒用来加密数据，而且在加密过程中S盒会变化。

由于异或运算的对合性，RC4加密解密使用同一套算法。

C代码表示

  1. S-Box 也就是所谓的S盒，是一个256长度的char型数组，每个单元都是一个字节，算法运行的任何时候，S都包括0-255的8比特数的排列组合，只不过值的位置发生了变换。
  2. 密钥K char key[256] 密钥的长度keylen与明文长度、密钥流的长度没有必然关系
  3. 临时向量k 长度也为256，每个单元也是一个字节。如果密钥的长度是256字节，就直接把密钥的值赋给k，否则，轮转地将密钥的每个字节赋给k

RC4 主要包含三个流程

  • 初始化 S 和 T 数组。
  • 初始化置换 S。
  • 生成密钥流。

<1>.初始化

三个参数：

1.256长度的char型数组，定义为: unsigned char sBox[256];

2.密钥，其内容可以随便定义：char key[256];

3.密钥的长度，Len = strlen(key);

初始化长度为256的S盒。第一个for循环将0到255的互不重复的元素装入S盒。第二个for循环根据密钥打乱S盒。

初始化s和t

void rc4_init(unsigned char *s,unsigned char *key, unsigned long Len)
{
    int i=0,j=0;
    char k[256]={0};
    unsigned char tmp=0;
	
    for(i=0;i<256;i++) 
	{
        s[i]=i; 						//v6[i] = i1;
        k[i]=key[i%Len];				//v7 = i1++ % len;  *v6 = *(_BYTE *)(v7 + a2);
    }
	
    for(i=0;i<256;i++)
	{
        j=(j+s[i]+k[i])%256;			//v3 = ((unsigned __int8)*result + result[v8] + v3) % 256;
        tmp=s[i];
        s[i]=s[j];     //交换s[i]和s[j]
        s[j]=tmp;
    }
}

<2>. 加解密

参数1是上边rc4_init函数中，被搅乱的S-box;

参数2是需要加密的数据data;

参数3是data的长度.

每收到一个字节，就进行while循环。通过一定的算法定位S盒中的一个元素，并与输入字节异或，得到k。循环中还改变了S盒。如果输入的是明文，输出的就是密文；如果输入的是密文，输出的就是明文。

初始化置换S

void rc4_crypt(unsigned char *s,unsigned char *Data,unsigned long Len)
{
    int i=0,j=0,t=0;
    unsigned long k=0;
    unsigned char tmp;
	
    for(k=0;k<Len;k++)
    {
        i=(i+1)%256;
        j=(j+s[i])%256;
        tmp=s[i];
        s[i]=s[j];      //交换s[x]和s[y]
        s[j]=tmp;
        t=(s[i]+s[j])%256;
        Data[k]^=s[t]; //生成流密钥
    }
}

生成流密钥

我们一般称前两部分为 KSA ，最后一部分是 PRGA。

<3>.主函数

int main()
{
    unsigned char s[256] = { 0 }, s2[256] = { 0 };//S-box
    char key[256] = { "justfortest" };
    char pData[512] = "这是一个用来加密的数据Data";
    unsigned long len = strlen(pData);
    int i;
 
    printf("pData=%s\n", pData);
    printf("key=%s,length=%d\n\n", key, strlen(key));
    rc4_init(s, (unsigned char*)key, strlen(key)); //已经完成了初始化
    printf("完成对S[i]的初始化，如下：\n\n");
    for (i = 0; i<256; i++)
    {
        printf("%02X", s[i]);
        if (i && (i + 1) % 16 == 0)putchar('\n');
    }
    printf("\n\n");
    for (i = 0; i<256; i++)           //用s2[i]暂时保留经过初始化的s[i]，很重要的！！！
    {
        s2[i] = s[i];
    }
    printf("已经初始化，现在加密:\n\n");
    rc4_crypt(s, (unsigned char*)pData, len);//加密
    printf("pData=%s\n\n", pData);
    printf("已经加密，现在解密:\n\n");
    //rc4_init(s,(unsignedchar*)key,strlen(key));//初始化密钥
    rc4_crypt(s2, (unsigned char*)pData, len);//解密pData的len
    printf("pData=%s\n\n", pData);
    return 0;
}

逆向分析

安恒杯2018-9的NewDriver

int __cdecl main(int argc, const char **argv, const char **envp)
{
  const char *v3; // esi
  int v4; // eax
  int v5; // esi
  char v7[255]; // [esp+Dh] [ebp-237h] BYREF
  char v8[256]; // [esp+10Ch] [ebp-138h] BYREF
  char v9[52]; // [esp+20Ch] [ebp-38h] BYREF

  memset(v7, 0, sizeof(v7));
  strcpy(v8, "flag{this_is_not_the_flag_hahaha}");
  memset(&v8[34], 0, 0xDEu);
  printf("input flag:\n");
  scanf("%50s", v9);
  if ( strlen(v9) == 33 )
  {
    v3 = (const char *)sub_401160(); //base64加密 改表,直接给出换的表没什么好说的
    sub_401000(v8, strlen(v8));  //rc4的初试化
    sub_4010E0(v3, strlen(v3));  //rc4的加密
    v4 = 0;
    v5 = v3 - byte_402104;
    do
    {
      if ( byte_402104[v5 + v4] != byte_402104[v4] )
        exit(0);
      ++v4;
    }
    while ( v4 < 44 );
    printf("Congratulation!!!!!!\n");
  }
  return 0;
}

看一下4010E0

int __usercall sub_4010E0@<eax>(int result@<eax>, int a2, unsigned int a3)
{
  int v3; // ecx
  int v4; // esi
  unsigned int i; // edi
  unsigned __int8 v6; // dl

  v3 = 0;
  v4 = 0;
  for ( i = 0; i < a3; ++i )
  {
    v3 = (v3 + 1) % 256;
    v6 = *(_BYTE *)(v3 + result);
    v4 = (v6 + v4) % 256;
    *(_BYTE *)(v3 + result) = *(_BYTE *)(v4 + result);
    *(_BYTE *)(v4 + result) = v6;
    *(_BYTE *)(i + a2) ^= *(_BYTE *)((v6 + *(unsigned __int8 *)(v3 + result)) % 256 + result);
  }
  return result;
}

再查看汇编,很明显了

;截取部分
.text:004010F1                   loc_4010F1:                   ; CODE XREF: sub_4010E0+6B↓j
.text:004010F1 41                inc     ecx
.text:004010F2 81 E1 FF 00 00 80 and     ecx, 800000FFh
.text:004010F8 79 08             jns     short loc_401102
.text:004010FA 49                dec     ecx
.text:004010FB 81 C9 00 FF FF FF or      ecx, 0FFFFFF00h
.text:00401101 41                inc     ecx
.text:00401102
.text:00401102                   loc_401102:                   ; CODE XREF: sub_4010E0+18↑j
.text:00401102 8A 14 01          mov     dl, [ecx+eax]
.text:00401105 0F B6 DA          movzx   ebx, dl
.text:00401108 03 F3             add     esi, ebx
.text:0040110A 81 E6 FF 00 00 80 and     esi, 800000FFh
.text:00401110 79 08             jns     short loc_40111A
.text:00401112 4E                dec     esi
.text:00401113 81 CE 00 FF FF FF or      esi, 0FFFFFF00h
.text:00401119 46                inc     esi

key是v8提取的数据,利用上面的函数写一个脚本

unsigned char s[256] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255};
   unsigned char k[256] = {"flag{this_is_not_the_flag_hahaha}"};
   rc4_init(s, k, 33);
   for (int i = 0; i < 256; i++)
   {
       printf("0x%x,", s[i]);
   }

key2是byte_402104的数组

key=[0x66, 0x32, 0xCA, 0xA0, 0xBF, 0x98, 0x2D, 0x76, 0xF1, 0x59, 0x2A, 0x4A, 0xF4, 0x30, 0xAD, 0xD2, 0x1D, 0x02, 0xD8, 0x23, 0x89, 0x5D, 0x83, 0x38, 0x09, 0xF2, 0x74, 0x65, 0x40, 0x19, 0xC6, 0xDD, 0x18, 0xD3, 0x8F, 0x6C, 0x8B, 0xC0, 0xC5, 0x54, 0x2E, 0x81, 0x10, 0xC4, 0x26, 0x56, 0x5F, 0x53, 0x80, 0x43, 0x27, 0x62, 0xEA, 0x3D, 0xE6, 0x00, 0xE7, 0xB7, 0x50, 0x94, 0x90, 0x4C, 0x3F, 0x9D, 0x07, 0xE0, 0xA3, 0x9C, 0x4E, 0x0F, 0x9F, 0xFE, 0x5B, 0x8E, 0xDE, 0x88, 0x72, 0x2F, 0xC1, 0x67, 0x31, 0x70, 0x8D, 0xFD, 0xBE, 0x64, 0xC3, 0xBD, 0x6B, 0x7A, 0xCF, 0x0C, 0x34, 0x1F, 0x6F, 0x01, 0xF0, 0x7C, 0x5E, 0xA4, 0x1E, 0x49, 0x8C, 0x75, 0x1C, 0xE3, 0x20, 0x48, 0x28, 0x79, 0xA5, 0x7F, 0xF5, 0xEC, 0x4F, 0x78, 0x58, 0x11, 0xF7, 0xCD, 0x91, 0x13, 0xFC, 0xB8, 0x2C, 0x04, 0xEE, 0xD5, 0x08, 0x44, 0xA9, 0xE1, 0xB1, 0x42, 0x84, 0x29, 0xA7, 0x47, 0x97, 0x7E, 0xE8, 0xB3, 0x60, 0x0B, 0xF9, 0x4B, 0x3C, 0x77, 0x17, 0x03, 0x82, 0x69, 0x87, 0xD4, 0x95, 0x1A, 0x33, 0x25, 0x6E, 0xCC, 0xD6, 0xBB, 0x99, 0xB0, 0x85, 0x41, 0xB2, 0x0D, 0xDB, 0x35, 0x3B, 0x5C, 0xF8, 0xED, 0x9E, 0xA6, 0x96, 0x39, 0x63, 0x0A, 0x1B, 0x93, 0x21, 0x46, 0x12, 0xD0, 0xB4, 0x22, 0x51, 0xC9, 0x61, 0xD1, 0x2B, 0xAA, 0x45, 0x06, 0x05, 0xCE, 0xFA, 0x92, 0x68, 0xAB, 0x36, 0xDA, 0xC8, 0xE2, 0x37, 0xD9, 0xA2, 0x5A, 0xD7, 0x6A, 0xB5, 0xFF, 0xE9, 0xBA, 0x52, 0x15, 0xF6, 0xBC, 0x9A, 0xB6, 0xEF, 0x6D, 0xCB, 0x4D, 0xAE, 0xE4, 0xA1, 0xAC, 0xEB, 0x0E, 0x71, 0x7B, 0xF3, 0x24, 0xC2, 0xFB, 0x7D, 0x86, 0x55, 0xAF, 0x3A, 0xDF, 0x3E, 0x14, 0xB9, 0x9B, 0x16, 0xDC, 0x73, 0x57, 0xE5, 0xC7, 0x8A, 0xA8, 0x66, 0x6C, 0x61, 0x67, 0x7B, 0x74, 0x68, 0x69, 0x73, 0x5F, 0x69, 0x73, 0x5F, 0x6E, 0x6F, 0x74, 0x5F, 0x74, 0x68, 0x65, 0x5F, 0x66, 0x6C, 0x61, 0x67, 0x5F, 0x68, 0x61, 0x68, 0x61, 0x68, 0x61, 0x7D]
key2=[0x20, 0xC3, 0x1A, 0xAE, 0x97, 0x3C, 0x7A, 0x41, 0xDE, 0xF6, 0x78, 0x15, 0xCB, 0x4B, 0x4C, 0xDC, 0x26, 0x55, 0x8B, 0x55, 0xE5, 0xE9, 0x55, 0x75, 0x40, 0x3D, 0x82, 0x13, 0xA5, 0x60, 0x13, 0x3B, 0xF5, 0xD8, 0x19, 0x0E, 0x47, 0xCF, 0x5F, 0x5E, 0xDE, 0x9D, 0x14, 0xBD]
key3=[]
v3=0
v4=0
v6=0
s=""
for v3 in range(44):
  v3+=1
  v6=key[v3]
  v4=(v6+v4)%256
  key[v3]=key[v4]
  key[v4]=v6
  key3.append(key[(key[v3]+v6)%256])
for i in range(44):
  key2[i]^=key3[i]
for i in key2:
  s+=chr(i)
print (s)

得到字符串

ZeptZ3l5UHQra25nd19yYzMrYR5wX2Jtc2P2VF9gYNM9

base64解密

#include<stdio.h>
#include<string.h>
int findchar(char *str,char c){
for(int i=0;str[i];i++)
  if(str[i]==c)
      return i;
return -1;
}

int main(){
char key[]="ABCDEFGHIJSTUVWKLMNOPQRXYZabcdqrstuvwxefghijklmnopyz0123456789+/";
char str[100];
char ans[100];
int temp[2];
memset(str,0,100);
memset(ans,0,100);
scanf("%s",str);
for(int i=0,j=0;str[i];i+=4,j+=3)
  {temp[0]=findchar(key,str[i]);
   temp[1]=findchar(key,str[i+1]);
   ans[j]=(temp[0]<<2&0xfc)|(temp[1]>>4&0x3);
   if(!str[i+2]||str[i+2]=='=')
            break;
   else{
      temp[0]=findchar(key,str[i+2]);
      ans[j+1]=(temp[1]<<4&0xf0)|(temp[0]>>2&0xf);  
       }
   if(!str[i+3]||str[i+3]=='=')
            break;
    else{
       temp[1]=findchar(key,str[i+3]);
       ans[j+2]=(temp[0]<<6&0xc0)|(temp[1]&0x3f);
         }
    }
puts(ans);
}

最后flag{y0u_know_rc4_and_base64_ha$}

魔改RC4

RC4魔改还是比较难的，稍有改变，整个算法就完全不同了。因此，大多数赛题将rc4与其他算法进行组合来加密flag

常见变化位置

  1. 密钥经过上一步的其他加密后传入
  2. s盒内部数据固定
  3. rc4加密后数据进行重加密

参考链接