Information Security
Programming
Assembler
6 November 2013

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

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

Начинаем


Для начало, необходимо убедится что расширение AES-NI присутствует в нашем процессоре. Для этого существует специальная команда CPUID, которая при значение eax=0x00000001, должна выставить в регистрах биты относительно присутствующих расширений. Для расширения AES это 25 бит регистра ECX:
код проверки AES-NI:
		mov eax,0x00000001;
		CPUID;
		test ecx,0x2000000;
		je L_no_AES; 

Если бит установлен в 1, значит мы можем переходить к шифрованию.

Расширение ключа/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
  5. Статья на wikipedia со списком библиотек и программ использующих AES-Ni инструкции

+53
37.8k 109
Comments 23
Top of the day