Аппаратная поддержка алгоритма 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 инструкции

Пример расширения 128b ключа

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++, реализующий операции шифрования и расшифрования в режиме ECB. После прогона теста была достигнута скорость шифрования на одном ядре i5-3740 (3.2GHz), равная 320MB/sec

Ссылки:

1. Intel® Advanced Encryption Standard(AES) New Instructions Set


2. Список процессоров поддерживающих расширение команд AES-NI


3. C++ класс с AES-NI ассемблерными вставками


4. Анимашка как работает AES

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends:

• Massacres That Matter - Part 1 - 'Responsibility To Protect' In Egypt, Libya And Syria


• Massacres That Matter - Part 2 - The Media Response On Egypt, Libya And Syria


• National demonstration: No attack on Syria - Saturday 31 August, 12 noon, Temple Place, London, UK