AES 夏洛魂的个人博客

夏洛魂收录于加密算法

2022-06-02 约 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

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

查找算法常量

交叉引用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.

验证.

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

动态查看MD5计算出来的值

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

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

MD5验证1

MD5验证2

AES

总体

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

https://github.com/lmshao/AES

AES-master.zip

在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.

密钥扩展

用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

算法描述

加密过程

总体

密钥扩展(keyExpansion)

字节代换(subBytes)

行移位(shiftRows)

列混合(mixColumns)

轮密相加(addRoundKey)

解密过程

总体

密钥扩展(keyExpansion)

逆字节代换(invSubBytes)

逆行移位(invShiftRows)

逆列混合(invMixColumns)

轮密相加(addRoundKey)

实战演练

选题

总体

MD5

AES

总体

密钥扩展

行移位

列混合

计算Flag

参考链接

相关内容