AESNI is an SIMD instruction set developed by Intel for the x64 architecture, specifically designed to provide hardware acceleration for the AES encryption algorithm. Anyone who has some understanding of SIMD is generally aware of the existence of AESNI. However, due to the asymmetric structure of AES itself and the special design of AESNI, there are still many details and theoretical knowledge that need to be understood in order to write correct code when using AESNI. Taking N1CTF 2021‘s easyRE as an example, I summarized my understanding of AESNI, and please correct me if there are any inaccuracies.The structure of AES takes AES128 as an example; its structure is a 10-round 4×4 permutation network, and the last round lacks a MixColumns transformation compared to the ordinary rounds.
It is important to note that although there are 10 rounds, if you look closely at the upper left corner, you can find that there is an AddRoundKey operation before entering the first round, so there are a total of 11 round keys. The beginning and end of the encryption process both involve AddRoundKey; this design is called whitening. The purpose of whitening is also easy to understand, as the other three operations do not involve keys and are merely fixed transformations. If placed at the beginning or end of the encryption, anyone can directly perform the inverse transformation to undo it. Therefore, the existence of these operations does not enhance the algorithm’s security and is thus meaningless.AESENC and AESECLAST are the two instructions used for encryption in AESNI, and they are also the easiest to understand. Any SIMD instruction can refer to the Intel® Intrinsics Guide,<span>AESENC</span> performs the ShiftRows, SubBytes, MixColumns, and AddRoundKey operations sequentially on the input. Among them, SubBytes operates on bytes, so it can be interchanged with ShiftRows. Comparing with the above diagram, it can be found that <span>AESENC</span> is exactly a normal round of encryption shown in the diagram.<span>AESENCLAST</span> performs ShiftRows, SubBytes, and AddRoundKey operations sequentially on the input, which is equivalent to the last round of encryption shown in the diagram.The 0th round key XOR operation can be completed using the <span>PXOR</span> instruction, so a complete AES encryption process is as follows (pt is plaintext, k[x] is round key, ct is ciphertext):
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 consists of 9 rounds of <span>AESENC</span> + 1 round of <span>AESENCLAST</span>, this is easy to remember, but it is easy to overlook that the 0th round key is directly <span>PXOR</span>, which requires extra attention.The decryption algorithm of AES and the equivalent decryption algorithm The asymmetric design of AES is quite misleading; when carefully observing the decryption process on the right side of the diagram, it can be found that decryption also involves whitening + 9 ordinary rounds + 1 last round. Here it should be noted that if we consider the reverse process of encryption directly, decryption should first decrypt the last round and then decrypt the ordinary rounds. However, the diagram clearly does not follow this order.If we do not consider the division of rounds and only look at the four separate operations, the decryption operations are exactly the inverse order of the encryption operations. But if we want to divide a series of operations into different rounds, there are many ways to partition them. The diagram shows the most common partitioning method, where the decryption round is not the inverse operation of the encryption round, and this partitioning method is the first counterintuitive aspect of AES design.In the diagram’s partitioning, one decryption round includes InvShiftRows, InvSubBytes, AddRoundKey, and InvMixColumns operations, while the last round also removes the InvMixColumns operation.AES was originally named Rijndael, and in the original proposal of Rijndael, the designer also provided an “equivalent decryption algorithm” (see 5.3.3 The equivalent inverse cipher structure). In the equivalent decryption, the order of AddRoundKey and InvMixColumns operations in the decryption round is swapped, forming a symmetric structure similar to the encryption round where AddRoundKey is always at the end (InvSubBytes and InvShiftRows can be interchanged):
This swap is not an equivalent transformation; InvMixColumns transforms each column’s 4 bytes over GF(2^8) by multiplying it with a 4×4 matrix to produce a new 1×4 vector, while AddRoundKey performs XOR operations on each byte. In GF(2^8), XOR is equivalent to addition, and based on the distributive property of multiplication, it can be concluded that if AddRoundKey is moved to InvMixColumns, the new RoundKey should be the original RoundKey multiplied by the same 4×4 matrix to ensure that the computation result remains unchanged.Upon further examining the decryption flowchart, the 0th round key is directly XORed, and the last round key is in the last round of decryption; both of these round keys do not involve the swap of InvMixColumns. Therefore, in the equivalent decryption process, in addition to needing to reverse the encryption round keys, the round keys from 1 to n-1 should first undergo InvMixColumns to transform into keys for decryption.AES encryption and equivalent decryption rounds have a peculiar aesthetic symmetry, but the round keys differ, which is the second counterintuitive aspect of AES design.
AESDEC, AESDECLAST, and AESIMC
According to the design white paper of AESNI, Intel also adopts equivalent decryption. Referencing the Intel® Intrinsics Guide, note that the <span>AESDEC</span> instruction is not the inverse of the <span>AESENC</span> instruction, and the <span>AESDECLAST</span> is also not the inverse of the <span>AESENCLAST</span>. A complete AES decryption process is as follows (pt is plaintext, k[x] is round key, ct is ciphertext):
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
where k[0] and k[n] are the same as the encryption keys, while k'[1]~k'[n-1] are the results of applying InvMixColumns transformation to the encryption keys k[1]~k[n-1]. To this end, Intel specially provided the <span>AESIMC</span> instruction, which performs a single InvMixColumns operation.
AESKEYGENASSIST and PCLMULQDQ
<span>AESKEYGENASSIST</span> is used in key expansion, and the specific usage can be referred to on page 19 of the [design white paper].<span>PCLMULQDQ</span>, full name Carry-Less Multiplication Quadword, is used to multiply two polynomials over the GF(2^128) field.<span>PCLMULQDQ</span> itself does not belong to the AESNI instruction set, but in addition to accelerating CRC32, <span>PCLMULQDQ</span> can also calculate the GMAC of GCM, and thus it frequently appears in SIMD encryption algorithms. The AES-256-GCM implementation in Libsodium is a perfect example.
Advanced Usage of AESNI
Isolating the 4 Operations of AES
When I first attempted to use AESNI, I was quite puzzled as to why Intel adopted equivalent encryption, which requires adding an extra AESIMC operation to generate the decryption key. After reading the white paper, I finally understood this ingenious design.On page 34 of the white paper, a method to implement the 4 operations of AES individually using AESNI is provided:
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 can be directly completed using the SSSE3 <span>PSHUFB</span> instruction, while SubBytes first performs a reverse shuffle and then uses a zero key for last round encryption to eliminate the other two operations of the last round. MixColumns combines encryption and decryption, utilizing the properties of the last round to retain MixColumns. This magical stitching method is truly impressive.In the previous section, it was mentioned that converting from encryption key to equivalent decryption key requires the <span>AESIMC</span> operation, but if the equivalent decryption key is known, how can the encryption key be obtained? AESNI does not have a direct MixColumns operation, but as mentioned above, it can be produced by combining <span>AESDECLAST</span> and <span>AESENC</span>. Furthermore, upon checking the Intel® Intrinsics Guide, it was found that on the Skylake microarchitecture, the latency and throughput of <span>AESIMC</span> are both twice that of <span>AESENC</span>, so it is boldly speculated that <span>AESIMC</span> internally is also a combination of <span>AESENCLAST</span> and <span>AESDEC</span>.
Using AESNI to Accelerate Other Algorithms
The flexible design of AESNI allows it to be used to implement larger permutation networks. As mentioned earlier, AES was originally named Rijndael, and referring to the Rijndael proposal, Rijndael actually has three variants with block sizes (not key sizes) of 128, 192, and 256, with only the 128 size being selected as AES. The white paper also provides other Rijndael implementations using AESNI, such as 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 is an 8×4 permutation network. SubBytes and AddRoundKey are byte-level transformations that work normally, while MixColumns transforms a 1×4 vector for each column, which also works normally; only ShiftRows requires using SSE4.1’s <span>PBLENDB</span> and SSSE3’s <span>PSHUFB</span> to adjust the offset. The 8×4 permutation network is double the size of the 4×4 network, so each round requires two <span>AESENC</span> instructions, and similarly two <span>AESENCLAST</span> instructions are needed at the end. This intricate yet aesthetically pleasing code is what attracts people to computing.The “non-linear transformation τ” in the national secret SM4 algorithm is actually an S-box over the binary field GF(2^8), which differs from AES’s S-box only in the generating polynomial p. According to group theory knowledge, these two GF(2^8) are isomorphic (please correct me if I’m wrong), and elements over the two fields can be transformed through algebraic operations. Markku-Juhani O. Saarinen designed an SM4 implementation accelerated by AESNI based on this. See sm4ni.
N1CTF 2021 easyRe
The problem is located here, and the main logic of the encryption function is to perform a series of encryption and scrambling operations on the plaintext in xmm0:
Although the program uses AVX2 instructions starting with ‘v’, it only utilizes xmm registers, allowing the decryption algorithm to be written using only SSE. First, use capstone to analyze the function body and generate an expression tree. One leaf node of this tree is the input, while the root node is the ciphertext. Then, transform the tree by rotating left and right to bring the input node to the top root. At this point, the corresponding expression of the tree will be the decryption expression.During the rotation process, <span>VPXOR</span>, <span>VPADDQ</span>, <span>VPSUBQ</span> can easily yield their inverse operations, while <span>VPSHUFD</span> rearranges the 4 32-bit values in xmm0, and it can similarly be rearranged back. When encountering the <span>VAESENC</span> instruction, first extract the entire <span>VAESENC</span> + <span>VAESENCLAST</span> block, invert the intermediate round key using <span>VAESIMC</span>, and then generate the opposite decryption tree. Note that the previously mentioned 0th round key of AES encryption is directly <span>VPXOR</span>; when the instruction before <span>VAESENC</span> is not <span>VPXOR</span>, it can be considered as having XORed with a zero key, making the last instruction of the decryption tree <span>VAESDECLAST</span> use a round key of 0. When encountering the <span>VAESDEC</span> decryption block, the processing method is similar, but the previously mentioned <span>VAESDECLAST</span> + <span>VAESENC</span> is used to synthesize the MixColumns operation and transform the round key.Based on the expression tree, a JIT was written, and the code generated by the JIT can be compiled and run to obtain the 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))
When compiling, add the <span>-maes</span> option to enable AESNI, and it will generate a program with the SSE instruction set. If you use <span>-march=native</span> to enable more instruction sets, it can automatically compile a program with AVX2 + VAES. Today’s compilers are quite intelligent.Flag: <span>n1ctf{Easy_AVX!}</span> (not easy at all)
- End -
Recommended Articles
【Technical Share】CVE-2019-10999 Dlink IP Camera Buffer Overflow
【Technical Share】Analysis of Dirty Cow 1_mmap How to Map Memory to File
【Technical Share】A Journey into Synology NAS Series - Introduction to Synology NAS
Click "Read Original" for more content