【技術分享】Intel AES-NI使用入門 - 網安 - 專業的網絡安全產業、社區、知識平臺

AESNI是Intel開發的一種x64架構的SIMD指令集，專門為AES加密算法提供硬件加速，對SIMD有一定了解的人基本都知道AESNI的存在。但由于AES本身的不對稱結構，以及AESNI的特殊設計，在實際使用AESNI時，還是有很多細節和理論知識需要了解，才能寫出正確的代碼。以N1CTF 2021中的easyRE為例，總結了一下自己對AESNI的理解，若有不對的地方敬請指正。

AES的結構

以AES128為例，其結構是10輪4×4排列置換網絡，尾輪相較普通輪缺少一個MixColumns變換。

需要注意的是雖然輪數是10，但是仔細看左上角可以發現進入首輪之前還有一個AddRondKey操作，所以共有11個輪密鑰。加密的開頭和結尾均為AddRondKey，這種設計叫做白化。白化的用意也容易理解，由于其它3種操作不涉及密鑰，僅為固定變換，如果放在加密的開頭或結尾，任何人都可以直接進行逆變換解除之，這些操作的存在不能提升算法的安全性，因此沒有意義。

AESENC和AESECLAST

這兩條指令是AESNI中用于加密的指令，也是最容易理解的指令。任何SIMD指令都可以參考Intel? Intrinsics Guide，AESENC對輸入依次進行ShiftRows，SubBytes，MixColumns，AddRoundKey操作。其中SubBytes是對字節的操作，因此可以和ShiftRows互換，與上面的圖比較，可以發現AESENC恰好是上圖的一個普通輪加密。

AESENCLAST對輸入依次進行ShiftRows，SubBytes，AddRoundKey操作，相當于上圖的尾輪加密。

第0個輪密鑰異或操作可以用PXOR指令完成，因此一個完整的AES加密過程如下（pt是明文，k[x]是輪密鑰，ct是密文）：

pxor pt, k[0]
aesenc pt, k[1]
aesenc pt, k[2]
...
aesenc pt, k[n-1]
aesenclast pt, k[n]
movdqa ct, pt

AES是9輪AESENC+1輪AESENCLAST這一點很容易記住，但第0個輪密鑰是直接PXOR這一點很容易被忽視掉，需要多加注意。

AES的解密算法和等價解密算法

AES的不對稱設計十分具有迷惑性，再仔細觀察上圖右側的解密過程，可以發現解密時也是白化+9輪普通輪+1輪尾輪。

這里要注意，如果直接按照加密的逆過程來考慮，那么解密應該是先解密尾輪，再解普通輪，然而上圖顯然不是這樣。

如果不考慮輪的劃分，只看分開的4種操作的話，解密的操作恰為加密操作的逆序。但若想將一系列的操作劃分成不同的輪，就有很多種劃分方式。上圖是最常見的劃分方式，其中解密輪并不是加密輪的逆運算，這一劃分方式是AES的設計中第一個違反直覺的地方。

在上圖的劃分中，一個解密輪包括InvShiftRows，InvSubBytes，AddRoundKey，InvMixColumns操作，尾輪同樣是移除InvMixColumns操作。

AES原名Rijndael，在Rijndael最初的提案中，設計者另外給出了一種“等價解密算法”（參見5.3.3 The equivalent inverse cipher structure），在等價解密中，解密輪的AddRoundKey和InvMixColumns操作順序互換，形成了一種和加密輪相同，AddRoundKey均在最后的對稱結構（InvSubBytes和InvShiftRows本身可以互換順序）：

這一交換并非等價變換，InvMixColumns是對每一列的4個字節在GF(2^8)上乘上一個4×4矩陣，得到一個新的1×4向量，而AddRoundKey是對每個字節進行異或操作。在GF(2^8)上，異或操作即為加法運算，根據乘法分配律就可以推出，若將AddRoundKey移至InvMixColumns后，新的RoundKey應為原RoundKey乘上同樣的4×4矩陣，才能保證運算結果不變。

再仔細觀察解密的流程圖，第0個輪密鑰直接異或，最后一個輪密鑰在解密的尾輪中，這兩個輪密鑰均不涉及InvMixcolumns的交換，因此在等價解密的過程中，除了需要將加密的輪密鑰逆序外，第1~第n-1個輪密鑰應先進行InvMixColumns，變換成解密用密鑰。

AES加密和等價解密的輪之間具有一種奇特的對稱美學，但輪密鑰不同，這是AES的設計中第二個違反直覺的地方。

AESDEC，AESDECLAST和AESIMC

根據AESNI的設計白皮書，Intel同樣采用了等價解密，參考Intel? Intrinsics Guide，注意AESDEC指令不是AESENC指令的逆過程，AESDECLAST同樣不是AESENCLAST的逆過程。一個完整的AES解密過程如下（pt是明文，k[x]是輪密鑰，ct是密文）：

pxor ct, k[n]
aesdec ct, k'[n-1]
aesdec ct, k'[n-2]
...
aesdec ct, k'[1]
aesdeclast ct, k[0]
movdqa pt, ct

其中k[0]和k[n]和加密密鑰相同，而k’[1]~k’[n-1]是加密密鑰k[1]~k[n-1]經InvMixColumns變換的結果。為此，Intel特意提供了AESIMC指令，該指令即為進行單個的InvMixColumns操作。

AESKEYGENASSIST和PCLMULQDQ

AESKEYGENASSIST用在密鑰擴展中，具體的用法可以參考[設計白皮書]19頁。

PCLMULQDQ全稱Carry-Less Multiplication Quadword，是對兩個GF(2^128)域上的多項式相乘。PCLMULQDQ本身并不屬于AESNI指令集，但除了用于加速CRC32外，PCLMULQDQ還能計算GCM的GMAC，因此經常出現在SIMD加密算法中。Libsodium中的AES-256-GCM實現就是一個完美的示例。

AESNI的進階用法

分離AES的4種操作

最初嘗試AESNI時曾經十分不解，為什么Intel要采用等價加密，使得生成解密密鑰還要額外加上AESIMC操作，后來讀完了白皮書才搞懂這一精巧的設計。

白皮書第34頁給出了用AESNI單獨實現AES的4種操作的方法：

Isolating ShiftRows 
 PSHUFB xmm0, 0x0b06010c07020d08030e09040f0a0500 
Isolating InvShiftRows 
 PSHUFB xmm0, 0x0306090c0f0205080b0e0104070a0d00 
Isolating MixColumns 
 AESDECLAST xmm0, 0x00000000000000000000000000000000 
 AESENC xmm0, 0x00000000000000000000000000000000 
Isolating InvMixColumns 
 AESENCLAST xmm0, 0x00000000000000000000000000000000 
 AESDEC xmm0, 0x00000000000000000000000000000000 
Isolating SubBytes 
 PSHUFB xmm0, 0x0306090c0f0205080b0e0104070a0d00 
 AESENCLAST xmm0, 0x00000000000000000000000000000000 
Isolating InvSubBytes 
 PSHUFB xmm0, 0x0b06010c07020d08030e09040f0a0500 
 AESDECLAST xmm0, 0x00000000000000000000000000000000

ShiftRows可以直接用SSSE3的PSHUFB指令完成，而SubBytes則是先反向shuffle，再用0密鑰進行尾輪加密，消掉尾輪的另外兩種操作。MixColumns則結合加密和解密，利用尾輪的特性將MixColumns保留下來。這個神奇的拼接方式令人嘖嘖稱奇。

上一節提到由加密密鑰變換為等價解密密鑰要經過AESIMC操作，但如果已知等價解密密鑰，如何獲得加密密鑰？AESNI里沒有直接的MixColumns操作，但根據上文，可以用AESDECLAST和AESENC組合產生。

而查詢Intel? Intrinsics Guide，發現Skylake微架構上，AESIMC的Latency和Throughput均是AESENC的兩倍，因此斗膽猜測AESIMC內部也是AESENCLAST和AESDEC的拼接。

用AESNI加速其它算法

AESNI的靈活設計使得它可以用來實現更大的排列置換網絡，前文提到AES原名Rijndael，而參考Rijndael的提案，Rijndael實際上有塊大小（不是密鑰大小）為128，192，256的三種變種，只有128大小的Rijndael被選為AES。白皮書則給出了AESNI實現的其它Rijndael，例如Rijndael-256：

#include <emmintrin.h>#include <smmintrin.h>void Rijndael256_encrypt(unsigned char* in,                         unsigned char* out,                         unsigned char* Key_Schedule,                         unsigned long long length,                         int number_of_rounds) {
  __m128i tmp1, tmp2, data1, data2;
  __m128i RIJNDAEL256_MASK =
      _mm_set_epi32(0x03020d0c, 0x0f0e0908, 0x0b0a0504, 0x07060100);
  __m128i BLEND_MASK =
      _mm_set_epi32(0x80000000, 0x80800000, 0x80800000, 0x80808000);
  __m128i* KS = (__m128i*)Key_Schedule;  int i, j;  for (i = 0; i < length / 32; i++) { /* loop over the data blocks */
    data1 = _mm_loadu_si128(&((__m128i*)in)[i * 2 + 0]); /* load data block */
    data2 = _mm_loadu_si128(&((__m128i*)in)[i * 2 + 1]);
    data1 = _mm_xor_si128(data1, KS[0]); /* round 0 (initial xor) */
    data2 = _mm_xor_si128(data2, KS[1]);    /* Do number_of_rounds-1 AES rounds */
    for (j = 1; j < number_of_rounds; j++) {      /*Blend to compensate for the shift rows shifts bytes between two
      128 bit blocks*/
      tmp1 = _mm_blendv_epi8(data1, data2, BLEND_MASK);
      tmp2 = _mm_blendv_epi8(data2, data1, BLEND_MASK);      /*Shuffle that compensates for the additional shift in rows 3 and 4
      as opposed to rijndael128 (AES)*/
      tmp1 = _mm_shuffle_epi8(tmp1, RIJNDAEL256_MASK);
      tmp2 = _mm_shuffle_epi8(tmp2, RIJNDAEL256_MASK);      /*This is the encryption step that includes sub bytes, shift rows,
      mix columns, xor with round key*/
      data1 = _mm_aesenc_si128(tmp1, KS[j * 2]);
      data2 = _mm_aesenc_si128(tmp2, KS[j * 2 + 1]);
    }
    tmp1 = _mm_blendv_epi8(data1, data2, BLEND_MASK);
    tmp2 = _mm_blendv_epi8(data2, data1, BLEND_MASK);
    tmp1 = _mm_shuffle_epi8(tmp1, RIJNDAEL256_MASK);
    tmp2 = _mm_shuffle_epi8(tmp2, RIJNDAEL256_MASK);
    tmp1 = _mm_aesenclast_si128(tmp1, KS[j * 2 + 0]); /*last AES round */
    tmp2 = _mm_aesenclast_si128(tmp2, KS[j * 2 + 1]);
    _mm_storeu_si128(&((__m128i*)out)[i * 2 + 0], tmp1);
    _mm_storeu_si128(&((__m128i*)out)[i * 2 + 1], tmp2);
  }
}

Rijndael-256是8×4排列置換網絡，SubBytes，AddRoundKey是字節層面變換，可以正常工作，而MixColumns是對每列的1×4向量進行變換，同樣正常工作，只有ShiftRows需要利用SSE4.1的PBLENDB和SSSE3的PSHUFB調整偏移。8×4排列置換網絡是4×4的兩倍，因此每一輪需要兩個AESENC指令，結尾同樣兩個AESENCLAST。這種錯落有致又不失美感的代碼正是計算機吸引入的地方。

國密SM4算法中的“非線性變換τ”實際上也是一個二進制域GF(2^8)上的S盒，和AES的S盒相比，只有生成多項式p不同。根據群論知識，這兩個GF(2^8)是同構的（若有不對請指正），兩個域上的元素可通過代數運算互相變換。Markku-Juhani O. Saarinen據此設計了利用AESNI加速的SM4實現。參見sm4ni。

N1CTF 2021 easyRe

題目位于這里，加密函數的主要邏輯是對xmm0中的明文進行一系列的加密和打亂操作：

雖然程序是v開頭的AVX2指令集，但只用到了xmm寄存器，可以只用SSE寫出解密算法。先利用capstone解析一遍函數體，生成一個表達式樹，該樹的一個葉節點是輸入，而該樹的根節點是密文。再對該樹進行變換，通過左右旋轉，設法將輸入節點轉至最頂端根部，此時該樹對應的表達式就是解密表達式。

在旋轉過程中，VPXOR，VPADDQ，VPSUBQ很容易求出逆運算，VPSHUFD是對xmm0里的4個32位值重新排列，同樣用VPSHUFD可以排列回去。遇到VAESENC指令時，首先將整個VAESENC+VAESENCLAST塊提取出來，對中間的輪密鑰VAESIMC求逆，再生成相反的解密樹。注意前文提到過AES加密的第0個輪密鑰是直接VPXOR異或，碰到VAESENC指令前不是VPXOR時，可以看作是異或了一個全0密鑰，那么解密樹的最后一條指令VAESDECLAST的輪密鑰就是0。遇VAESDEC解密塊時處理方法類似，但要使用前文提到的VAESDECLAST+VAESENC合成出MixColumns操作，對輪密鑰進行變換。

根據表達式樹寫出了一個JIT，JIT產生的代碼編譯后運行就能得到flag：

import sysimport capstoneimport binascii
sys.setrecursionlimit(0x100000)class Node:
    def __init__(self):
        self.emitted = False
        self.parent = None
    def __str__(self):
        return "v"+hex(id(self))    def emit(self, f):
        if self.emitted:            return
        self.emitted = True
        self.do_emit(f)class Constant(Node):
    def __init__(self, c):
        super().__init__()
        self.c = c    def do_emit(self, f):
        if self.c == 0:
            f.write("__m128i {}=_mm_setzero_si128();\n".format(self))        else:
            f.write("__m128i {}=_mm_set_epi64x({}ULL,{}ULL);\n".format(
                self, hex(self.c >> 64), hex(self.c & ((1 << 64)-1))))class Binary(Node):
    def __init__(self, a, b):
        super().__init__()
        self.a = a
        self.b = b
        a.parent = self
        b.parent = selfclass Add(Binary):
    def __init__(self, a, b):
        super().__init__(a, b)    def do_emit(self, f):
        self.a.emit(f)
        self.b.emit(f)
        f.write("__m128i {}=_mm_add_epi64({},{});\n".format(
            self, self.a, self.b))class Sub(Binary):
    def __init__(self, a, b):
        super().__init__(a, b)    def do_emit(self, f):
        self.a.emit(f)
        self.b.emit(f)
        f.write("__m128i {}=_mm_sub_epi64({},{});\n".format(
            self, self.a, self.b))class Xor(Binary):
    def __init__(self, a, b):
        super().__init__(a, b)    def do_emit(self, f):
        self.a.emit(f)
        self.b.emit(f)
        f.write("__m128i {}=_mm_xor_si128({},{});\n".format(
            self, self.a, self.b))class Aes(Node):
    def __init__(self, base, key, is_enc, is_last):
        super().__init__()
        self.base = base
        self.key = key
        self.is_enc, self.is_last = is_enc, is_last
        base.parent = self
        key.parent = self    def do_emit(self, f):
        self.base.emit(f)
        self.key.emit(f)
        f.write("__m128i {}=_mm_aes{}{}_si128({},{});\n".format(
            self, "enc" if self.is_enc else "dec", "last" if self.is_last else "", self.base, self.key))class Aesimc(Node):
    def __init__(self, a, is_imc):
        super().__init__()
        self.a = a
        self.is_imc = is_imc
        a.parent = self    def do_emit(self, f):
        self.a.emit(f)        if self.is_imc:
            f.write("__m128i {}=_mm_aesimc_si128({});\n".format(self, self.a))        else:
            f.write("__m128i {}=_mm_aesenc_si128(_mm_aesdeclast_si128({},zero),zero);\n".format(
                self, self.a))class Shuffle(Node):
    def __init__(self, a, x):
        super().__init__()
        self.a = a
        self.x = x
        a.parent = self    def do_emit(self, f):
        self.a.emit(f)
        f.write("__m128i {}=_mm_shuffle_epi32({},{});\n".format(
            self, self.a, hex(self.x)))def flip(root):
    parent = root.parent    if isinstance(parent, Constant):        return parent    elif isinstance(parent, Xor):        if root == parent.a:            return Xor(parent.b, flip(parent))        else:            return Xor(parent.a, flip(parent))    elif isinstance(parent, Add):        if root == parent.a:            return Sub(flip(parent), parent.b)        else:            return Sub(flip(parent), parent.a)    elif isinstance(parent, Sub):        if root == parent.a:            return Add(flip(parent), parent.b)        else:            return Sub(parent.a, flip(parent))    elif isinstance(parent, Shuffle):
        x = parent.x
        shuffle = []        for i in range(4):
            shuffle.append(x & 3)
            x >>= 2
        assert set(shuffle) == set({0, 1, 2, 3})
        x = 0
        for i in range(4):
            x <<= 2
            x += shuffle.index(3-i)        return Shuffle(flip(parent), x)    elif isinstance(parent, Aesimc):        return Aesimc(flip(parent), not parent.is_imc)    elif isinstance(parent, Aes):
        keys = [parent]
        p = parent.parent        while True:            if isinstance(p, Aes):
                keys.append(p)                if p.is_last:                    break
                p = p.parent            else:                raise ValueError
        keys.reverse()
        r = Xor(flip(p), keys[0].key)
        r_keys = {}        for i in range(1, len(keys)):            if id(keys[i].key) not in r_keys:
                r_keys[id(keys[i].key)] = Aesimc(keys[i].key, keys[i].is_enc)
            r = Aes(r, r_keys[id(keys[i].key)],                    not keys[i].is_enc, False)        return Aes(r, Constant(0), not keys[0].is_enc, True)    else:        raise ValueError
xmmnames = ['xmm{}'.format(i) for i in range(16)]
xmm = [None for i in range(16)]
target = Node()
xmm[0] = target
memory = {}
c = ['2f0fc4f2839a1d5401ead9842fc23d00',     '24e1c94761c31694cdb7d3a38fb0c100',     '2af5fcb6d4373ceac4590d4f86956d00',     'cbc6b50249b0b519a2620a3cc73d9200',     '60a876c1193162a02a1531a79d6a5900',     'd083cfb2f3a048c4cf47af9bcaaefa00',     'eb93d59f3756816e2671cd0d1c73bf00',     'c32de58cdbcf9fdd7de74f364a594b00',     '6055580a46572c4e6a591ddd77c0ce00',     '13bf3e7536d86ce89d81348f6f10e000', ]for i in range(len(c)):
    memory[0x620-i *           0x10] = Constant(int.from_bytes(binascii.a2b_hex(c[i]), 'little'))
c = capstone.Cs(capstone.CS_ARCH_X86, capstone.CS_MODE_64)
c.detail = Trueit = c.disasm(open('easyRe', 'rb').read()[0xc4d:0x19d90], 0x100000C4D)for ins in it:    if ins.mnemonic == 'vmovdqa':
        a, b = ins.op_str.split(',')
        a, b = a.strip(), b.strip()        if a in xmmnames and b not in xmmnames:            assert b.startswith('xmmword ptr [rbp - ')
            off = int(b[19:b.index(']')], 16)            assert off in memory
            xmm[xmmnames.index(a)] = memory[off]        elif b in xmmnames and a not in xmmnames:            assert a.startswith('xmmword ptr [rbp - ')
            off = int(a[19:a.index(']')], 16)
            memory[off] = xmm[xmmnames.index(b)]        else:
            xmm[xmmnames.index(a)] = xmm[xmmnames.index(b)]    elif ins.mnemonic == 'vpxor':
        a, b, c = ins.op_str.split(',')
        a, b, c = a.strip(), b.strip(), c.strip()        if c in xmmnames:
            xmm[xmmnames.index(a)] = Xor(
                xmm[xmmnames.index(b)], xmm[xmmnames.index(c)])        else:            assert c.startswith('xmmword ptr [rbp - ')
            off = int(c[19:c.index(']')], 16)
            xmm[xmmnames.index(a)] = Xor(
                xmm[xmmnames.index(b)], memory[off])    elif ins.mnemonic == 'vpaddq' or ins.mnemonic == 'vpsubq':
        a, b, c = ins.op_str.split(',')
        a, b, c = a.strip(), b.strip(), c.strip()        if c in xmmnames:
            xmm[xmmnames.index(a)] = (Add if ins.mnemonic == 'vpaddq' else Sub)(
                xmm[xmmnames.index(b)], xmm[xmmnames.index(c)])        else:            assert c.startswith('xmmword ptr [rbp - ')
            off = int(c[19:c.index(']')], 16)
            xmm[xmmnames.index(a)] = (Add if ins.mnemonic == 'vpaddq' else Sub)(
                xmm[xmmnames.index(b)], memory[off])    elif ins.mnemonic == 'vpshufd':
        a, b, c = ins.op_str.split(',')
        a, b, c = a.strip(), b.strip(), c.strip()
        c = int(c, 16)
        xmm[xmmnames.index(a)] = Shuffle(
            xmm[xmmnames.index(b)], c)    elif ins.mnemonic == 'vaesenc' or ins.mnemonic == 'vaesdec':
        is_enc = ins.mnemonic == 'vaesenc'
        a, b, c = ins.op_str.split(',')
        a, b, c = a.strip(), b.strip(), c.strip()
        xmm[xmmnames.index(a)] = Aes(xmm[xmmnames.index(b)],
                                     xmm[xmmnames.index(c)], is_enc, False)    elif ins.mnemonic == 'vaesenclast' or ins.mnemonic == 'vaesdeclast':
        is_enc = ins.mnemonic == 'vaesenclast'
        a, b, c = ins.op_str.split(',')
        a, b, c = a.strip(), b.strip(), c.strip()
        xmm[xmmnames.index(a)] = Aes(xmm[xmmnames.index(b)],
                                     xmm[xmmnames.index(c)], is_enc, True)    elif ins.mnemonic == 'vaesimc':
        a, b = ins.op_str.split(',')
        a, b = a.strip(), b.strip()
        xmm[xmmnames.index(a)] = Aesimc(xmm[xmmnames.index(b)], True)    elif ins.mnemonic == 'movabs' or ins.mnemonic == 'mov':        pass
    else:
        print(ins)        raise ValueError
xmm[0].parent = Constant(0x79eeb3fa8c39dbd77bc066c7647d0b72)
target = flip(target)
f = open('a.c', 'w')
f.write('''
#include <immintrin.h>
#include <stdio.h>
int main(){
__m128i zero=_mm_setzero_si128();
''')
target.emit(f)
f.write('''char pt[16];
_mm_storeu_si128((__m128i*)pt, {});
fwrite(pt,16,1,stdout);
return 0;
}}
'''.format(target))

編譯的時候加上-maes選項打開AESNI，會生成SSE指令集的程序，如果用-march=native再多打開一些指令集，還能自動編譯出AVX2+VAES的程序，現在的編譯器也是十分智能。

flag: n1ctf{Easy_AVX!}（一點都不easy）