Clinale's Blog
0%

Emulating x86 AES Intrinsics on ARMv8-A

发表于 更新于 分类于

本篇博客翻译自Emulating x86 AES Intrinsics on ARMv8-A。

最近，我需要移植一些 C 加密代码才能在 ARMv8-A(aarch64) 处理器上运行。问题在于代码使用了一些 x86 AES 内部函数，编译器在面向 ARM 体系结构时无法识别这些内部函数。ARMv8-A确实有一个可选的加密扩展，其中包括几个 AES 指令，但它们的语义与 x86 指令略有不同。我对 AES 没有太多经验，最初发现这非常令人困惑，因为我假设所有 AES 实现都需要以相同的方式工作（毕竟 AES 是一个标准！事实证明，这两种方法都足以实现 AES，但 x86 和 ARM 选择以不同的方式解决问题。

关于 AES 的背景资料

高级加密标准(AES) 是常见的对称加密算法，它使用密钥来加密和解密数据。AES 一次加密 16 个字节，并使用 128 位到 256 位的密钥大小。16 字节数据块通过一系列被称为轮次 的步骤进行转换。步骤的顺序是固定的，但轮次数可能因密钥大小而异。例如，AES 标准规定，对于 128 位密钥大小，AES 加密算法将迭代 10 轮。

AES 每一轮步骤定义为对 16 字节的 $4 \times 4$ 矩阵执行的操作，如下所示：

|b0 b4 b8 b12|
|b1 b5 b9 b13|
|b2 b6 b10 b14|
|b3 b7 b11 b15|

其中 bN 是 16 字节数据块的第 N 个字节。

AES 每一轮的操作定义如下：

  1. SubBytes — 使用查找表将每个字节映射到唯一的字节值
  2. ShiftRows — 将每行中的字节循环左移不同的值
  3. MixColumns — 通过组合每列中的四个字节进行列混淆
  4. AddRoundKey — 将矩阵中的每个字节和轮密钥进行异或

Intel 与 ARM 中 AES 加密的比较

Intel 在 x86 中提供了两条用于加密的 AES 指令，它们与 AES 轮次非常匹配：

  1. AESENC — AES Encrypt（Normal Round）

    a. ShiftRows

    b. SubBytes

    c. MixColumns

    d. AddRoundKey

  2. AESENCLAST — AES Encrypt（Last Round, No MixColumns）

    a. ShiftRows

    b. SubBytes

    c. AddRoundKey

（你可能会注意到这里的 ShiftRows 和 SubBytes 与 AES 标准定义中的位置进行了交换。这没关系，因为这两种操作的位置交换不会改变最终结果。）

ARM 还提供了两个用于加密的 AES 指令，但稍微模糊了不同加密轮次之间的界限：

  1. AESE — AES Encrypt（AddRoundKey is first, No MixColumns）

    a. AddRoundKey

    b. ShiftRows

    c. SubBytes

  2. AESMC — AES MixCoumns

    a. MixColumns

（有关 ARM 指令的详细信息，请参阅ARM 体系结构手册

以下是 Intel 和 ARM 如何实现三轮 AES 加密：

ROUND AES STEPS INTEL ARM
Round 1 AddRoundKey XOR AESE
SubBytes AESENC
ShiftRows
MixColumns AESMC
AddRoundKey AESE
Round 2 SubBytes AESENC
ShiftRows
MixColumns AESMC
AddRoundKey AESE
Round 3 SubBytes AESENCLAST
ShiftRows
AddRoundKey XOR

使用 ARM 指令实现 AESENC

我想避免重写我正在移植的算法，所以我决定坚持使用 Intel 语义，并使用 ARM NEON 内部函数和 GCC 矢量扩展重新实现 x86 内部函数。x86 中的内部函数 AESENC 和 AESENCLAST 具有以下原型：

1
2
__m128i _mm_aesenc_si128 (__m128i a, __m128i RoundKey);
__m128i _mm_aesenclast_si128 (__m128i a, __m128i RoundKey);

实现这一目标的第一步是在 ARM 中为 __m128i 定义等效的类型，我将其映射为 NEON 类型 uint8x16_t：

1
2
3
4
#include <stdint.h>
#include <arm_neon.h>

typedef uint8x16_t __m128i;

接下来，我需要想出一系列可用于模拟 x86 AESENC 语义的 ARM 指令。 使用 AESE+AESMC+XOR 将使我们能够接近这个目标，除了 ARM AESE在开始时有一个在 x86 AESENC 中不存在额外的 AddRoundKey。但是，由于 AddRoundKey 只需将密钥与数据进行简单地 XOR，因此密钥值为零会将这一步转换为 NOP。这是最终的实现：

1
2
3
4
5
6
7
8
9
__m128i _mm_aesenc_si128 (__m128i a, __m128i RoundKey)
{
    return vaesmcq_u8(vaeseq_u8(a, (__m128i){})) ^ RoundKey;
}

__m128i _mm_aesenclast_si128 (__m128i a, __m128i RoundKey)
{
    return vaeseq_u8(a, (__m128i){}) ^ RoundKey;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# clang-6.0 -target aarch64-none-linux -march=armv8+crypto -O3

000000000000003c <_mm_aesenc_si128>:
  3c:   6f00e402        movi    v2.2d, #0x0
  40:   4e284840        aese    v0.16b, v2.16b
  44:   4e286800        aesmc   v0.16b, v0.16b
  48:   6e211c00        eor     v0.16b, v0.16b, v1.16b
  4c:   d65f03c0        ret

0000000000000050 <_mm_aesenclast_si128>:
  50:   6f00e402        movi    v2.2d, #0x0
  54:   4e284840        aese    v0.16b, v2.16b
  58:   6e211c00        eor     v0.16b, v0.16b, v1.16b
  5c:   d65f03c0        ret

使用 ARM 指令实现 AESDEC

有两种方法可以实现 AES 解密算法。第一种称为 “Inverse Cipher”，这种方法只是简单地颠倒加密的步骤顺序。换句话说，不使用 ShiftRows、 SubBytes 和 MixColumns，解密算法使用逆变换 InvShiftRows、InvSubBytes 和 InvMixColumns。第二种方法是一种称为 “Equivalent Inverse Cipher” 的技术，它以不同的方式生成解密密钥，但允许以在硬件中更快地实现的方式对解密步骤进行重新排序。x86 和 ARMv8-A 中的 AES 指令被设计用于第二种解密算法。您可以在Intel 白皮书中阅读有关它的更多信息。

Intel 在 x86 中提供了 AESDEC 和 AESDECLAST 指令以帮助实现 AES 解密算法，而 ARM 则提供了 AESD 和 AESIMC 指令。就像加密一样，与其他架构相比，这些指令的语义略有不同。幸运的是，仍然可以使用用一系列 ARM 内部函数替换 Intel 内部函数。

1
2
3
4
5
6
7
8
9
__m128i _mm_aesdec_si128 (__m128i a, __m128i RoundKey)
{
    return vaesimcq_u8(vaesdq_u8(a, (__m128i){})) ^ RoundKey;
}

__m128i _mm_aesdeclast_si128 (__m128i a, __m128i RoundKey)
{
    return vaesdq_u8(a, (__m128i){}) ^ RoundKey;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# clang-6.0 -target aarch64-none-linux -march=armv8+crypto -O3

0000000000000060 <_mm_aesdec_si128>:
  60:   6f00e402        movi    v2.2d, #0x0
  64:   4e285840        aesd    v0.16b, v2.16b
  68:   4e287800        aesimc  v0.16b, v0.16b
  6c:   6e211c00        eor     v0.16b, v0.16b, v1.16b
  70:   d65f03c0        ret

0000000000000074 <_mm_aesdeclast_si128>:
  74:   6f00e402        movi    v2.2d, #0x0
  78:   4e285840        aesd    v0.16b, v2.16b
  7c:   6e211c00        eor     v0.16b, v0.16b, v1.16b
  80:   d65f03c0        ret

使用 ARM 指令实现 AESKEYGENASSIST

我掩盖了 AES 的一个部分是如何为 AddRoundKey 步骤生成轮函数。AES 标准定义了一种密钥生成算法，Intel 通过 AESKEYGENASSIT 指令实现了密钥生成算法。不幸的是，ARM 没有为 ARMv8-A 提供等效的指令，所以我们必须手动实现。

Intel 文档为 AESKEYGENASSIT 指令的功能提供了相当精确的定义：

1
2
3
4
5
6
7
8
9
X3[31:0] := a[127:96]
X2[31:0] := a[95:64]
X1[31:0] := a[63:32]
X0[31:0] := a[31:0]
RCON[31:0] := ZeroExtend(imm8[7:0]);
dst[31:0] := SubWord(X1)
dst[63:32] := (RotWord(SubWord(X1)) XOR RCON;
dst[95:64] := SubWord(X3)
dst[127:96] := RotWord(SubWord(X3)) XOR RCON;

唯一真正棘手的部分是 SubWord() 函数，它使用与 AES 步骤相同的查表算法。实现自定义查找表不是很有效，因此使用 AESE 指令实现查找表会很方便。

就像使用 AES 加密一样，我使用了一个清零的轮密钥来跳过 AddRoundKey这一步。AESE 指令便只剩下使用SubBytes 和 ShiftRows 步骤用来对输入进行变换：

|b0 b4 b8 b12| |sub(b0) sub(b4) sub(b8) sub(b12)|
|b1 b5 b9 b13| AESE |sub(b5) sub(b9) sub(b13) sub(b1) |
|b2 b6 b10 b14| ====> |sub(b10) sub(b14) sub(b2) sub(b6) |
|b3 b7 b11 b15| |sub(b15) sub(b3) sub(b7) sub(b11)|

使用 NEON TBL 指令，我可以提取所需的字节来构建一个新的向量。在左侧，X1 是 b4、b5、b6、b7，在右侧，这些字节已移动到位置 4、1、14 和 11。同样，X3 是 b12、b13、b14、b15，这些字节已移至位置 9、6、3、12。

1
2
3
4
5
6
7
__m128i dest = {
    // Undo ShiftRows step from AESE and extract X1 and X3
    a[0x4], a[0x1], a[0xE], a[0xB], // SubBytes(X1)
    a[0x4], a[0x1], a[0xE], a[0xB], // SubBytes(X1)
    a[0xC], a[0x9], a[0x6], a[0x3], // SubBytes(X3)
    a[0xC], a[0x9], a[0x6], a[0x3], // SubBytes(X3)
};

下一步是旋转 X1 和 X3 的字节。没有一个很好的指令来做到这一点，但是由于我已经打乱了 AESE 的输出，我可以再打乱一点来执行旋转：

1
2
3
4
5
6
7
__m128i dest = {
    // Undo ShiftRows step from AESE and extract X1 and X3
    a[0x4], a[0x1], a[0xE], a[0xB], // SubBytes(X1)
    a[0x1], a[0xE], a[0xB], a[0x4], // ROT(SubBytes(X1))
    a[0xC], a[0x9], a[0x6], a[0x3], // SubBytes(X3)
    a[0x9], a[0x6], a[0x3], a[0xC], // ROT(SubBytes(X3))
};

最后，RCON 值需要是与 X1 和 X3 进行 XOR。这是最终的实现：

1
2
3
4
5
6
7
8
9
10
11
12
__m128i _mm_aeskeygenassist_si128 (__m128i a, const int imm8)
{
    a = vaeseq_u8(a, (__m128i){}); // AESE does ShiftRows and SubBytes on A
    __m128i dest = {
        // Undo ShiftRows step from AESE and extract X1 and X3
        a[0x4], a[0x1], a[0xE], a[0xB], // SubBytes(X1)
        a[0x1], a[0xE], a[0xB], a[0x4], // ROT(SubBytes(X1))
        a[0xC], a[0x9], a[0x6], a[0x3], // SubBytes(X3)
        a[0x9], a[0x6], a[0x3], a[0xC], // ROT(SubBytes(X3))
    };
    return dest ^ (__m128i)((uint32x4_t){0, rcon, 0, rcon});
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# clang-6.0 -target aarch64-none-linux -march=armv8+crypto -O3

00000000000000d0 <_mm_aeskeygenassist_si128>:
  d0:   90000008        adrp    x8, 0 <load_8>
  d4:   3dc00102        ldr     q2, [x8]
  d8:   6f00e401        movi    v1.2d, #0x0
  dc:   4e040fe3        dup     v3.4s, wzr
  e0:   4e284820        aese    v0.16b, v1.16b
  e4:   4e0c1c03        mov     v3.s[1], w0
  e8:   4e020000        tbl     v0.16b, {v0.16b}, v2.16b
  ec:   4e1c1c03        mov     v3.s[3], w0
  f0:   6e231c00        eor     v0.16b, v0.16b, v3.16b
  f4:   d65f03c0        ret

0000000000000000 <.rodata.cst16>:
        ...
  40:   0b0e0104        .word   0x0b0e0104
  44:   040b0e01        .word   0x040b0e01
  48:   0306090c        .word   0x0306090c
  4c:   0c030609        .word   0x0c030609

参考链接

Emulating x86 AES Intrinsics on ARMv8-A

Markdown表格合并单元格