Аппаратная поддержка алгоритма AES современными процессорами

Компанией Intel в 2008 г. были предложены новые команды для x86 архитектуры, которые добавили поддержку на аппаратном уровне симметричного алгоритма шифрование AES(Advanced Encryption Standard). На данный момент AES — один из самых популярных алгоритмов блочного шифрования. Поэтому аппаратная реализация должна привести к повышению производительности программ использующих этот алгоритм шифрования(OpenSSL, The Bat, TrueCrypt ...). Новое расширение команд получило название AES-NI. Оно содержит в себе следующие инструкции:

• AESENC — Выполнить один раунд шифрования AES,
• AESENCLAST- Выполнить последний раунд шифрования AES,
• AESDEC — Выполнить один раунд расшифрования AES,
• AESDECLAST — Выполнить последний раунд расшифрования AES,
• AESKEYGENASSIST — Поспособствовать в генерации раундового ключа AES,
• AESIMC — Обратный Mix Columns.

Так как про сам алгоритм шифрования AES было уже было сказано многое, то в этом посте рассмотрим, как можно воспользоваться этими инструкциями.

Для начала вспомним, как работает AES. Это потребуется для того, чтобы понять, какие механизмы реализованы в этих инструкциях.
Алгоритм AES использует 4 функции:

1. AddRound — XOR(исключающие или) сообщения с ключом,
2. SubBytes — функция подстановки,
3. ShiftRows- циклический сдвиг полей в блоке по заданному правилу,
4. MixColumns — процедура смешивания.

Сам алгоритм шифрования выглядит так:

Расширение ключа/ExpandKey

Алгоритм расширения ключа в псевдокоде выглядит так:

KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)
begin
    word temp
    i = 0;
    while ( i < Nk)
        w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])
        i = i+1
    end while
    i = Nk
    while ( i < Nb * (Nr+1))
        temp = w[i-1]
        if (i mod Nk = 0)
            temp = SubWord(RotWord(temp)) xor Rcon[i/Nk]
        else if (Nk > 6 and i mod Nk = 4)
            temp = SubWord(temp)
        end if
        w[i] = w[i-Nk] xor temp
        i = i + 1
    end while
end

Для аппаратной поддержки надо использовать инструкцию AESKEYGENASSIST, которая выполнит:

AESKEYGENASSIST xmm1, xmm2/m128, imm8 
Tmp := xmm2/LOAD(m128) 
X3[31-0] = Tmp[127-96]; 
X2[31-0] = Tmp[95-64]; 
X1[31-0] = Tmp[63-32]; 
X0[31-0] = Tmp[31-0]; 
RCON[7-0]:= imm8; 
RCON [31-8]:= 0; 
xmm1 :=[RotWord (SubWord (X3)) XOR RCON, SubWord (X3), RotWord (SubWord (X1)) XOR RCON, SubWord (X1)] 

Как легко заметить, инструкция не выполняет:

w[i] = w[i-Nk] xor temp

Эти операции придется выполнить самим, используя MMX инструкции

aeskeygenassist xmm2, xmm1, 0x1 ; 1 раунд
pshufd xmm2, xmm2, 0xff; 
movups xmm3, xmm4;
pxor xmm2,xmm3;
pshufd xmm2, xmm2, 0x00;

pshufd xmm3, xmm3, 0x39;
pslldq xmm3,0x4;
pxor xmm2,xmm3;
pshufd xmm2, xmm2, 0x14;

pshufd xmm3, xmm3, 0x38;
pslldq xmm3,0x4;
pxor xmm2,xmm3;
 pshufd xmm2, xmm2, 0xA4;

pshufd xmm3, xmm3, 0x34;
pslldq xmm3,0x4;
pxor xmm2,xmm3;

Шифрование/Encryption

Для реализации одного раунда шифрования используется инструкция AESENC, которая выполняет следующие действия:

AESENC xmm1, xmm2/m128
Tmp = xmm1
Round Key := xmm2/m128
Tmp = ShiftRows (Tmp)
Tmp = SubBytes (Tmp)
Tmp = MixColumns (Tmp)
xmm1 = Tmp xor Round Key 

Последний раунд шифрования реализуется при помощи инструкции AESENCLAST:

AESENC xmm1, xmm2/m128
Tmp = xmm1
Round Key := xmm2/m128
Tmp = ShiftRows (Tmp)
Tmp = SubBytes (Tmp)
xmm1 = Tmp xor Round Key 

Отличие этой инструкции от AESENC состоит в том, что операция MixColums на последнем шаге не выполняется:

aesenc xmm1, xmm2 ; 
aesenclast xmm1, xmm3;

Расшифровывание/decryption

Для реализации процедуры расшифрования используется инструкция AESDEC:

AESDEC xmm1, xmm2/m128
Tmp = xmm1
Round Key = xmm2/m128
Tmp = InvShift Rows (Tmp)
Tmp = InvSubBytes (Tmp)
Tmp = InvMixColumns (Tmp)
xmm1 = Tmp xor Round Key 

Для получения InvKey надо выполнить операцию InvMixClomuns для ключа. Инструкция, которая это делает — AESIMC xmm1.xmm2
И для последнего раунда расшифрования используется Инструкция AESDECLAST:

AESDECLAST xmm1, xmm2/m128
State = xmm1
Round Key = xmm2/m128
Tmp = InvShift Rows (State)
Tmp = InvSubBytes (Tmp)
xmm1= Tmp xor RoundKey

aesmic xmm2,xmm2;
aesdec xmm1, xmm2 ; 
aesdeclast xmm1, xmm3;

Итак, аппаратное поддержка должна нам дать приличный прирост к скорости шифрования. В качестве завершения поста приведу класс на C++ ^[1], реализующий операции шифрования и расшифрования в режиме ECB. После прогона теста была достигнута скорость шифрования на одном ядре i5-3740 (3.2GHz), равная 320MB/sec

Ссылки:

1. Intel® Advanced Encryption Standard(AES) New Instructions Set ^[2]
2. Список процессоров поддерживающих расширение команд AES-NI ^[3]
3. C++ класс с AES-NI ассемблерными вставками ^[1]
4. Анимашка как работает AES ^[4]

Автор: iostreamawm

Источник ^[5]