常见加密算法逆向分析

常见加密算法逆向分析

1 简单加密算法逆向分析

1.1 异或加密

如果使用不断重复的密钥，利用频率分析就可以破解这种简单的异或密码,易于实现，而且计算成本小

异或，相同为0不同为1，自己xor自己=0，自己xor0=自己

XOR 运算有一个很奇妙的特点：如果对一个值连续做两次 XOR，会返回这个值本身

原始信息是message，密钥是key，第一次 XOR 会得到加密文本cipherText。对方拿到以后，再用key做一次 XOR 运算，就会还原得到message

key的长度大于等于message key必须是一次性的，且每次都要随机产生

如果每次的key都是随机的，那么产生的CipherText具有所有可能的值，而且是均匀分布，无法从CipherText看出message的任何特征。也就是说，它具有最大的"信息熵"，因此完全不可能破解。

strlen()：

1. 用户输入的内容是保存在地址esp+20h+var_C处的， 指令lea edi,[esp+20h+var_C]功能就是将 esp+20h+var_C的值放入寄存器edi中，所以现在edi寄存器是指向用户输入的内容的。

2. 指令or ecx,0FFFFFFFFh是将寄存器ecx的值设置为 0xFFFFFFFF（也就是所有位设置为1）

3. 指令xor eax, eax将eax的值设置为0（0在C语言中就是字符串的结尾）

4. 指令add esp,10h是用来平衡栈的（这里不用关心）

5. repne：

   repne是一个串操作指令中的条件重复前缀指令，加在串操作指令前，使串操作重复进行。

   repne可检查两个字符串是否不同，发现相同立即停止比较。

   repne的重复条件是CX≠0且ZF＝0，每执行一次，CX的内容就减1，直到CX减为0时，结束串指令操作。若重复条件满足，重复前缀先使CX←CX－1，然后执行后面的串指令。

6. 指令repne scasb表示如果ecx的值不为0就继续执行 后面的内容–>scasb

7. scasb则是串扫描指令，比较edi寄存器指向的值与eax寄存器中的值是否相等，每次将edi的值增加1，如果相等就退出循环（执行该指令后面的指令），不相等就继续比较

8. repne scasb（repeat not equal）该指令的功能是比较寄存器edi指向的值（用户输入值）和寄存器eax的值是否相等，如果不相等则将edi的值增一，并继续比较，相等则结束循环。

9. 这里eax寄存器的值为0，将edi寄存器指向的值与0比较，是在判断是否到达了用户输入字符串的末尾

10. 每比较一次，寄存器ecx的值会减一。因此寄存器ecx减少的值即为字符串的长度。(逐字节比较)

11. not ecx以及dec ecx就是在计算ecx减少了多少，经过这两条指令后ecx就是字符串的长度了

12. 将ecx与0xAH(即二进制10)比较，看是否相等，不相等就输出wrong

    一开始ecx的值为0xFFFFFFFF，假设循环了5次，也就是减了5。

    0xFFFFFFFF对应的是-1，-1-5=-6，-6对应0xFFFFFFFA,然后 对其取反，得到的值为5 ，还有一个减1的操作，这样得到的结果就为4

    

1. 第一条指令mov指令从指定的字节数组0x409030处取出一个字节，放到寄存器ecx中，看第一条指令mov cl,byte_409030[eax]，其中地址 0x409030指向的是一片内存，byte_409030[eax]的意思就是取地址0x409030+eax处的一个字节的意思 ，这样不断将eax的值增加1，实现逐字节取数据
2. 第二条mov指令则是从用户输入的内容中取一个字节放入edx寄存器中
3. 第三条指令xor dl,cl就是异或操作指令，异或操作xor dl,cl，会将寄存器edx和ecx的异或后的结果放入到第一个操作数edx中
4. 第四条指令，该指令将异或操作后得到的结果又放入到了用户输入的地址处。

这里为什么会是逐字节进行异或的，就是通过在最开始的xor eax,eax指令将eax寄存器置为0，然后用 eax当做数组的下标，每次增加1来实现循环取数据并进行异或操作

可以看到第四条mov下面的inc eax就是将eax的值增加1的指令，然后在下面一条指令cmp eax，0xA中 将eax的值与10进行比较，判断是否要退出循环了

最后在将eax的值与10比较，小于10就跳转到地址 0x401080处（也就是循环的开始）继续执行—>实现循环

第二个方框只不过这里是利用esi寄存器来实现循环的（通过xor esi,esi将esi置0）

将用户输入的数据取出一字节，放入寄存器eax， 将字节数组0x40903C处的数据（正确的密文）取出 一字节放入edx中，接着比较eax与edx的值是否相等，不相等（jnz short loc_4010B2）就跳到 0x4010B2处执行（这里是输出wrong answer），否则继续循环，直到循环了10次为止

1.2 仿射加密

古典密码

• 置换密码 根据一定的规则重新排列明文
• 代换密码 将明文中的字符串替换为其他字符 (仿射加密便是代换密码中的一种)

仿射加密的加密算法是一个线性变换

y=(ax+b) mod 26

x=(y-b)*(a^-1 mod 26)

如果a, b分别为1和3，则以上加密算法为著名的凯撒密码

分析上述汇编代码，可以知道0x401047处的循环为判断用户输入的内容是否有小于0x61（对应字符为 ‘a’）或大于0x7A（对应字符为‘z’）的情况， 有则跳转到0x4010B3处

这里需要根据3*eax-0x11C来推算加密密钥（a, b）
结合加密算法y=(ax+b) mod 26，可知
y=a*(eax-0x61)+b=3*eax-0x11C=a*eax-a*0x61+b – 通过解方程，我们可以得到a=3, b=7

在 x86 汇编中，IDIV 指令是带符号整数除法，它的默认行为是将 EDX:EAX 作为被除数，除以寄存器或内存指定的除数。

在汇编语言中，IDIV 指令会进行带符号除法，并将结果的商存储在 EAX，余数存储在 EDX 中。

如何得到的?y=(ax+b) mod 26 的x不是直接的asc而是位置比如a是0

所以y =(3*eax-0x11C) = ax+b= a(x-0x61)+b

ax-0x61x+b = 3x-0x11c

a = 3 b = 0x61*3-0x11c = 97x3-284=291-284=7

这里暂且都不去做mod26，因为这几个式子都有mod26 ，可以暂时忽略，我们的目标是求a,b

x=(y-b)*(a^-1 mod 26)

3*a^-1 = 1 mod 26 a^-1=9

2 对称加密算法逆向分析

2.1 RC4

RC4本质上是流密码算法，利用生成的密钥流序列和输入明文进行异或完成加密。

密钥流的生成以一个足够大的数组为基础，对其进 行非线性变换，把这个大数组称为S盒。

RC4的处理包括两个过程

• 密钥调度算法来置乱S盒的初始排列

  密钥调度算法是根据用户选定的密钥K(0<=len(k)<=256)

  依次对数组中的数据进行换位，进而打乱S盒的初始排序,其中，如果K的长度小于256，则将K重复拼接起来，直到长度为256为止。

• 伪随机生成算法，来输出随机序列并修改S盒的当前排列顺序

  是利用初始化后的S盒，按照一定的规则从中选取数据输出，同时更新S盒的排列顺序，达到生成伪随机序列的目的。

RC4加解密的关键步骤在于按照密钥生成伪随机序列，得到伪随机序列后直接与明/密文进行异或操作即可。

由密钥初始化S盒

S盒的长度为256，程序首先会将0到255的互不重复的元素装入S盒，使得0<=S[i]<=255

同时建立一个长度为256的临时数组T，如果密钥K的长度等于256字节，那么直接将密钥的值赋给T，否则将K的元素依次赋给T，并不断重复的将K的值赋给T，直到T被填满。

for i from 0 to 255S[i]:= i
end for
j :=0
// 混淆 S 数组
for( i=0; i<256; i++)j :=(j + S[i]+ key[i mod keylength])%256swap values of S[i]and S[j]
end for

生成密钥流,生成密钥流的过程中，根据i、j的值来确定选取S盒的哪个元素，并更新S盒中元素的排列顺序

i :=0
j :=0
while GeneratingOutput:i :=(i +1) mod 256j :=(j + S[i]) mod 256swap values of S[i]and S[j]t :=(S[i]+S[j]) mod 256k := inputByte ^ S[t]output k
end while

#include<stdio.h>
#include<string.h>
typedef unsigned longULONG;
/*初始化函数*/
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;k[i] = key[i % Len];}for (i = 0; i < 256; i++) {j = (j + s[i] + k[i]) % 256;tmp = s[i];s[i] = s[j];//交换s[i]和s[j]s[j] = tmp;}
}
/*加解密*/
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];}
}int main()
{unsigned char flag[] ={0xA7,0x1A,0x68,0xEC,0xD8,0x27,0x11,0xCC,0x8C,0x9B,0x16,0x15,0x5C,0xD2,0x67,0x3E,0x82,0xAD,0xCE,0x75,0xD4,0xBC,0x57,0x56,0xC2,0x8A,0x52,0xB8,0x6B,0xD6,0xCC,0xF8,0xA4,0xBA,0x72,0x2F,0xE0,0x57,0x15,0xB9,0x24,0x11};unsigned char key[] = "RC4_1s_4w3s0m3";unsigned  char s[256] = { 0 };rc4_init(s, key, 14);rc4_crypt(s, flag, 42);int i;for (i = 0; i <= 42; i++) {printf("%c", flag[i]);}
}

2.2 DES

DES属于对称密码体制，有效密钥的长度为56位。DES为分组密码算法，分组长度为64位，使用Feistel的结构作为加解密的基本结构。

首先,将输入的64位明文进行一个初始置换（IP）， 并将得到的结果分为左右两个分组，各为32位。

进行初始置换后，对左右两个分组进行16轮相同轮函数的迭代，每轮迭代都有置换和代换。需要注意的是最后一轮迭代输出不进行左右两个分组的交换。

经16轮迭代后，得到的结果再经逆初始置换（FP） 的作用后,作为加密的最终输出。

DES利用56比特串长度的密钥K来加密长度为64位的 明文，得到长度为64位的密文

1. 初始置换（IP置换）：将输入的64位明文块进行置换和重新排列，生成新的64位数据块。

2. 加密轮次：DES加密算法共有16个轮次，每个轮次都包括四个步骤：

   • 将64位数据块分为左右两个32位块。
   • 右侧32位块作为输入，经过扩展、异或、置换等操作生成一个48位的数据块。这个48位的数据块被称为“轮密钥”，它是根据加密算法的主密钥生成的子密钥。
   • 将左侧32位块和轮密钥进行异或运算，结果作为新的右侧32位块。
   • 将右侧32位块与原来的左侧32位块进行连接，生成一个新的64位数据块，作为下一轮的输入。

3. 末置换（FP置换）：在最后一个轮次完成后，将经过加密的数据块进行置换和重新排列，得到加密后的64位密文。

通俗易懂，十分钟读懂DES，详解DES加密算法原理，DES攻击手段以及3DES原理。Python DES实现源码-CSDN博客

3 单向散列算法逆向分析

3.1 MD5

Hash值长度为128

输入：任意长度的消息

输出：128位消息摘要

处理：以512位输入数据块为单位

MD5算法逻辑

1. 分组和填充：把明文消息按512位分组，最后填充一定长度的1000…，使得每个消息的长度满 足length = 448 mod 512。填充的方法是先将比特 “1”添加到消息的末尾，再添加k个零。

2. 附加消息：最后加上64位的消息摘要长度字段，整个明文恰好为512的整数倍。

3. 初始化MD缓冲区。一个128位MD缓冲区用以保存中间和最终散列函数的结果。置4个32比特长的缓冲区ABCD分别为

   

4. 处理消息块（512位 = 16个32位字）。一个压缩函数是本算法的核心(HMD5)。它包括4轮处理。 四轮处理具有相似的结构，但每次使用不同的基本逻辑函数，记为F,G,H,I。

   

5. 输出结果。所有L个512位数据块处理完毕后，最后的结果就 是128位消息摘要。

   

   

3.2 SHA算法

SHA-256算法输入消息的最大长度不超过比特，以 512比特分组来处理输入的消息，产生的输出是256 比特的消息摘要。消息的分组长度为512比特

链接变量的中间及最终结果存储于256比特的缓冲区中，缓冲区可用8个32位的寄存器A-H表示，首先对链接变量进行初始化，这些初值是取自前8个素数(2，3，5，7，11，13，17，19) 的平方根的小数部分，用其二进制表示的前32位。

A =0x6a09e667;
B =0xbb67ae85;
C =0x3c6ef372;
D =0xa54ff53a;
E =0x510e527f;
F =0x9b05688c;
G =0x1f83d9ab;
H =0x5be0cd19

压缩函数：消息块以512位分组为单位进行处理，需要进行64步循环操作(步函数)， 每一轮的输入均为当前处理的消息分组和上一轮输 出的256位缓冲区A-H的值，每一步中均采用了不同的消息字Wt和32位常数Kt