AES加密学习笔记

Posted on

AES128 ECB 分析

key expansion

AES128 ECB的密钥拓展是将Nk * 4字节的密钥Key拓展为(Nr + 1) * Nb * 4字节的ExpKey。
ExpKey里面的数据分成了(Nr + 1)组，每一组就是用来和state相加的RoundKey。

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
static void KeyExpansion(uint8_t* RoundKey, const uint8_t* Key)
{
  unsigned i, j, k;
  uint8_t tempa[4]; // Used for the column/row operations
  
  // The first round key is the key itself.
  // 第一个循环，填充0号RoundKey
  for (i = 0; i < Nk; ++i)
  {
    RoundKey[(i * 4) + 0] = Key[(i * 4) + 0];
    RoundKey[(i * 4) + 1] = Key[(i * 4) + 1];
    RoundKey[(i * 4) + 2] = Key[(i * 4) + 2];
    RoundKey[(i * 4) + 3] = Key[(i * 4) + 3];
  }

  // All other round keys are found from the previous round keys.
  // 第二个循环，计算剩余RoundKey
  for (i = Nk; i < Nb * (Nr + 1); ++i)
  {
    {
      k = (i - 1) * 4;
      tempa[0]=RoundKey[k + 0];
      tempa[1]=RoundKey[k + 1];
      tempa[2]=RoundKey[k + 2];
      tempa[3]=RoundKey[k + 3];

    }

    if (i % Nk == 0)
    {
      // This function shifts the 4 bytes in a word to the left once.
      // [a0,a1,a2,a3] becomes [a1,a2,a3,a0]

      // Function RotWord()
      {
        const uint8_t u8tmp = tempa[0];
        tempa[0] = tempa[1];
        tempa[1] = tempa[2];
        tempa[2] = tempa[3];
        tempa[3] = u8tmp;
      }

      // SubWord() is a function that takes a four-byte input word and 
      // applies the S-box to each of the four bytes to produce an output word.

      // Function Subword()
      {
        tempa[0] = getSBoxValue(tempa[0]);
        tempa[1] = getSBoxValue(tempa[1]);
        tempa[2] = getSBoxValue(tempa[2]);
        tempa[3] = getSBoxValue(tempa[3]);
      }

      tempa[0] = tempa[0] ^ Rcon[i/Nk];
    }
#if defined(AES256) && (AES256 == 1)
    if (i % Nk == 4)
    {
      // Function Subword()
      {
        tempa[0] = getSBoxValue(tempa[0]);
        tempa[1] = getSBoxValue(tempa[1]);
        tempa[2] = getSBoxValue(tempa[2]);
        tempa[3] = getSBoxValue(tempa[3]);
      }
    }
#endif
    j = i * 4; k=(i - Nk) * 4;
    RoundKey[j + 0] = RoundKey[k + 0] ^ tempa[0];
    RoundKey[j + 1] = RoundKey[k + 1] ^ tempa[1];
    RoundKey[j + 2] = RoundKey[k + 2] ^ tempa[2];
    RoundKey[j + 3] = RoundKey[k + 3] ^ tempa[3];
  }
}

第一个循环用来将Key复制到索引为0的RoundKey的位置，

如图所示，假设我们的key为 0x2b, 0x7e, 0x15, 0x16, 0x28, 0xae, 0xd2, 0xa6, 0xab, 0xf7, 0x15, 0x88, 0x09, 0xcf, 0x4f, 0x3c，经过第一次循环后，RoundKey前16个字节变为途中红色部分（也就是0号RoundKey）。

第一个循环填充了Nk * 4个字节，即Nk个DWORD。第二个循环将剩余的Nb * (Nr + 1) - Nk个DWORD计算并填充到RoundKey。

第二个循环首先获取已经填充到RoundKey的最后一个DWORD，存入tmpa，这里就是09 cf 4f 3c。接下来，如果当前循环变量i可以被Nk整除，就将tmpa的每一个字节循环移动一个位置，变成cf 4f 3c 09，然后每一个字节使用AES的SBox进行代换，得到8a 84 eb 01，并将tmpa[0]与Round Constant的索引为i / Nk的值进行异或。

得到最终的tmpa结果后，从RoundKey的索引为(i - Nk) * 4也就是将要填充的位置的前16个字节开始读取一个DWORD，将该DWORD的4个字节与tmpa的4个字节对应进行异或。

比如此时，在第二个循环的第一次循环中，tmpa为8a 84 eb 01，从将要填充的位置的前16个字节开始读取一个DWORD得到的就是2b 7e 15 16，将它们对应异或之后得到a0 fa fe 17。

加密流程

Round 0：初始化state

AES每次加密只针对一个state对应的大小的数据，也就是16个字节。在进入Nr轮循环之前，会将索引为0的RoundKey与当前state相加。

上图中，要加密的数据为6b c1 be e2 2e 40 9f 96 e9 3d 7e 11 73 93 17 2a，也就是state所存储的值。与RoundKey 02b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c进行AddRound之后，变为了40 bf ab f4 06 ee 4d 30 42 ca 6b 99 7a 5c 58 16。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void Cipher(state_t* state, const uint8_t* RoundKey)
{
  uint8_t round = 0;

  // Add the First round key to the state before starting the rounds.
  AddRoundKey(0, state, RoundKey);

  // There will be Nr rounds.
  // The first Nr-1 rounds are identical.
  // These Nr rounds are executed in the loop below.
  // Last one without MixColumns()
  for (round = 1; ; ++round)
  {
    SubBytes(state);
    ShiftRows(state);
    if (round == Nr) {
      break;
    }
    MixColumns(state);
    AddRoundKey(round, state, RoundKey);
  }
  // Add round key to last round
  AddRoundKey(Nr, state, RoundKey);
}

Round 1…Nr

接下来的Nr轮加密，除最后一轮外每一轮都依次执行字节代换、行移位、列混合、轮密钥加。最后一轮加密（第Nr轮）没有列混合操作。

轮密钥加：AddRoundKey

1
2
3
4
5
6
7
8
9
10
11
static void AddRoundKey(uint8_t round, state_t* state, const uint8_t* RoundKey)
{
  uint8_t i,j;
  for (i = 0; i < 4; ++i)
  {
    for (j = 0; j < 4; ++j)
    {
      (*state)[i][j] ^= RoundKey[(round * Nb * 4) + (i * Nb) + j];
    }
  }
}

轮密钥加是将state与当前轮对应的RoundKey进行GF(2^8)上的相加，也就是二进制上的异或操作。

字节代换：getSBoxValue

1
2
3
4
static uint8_t getSBoxValue(uint8_t num)
{
  return sbox[num];
}

字节代换是取当前值在GF(2^8)上的逆元，为了提高效率AES就将每个值对应的逆元的值直接存储在SBox中。

行移位：ShiftRows

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
static void ShiftRows(state_t* state)
{
  uint8_t temp;

  // Rotate first row 1 columns to left  
  temp           = (*state)[0][1];
  (*state)[0][1] = (*state)[1][1];
  (*state)[1][1] = (*state)[2][1];
  (*state)[2][1] = (*state)[3][1];
  (*state)[3][1] = temp;

  // Rotate second row 2 columns to left  
  temp           = (*state)[0][2];
  (*state)[0][2] = (*state)[2][2];
  (*state)[2][2] = temp;

  temp           = (*state)[1][2];
  (*state)[1][2] = (*state)[3][2];
  (*state)[3][2] = temp;

  // Rotate third row 3 columns to left
  temp           = (*state)[0][3];
  (*state)[0][3] = (*state)[3][3];
  (*state)[3][3] = (*state)[2][3];
  (*state)[2][3] = (*state)[1][3];
  (*state)[1][3] = temp;
}

行移位让state的字节在其所在行中进行循环移动位置。

列混合：MixColumns

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void MixColumns(state_t* state)
{
  uint8_t i;
  uint8_t Tmp, Tm, t;
  for (i = 0; i < 4; ++i)
  {  
    t   = (*state)[i][0];
    Tmp = (*state)[i][0] ^ (*state)[i][1] ^ (*state)[i][2] ^ (*state)[i][3] ;
    Tm  = (*state)[i][0] ^ (*state)[i][1] ; Tm = xtime(Tm);  (*state)[i][0] ^= Tm ^ Tmp ;
    Tm  = (*state)[i][1] ^ (*state)[i][2] ; Tm = xtime(Tm);  (*state)[i][1] ^= Tm ^ Tmp ;
    Tm  = (*state)[i][2] ^ (*state)[i][3] ; Tm = xtime(Tm);  (*state)[i][2] ^= Tm ^ Tmp ;
    Tm  = (*state)[i][3] ^ t ;              Tm = xtime(Tm);  (*state)[i][3] ^= Tm ^ Tmp ;
  }
}

列混合用到了GF(2^8)上的乘法，目前还没有学明白，后面再补（挖坑+1）

reverse中的AES128

AES这种算法在CTF的reverse题目中还是比较常见的，出题人可以直接把AES原封不动放到题目里，也可以是魔改一部分代码，甚至是把AES最核心的GF(2^8)运算作为出题点。

常见的识别AES算法的方法有：

  1. 使用findcrypt判断是否存在aes的sbox
  2. 程序中使用的加密算法密钥、明文密文是16字节，有一个10次的循环……（当然这个不一定就是aes）
  3. 存在将16字节的数据经过一定计算操作并写入到176字节的空间
  4. 当然上面都是我为了凑字数写的，最重要的还是学好密码学，掌握算法的原理然后多积累逆向经验