ГОСТ Р 34.12 '15 на SSE2, або Не так вже й поганий Коник

На Хабре вже як мінімум двічі згадувався новий вітчизняний стандарт блочного шифрування ГОСТ Р 34.12 2015 «Коник», ru_crypt у своєму пості розглянув основні механізми і перетворення нового стандарту, а sebastian_mg займався покрокової трасуванням базового перетворення. Але багато питань залишилися без відповіді. Наскільки швидкий новий ГОСТ? Чи можна його оптимізувати, ефективно реалізувати, прискорити апаратно?
GOST R 34.12 2015 with SSE2
стандарті ГОСТ Р 34.12 '15
Наказом від 19 червня 2015 року №749 в якості нового стандарту блочного шифрування затверджено ГОСТ Р 34.12 2015. Стандарт розроблений Центром захисту інформації та спеціального зв'язку ФСБ Росії з участю ВАТ «Інфотекс», внесено Технічним комітетом з стандартизації ТК 26 «Криптографічний захист інформації», і вступив в дію з 1 січня 2016 року.
Офіційне pdf-видання стандарту качаємо тут, а еталонну реалізацію — тут (обидві ведуть посилання на офіційний сайт ТК 26).
Цей стандарт містить опис двох блочних шифрів: «Магми» з довжиною блоку 64 біта і «Коника» з довжиною блоку 128 біт; при цьому «Магма» — всього лише нова назва старого, всім добре відомого блочного шифру ГОСТ 28147 '89 (насправді, не зовсім нове, саме під цим кодовою назвою розроблявся колишній стандарт блочного шифрування аж до 1994 року) із зафіксованими вузлами заміни. «Нарешті, історія нас чомусь навчила», — скажете ви, і будете праві.
У цій статті піде мова про інший шифр, що має довжину блоку 128 біт, і носить кодове ім'я «Коник». За міською ленді, ім'я шифру зовсім не пов'язане з зеленим комах, а утворено першими складами прізвищ авторів цього шифру: Кзозьмин, Нечаев і ккомпанія.
Опис «Коника»
Відзнаки «Коника» від «Магми»
Новий шифр істотно відрізняється від старого, серед його основних переваг можна виділити
  • вдвічі збільшену довжину блоку (128 біт, або 16 байт, проти 64 біт, або 8 байт),
  • нетривіальне ключове розклад (мережа Фейстеля як ключове розклад проти використання частин секретного ключа в якості циклових ключів),
  • скорочене число циклів (10 циклів проти 32 циклів),
  • принципово інше пристрій самого шифру (LSX-шифр проти мережі Фейстеля).
Базове перетворення
Шифр належить до класу LSX-шифрів: його базове перетворення (функція шифрування блоку) видається десятьма циклами послідовних перетворень L (лінійне перетворення), S (підстановка) і X (змішування з цикловим ключем):

Повний цикл базового перетворення
Алгебраїчно шифртекст C залежить від відкритого тексту P наступним чином:
C = X_{9} \circ LSX_{8} \circ \dots \circ LSX_{0} \left( P \right),
тобто за дев'ятьма повними циклами слід останній неповний (тільки змішування з ключем). Перетворення X змішує проміжний текст чергового циклу з відповідним цикловим ключем простим додаванням за модулем 2:
X(M_i) = M_i \oplus K_i.
Перетворення S застосовує одну й ту саму фіксовану підстановку \piдо кожного байту проміжного тексту:
S(M_i) = \overline{\pi(m_0) \pi(m_1) \dots \pi(m_{15})}, \text{ де } \pi \colon \mathbb{Z}_2^8 \mapsto \mathbb{Z}_2^8 \text{ і } M_i = \overline{m_0 m_1 \dots m_{15}}.
Перетворення L представимо лінійної формою над полем GF(256), побудованим за допомогою непривідного многочлена
p(x) = x^8 + x^7 + x^6 + x + 1,
і зводиться до множення вектора–рядка проміжного тексту на деяку матрицю над цим полем (кожен байт тексту і матриці є многочленом поля, представленим своїми коефіцієнтами):
L(M_i) = M_i \times M_{16 \times 16}.
Приклад коду базового перетворення
/* Застосовує S-перетворення до блоку. */
static void 
applySTransformation(
uint8_t *block
) {
for (int byteIndex = 0; byteIndex < BlockLengthInBytes; byteIndex += 8) {
block[byteIndex + 0] = Pi[block[byteIndex + 0]];
block[byteIndex + 1] = Pi[block[byteIndex + 1]];
block[byteIndex + 2] = Pi[block[byteIndex + 2]];
block[byteIndex + 3] = Pi[block[byteIndex + 3]];

block[byteIndex + 4] = Pi[block[byteIndex + 4]];
block[byteIndex + 5] = Pi[block[byteIndex + 5]];
block[byteIndex + 6] = Pi[block[byteIndex + 6]];
block[byteIndex + 7] = Pi[block[byteIndex + 7]];
}
}

/* Застосовує L-перетворення до блоку. */
static void 
applyLTransformation(
const uint8_t *input,
uint8_t *output
) {
for (int byteIndex = 0; byteIndex < BlockLengthInBytes; ++byteIndex) {
uint8_t cache = 0;

for (int addendIndex = 0; addendIndex < BlockLengthInBytes; ++addendIndex) {
cache ^= multiplyInGF256(LTransformationMatrix[addendIndex][byteIndex], 
input[addendIndex]);
}

output[byteIndex] = cache;
}
}

/* Повний цикл шифрування блоку. */
static void 
applyXSLTransformation(
const uint8_t *key,
uint8_t *block,
uint8_t *temporary
) {
applyXTransformation(key, block, temporary);
applySTransformation(temporary);
applyLTransformation(temporary, block);
}

/* Базове перетворення (шифрування блоку). */
void 
encryptBlock(
uint8_t *restrict block,
const uint8_t *restrict roundKeys
) {
uint8_t cache[BlockLengthInBytes] = {0};
int round = 0;
for (; round < NumberOfRounds - 1; ++round) {
applyXSLTransformation(&roundKeys[BlockLengthInBytes * round], block, cache);
}
applyXTransformation(&roundKeys[BlockLengthInBytes * round], block, block);
}

Обчислені матриця перетворення L і обернена до неї в C-friendly вигляді
/* Матриця перетворення L. */
const uint8_t LTransformationMatrix[16][16] = {
0xcf, 0x6e, 0xa2, 0x76, 0x72, 0x6c, 0x48, 0x7a, 0xb8, 0x5d, 0x27, 0xbd, 0x10, 0xdd, 0x84, 0x94,
0x98, 0x20, 0xc8, 0x33, 0xf2, 0x76, 0xd5, 0xe6, 0x49, 0xd4, 0x9f, 0x95, 0xe9, 0x99, 0x2d, 0x20,
0x74, 0xc6, 0x87, 0x10, 0x6b, 0xec, 0x62, 0x4e, 0x87, 0xb8, 0xbe, 0x5e, 0xd0, 0x75, 0x74, 0x85,
0xbf, 0xda, 0x70, 0x0c, 0xca, 0x0c, 0x17, 0x1a, 0x14, 0x2f, 0x68, 0x30, 0xd9, 0xca, 0x96, 0x10,
0x93, 0x90, 0x68, 0x1c, 0x20, 0xc5, 0x06, 0xbb, 0xcb, 0x8d, 0x1a, 0xe9, 0xf3, 0x97, 0x5d, 0xc2,
0x8e, 0x48, 0x43, 0x11, 0xeb, 0xbc, 0x2d, 0x2e, 0x8d, 0x12, 0x7c, 0x60, 0x94, 0x44, 0x77, 0xc0,
0xf2, 0x89, 0x1c, 0xd6, 0x02, 0xaf, 0xc4, 0xf1, 0xab, 0xee, 0xad, 0xbf, 0x3d, 0x5a, 0x6f, 0x01,
0xf3, 0x9c, 0x2b, 0x6a, 0xa4, 0x6e, 0xe7, 0xbe, 0x49, 0xf6, 0xc9, 0x10, 0xaf, 0xe0, 0xde, 0xfb,
0x0a, 0xc1, 0xa1, 0xa6, 0x8d, 0xa3, 0xd5, 0xd4, 0x09, 0x08, 0x84, 0xef, 0x7b, 0x30, 0x54, 0x01,
0xbf, 0x64, 0x63, 0xd7, 0xd4, 0xe1, 0xeb, 0xaf, 0x6c, 0x54, 0x2f, 0x39, 0xff, 0xa6, 0xb4, 0xc0,
0xf6, 0xb8, 0x30, 0xf6, 0xc4, 0x90, 0x99, 0x37, 0x2a, 0x0f, 0xeb, 0xec, 0x64, 0x31, 0x8d, 0xc2,
0xa9, 0x2d, 0x6b, 0x49, 0x01, 0x58, 0x78, 0xb1, 0x01, 0xf3, 0xfe, 0x91, 0x91, 0xd3, 0xd1, 0x10,
0xea, 0x86, 0x9f, 0x07, 0x65, 0x0e, 0x52, 0xd4, 0x60, 0x98, 0xc6, 0x7f, 0x52, 0xdf, 0x44, 0x85,
 0x8e, 0x44, 0x30, 0x14, 0xdd, 0x02, 0xf5, 0x2a, 0x8e, 0xc8, 0x48, 0x48, 0xf8, 0x48, 0x3c, 0x20,
0x4d, 0xd0, 0xe3, 0xe8, 0x4c, 0xc3, 0x16, 0x6e, 0x4b, 0x7f, 0xa2, 0x89, 0x0d, 0x64, 0xa5, 0x94,
0x6e, 0xa2, 0x76, 0x72, 0x6c, 0x48, 0x7a, 0xb8, 0x5d, 0x27, 0xbd, 0x10, 0xdd, 0x84, 0x94, 0x01,
};

/* Матриця, обернена до матриці перетворення L. */
const uint8_t inversedLTransformationMatrix[16][16] = {
0x01, 0x94, 0x84, 0xdd, 0x10, 0xbd, 0x27, 0x5d, 0xb8, 0x7a, 0x48, 0x6c, 0x72, 0x76, 0xa2, 0x6e,
0x94, 0xa5, 0x64, 0x0d, 0x89, 0xa2, 0x7f, 0x4b, 0x6e, 0x16, 0xc3, 0x4c, 0xe8, 0xe3, 0xd0, 0x4d,
0x20, 0x3c, 0x48, 0xf8, 0x48, 0x48, 0xc8, 0x8e, 0x2a, 0xf5, 0x02, 0xdd, 0x14, 0x30, 0x44, 0x8e,
0x85, 0x44, 0xdf, 0x52, 0x7f, 0xc6, 0x98, 0x60, 0xd4, 0x52, 0x0e, 0x65, 0x07, 0x9f, 0x86, 0xea,
0x10, 0xd1, 0xd3, 0x91, 0x91, 0xfe, 0xf3, 0x01, 0xb1, 0x78, 0x58, 0x01, 0x49, 0x6b, 0x2d, 0xa9,
0xc2, 0x8d, 0x31, 0x64, 0xec, 0xeb, 0x0f, 0x2a, 0x37, 0x99, 0x90, 0xc4, 0xf6, 0x30, 0xb8, 0xf6,
0xc0, 0xb4, 0xa6, 0xff, 0x39, 0x2f, 0x54, 0x6c, 0xaf, 0xeb, 0xe1, 0xd4, 0xd7, 0x63, 0x64, 0xbf,
0x01, 0x54, 0x30, 0x7b, 0xef, 0x84, 0x08, 0x09, 0xd4, 0xd5, 0xa3, 0x8d, 0xa6, 0xa1, 0xc1, 0x0a,
0xfb, 0xde, 0xe0, 0xaf, 0x10, 0xc9, 0xf6, 0x49, 0xbe, 0xe7, 0x6e, 0xa4, 0x6a, 0x2b, 0x9c, 0xf3,
0x01, 0x6f, 0x5a, 0x3d, 0xbf, 0xad, 0xee, 0xab, 0xf1, 0xc4, 0xaf, 0x02, 0xd6, 0x1c, 0x89, 0xf2,
0xc0, 0x77, 0x44, 0x94, 0x60, 0x7c, 0x12, 0x8d, 0x2e, 0x2d, 0xbc, 0xeb, 0x11, 0x43, 0x48, 0x8e,
0xc2, 0x5d, 0x97, 0xf3, 0xe9, 0x1a, 0x8d, 0xcb, 0xbb, 0x06, 0xc5, 0x20, 0x1c, 0x68, 0x90, 0x93,
0x10, 0x96, 0xca, 0xd9, 0x30, 0x68, 0x2f, 0x14, 0x1a, 0x17, 0x0c, 0xca, 0x0c, 0x70, 0xda, 0xbf,
0x85, 0x74, 0x75, 0xd0, 0x5e, 0xbe, 0xb8, 0x87, 0x4e, 0x62, 0xec, 0x6b, 0x10, 0x87, 0xc6, 0x74,
0x20, 0x2d, 0x99, 0xe9, 0x95, 0x9f, 0xd4, 0x49, 0xe6, 0xd5, 0x76, 0xf2, 0x33, 0xc8, 0x20, 0x98,
0x94, 0x84, 0xdd, 0x10, 0xbd, 0x27, 0x5d, 0xb8, 0x7a, 0x48, 0x6c, 0x72, 0x76, 0xa2, 0x6e, 0xcf,
};

Ключове розклад
Справді, багато помилки, допущені при розробці старшого шифру, були виправлені, в тому числі вразливе ключове розклад. Нагадаю читачеві, що в шифрі ГОСТ 28147 '89 в якості циклових ключів використовувалися вісім 32-бітних частин 256-бітного секретного ключа в прямому порядку на циклах шифрування з першого по восьмий, з дев'ятого по шістнадцяте, з сімнадцятого по двадцять четвертий; і в зворотному порядку на циклах з двадцять п'ятого по тридцять другий:
<img src=«tex.s2cms.ru/svg/%0AK_0%2C%20K_1%2C%20%5Cdots%2C%20K_6%2C%20K_7%2C%5C%5C%0AK_0%2C%20K_1%2C%20%5Cdots%2C%20K_6%2C%20K_7%2C%5C%5C%0AK_0%2C%20K_1%2C%20%5Cdots%2C%20K_6%2C%20K_7%2C%5C%5C%0AK_7%2C%20K_6%2C%20%5Cdots%2C%20K_1%2C%20K_0.%5C%5C%0A» alt=«K_0, K_1, \dots, K_6, K_7,\\
K_0, K_1, \dots, K_6, K_7,\\
K_0, K_1, \dots, K_6, K_7,\\
K_7, K_6, \dots, K_1, K_0.\\»/>
І саме таке слабке ключове розклад дозволило здійснити атаку з відображенням на повний ГОСТ, знизивши його стійкість з 256 біт до 225 біт (при будь-яких вузлах заміни, з 2^32 матеріалу на одному ключі; почитати про цю атаку можна тут).
В новому стандарті вироблення циклових ключів здійснюється за схемою Фейстеля, при цьому першими двома цикловими ключами є половини 256-бітного секретного ключа, а кожна наступна пара циклових ключів виходить в результаті застосування восьми циклів перетворення Фейстеля до попередньої парі циклових ключів, де в якості циклової функції використовується той же LSX перетворення, що і в базовому перетворенні, а в якості циклових ключів у схемі використовується фіксований набір констант:
\left( K_{2i + 1}, K_{2i + 2} \right) = 
F^8 \left( K_{2i - 1}, K_{2i} \right);
\text{ де }
F \left( x, y \right) = \left( LSX_i(y) \oplus x, y \right).
Приклад коду, що реалізує таке ключове розклад
/* Виробляє циклові ключі для шифрування по ГОСТ Р 34.12 '15. */
static void 
scheduleRoundKeys(
uint8_t *restrict roundKeys,
const void *restrict key,
uint8_t *restrict memory
) {
/* Копіювання першої пари циклових ключів. */
memcpy(&roundKeys[0], key, BlockLengthInBytes * 2);

for (int nextKeyIndex = 2, constantIndex = 0;
nextKeyIndex != NumberOfRounds;
nextKeyIndex += 2) {

/* Копіювання попередньої пари циклових ключів. */
memcpy(&roundKeys[BlockLengthInBytes * (nextKeyIndex)],
&roundKeys[BlockLengthInBytes * (nextKeyIndex - 2)],
BlockLengthInBytes * 2);

/* Застосування перетворень Фейстеля. */
for (int feistelRoundIndex = 0; 
feistelRoundIndex < NumberOfRoundsInKeySchedule; 
++feistelRoundIndex) {
applyFTransformation(&roundConstants[BlockLengthInBytes * constantIndex++],
&roundKeys[BlockLengthInBytes * (nextKeyIndex)],
&roundKeys[BlockLengthInBytes * (nextKeyIndex + 1)],
&memory[0],
&memory[BlockLengthInBytes]);
}
}
}

Примітки
256 біт допоміжної пам'яті для циклового перетворення тут передаються за вказівником
memory
, але їх можна виділяти та на стеку.
Явна індексація масиву з цикловими ключами
roundKeys
здійснена для наочності і простоти, і може бути легко замінена на арифметику покажчиків.
Функція
applyFTransformation
застосовує цикловое перетворення до полублокам схеми і виробляє своп цих напівблоків, наприклад, так:
/* Застосовує цикловое перетворення схеми Фейстеля ключового розкладу. */
static void 
applyFTransformation(
const uint8_t *restrict key,
uint8_t *restrict left,
uint8_t *restrict right,
uint8_t *restrict temporary1,
uint8_t *restrict temporary2
) {
memcpy(temporary1, left, BlockLengthInBytes);
applyXSLTransformation(key, temporary1, temporary2);
applyXTransformation(temporary1, right, right);
swapBlocks(left, right, temporary2);
}

Обчислені циклові ключі в ключовому розкладі C-friendly вигляді
const uint8_t roundConstants[512] = {
0x6e, 0xa2, 0x76, 0x72, 0x6c, 0x48, 0x7a, 0xb8, 0x5d, 0x27, 0xbd, 0x10, 0xdd, 0x84, 0x94, 0x01,
0xdc, 0x87, 0xec, 0xe4, 0xd8, 0x90, 0xf4, 0xb3, 0xba, 0x4e, 0xb9, 0x20, 0x79, 0xcb, 0xeb, 0x02,
0xb2, 0x25, 0x9a, 0x96, 0xb4, 0xd8, 0x8e, 0x0b, 0xe7, 0x69, 0x04, 0x30, 0xa4, 0x4f, 0x7f, 0x03,
0x7b, 0xcd, 0x1b, 0x0b, 0x73, 0xe3, 0x2b, 0xa5, 0xb7, 0x9c, 0xb1, 0x40, 0xf2, 0x55, 0x15, 0x04,
0x15, 0x6f, 0x6d, 0x79, 0x1f, 0xab, 0x51, 0x1d, 0xea, 0xbb, 0x0c, 0x50, 0x2f, 0xd1, 0x81, 0x05,
0xa7, 0x4a, 0xf7, 0xef, 0xab, 0x73, 0xdf, 0x16, 0x0d, 0xd2, 0x08, 0x60, 0x8b, 0x9e, 0xfe, 0x06,
0xc9, 0xe8, 0x81, 0x9d, 0xc7, 0x3b, 0xa5, 0xae, 0x50, 0xf5, 0xb5, 0x70, 0x56, 0x1a, 0x6a, 0x07,
0xf6, 0x59, 0x36, 0x16, 0xe6, 0x05, 0x56, 0x89, 0xad, 0xfb, 0xa1, 0x80, 0x27, 0xaa, 0x2a, 0x08,
0x98, 0xfb, 0x40, 0x64, 0x8a, 0x4d, 0x2c, 0x31, 0xf0, 0xdc, 0x1c, 0x90, 0xfa, 0x2e, 0xbe, 0x09,
0x2a, 0xde, 0xda, 0xf2, 0x3e, 0x95, 0xa2, 0x3a, 0x17, 0xb5, 0x18, 0xa0, 0x5e, 0x61, 0xc1, 0x0a,
0x44, 0x7c, 0xac, 0x80, 0x52, 0xdd, 0xd8, 0x82, 0x4a, 0x92, 0xa5, 0xb0, 0x83, 0xe5, 0x55, 0x0b,
0x8d, 0x94, 0x2d, 0x1d, 0x95, 0xe6, 0x7d, 0x2c, 0x1a, 0x67, 0x10, 0xc0, 0xd5, 0xff, 0x3f, 0x0c,
0xe3, 0x36, 0x5b, 0x6f, 0xf9, 0xae, 0x07, 0x94, 0x47, 0x40, 0xad, 0xd0, 0x08, 0x7b, 0xab, 0x0d,
0x51, 0x13, 0xc1, 0xf9, 0x4d, 0x76, 0x89, 0x9f, 0xa0, 0x29, 0xa9, 0xe0, 0xac, 0x34, 0xd4, 0x0e,
0x3f, 0xb1, 0xb7, 0x8b, 0x21, 0x3e, 0xf3, 0x27, 0xfd, 0x0e, 0x14, 0xf0, 0x71, 0xb0, 0x40, 0x0f,
0x2f, 0xb2, 0x6c, 0x2c, 0x0f, 0x0a, 0xac, 0xd1, 0x99, 0x35, 0x81, 0xc3, 0x4e, 0x97, 0x54, 0x10,
0x41, 0x10, 0x1a, 0x5e, 0x63, 0x42, 0xd6, 0x69, 0xc4, 0x12, 0x3c, 0xd3, 0x93, 0x13, 0xc0, 0x11,
0xf3, 0x35, 0x80, 0xc8, 0xd7, 0x9a, 0x58, 0x62, 0x23, 0x7b, 0x38, 0xe3, 0x37, 0x5c, 0xbf, 0x12,
0x9d, 0x97, 0xf6, 0xba, 0xbb, 0xd2, 0x22, 0xda, 0x7e, 0x5c, 0x85, 0xf3, 0xea, 0xd8, 0x2b, 0x13,
0x54, 0x7f, 0x77, 0x27, 0x7c, 0xe9, 0x87, 0x74, 0x2e, 0xa9, 0x30, 0x83, 0xbc, 0xc2, 0x41, 0x14,
0x3a, 0xdd, 0x01, 0x55, 0x10, 0xa1, 0xfd, 0xcc, 0x73, 0x8e, 0x8d, 0x93, 0x61, 0x46, 0xd5, 0x15,
0x88, 0xf8, 0x9b, 0xc3, 0xa4, 0x79, 0x73, 0xc7, 0x94, 0xe7, 0x89, 0xa3, 0xc5, 0x09, 0xaa, 0x16,
0xe6, 0x5a, 0xed, 0xb1, 0xc8, 0x31, 0x09, 0x7f, 0xc9, 0xc0, 0x34, 0xb3, 0x18, 0x8d, 0x3e, 0x17,
0xd9, 0xeb, 0x5a, 0x3a, 0xe9, 0x0f, 0xfa, 0x58, 0x34, 0xce, 0x20, 0x43, 0x69, 0x3d, 0x7e, 0x18,
0xb7, 0x49, 0x2c, 0x48, 0x85, 0x47, 0x80, 0xe0, 0x69, 0xe9, 0x9d, 0x53, 0xb4, 0xb9, 0xea, 0x19,
0x05, 0x6c, 0xb6, 0xde, 0x31, 0x9f, 0x0e, 0xeb, 0x8e, 0x80, 0x99, 0x63, 0x10, 0xf6, 0x95, 0x1a,
0x6b, 0xce, 0xc0, 0xac, 0x5d, 0xd7, 0x74, 0x53, 0xd3, 0xa7, 0x24, 0x73, 0xcd, 0x72, 0x01, 0x1b,
 0xa2, 0x26, 0x41, 0x31, 0x9a, 0xec, 0xd1, 0xfd, 0x83, 0x52, 0x91, 0x03, 0x9b, 0x68, 0x6b, 0x1c,
0xcc, 0x84, 0x37, 0x43, 0xf6, 0xa4, 0xab, 0x45, 0xde, 0x75, 0x2c, 0x13, 0x46, 0xec, 0xff, 0x1d,
0x7e, 0xa1, 0xad, 0xd5, 0x42, 0x7c, 0x25, 0x4e, 0x39, 0x1c, 0x28, 0x23, 0xe2, 0xa3, 0x80, 0x1e,
0x10, 0x03, 0xdb, 0xa7, 0x2e, 0x34, 0x5f, 0xf6, 0x64, 0x3b, 0x95, 0x33, 0x3f, 0x27, 0x14, 0x1f,
0x5e, 0xa7, 0xd8, 0x58, 0x1e, 0x14, 0x9b, 0x61, 0xf1, 0x6a, 0xc1, 0x45, 0x9c, 0xed, 0xa8, 0x20,
};

Пристрій вузла заміни
У стандарті вузол заміни задано таблицею значень; розробники шифру стверджують, що ця таблиця отримана в результаті перебору таблиць випадкових значень з урахуванням вимог до лінійним різницевим і властивостями.

Шар підстановки S-перетворення
Вузол заміни і зворотний до нього в C-friendly вигляді
/* Вузол заміни pi стандарту шифрування ГОСТ 34.12 2015 Р. */
const uint8_t Pi[256] = {
0xfc, 0xee, 0xdd, 0x11, 0xcf, 0x6e, 0x31, 0x16, 0xfb, 0xc4, 0xfa, 0xda, 0x23, 0xc5, 0x04, 0x4d,
0xe9, 0x77, 0xf0, 0xdb, 0x93, 0x2e, 0x99, 0xba, 0x17, 0x36, 0xf1, 0xbb, 0x14, 0xcd, 0x5f, 0xc1,
0xf9, 0x18, 0x65, 0x5a, 0xe2, 0x5c, 0xef, 0x21, 0x81, 0x1c, 0x3c, 0x42, 0x8b, 0x01, 0x8e, 0x4f,
0x05, 0x84, 0x02, 0xae, 0xe3, 0x6a, 0x8f, 0xa0, 0x06, 0x0b, 0xed, 0x98, 0x7f, 0xd4, 0xd3, 0x1f,
0xeb, 0x34, 0x2c, 0x51, 0xea, 0xc8, 0x48, 0xab, 0xf2, 0x2a, 0x68, 0xa2, 0xfd, 0x3a, 0xce, 0xcc,
0xb5, 0x70, 0x0e, 0x56, 0x08, 0x0c, 0x76, 0x12, 0xbf, 0x72, 0x13, 0x47, 0x9c, 0xb7, 0x5d, 0x87,
0x15, 0xa1, 0x96, 0x29, 0x10, 0x7b, 0x9a, 0xc7, 0xf3, 0x91, 0x78, 0x6f, 0x9d, 0x9e, 0xb2, 0xb1,
0x32, 0x75, 0x19, 0x3d, 0xff, 0x35, 0x8a, 0x7e, 0x6d, 0x54, 0xc6, 0x80, 0xc3, 0xbd, 0x0d, 0x57,
0xdf, 0xf5, 0x24, 0xa9, 0x3e, 0xa8, 0x43, 0xc9, 0xd7, 0x79, 0xd6, 0xf6, 0x7c, 0x22, 0xb9, 0x03,
0xe0, 0x0f, 0xec, 0xde, 0x7a, 0x94, 0xb0, 0xbc, 0xdc, 0xe8, 0x28, 0x50, 0x4e, 0x33, 0x0a, 0x4a,
0xa7, 0x97, 0x60, 0x73, 0x1e, 0x00, 0x62, 0x44, 0x1a, 0xb8, 0x38, 0x82, 0x64, 0x9f, 0x26, 0x41,
0xad, 0x45, 0x46, 0x92, 0x27, 0x5e, 0x55, 0x2f, 0x8c, 0xa3, 0xa5, 0x7d, 0x69, 0xd5, 0x95, 0x3b,
0x07, 0x58, 0xb3, 0x40, 0x86, 0xac, 0x1d, 0xf7, 0x30, 0x37, 0x6b, 0xe4, 0x88, 0xd9, 0xe7, 0x89,
0xe1, 0x1b, 0x83, 0x49, 0x4c, 0x3f, 0xf8, 0xfe, 0x8d, 0x53, 0xaa, 0x90, 0xca, 0xd8, 0x85, 0x61,
0x20, 0x71, 0x67, 0xa4, 0x2d, 0x2b, 0x09, 0x5b, 0xcb, 0x9b, 0x25, 0xd0, 0xbe, 0xe5, 0x6c, 0x52,
0x59, 0xa6, 0x74, 0xd2, 0xe6, 0xf4, 0xb4, 0xc0, 0xd1, 0x66, 0xaf, 0xc2, 0x39, 0x4b, 0x63, 0xb6,
};

/* Вузол заміни, зворотний до pi, стандарту шифрування ГОСТ 34.12 2015 Р. */
const uint8_t InversedPi[256] = {
0xa5, 0x2d, 0x32, 0x8f, 0x0e, 0x30, 0x38, 0xc0, 0x54, 0xe6, 0x9e, 0x39, 0x55, 0x7e, 0x52, 0x91,
0x64, 0x03, 0x57, 0x5a, 0x1c, 0x60, 0x07, 0x18, 0x21, 0x72, 0xa8, 0xd1, 0x29, 0xc6, 0xa4, 0x3f,
0xe0, 0x27, 0x8d, 0x0c, 0x82, 0xea, 0xae, 0xb4, 0x9a, 0x63, 0x49, 0xe5, 0x42, 0xe4, 0x15, 0xb7,
0xc8, 0x06, 0x70, 0x9d, 0x41, 0x75, 0x19, 0xc9, 0xaa, 0xfc, 0x4d, 0xbf, 0x2a, 0x73, 0x84, 0xd5,
0xc3, 0xaf, 0x2b, 0x86, 0xa7, 0xb1, 0xb2, 0x5b, 0x46, 0xd3, 0x9f, 0xfd, 0xd4, 0x0f, 0x9c, 0x2f,
0x9b, 0x43, 0xef, 0xd9, 0x79, 0xb6, 0x53, 0x7f, 0xc1, 0xf0, 0x23, 0xe7, 0x25, 0x5e, 0xb5, 0x1e,
0xa2, 0xdf, 0xa6, 0xfe, 0xac, 0x22, 0xf9, 0xe2, 0x4a, 0xbc, 0x35, 0xca, 0xee, 0x78, 0x05, 0x6b,
0x51, 0xe1, 0x59, 0xa3, 0xf2, 0x71, 0x56, 0x11, 0x6a, 0x89, 0x94, 0x65, 0x8c, 0xbb, 0x77, 0x3c,
0x7b, 0x28, 0xab, 0xd2, 0x31, 0xde, 0xc4, 0x5f, 0xcc, 0xcf, 0x76, 0x2c, 0xb8, 0xd8, 0x2e, 0x36,
0xdb, 0x69, 0xb3, 0x14, 0x95, 0xbe, 0x62, 0xa1, 0x3b, 0x16, 0x66, 0xe9, 0x5c, 0x6c, 0x6d, 0xad,
0x37, 0x61, 0x4b, 0xb9, 0xe3, 0xba, 0xf1, 0xa0, 0x85, 0x83, 0xda, 0x47, 0xc5, 0xb0, 0x33, 0xfa,
0x96, 0x6f, 0x6e, 0xc2, 0xf6, 0x50, 0xff, 0x5d, 0xa9, 0x8e, 0x17, 0x1b, 0x97, 0x7d, 0xec, 0x58,
0xf7, 0x1f, 0xfb, 0x7c, 0x09, 0x0d, 0x7a, 0x67, 0x45, 0x87, 0xdc, 0xe8, 0x4f, 0x1d, 0x4e, 0x04,
0xeb, 0xf8, 0xf3, 0x3e, 0x3d, 0xbd, 0x8a, 0x88, 0xdd, 0xcd, 0x0b, 0x13, 0x98, 0x02, 0x93, 0x80,
0x90, 0xd0, 0x24, 0x34, 0xcb, 0xed, 0xf4, 0xce, 0x99, 0x10, 0x44, 0x40, 0x92, 0x3a, 0x01, 0x26,
0x12, 0x1a, 0x48, 0x68, 0xf5, 0x81, 0x8b, 0xc7, 0xd6, 0x20, 0x0a, 0x08, 0x00, 0x4c, 0xd7, 0x74,
};

Проте все таємне рано чи пізно стає явним, і спосіб вибору вузла заміни не виняток. Команді криптографів з Люксембургу, очолюваної Алексом Бірюковим, вдалося виявити певні закономірності в статистичних характеристиках заміни вузла, що, в свою чергу, дозволило їм відновити спосіб його отримання. Докладніше про цей спосіб можна почитати в їх статті, опублікованій на iacr.org.

Секретна структура вузла заміни
Алгоритмічна оптимізація
Команді дослідників з ВАТ «Інфотекс», а конкретно Михайлу Бородіну і Андрію Рибкіну, вдалося запозичити алгоритмічну оптимізацію множення вектора на стовпець у швидкісних реалізацій шифру AES (Rijndael), яка дозволяє замінити класичну реалізацію множення за O(n^2) множень в полі на O(n) складання по модулю два векторів довжини O(n) з використанням предвычисленных таблиць, і про яку було повідомлено на конференції РусКрипто, якщо мені не зраджує пам'ять, в 2014 році.
Коротко, оптимізація полягає в наступному: припустимо, в результаті твори деякого вектора U
U = \left( u_0, u_1, \dots, u_{n - 1} \right) \in \left(\mathrm{GF}(256)\right)^n
на матрицю A
A = 
\begin{pmatrix}
a_{0, 0} &amp;amp; a_{0, 1} &amp;amp; \cdots &amp;amp; a_{0, n-1} \\
a_{1, 0} &amp;amp; a_{1, 1} &amp;amp; \cdots &amp;amp; a_{1, n-1} \\
\vdots &amp;amp; \vdots &amp;amp; \ddots &amp;amp; \vdots \\
a_{n-1, 0} &amp;amp; a_{n-1, 1} &amp;amp; \cdots &amp;amp; a_{n-1, n-1} 
\end{pmatrix}_{n \times n} \in \left( GF(256) \right)^{n \times n}
вийшов вектор V:
V = U \times A = \left( v_0, v_1, \dots, v_{n-1} \right).
Традиційний спосіб обчислення компонент цього вектора полягає в послідовному скалярному множення рядка вектора U на стовпці матриці A:
v_i = \bigoplus_{j = 0}^{n-1} u_j a_{j, i}
Обчислення кожної з n компонент вектора V n операцій множення в полі n-1 операцію додавання по модулю 2, так трудомісткість обчислення всіх компонент становить O(n^2). Так, звичайно, можна не множити в полі кожен раз, можна заздалегідь обчислити таблиці логарифма та експоненти; можна навіть заздалегідь обчислити твори всіх можливих байт на елементи матриці (матриця адже фіксована і не змінюється в процесі шифрування), і зберігати ~256 таблиць по 256 байт-творів. У матриці є однакові елементи? Відмінно, кількість таблиць можна скоротити, але асимптотична складність не зміниться.
А можна піти іншим шляхом. Замість того, щоб обчислювати кожну компоненту вектора-твори як суму n однобайтових прозведений, скористаємось особливістю множення вектора на матрицю і будемо обчислювати одразу всі компоненти вектора як суму n векторів:
V = 
\left( \bigoplus_j m_j a_{j, 0}, \bigoplus_j m_j a_{j, 1}, \dots, \bigoplus_j m_j a_{j, n-1} \right) =
\bigoplus_j m_j \left( a_{j, 0}, a_{j, 1}, \dots, a_{j, n-1} \right).
Здавалося б, що змінилося? Ті ж операції, але в іншому порядку. Зауважу, однак, що, по-перше, підвищилася розряди доданків з одного байта до n байт, і такі суми можна (і потрібно) обчислювати в довгих регістрах, а, по-друге, кожний доданок є покомпонентним твором одного (!) байти вектора на фіксовану рядок матрицю.
Ось тут детальніше: можна заздалегідь обчислити твори виду
m_i \times \left( a_{i, 0}, a_{i, 1}, \dots, a_{i, n-1} \right), \quad \forall m_i \in \mathrm{GF}(256),
тобто помножити відому рядок i матриці A на всі можливі значення байта i вектора U, і замість множення чергового байта на цей рядок просто читати твір з таблиці. Тоді множення вектора на матрицю зводиться до зчитування n рядків творів з заздалегідь обчисленій таблиці і побітове додавання цих рядків для отримання результуючого вектора V. Ось так, досить просто, можна сильно спростити множення вектора на матрицю до O(n), якщо додавання векторів вважати елементарними операціями.
У разі ГОСТ Р 34.12 '15 n = 16, так, вектори мають довжину 16 байт, або 128 біт, і дуже здорово поміщаються в довгі XMM регістри, а для їх складання передбачені додаткові процесорні інструкції, наприклад,
pxor
.
Все дуже здорово, але як бути з вузлом заміни? Читач напевно помітить, що при наявності побайтовых вузлів заміни, які в загальному випадку не векторизуются, всі алгоритмічні принади такого обчислення L-перетворення нівелюються вартістю завантаження векторів в регістри до перетворення та їх вивантаження після перетворення. Хороше питання.
Хороший, і дуже витончено вирішуване. Виявляється, вузли заміни можна просто «склеїти» L-перетворенням, замінивши обчислювані заздалегідь рядки твору з
m_i \times \left( a_{i, 0}, a_{i, 1}, \dots, a_{i, n-1} \right), \quad \forall m_i \in \mathrm{GF}(256),
на
\pi(m_i) \times \left( a_{i, 0}, a_{i, 1}, \dots, a_{i, n-1} \right), \quad \forall m_i \in \mathrm{GF}(256),
Тоді один повний цикл шифрування зводиться до
  • змішування з ключем (
    pxor
    ),
  • застосування склеєного перетворення LS (в найкращому випадку це 16 завантажень 128-бітних векторів з кешу і 15 додавань
    pxor
    ).
Звичайно, такі оптимізації не безкоштовні, для їх використання потрібно, по-перше, обчислювати і зберігати в кеші единовременну одну з двох таблиць з рядками-творами, кожна з яких містить 256 * 16 * 16 байт, або 64 КБ. Чому таблиць дві? Тому що зворотне перетворення, що використовується при расшифровании, зажадає множення на обернену до L матрицю, і спричинить за собою нові твори.
По-друге, склеювання вузлів заміни з множенням на матрицю можливо тільки в тому випадку, якщо до блоку спочатку застосовують підстановку, а потім множення, тому алгоритм розшифрування доведеться трохи змінити. Відкритий текст виходить з шифртекста простим зверненням всієї схеми (всі перетворення оборотні):
P = X_0 S^{-1} L^{-1} \circ \dots \circ X_8 S^{-1} L^{-1} \circ X_9 ©.
Зауважимо, що при расшифровании «в лоб» до проміжного тексту спочатку застосовують множення на обернену матрицю, а потім вже дія підстановкою, тому, щоб склеїти ці перобразования і тут, доведеться впорядкувати алгоритм розшифрування.
Зауважу, що композиція перетворень
V = L^{-1} X_{K_i} S^{-1} (U) = L^{-1} \left( S^{-1}(U) \oplus K_i \right)
тотожна композиції
V = L^{-1} S^{-1}(U) \oplus L^{-1} \left( K_i \right) = X_{L^{-1} (K_i)} L^{-1} S^{-1} (U)
в силу лінійності перетворення L. Тоді розшифрування можна здійснити наступним чином:
P = 
X_{K_0} S^{-1} \circ 
\left( X_{L^{-1} (K_1)} L^{-1} S^{-1} \right) \circ 
\dots \circ
\left( X_{L^{-1} (K_8)} L^{-1} S^{-1} \right) \circ 
X_{L^{-1} (K_9)} L^{-1} S^{-1} S ©
Тут кожне з перетворень, зворотних до SL, можна здійснювати за схемою, аналогічною до розглянутої. Обчислені таблиці рядків-творів постити не буду, — вони занадто великі навіть для спойлерів; їх можна знайти, наприклад, здесь.
Оптимізація з використанням SSE2
В принципі, з базовими перетвореннями все зрозуміло, залишилося всі ці оптимізації покласти на asm.
Для роботи з блоками пропоную використовувати набір інструкцій SSE2, будемо використовувати інструкції
movdqu
та
movdqa
для завантаження і вивантаження даних в регістри, інструкції
pxor
,
pand
,
pandn
для булевих операцій, інструкції
psrlw
та
psllw
для двійковими зрушень,
pextrw
для вивантаження байт регістра.
Так, є ще одна тонкість реалізації ГОСТ Р 34.12 '15. Крім общеалгоритмических оптимізацій на зразок описаних вище, для подальшого прискорення продуктивності потрібно враховувати особливості асемблера та особливості планувальника, який інструкції може поставити на паралельне виконання різних виконуючих пристроїв.
Облік особливостей адресної арифметики
Перша особливість реалізації алгоритму пов'язана з тим, що, якщо не враховувати пристрій предвычисленной таблиці і непрямої індексної адресації зі зміщенням, то при компіляції можна отримати приблизно наступний вихлоп складання з черговою рядком-твором:
pextrb xmmX, eax, i ; виділення байта i (SSE 4.1) в 32--бітний регістр eax
movzxd rcx, eax ; переміщення виділеного байта в 64--бітний регістр rcx
add rcx, rcx ; подвоєння значення байта
pxor xmmY, [rbx + 8*rcx + 0xi000] ; обчислення зсуву по таблиці

В регістрах при цьому зберігаються:
  • rbx
    містить адресу базового зміщення таблиці,
  • xmmX
    містить вхідний блок,
  • xmmY
    містить вихідний блок (акумулятор, суму),
  • eax
    та
    rcx
    використовуються для виділення і подвоєння байта зміщення.
Слід мати на увазі, що предвычисленная таблиця влаштована таким чином:
uint8_t table[16][256][16],

тобто значення рядків-творів зберігаються в цій таблиці безперервно, один за одним, зовнішній індекс i відповідає i-ой рядку матриці L-перетворення, середній індекс j дорівнює i-ому байту вхідного блоку, а внутрішній індекс k відповідає індексу чергового байта доданку:
Xi = table[i][input[i]][0] ... [16]

Таким чином, адреса першого байта чергового доданку
Xi
виражається наступним чином:
[Xi] = rbx + (0x1000 * i) + (16 * input[i]),

де
  • (0x1000 * i)
    відповідає зміщенню поточного рядка (
    table[i]
    ),
  • (16 * input[i])
    відповідає зміщенню поточного доданку
    Xi
    (
    table[i][input[i]]
    ).
Так, значення поточного байта доводиться множити на 16, але адресна арифметика дозволяє використовувати максимальне значення коефіцієнта-множника дорівнює восьми. Тому компілятор доводиться перекладати значення байта в
rcx
, подвоювати його, і тільки потім обчислювати адресу
Xi
.
Для того, щоб уникнути подібних надмірностей, можна скористатися ідеологією SIMD, і обчислити наведені зміщення заздалегідь, а не за допомогою адресної арифметики.

Попереднє обчислення наведених зсувів (доданки в адресі чергового
Xi
)

Тут числами 0..15 позначені відповідні байти вхідного блоку, а
00
та
FF
відповідають нульовому байту і його інверсії.
З допомогою маски
00FF 00FF 00FF 00FF 00FF 00FF 00FF 00FF
та інструкцій
pand
та
pandn
парні і непарні байти вхідного блоку виділяються в регістри лівих і правих зсувів відповідно; потім з допомогою інструкцій
psrlw
та
psllw
зміщення наводяться (домножаются на 16) до значень, придатним для використання адресної арифметики.
Так, кожне L-перетворення доповнюється наступними рядками:
pand xmmR, xmmZ ; виділення правих зсувів
pandn xmmL, xmmZ ; виділення лівих зсувів
psllw xmmR, 4 ; приведення правих зсувів
psrlw xmmL, 4 ; приведення лівих зсувів

і попередньою завантаженням маски в регістр
xmmZ
. Зате обчислення адрес доданків
Xi
тепер може бути здійснено лише за дві інструкції:
pextrw eax, i ; виділення наведеного зміщення i
pxor xmmY, [rbx + rax + 0xi000] ; обчислення зсуву по таблиці за допомогою адресної арифметики

Облік специфіки мікроархітектури
Більшість сучасних процесорів Intel і AMD мають два, або більше, виконуючих АЛУ, здатних одночасно виробляти арифметичні дії з різними регістрами, і планувальник, здатний розподілити блок виконуваних інструкцій за різними АЛУ для паралельного виконання з метою економії процесорного часу.
Так, чергуючи команди, що використовують різні регістри, можна допомогти процесору виконувати код паралельно. Склеєне LS-перетворення є двійковій сумою шістнадцяти різних 128-бітних чисел
Xi
, і, швидше за все, на сучасних процесорах може бути здійснена у два паралельних потоки (на одному ядрі) з використанням двох акумуляторів: лівого і правого кешей.
Приклад коду, що реалізує базову перетворення (шифрування блоку)
.code

extern bitmask:xmmword
extern precomputedLSTable:xmmword

encrypt_block proc

initialising:
movdqu xmm0, [rcx] ; [unaligned] loading block
lea r8, [precomputedLSTable + 01000h] ; [aligned] aliasing table base with offset
lea r11, [precomputedLSTable] ; [aligned] aliasing table base
movdqa xmm4, [bitmask] ; [aligned] loading bitmask
mov r10d, 9 ; number of rounds, base 0

round:
pxor xmm0, [rdx] ; [aligned] mixing round with key

movaps xmm1, xmm4 ; securing bitmask from @xmm4
movaps xmm2, xmm4 ; securing bitmask from @xmm4

pand xmm2, xmm0 ; calculating offsets
pandn xmm1, xmm0
psrlw xmm2, 4
psllw xmm1, 4

pextrw eax, xmm1, 0h ; accumulating caches
movdqa xmm0, [r11 + rax + 00000h]
pextrw eax, xmm2, 0h
movdqa xmm3, [r8 + rax + 00000h]
pextrw eax, xmm1, 1h
pxor xmm0, [r11 + rax + 02000h]
pextrw eax, xmm2, 1h
pxor xmm3, [r8 + rax + 02000h]
pextrw eax, xmm1, 2h
pxor xmm0, [r11 + rax + 04000h]
pextrw eax, xmm2, 2h
pxor xmm3, [r8 + rax + 04000h]
pextrw eax, xmm1, 3h
pxor xmm0, [r11 + rax + 06000h]
pextrw eax, xmm2, 3h
pxor xmm3, [r8 + rax + 06000h]
pextrw eax, xmm1, 4h
pxor xmm0, [r11 + rax + 08000h]
pextrw eax, xmm2, 4h
pxor xmm3, [r8 + rax + 08000h]
pextrw eax, xmm1, 5h
pxor xmm0, [r11 + rax + 0a000h]
pextrw eax, xmm2, 5h
pxor xmm3, [r8 + rax + 0a000h]
pextrw eax, xmm1, 6h
pxor xmm0, [r11 + rax + 0c000h]
pextrw eax, xmm2, 6h
pxor xmm3, [r8 + rax + 0c000h]
pextrw eax, xmm1, 7h
pxor xmm0, [r11 + rax + 0e000h]
pextrw eax, xmm2, 7h
pxor xmm3, [r8 + rax + 0e000h]

pxor xmm0, xmm3 ; mixing caches

add rdx, 10h ; advancing to next round key
dec r10 ; decrementing round index
jnz round

last_round:
pxor xmm0, [rdx] ; [aligned] mixing round with key
movdqu [rcx], xmm0 ; [unaligned] storing block

ret

encrypt_block endp

end

Висновок
Всі описані техніки прискорення базового перетворення дозволяють істотно підвищити продуктивність шифру; в якості конкретного прикладу можу навести числа, отримані на одному ядрі Intel Core i7-2677M Sandy Bridge @ 1.80 GHz, це 120 МБ/с у версії з SSE інструкціями проти 1.3 МБ/с в неоптимізованого версії.
Далі — більше, ГОСТу можна надати додаткове прискорення:
  • наявність регістрів більшої довжини дозволяє ще більше оптимізувати пакетне шифрування (тільки в режимах, які допускають паралельну обробку блоків);
  • теоретично, заміна обчислення підстановки по таблиці значень обчисленням з використанням секретної структури вузла заміни, може дати невеликий приріст продуктивності при расшифровании.
Пограти з різними реалізаціями базового перетворення ГОСТ Р 34.12 '15 можна, зібравши у себе проект. Написаний він на C99, на досконалість коду і абсолютну оптимальність він не претендує, але автор буде радий будь-якої конструктивної критики. Для складання потрібно CMake 3.2.1+ і компілятор, що підтримує C99. Шифр реалізовано в трьох версіях, за стандартом без істотних оптимізацій (compact), з передобчисленням, але без SIMD інструкцій (optimised) та з використанням інструкцій SSE2 (SIMD).
Безпосередні кроки складання можна подивитися в скрипті Travis CI в корені проекту, в комплект входять модульні тести на контрольні приклади з стандарту (ключове розклад, шифрування і розшифрування блоку) на CTest і примітивний спосіб вимірювати продуктивність з використанням
std::chrono
на C++11.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.