AES算法

简介

AES,高级加密标准(英语:Advanced Encryption Standard,缩写:AES),在密码学中又称Rijndael加密法,是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES,已经被多方分析且广为全世界所使用。严格地说,AES和Rijndael加密法并不完全一样(虽然在实际应用中二者可以互换),因为Rijndael加密法可以支持更大范围的区块和密钥长度:AES的区块长度固定为128 比特,密钥长度则可以是128,192或256比特;而Rijndael使用的密钥和区块长度可以是32位的整数倍,以128位为下限,256比特为上限。

原理

基本术语

字节

AES基本处理单位为字节,在AES中字节可以以有限域上的多项式表示
$b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x+b_0$
例:字节 01100011(0x63):$x^6+x^5+x+1$

状态

AES的操作在称为状态(state)的二维字节数组上进行。状态由4行字节组成,每行长度为(分组长度/32)个字节。在实际实现中将每一列的4个字节作为32位字。
例:长度为128位的分组数据块
F6 14 46 C1 A6 8C EA 53 82 48 26 A7 A4 7F 19 14
| F6 | A6 | 82 | A4 |
| :—–:| :—-: | :—-: | :—-: |
| 14 | 8C | 48 | 7F |
| 46 | EA | 26 | 19 |
| C1 | 53 | A7 | 14 |

数学基础

加减法

有限域上加减法是通过对应多项式中相同次幂系数相加减后模2来实现的,加法也可以看作异或操作。

乘法

对应多项式相乘再模$x^8+x^4+x^3+x+1$

乘x

多项式乘x得到$b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x$
模$x^8+x^4+x^3+x+1$约简,$b_7=0$则为最简,不为零则减去$x^8+x^4+x^3+x+1$。
这种乘法在AES中称作xtime()

算法描述

AES输入、输出分组及状态数组的长度都是128位,即Nb(分组长度/32)=4,密钥K长度为128/192/256位,即Nk=4/6/8。轮数用Nr表示,Nk=4时,Nr=10,Nk=6时,Nr=12,Nk=10时,Nr=14。

加密过程

将输入复制到状态数组。进行一个初始轮密钥加,然后执行轮函数Nr次,其中最后一轮不同于前Nr-1轮。最后得到密文。
轮函数有四个组成部分:SubBytes(),ShiftRows(),MixColumns(),AddRoundKey()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
cipher(byte in[4][Nb],byte out[4][Nb],dword dw[Nb][Nr+1])
{
byte state[4][Nb]
state=in
AddRoundKey(state,dw[0][Nb-1]) //初始轮密钥加
for(i=0;i<Nr-1;i++) //Nr-1轮轮函数
{
SubBytes(state)
ShiftRows(state)
MixColumns(state)
AddRoundKey(state,dw[i*Nb,(i+1)*Nb-1])
}
SubBytes(state)
ShiftRows(state)
AddRoundKey(state,dw[Nr*Nb,(Nr+1)*Nb-1])
out=state
}

SubBytes()

字节代换,AES定义了一个16x16的S-box。
在这里插入图片描述
以状态数组每个元素高4位作行标,低4位作列标,取出S-box中元素作为操作结果。

ShiftRows()

状态数组第一行保持不变,第二行循环左移一个字节,第三行循环左移两个字节,第四行循环左移三个字节。

MixColumns()

以列为单位作变换
$\begin{bmatrix}s_{0,c}\s_{1,c}\s_{2,c}\s_{3,c}\\end{bmatrix}=\begin{bmatrix}02&03&01&01\01&02&03&01\01&01&02&03\03&01&01&02\end{bmatrix}\begin{bmatrix}s_{0,c}\s_{1,c}\s_{2,c}\s_{3,c}\\end{bmatrix}$

AddRoundKey()

将状态中元素同轮密钥通过简单的异或运算相加。轮密钥是由密钥通过密钥扩展生成的,也可看做一个状态数组。
密钥扩展:
将密钥进行处理,生成Nb(Nr+1)个32位双字,为轮函数提供密钥。
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

解密过程

加密算法的逆过程,解密轮函数也有四部分:
InvShiftRows(ShiftRows的逆过程):执行相应的向右位移
InvSubBytes(SubBytes的逆过程):在Inverse S-box中查表操作
InvMixColumns(MixColumns的逆过程):乘矩阵$\begin{bmatrix}0e&0b&0d&09\09&0e&0b&0d\0d&09&0e&0b\0b&0d&09&0e\end{bmatrix}$
AddRoundKey为异或操作,逆过程是其本身。

具体实现

实际软件实现采用了空间换时间的方法,与上述过程不同,常常将轮函数的几个步骤合并为一组查表操作。
实现过程中定义了4个T表,每个T表都有256个4字节的32位双字(共4KB),以此将SubBytes,ShiftRows,MixColumns合并为简单的查表操作。AddRoundKey可以通过在每一列上执行一个32位异或来实现。

exe转py

使用python打包成的exe文件可以使用反编译的方法获得源码

准备

在这里插入图片描述
查看编译信息,注意python版本

exe转pyc

使用工具pyinstxtractor
https://github.com/countercept/python-exe-unpacker/blob/master/pyinstxtractor.py
使用相同版本的python,输入命令python pyinstxtractor.py [filename]
在这里插入图片描述
在生成的[filename]_extracted文件夹下找到主程序
在这里插入图片描述
可以看到主程序并没有.pyc的扩展名,这是由于反编译出的程序缺少pyc文件头,需要我们自己补上。
可以安装struct的文件头来补。
在这里插入图片描述
补充后变为
在这里插入图片描述

pyc转py

使用uncompyle6
命令行输入 uncompyle6.exe [源文件] > [目标文件]
在这里插入图片描述
如果反编译失败很有可能是文件头没有修改正确,多改几次到正确为止即可。

TSCTF-J 2019 EasyCPP

TSCTF-J 2019 EasyCPP

准备

在这里插入图片描述
使用64位IDA打开

代码分析

主函数

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
int __cdecl main(int argc, const char **argv, const char **envp)
{
__int64 v3; // rax
__int64 v4; // rbx
__int64 v5; // rax
bool v6; // bl
__int64 v7; // rax
__int64 v8; // rax
__int64 v9; // rax
__int64 v10; // rax
__int64 v11; // rax
__int64 v12; // rax
char v14[40]; // [rsp+0h] [rbp-140h] BYREF
__int64 v15; // [rsp+28h] [rbp-118h] BYREF
__int64 v16; // [rsp+30h] [rbp-110h] BYREF
int v17; // [rsp+3Ch] [rbp-104h] BYREF
char v18[32]; // [rsp+40h] [rbp-100h] BYREF
char v19[48]; // [rsp+60h] [rbp-E0h] BYREF
char v20[31]; // [rsp+90h] [rbp-B0h] BYREF
char v21; // [rsp+AFh] [rbp-91h] BYREF
char v22[47]; // [rsp+B0h] [rbp-90h] BYREF
char v23; // [rsp+DFh] [rbp-61h] BYREF
char v24[36]; // [rsp+E0h] [rbp-60h] BYREF
unsigned int v25; // [rsp+104h] [rbp-3Ch]
char *v26; // [rsp+108h] [rbp-38h]
int *v27; // [rsp+110h] [rbp-30h]
_DWORD *v28; // [rsp+118h] [rbp-28h]
int *v29; // [rsp+120h] [rbp-20h]
int i; // [rsp+128h] [rbp-18h]
int v31; // [rsp+12Ch] [rbp-14h]

v31 = 0;
std::vector<int>::vector(v20, argv, envp); // 创建int容器
std::vector<bool>::vector(v19); // 创建bool容器
std::allocator<char>::allocator(&v21);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(v18, &unk_500E, &v21);
std::allocator<char>::~allocator(&v21);
v3 = std::operator<<<std::char_traits<char>>(&std::cout, "give me your key!");
std::ostream::operator<<(v3, &std::endl<char,std::char_traits<char>>);
for ( i = 0; i <= 8; ++i ) // 输入8个key
{
std::istream::operator>>(&std::cin, &keys[i]);
std::__cxx11::to_string((std::__cxx11 *)v22, keys[i]);// 将输入的keys转为字符串
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::operator+=(v18, v22);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(v22);
}
v28 = keys;
v29 = keys;
v27 = (int *)&unk_83E4;
while ( v29 != v27 )
{
v17 = *v29;
std::vector<int>::push_back(v20, &v17); // 将输入压入v20
++v29;
}
v4 = std::vector<int>::end(v20);
v5 = std::vector<int>::begin(v20);
std::for_each<__gnu_cxx::__normal_iterator<int *,std::vector<int>>,main::{lambda(int &)#1}>(v5, v4);// 遍历并执行lamada函数,进入后发现是与1异或
v26 = v20;
v16 = std::vector<int>::begin(v20);
v15 = std::vector<int>::end(v26);
while ( (unsigned __int8)__gnu_cxx::operator!=<int *,std::vector<int>>(&v16, &v15) )
{
v25 = *(_DWORD *)__gnu_cxx::__normal_iterator<int *,std::vector<int>>::operator*(&v16);
std::allocator<char>::allocator(&v23);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(v14, &unk_500E, &v23);// 创建字符串v14
std::allocator<char>::~allocator(&v23);
depart(v25, v14); // 用depart函数加密
{lambda(std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>> &)#1}::operator()(
(__int64)&func,
(__int64)v14);//对字符进行替换
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(v24, v14);
v6 = !{lambda(std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>,int)#2}::operator()(// 比较结果
(__int64)&check,
(__int64)v24,
v31);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(v24);
if ( v6 )
{
v7 = std::operator<<<std::char_traits<char>>(&std::cout, "Wrong password!");
std::ostream::operator<<(v7, &std::endl<char,std::char_traits<char>>);
system("pause");
exit(0);
}
++v31;
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(v14);
__gnu_cxx::__normal_iterator<int *,std::vector<int>>::operator++(&v16);
}
v8 = std::operator<<<std::char_traits<char>>(&std::cout, "right!");
std::ostream::operator<<(v8, &std::endl<char,std::char_traits<char>>);
v9 = std::operator<<<std::char_traits<char>>(&std::cout, "flag:MRCTF{md5(");// flag使用MD5 32位大写加密
v10 = std::operator<<<char>(v9, v18);
v11 = std::operator<<<std::char_traits<char>>(v10, ")}");
std::ostream::operator<<(v11, &std::endl<char,std::char_traits<char>>);
v12 = std::operator<<<std::char_traits<char>>(
&std::cout,
"md5()->{32/upper case/put the string into the function and transform into md5 hash}");
std::ostream::operator<<(v12, &std::endl<char,std::char_traits<char>>);
system("pause");
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(v18);
std::vector<bool>::~vector(v19);
std::vector<int>::~vector(v20);
return 0;
}

depart函数

这个递归一开始没看懂,看大佬writeup明白是分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
__int64 __fastcall depart(int a1, __int64 a2)
{
char v3[32]; // [rsp+20h] [rbp-60h] BYREF
char v4[40]; // [rsp+40h] [rbp-40h] BYREF
int i; // [rsp+68h] [rbp-18h]
int v6; // [rsp+6Ch] [rbp-14h]

v6 = a1;
for ( i = 2; std::sqrt<int>((unsigned int)a1) >= (double)i; ++i )
{
if ( !(a1 % i) ) // a1整除i时,继续分解v6/i
{
v6 = i;
depart(a1 / i, a2);
break;
}
}
std::__cxx11::to_string((std::__cxx11 *)v4, v6);
std::operator+<char>(v3, &unk_500C, v4);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::operator+=(a2, v3);// 质因数最后以字符型存入a2
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(v3);
return std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(v4);
}

结果比较函数

1
2
3
4
5
6
7
8
9
_BOOL8 __fastcall {lambda(std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>,int)#2}::operator()(__int64 a1, __int64 a2, int a3)
{
const char *v3; // rbx
const char *v4; // rax

v3 = (const char *)std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::c_str((char *)&ans[abi:cxx11] + 32 * a3);//对比较的字符串进行交叉引用
v4 = (const char *)std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::c_str(a2);
return strcmp(v4, v3) == 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
int __fastcall __static_initialization_and_destruction_0(int a1, int a2)
{
int result; // eax
char v3; // [rsp+17h] [rbp-29h] BYREF
char v4; // [rsp+18h] [rbp-28h] BYREF
char v5; // [rsp+19h] [rbp-27h] BYREF
char v6; // [rsp+1Ah] [rbp-26h] BYREF
char v7; // [rsp+1Bh] [rbp-25h] BYREF
char v8; // [rsp+1Ch] [rbp-24h] BYREF
char v9; // [rsp+1Dh] [rbp-23h] BYREF
char v10; // [rsp+1Eh] [rbp-22h] BYREF
char v11[33]; // [rsp+1Fh] [rbp-21h] BYREF

if ( a1 == 1 && a2 == 0xFFFF )
{
std::ios_base::Init::Init((std::ios_base::Init *)&std::__ioinit);
__cxa_atexit((void (__fastcall *)(void *))&std::ios_base::Init::~Init, &std::__ioinit, &_dso_handle);
std::allocator<char>::allocator(&v3);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(
&ans[abi:cxx11],
"=zqE=z=z=z",
&v3);
std::allocator<char>::~allocator(&v3);
std::allocator<char>::allocator(&v4);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(
(char *)&ans[abi:cxx11] + 32,
"=lzzE",
&v4);
std::allocator<char>::~allocator(&v4);
std::allocator<char>::allocator(&v5);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(
(char *)&ans[abi:cxx11] + 64,
"=ll=T=s=s=E",
&v5);
std::allocator<char>::~allocator(&v5);
std::allocator<char>::allocator(&v6);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(
(char *)&ans[abi:cxx11] + 96,
"=zATT",
&v6);
std::allocator<char>::~allocator(&v6);
std::allocator<char>::allocator(&v7);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(
(char *)&ans[abi:cxx11] + 128,
"=s=s=s=E=E=E",
&v7);
std::allocator<char>::~allocator(&v7);
std::allocator<char>::allocator(&v8);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(
(char *)&ans[abi:cxx11] + 160,
"=EOll=E",
&v8);
std::allocator<char>::~allocator(&v8);
std::allocator<char>::allocator(&v9);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(
(char *)&ans[abi:cxx11] + 192,
"=lE=T=E=E=E",
&v9);
std::allocator<char>::~allocator(&v9);
std::allocator<char>::allocator(&v10);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(
(char *)&ans[abi:cxx11] + 224,
"=EsE=s=z",
&v10);
std::allocator<char>::~allocator(&v10);
std::allocator<char>::allocator(v11);
std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(
(char *)&ans[abi:cxx11] + 256,
"=AT=lE=ll",
v11);
std::allocator<char>::~allocator(v11);
result = __cxa_atexit(_tcf_0, 0LL, &_dso_handle);
}
return result;
}

解密

解密脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
str=["=zqE=z=z=z","=lzzE","=ll=T=s=s=E","=zATT","=s=s=s=E=E=E","=EOll=E","=lE=T=E=E=E","=EsE=s=z","=AT=lE=ll"]
flag=[]

for i in range(0,9):
str[i] = str[i].replace("O", "0")
str[i] = str[i].replace("l", "1")
str[i] = str[i].replace("z", "2")
str[i] = str[i].replace("E", "3")
str[i] = str[i].replace("A", "4")
str[i] = str[i].replace("s", "5")
str[i] = str[i].replace("G", "6")
str[i] = str[i].replace("T", "7")
str[i] = str[i].replace("B", "8")
str[i] = str[i].replace("q", "9")
str[i] = str[i].replace("=", " ")
str[i] = str[i].split( )
k=1;
for j in str[i]:
k=k*int(j)
print(k^1,end=' ')

在这里插入图片描述

动态调试练习

[CSTC2021]Crackme

准备

使用exeinfo查看信息,发现是32位文件,存在UPX壳
在这里插入图片描述
脱壳后使用IDA反汇编

分析

经过分析,发现主函数为sub_401109,使用F5生成伪代码
在这里插入图片描述
观察到程序在此处判断生成的验证码是否正确,因此在这里下断点,并修改代码防止程序跳转到LABEL_35
在这里插入图片描述
每次运行到断点时查看dl
得到验证码为0x58,0x42,0x49,0x48,0x44,0x43,0x45,0x43,0x53,0x42

1
2
3
4
serial=[0x58,0x42,0x49,0x48,0x44,0x43,0x45,0x43,0x53,0x42]
for i in serial:
print(chr(i))
#XBIHDCECSB

总结

对于一些比较简单的题目,只需要在比较的地方下个断点,然后通过查看内存得到flag。