夏洛魂
夏洛魂

AES

夏洛魂 夏洛魂 收录于 加密算法
 约 4800 字 预计阅读 10 分钟 

算法描述

在AES算法中密钥长度、分组长度和轮数的对应关系如下:

密钥长度(Nk个32位双字) 分组长度(Nb个32位双字) 轮数(Nr)
AES-128 4 4 10
AES-192 6 4 12
AES-256 8 4 14

对AES算法来说,输入分组、输出分组及状态分组的长度都是128比特,即Nb = 4.

加密过程

总体

将输入复制到状态数组中,在进行一次初始轮密钥相加操作之后,执行Nr次轮函数,对状态数组进行变换,其中最后一轮不同于前Nr-1轮.将最终的状态数组复制到输出数组中,即得到最终的密文.

轮函数由4部分组成,分别是subBytes(),shiftRows(),mixColumns(),addRoundKey().

其加密过程的伪代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

//对AES-128加密来说,Nk = 4,Nb = 4,Nr = 10
void AES_XXX_Encrypt(uint8 in[4*Nb], uint8 out[4*Nb], uint8 key[4*Nk]) {
	//将输入复制到状态数组
	uint8 state[4*Nb] = in;

	//密钥扩展
	uint32 dw[Nb*(Nr+1)] = keyExpansion(key[4*Nk]);
	//轮密相加
	addRoundKey(state, dw[0, Nb-1]);

	for (int round = 1; round < Nr; ++round) {
		subBytes(state); //字节代换
		shiftRows(state); //行移位
		mixColumns(state); //列混合
		addRoundKey(state, dw[round*Nb, (round+1)*Nb-1]); //轮密相加 dw[4-7],dw[8-11]...
	}

	subBytes(state);
	shiftRows(state);
	addRoundKey(state, dw[Nr*Nb,(Nr+1)*Nb-1]);
	out = state;
}

密钥扩展(keyExpansion)

通过对用户输入的128位、192位或者256位的密钥进行处理,共生成Nb*(Nr+1)个32位双字,为加解密算法的轮函数提供轮密钥.

其代码表示如下:

 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

void XorWords(uint8* a, uint8* b, uint8* c)
{
	int i;
	for (i = 0; i < 4; i++)
	{
		c[i] = a[i] ^ b[i];
	}
}

uint8 xtime(uint8 b)    // multiply on x
{
	return (b << 1) ^ (((b >> 7) & 1) * 0x1b);
}

void Rcon(uint8* a, int n)
{
	int i;
	uint8 c = 1;
	for (i = 0; i < n - 1; i++)
	{
		c = xtime(c);
	}

	a[0] = c;
	a[1] = a[2] = a[3] = 0;
}

void SubWord(uint8* a)
{
	int i;
	for (i = 0; i < 4; i++)
	{
		a[i] = S[a[i] / 16][a[i] % 16];
	}
}

void RotWord(uint8* a)
{
	uint8 c = a[0];
	a[0] = a[1];
	a[1] = a[2];
	a[2] = a[3];
	a[3] = c;
}

//密钥扩展
void KeyExpansion(uint8 key[4 * Nk], uint8 w[4 * Nb * (Nr + 1)])
{
	uint8* temp = new uint8[4];
	uint8* rcon = new uint8[4];

	int i = 0;
	while (i < 4 * Nk)
	{
		w[i] = key[i];
		i++;
	}

	i = 4 * Nk;
	while (i < 4 * Nb * (Nr + 1))
	{
		temp[0] = w[i - 4 + 0];
		temp[1] = w[i - 4 + 1];
		temp[2] = w[i - 4 + 2];
		temp[3] = w[i - 4 + 3];

		if (i / 4 % Nk == 0)
		{
			RotWord(temp);
			SubWord(temp);
			Rcon(rcon, i / (Nk * 4));
			XorWords(temp, rcon, temp);
		}
		else if (Nk > 6 && i / 4 % Nk == 4)
		{
			SubWord(temp);
		}

		w[i + 0] = w[i - 4 * Nk] ^ temp[0];
		w[i + 1] = w[i + 1 - 4 * Nk] ^ temp[1];
		w[i + 2] = w[i + 2 - 4 * Nk] ^ temp[2];
		w[i + 3] = w[i + 3 - 4 * Nk] ^ temp[3];
		i += 4;
	}

	delete[]rcon;
	delete[]temp;
}

字节代换(subBytes)

实际上就是一个简单的查表操作.AES定义了一个16x16字节的S-box,以状态数组中的每个字节元素的高4位为行标,低4位为列标,取出相应的元素作为subBytes操作的结果.例如,16进制值{21},高4位为2,低4位为1,取S-box中行标为2、列表为1的值组成16进制值{FD},则{21}被替换为{FD}.

AES-S-Box

其代码表示如下:

1
2
3
4
5
6
7
8

void subBytes(uint8(*state)[4]) {
	/* i: row, j: col */
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			state[i][j] = S[state[i][j]];
		}
	}
}

行移位(shiftRows)

状态数组的第1行保持不变,第2行循环左移1字节,第3行循环左移2字节,第4行循环左移3字节.例如,对状态:

F6 A6 82 A4
14 8C 48 7F
46 EA 26 19
C1 53 A7 14

进行行移位之后,结果为:

F6 A6 82 A4
8C 48 7F 14
26 19 46 EA
14 C1 53 A7

其代码表示如下:

 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

//循环左移
void leftLoop4int(uint32 array[4], int step) {
	uint32 temp[4];
	for (int i = 0; i < 4; i++)
		temp[i] = array[i];

	int index = step % 4 == 0 ? 0 : step % 4;
	for (int i = 0; i < 4; i++) {
		array[i] = temp[index];
		index++;
		index = index % 4;
	}
}

//行移位
void shiftRows(uint8 array[4][4]) {
	uint32 rowTwo[4], rowThree[4], rowFour[4];
	//复制状态矩阵的第2,3,4行
	for (int i = 0; i < 4; i++) {
		rowTwo[i] = array[1][i];
		rowThree[i] = array[2][i];
		rowFour[i] = array[3][i];
	}
	//循环左移相应的位数
	leftLoop4int(rowTwo, 1);
	leftLoop4int(rowThree, 2);
	leftLoop4int(rowFour, 3);

	//把左移后的行复制回状态矩阵中
	for (int i = 0; i < 4; i++) {
		array[1][i] = rowTwo[i];
		array[2][i] = rowThree[i];
		array[3][i] = rowFour[i];
	}
}

列混合(mixColumns)

先把状态矩阵初始状态复制一份到tmpArray中,然后将tmpArray与M矩阵相乘,其中M存放的是要乘的常数矩阵数组,GMul函数定义了矩阵相乘时的乘法,加法则直接通过异或来实现.

其代码表示如下:

 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

uint8 GMul(uint8 u, uint8 v) {
    uint8 p = 0;

    for (int i = 0; i < 8; ++i) {
        if (u & 0x01) {    //
            p ^= v;
        }

        int flag = (v & 0x80);
        v <<= 1;
        if (flag) {
            v ^= 0x1B; /* x^8 + x^4 + x^3 + x + 1 */
        }

        u >>= 1;
    }

    return p;
}

int mixColumns(uint8(*state)[4]) {
	uint8 tmpArray[4][4];
	uint8 M[4][4] = { {0x02, 0x03, 0x01, 0x01},
					   {0x01, 0x02, 0x03, 0x01},
					   {0x01, 0x01, 0x02, 0x03},
					   {0x03, 0x01, 0x01, 0x02} };

	/* copy state[4][4] to tmp[4][4] */
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			tmpArray[i][j] = state[i][j];
		}
	}

	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			state[i][j] = GMul(M[i][0], tmpArray[0][j]) ^ GMul(M[i][1], tmpArray[1][j])
				^ GMul(M[i][2], tmpArray[2][j]) ^ GMul(M[i][3], tmpArray[3][j]);
		}
	}

	return 0;
}

轮密相加(addRoundKey)

将状态数组中的元素与轮密钥通过简单的异或运算相加.轮密钥是由用户输入的密钥通过密钥扩展生成的,同样可以看成一个状态数组.

其代码表示如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#define BYTE(x, n) (((x) >> (8 * (n))) & 0xff)
void addRoundKey(uint8(*state)[4], const uint32* key) {
	uint8 k[4][4];

	/* i: row, j: col */
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			k[i][j] = (uint8)BYTE(key[j], 3 - i);  /* copy uint32 key[4] to uint8 k[4][4] */
			state[i][j] ^= k[i][j];
		}
	}
}

解密过程

总体

加密算法的逆过程就是解密算法.因此,解密算法的轮函数也是由4部分组成,分别是invShiftRows、invSubBytes、invMixColumns、addRoundKey.

其解密过程的伪代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//对AES-128解密来说, Nk = 4, Nb = 4, Nr = 10
void AES_XXX_Decrypt(uint8 in[4 * Nb], uint8 out[4 * Nb], uint8 key[4 * Nk]) {
	//将输入复制到状态数组
	uint8 state[4 * Nb] = in;

	//密钥扩展
	uint32 dw[Nb * (Nr + 1)] = keyExpansion(key[4 * Nk]);
	//轮密相加
	//此时使用的秘钥是加密时使用秘钥的倒序
	addRoundKey(state, dw);

	for (int i = 1; i < 10; ++i) {
		dw += 4;
		invSubBytes(state);
		invShiftRows(state);
		addRoundKey(state, dw);
		invMixColumns(state);
	}

	invSubBytes(state);
	invShiftRows(state);
	addRoundKey(state, dw + 4);
	out = state;
}

密钥扩展(keyExpansion)

加密过程中的密钥扩展结果倒序就是解密过程中使用的密钥.

逆字节代换(invSubBytes)

是字节代换的逆过程,和字节代换一样,逆字节代换只进行简单的查表操作.

AES同时定义了一个逆S盒(Inverse S-Box).

AES-inv-S-Box

逆行移位(invShiftRows)

是行移位的逆过程,即状态数组中的后3行执行相应的右移操作.

逆列混合(invMixColumns)

和列混合的原理相同,区别在于它们使用了不同的多项式.逆列混合使用的系数矩阵如下:

1
2
3
4

uint8_t M[4][4] = {{0x0E, 0x0B, 0x0D, 0x09},
                   {0x09, 0x0E, 0x0B, 0x0D},
                   {0x0D, 0x09, 0x0E, 0x0B},
                   {0x0B, 0x0D, 0x09, 0x0E}};

它与列混合使用的矩阵互为逆矩阵.

轮密相加(addRoundKey)

轮密相加的逆过程就是它本身,因为异或操作是其本身的逆.

实战演练

选题

本题选自2022年看雪KCTF的第三题-石像病毒.这是一道利用Windows异常机制来修改标准算法,考察选手对加密算法的熟悉程度.

2022-KCTF-第三题-石像病毒.rar

总体

首先经过简单动态调试,去掉Main函数异常干扰代码,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

int __cdecl main_0(int argc, const char **argv, const char **envp)
{
  void *v3; // esp
  int result; // eax
  char v5; // [esp-10h] [ebp-1048h]
  struc_Luo Src; // [esp+0h] [ebp-1038h] BYREF
  CPPEH_RECORD ms_exc; // [esp+1020h] [ebp-18h]

  v3 = alloca(0x1020);
  memset(&Src, 0xCCu, sizeof(Src));
  ms_exc.registration.ScopeTable = (PSCOPETABLE_ENTRY)((int)ms_exc.registration.ScopeTable ^ __security_cookie);
  memset(Src.szFlag_78, 0, sizeof(Src.szFlag_78));
  Src.result_48 = 0;
  Src.field_4C = 0;
  Src.field_50 = 0;
  Src.field_54 = 0;
  Src.field_58 = 0;
  Src.field_5C = 0;
  Src.field_60 = 0;
  Src.field_64 = 0;
  Src.field_68 = 0;
  Src.field_6C = 0;
  gets_s(Src.szFlag_78, 0xFA0u);
  if ( strlen(Src.szFlag_78) == 0x20 )
  {
    Src.field_40 = 0x200;
    strcpy(&Src.field_24, "Enj0y_1t_4_fuuuN");
    *(_WORD *)((char *)&Src.field_34 + 1) = 0;
    HIBYTE(Src.field_34) = 0;
    Src.field_8 = 0;
    Src.field_C = 0;
    Src.field_10 = 0;
    Src.field_14 = 0;
    Src.field_18 = 0;
    Src.field_0 = 0x200;
    sub_401109(&Src.field_24, 0x10u, (int)&Src.field_8);// MD5
    sub_401104(&Src.field_8, 0x10u, (int)Src.szFlag_78, (int)&Src.result_48, 0x20);// AES
    if ( !memcmp(&Src.result_48, byte_40B200, 0x20u) )
      printf("OK\n", v5);
    else
      printf("NO\n", v5);
    result = 0;
  }
  else
  {
    printf("NO\n", v5);
    result = 0;
  }
  return result;
}

可以看到本题简单明了,首先要求我们输入的字符串长度等于0x20,然后通过对字符串"Enj0y_1t_4_fuuuN"计算MD5值,将其作为密钥,利用AES算法加密我们输入的值,看是否和内置的值相同.若相同,则正确.

注意
这里用到MD5和AES都是利用了Windows异常机制对其标准过程进行了修改.

MD5

  1. 利用IDA插件Findcrypt查找算法常量.

查找算法常量

  1. 交叉引用MD5相关算法常量.

交叉引用MD5算法常量

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

.text:00402C60 sub_402C60      proc near               ; CODE XREF: sub_4010FA↑j
.text:00402C60                 push    ebp
.text:00402C61                 mov     ebp, esp
.text:00402C63                 mov     eax, 4
.text:00402C68                 imul    ecx, eax, 2Ah ; '*'
.text:00402C6B                 mov     MD5_Constants_40B298[ecx], 0D4AF3085h
.text:00402C75                 mov     eax, 1
.text:00402C7A                 pop     ebp
.text:00402C7B                 retn
.text:00402C7B sub_402C60      endp

发现这里修改了MD5常量表中的第(0x2A + 1 = 43)项的值为0x0D4AF3085.

  1. 验证.

在x64Dbg中定位到sub_401109函数,看魔改后的MD5计算出来的值.

动态查看MD5计算出来的值

可以看到上面计算出来的值为:2F65B1FF31ED86D09A285C0F4048059D

找一份标准MD5算法,修改常量表的第43项值为0x0D4AF3085,然后查看是否和上面计算出来的结果相同.

MD5验证1

MD5验证2

AES

总体

  1. 首先利用程序中的特征,在Github上搜索一份跟程序中相近的AES源码.

https://github.com/lmshao/AES

AES-master.zip

  1. 在IDA中查看下AES相关函数.
 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

int __cdecl sub_401104(void *Src, size_t Size, int a3, int a4, int a5)
{
  return sub_402070((uint8_t *)Src, Size, (uint8_t *)a3, (uint8_t *)a4, a5);
}

int __cdecl sub_402070(uint8_t *key, size_t keyLen, uint8_t *in, uint8_t *out, int inLen)
{
  int j; // [esp+4h] [ebp-1C8h]
  unsigned int i; // [esp+8h] [ebp-1C4h]
  int v8[6]; // [esp+10h] [ebp-1BCh] BYREF
  int state[11]; // [esp+28h] [ebp-1A4h] BYREF
  char *v10; // [esp+54h] [ebp-178h]
  uint8_t *_out; // [esp+58h] [ebp-174h]
  char v12[360]; // [esp+60h] [ebp-16Ch] BYREF

  _out = out;
  v10 = v12;
  state[6] = 0;
  state[7] = 0;
  state[8] = 0;
  state[9] = 0;
  state[0] = 0;
  state[1] = 0;
  state[2] = 0;
  state[3] = 0;
  v8[0] = 0;
  v8[1] = 0;
  v8[2] = 0;
  v8[3] = 0;
  if ( !key || !in || !out )
    return 0xFFFFFFFF;
  if ( keyLen > 0x10 )
    return 0xFFFFFFFF;
  if ( inLen % 0x10u )
    return 0xFFFFFFFF;
  memcpy(state, key, keyLen);                   // 密钥长度是0x10,可以看出用的是AES-128加密
  keyExpansion_4010BE((int)state, 0x10, (int)v12);// 密钥扩展 
  for ( i = 0; i < inLen; i += 0x10 )
  {
    sub_401145((uint8_t *)v8, in);
    addRoundKey_401186(v8, v10);                // 轮密相加
    for ( j = 1; j < 0xA; ++j )                 // 轮数(Nr) = 10,可以也看出这里用的是AES-128加密
    {
      v10 += 0x10;
      subBytes_401172((int)v8);                 // 字节代换
      sub_40122B((int)v8);
      mixColumns_40100F((int)v8);               // 列混合
      addRoundKey_401186(v8, v10);              // 轮密相加
    }
    subBytes_401172((int)v8);
    sub_40122B((int)v8);
    addRoundKey_401186(v8, v10 + 0x10);
    sub_40125D((int)v8, _out);
    _out += 0x10;
    in += 0x10;
    v10 = v12;
  }
  return 0;
}

这里我们输入的字符串是"XiaLuoHun12345675434567876543Hun",长度是0x20.

密钥扩展

  1. 用IDA查看密钥扩展函数.

IDA密钥扩展函数

切换到反汇编窗口,可以看到有两处异常.

密钥扩展异常1

密钥扩展异常2

接下来查看下异常处理代码.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int sub_40108C()
{
  return sub_402330();
}

int sub_402330()
{
  RijnDael_AES_LONG_40B000[0x71] ^= RijnDael_AES_LONG_40B000[0xA3];
  RijnDael_AES_LONG_40B000[0xA3] ^= RijnDael_AES_LONG_40B000[0x71];
  RijnDael_AES_LONG_40B000[0x71] ^= RijnDael_AES_LONG_40B000[0xA3];
  return 1;
}

可以发现这里修改了AES的S-Box,以上修改相当于在标准AES算法源码中修改如下:

 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

int keyExpansion(const uint8_t *key, uint32_t keyLen, AesKey *aesKey) {

    if (NULL == key || NULL == aesKey){
        printf("keyExpansion param is NULL\n");
        return -1;
    }

    if (keyLen != 16){
        printf("keyExpansion keyLen = %d, Not support.\n", keyLen);
        return -1;
    }

    uint32_t *w = aesKey->eK;
    uint32_t *v = aesKey->dK;

    /* keyLen is 16 Bytes, generate uint32_t W[44]. */

    /* W[0-3] */
    for (int i = 0; i < 4; ++i) {
        LOAD32H(w[i], key + 4*i);
    }

    /* W[4-43] */
    for (int i = 0; i < 10; ++i) {

        //修改开始------------
		S[0x71] ^= S[0xA3];
		S[0xA3] ^= S[0x71];
		S[0x71] ^= S[0xA3];
        //修改结束-----------

        w[4] = w[0] ^ MIX(w[3]) ^ rcon[i];
        w[5] = w[1] ^ w[4];
        w[6] = w[2] ^ w[5];
        w[7] = w[3] ^ w[6];
        w += 4;
    }

    w = aesKey->eK+44 - 4;
    for (int j = 0; j < 11; ++j) {
		//修改开始------------
		S[0x71] ^= S[0xA3];
		S[0xA3] ^= S[0x71];
		S[0x71] ^= S[0xA3];
		//修改结束-----------

        for (int i = 0; i < 4; ++i) {
            v[i] = w[i];
        }
        w -= 4;
        v += 4;
    }

	//修改开始------------
    //根据S-Box计算逆S-Box
	calc_InvS_Box();
	//修改结束-----------

    return 0;
}
注意
修改了AES的S-Box,我们也要同步修改AES的inv_S-Box.
1
2
3
4
5
6
7
8
9

//由AES的S盒计算逆S盒.
void calc_InvS_Box() {
	unsigned char sbox_inv[256] = { 0 };
	for (int i = 0; i < 256; i++)
	{
		unsigned char temp1 = S[i];
		inv_S[temp1] = i;
	}
}

行移位

用IDA查看下与行移位相关的代码.

行移位1

既然F5不行,那就切换到反汇编窗口看下.

行移位2

这里我们注意到用到了右移,正常来说加密过程中的行移位用的是左移,解密过程中用的是右移.再加上动态调试结果,确认这里是将标准AES加密过程中的行移位修改为了逆行移位.与此同时需要修改解密过程中的逆行移位为行移位.

列混合

IDA列混合GMUL

用IDA伪代码查看列混合中的Gmul函数好像没问题,但切到汇编窗口就会看到有异常处理.

IDA列混合Gmul异常处理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int sub_401249()
{
  return sub_4023D0();
}

int sub_4023D0()
{
  byte_40B200[0x10] = 0xF4;
  byte_40B200[0x11] = 0xF2;
  return 1;
}

byte_40B200里面存放的是最终AES计算出来的结果要比对的值,在这里进行了修改.

计算Flag

既然知道了程序修改标准算法的地方,那我们就来写代码计算下Flag.

计算Flag

计算Flag2

最终得到的Flag为:flag{db5c6a8dfec4d0ec5569899640}

参考链接

AES算法描述及C语言实现

AES加密算法原理的详细介绍与实现

AES

AES

更新于 2022-06-02 
AES
返回 | 主页
0%