ГОСТ Р 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-битного секретного ключа в прямом порядке на циклах шифрования с первого по восьмой, с девятого по шестнадцатый, с семнадцатого по двадцать четвертый; и в обратном порядке на циклах с двадцать пятого по тридцать второй:


    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; a_{0, 1}   &amp; \cdots &amp; a_{0, n-1} \\
a_{1, 0}   &amp; a_{1, 1}   &amp; \cdots &amp; a_{1, n-1} \\
\vdots     &amp; \vdots     &amp; \ddots &amp; \vdots \\
a_{n-1, 0} &amp; a_{n-1, 1} &amp; \cdots &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 (C).


    Заметим, что при расшифровании «в лоб» к промежуточному тексту сначала применяют умножение на обратную матрицу, а потом уже действие подстановкой, поэтому, чтобы склеить эти перобразования и тут, придется переупорядочить алгоритм расшифрования.


    Замечу, что композиция преобразований


    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 (C)


    Здесь каждое из преобразований, обратных к 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 четные и нечетные байты входного блока выделяются в регистры левых и правых смещений соответственно; затем c помощью инструкций 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 with round 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 with round 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.

    Поделиться публикацией

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 51

      0
      Заранее извиняюсь за, возможно, тупой вопрос. Я не специалист по криптографии. Но меня волнует вопрос — чем этот алгоритм лучше существующих мировых аналогов?
        +8

        Сложно что-то сказать о криптостойкости алгоритма по сравнению с зарубежными аналогами, шифр сравнительно новый и пока мало исследован. На мой взгляд, он во многом похож на AES, выглядит очень крепко, очевидных слабых мест в нем нет.


        В России более важными вопросами являются вопросы сертификации средств защиты информации; и с средствами, использующими зарубежную криптографию, вы попросту не пройдете сертификацию в органах. Поэтому здесь выбора особо и нет.

          0
          Если для работы, то эти алгоритмы по ГОСТУ нужны, например, для работы, образно говоря, с секретными документами (банковская сфера, финансовая, военка и т.д. и т.п.).
          Если для поиграться, то есть, например, такой подход: житель России используй AES (или другой зарубежный шифр), житель США — используй какой-нибудь ГОСТ.
            +3
            А меня вот другое интересует.
            Разработка средств шифрования — в России это лицензируемый вид деятельности.
            Стоимость лицензий от 350 тыс. рублей.
            Но не знаю, что это значит. Если как вы говорите «поиграться» и я вставляю всем известный алгоритм (хоть ГОСТ, хоть AES/RC5/RC6) в свою программу — это я нарушаю какие-то законы или нет?
            Или не нарушаю никаких законов то того момента пока государство не купит мою программу? Или как?
            А если программа просто использует протокол https — это требует лицензии?
            Может конечно глупый вопрос…
              0
              100% не нарушаете, если у вас длина ключа менее 56бит.
              Ну а вообще — разработка и применение готового алгоритма это разные вещи.
              Если начнёте продавать программу/устройства — как минимум вам светит статья «незаконное предпринимательство».
              Ну и из опыта — любые операции с информацией, не представляющей гостайну, оказанные в рамках «для собственных нужд», допускаются к использованию на предприятии. Например я могу сам установить криптопро на предприятии, для этого не нужна лицензия ФСБ.
              немного почитать
                0
                минимум будет если полученная прибыль 1.5 млн.руб, или причинен ущерб гос-ву, иначе всего навсего административный штраф, при чем сумма далеко не «неподъемная».
                +2
                А если программа просто использует протокол https — это требует лицензии?

                В любом случае, лучше занять очередь в пятницу, что бы по раньше освободится в субботу!
                  0
                  по оплате, насколько я понял из доклада Вартана Хачатурова (ссылка ниже) — оплачивать нужно только если сам занимаешься лицензируемым видом деятельности. ГОСТ можно хоть куда вставлять, это опенсорс в чистом виде.
                    0
                    Или не нарушаю никаких законов то того момента пока государство не купит мою программу? Или как?
                    Не знаю как сейчас, но 10 лет назад, когда я последний раз с этим сталкивался можно было использовать хоть чёрта лысого если не произносить запрещённых слов.

                    В частности в системе, которую использовали на выборах (уж куда государственнее?) использовался GnuPGP с некоторыми изменениями в названиях сигнатур (без измнения алгоритмов, конечно). В документация вся эта хрень с ключами на 4096 бит и прочим проходила как «фирменный модуль повышения надёжности передачи данных и обнаружения несанцкионированных изменений» (или что-то в этом духе, точное название сейчас не скажу).

                    Главное — не заявлять что вы что-то там шифруете и что-то там гарантируете. Как только вы это заявили — всё, требуются сертификаты и прочее. При работе с госструктурами иногда такие заявления нужны, иногда — нет.
                      +1
                      Лицензируется коммерческая разработка средств шифрования, здесь все слова важные.
                      Если вы для себя пилите (и не только поиграться, но и реально использовать в рамках своей организации) — это не лицензируется.
                      Если вы пилите продукт, но он опенсорс или вы просто (пока) его не продаёте в РФ — лицензия не нужна.
                      Лицензируется именно разработка продукта (программ и возможно железок). Алгоритмы тут как бы сбоку, пока вы не выходите на продажи в госсектор — вы можете брать любые.
                      Если ваш продукт нигде не называется «средством шифрования» и ничего такого не обещает — лицензия не нужна.
                      Ну и наконец вопрос с получением лицензии не в деньгах, точнее не в сумме 350 тыс. Во-первых, там с документами тот ещё геморрой, вы на картриджи для ксерокса, нотариуса и затраты времени гендиректора, который будет по этим нотариусам с банками бегать два месяца, потратите не сильно меньше. А во-вторых, у вас в штате (именно в штате, всё в белую) должно быть как минимум 2 инженера с высшим (возможно, вторым высшим) конкретно по специальности ИБ, причём никакие смежные специальности не допускаются. Та же кафедра ИУ8 в Бауманке очень неплохо зарабатывает именно на получающих второе высшее по данной теме. И ваши расходы на их содержание в штате по-белому превысят те 350 тысяч за то время, пока оформляется лицензия.
                        0
                        Это вообще скользкая тема, год назад интересовался. Смотрим пункт 3 постановления РФ от 16 апреля 2012 г. № 313, там перечень в каких случаях не распространяется.

                        Если вы используете программу для «внутренних или личных нужд», то использовать можно что угодно. Если же вы эту программу продаете, то попадает под перечень лицензируемых видов деятельности. Конкретно: «Разработка защищенных с использованием шифровальных (криптографических) средств информационных систем».

                        Ну и у отдельных типов финансовых учреждений уже свои правила на этот счет.

                        Для себя выделил несколько вариантов, когда изучал как вставить ЭЦП на борту криптотокена в коммерческую систему:
                        1) Самостоятельное получение лицензии ФСБ со всеми вытекающими последствиями;
                        2) Само приложение поставлять без криптозащиты. Ее подключать в виде отдельного модуля с помощью пользователя и/или посредника. При этом модуль в таком случае должен разрабатываться и распространяться отдельно посредником, имеющим лицензию. Поставлять модуль необходимо отдельно от основного приложения. Другими словами: использовать услуги другой стороны;
                        3) Использовать простую подпись без криптографии, например усиленную смс-подтверждением. При этом нужно формировать соглашение между сторонами обмена о том, что такая подпись признается юридически значимой. А в суде факт формирования такой подписи осуществляется проверкой логов сервера и др. согласно условиям соглашения.
                        4) Использовать средства СКЗИ встроенные в ОС. (под закон не попадает)
                        5) Осуществлять подпись не на территории РФ. (Электронные подписи, созданные в соответствии с нормами права иностранного государства и международными стандартами признаются юридически значимыми согласно законодательству РФ)
                        6) Не использовать криптографию и ЭЦП вовсе.

                        Самое смешное, что чтобы просто передать систему с критотокеном клиенту, курьер должен пройти курсы повышения квалификации.

                        Нет, https не требует лицензирования.

                        Поправьте если не прав, не юрист
                          0
                          Да я тоже не юрист.
                          Но мне как-то странно, что вот строится целая законодательная глыба по лицензированию, криптографии, все строго и серьезно и тот вдруг раз «https» — можно. Хотя тот же https — это серьезное шифрование с серьезными целями и т.д.
                          Строгость российских законов компенсируется необязательностью их исполнения.
                            0

                            Могу и обмануть, это только моё мнение:


                            Вся эта глыба документов применяется только в тот момент, когда вы говорите, что реализовали криптографию и гарантируете это.
                            Т. е. если информация относится к защищаемой согласно закону, например, персональные данные, то требуется доказуемая с точки зрения органов гарантия.
                            Для этого и есть лицензирование, сертификация и прочие радости, предназначенные для подтверждения этих гарантий.


                            Если же это не требуется, то всё использование алгоритмов шифрования и подписей — это просто меры, направленные на безопасность, но не гарантирующие её (с точки зрения органов).


                            TL;DR: Использовать криптографию можно, нельзя говорить, что она есть и что-то гарантирует.

                      +6
                      Здесь сначала нужно определиться, что такое «лучше» для алгоритма шифрования, и относительно интересов кого это «лучше» отсчитывается.
                      И вот для системных (=используемых на уровне государства и выше) шифров единственное разумное «лучше» — это пуленепробиваемая стойкость.
                      Ну, представьте, что некто взломал шифр, которым банки подписывают сообщения о переводе денег. И теперь может лепить поддельные сообщения на тему «ооо ромашка переводит ооо вектор сто тыщь миллионов». Хотя у «ромашки», возможно, таких денег отродясь не было, сообщение подписано банком ромашки и будет исполнено. Представили? Это мгновенный крах банковской системы и моментальная остановка экономики страны, потому как другого способа перевода крупных сумм, кроме как через банки, сегодня нет.

                      Потенциальные векторы угроз стойкости шифров можно разделить на три больших класса:

                      1. Баги реализации в конкретной библиотеке. Ну, из недавно нашумевшего — история с хартблидом в либе OpenSSL. Поскольку либа популярная, пострадали очень многие. Такие ситуации неприятны, но лечатся относительно легко: патчем либы либо переходом на более другую библиотеку. Сам стандарт тут не при чём и его не трогают.

                      2. Баги в алгоритме, которые делают возможным взлом шифра на обычном ПК или хотя бы на мощном суперкомпьютере. Пример: первые алгоритмы шифрования в сетях GSM. Лечится очень тяжело: нужно менять алгоритм, нужно внедрять новый алгоритм вообще везде, а это очень много времени и денег. Современные смартфоны, например, всё ещё несут на борту старые алгоритмы шифрования на случай, если где-то ещё встречаются старые базовые станции, и наоборот. Если удастся взломать одно или другое, можно вынудить вторую, невзломанную железку перейти на старый шифр, после чего перехват разговора становится делом техники.
                      Для защиты от подобных атак, кстати, помогает тактика неуловимого Джо. При прочих равных лучше иметь свой алгоритм, просто потому что он не самый распространённый в мире, и его будут тупо реже пытаться взламывать.

                      3. Сознательно внесённые в шифр бэкдоры. Есть обоснованное мнение, что все вот эти якобы случайные таблицы коэффициентов — нифига не случайны, и к ним есть «мастер ключ», резко снижающий стоимость вскрытия перебором. То есть хакер Вася или там Джон обламает зубы на ультрасложном матане и нехватке вычислительных мощностей, но вот заказчики бэкдора в погонах смогут при необходимости прочитать или подделать нужное сообщение. Точно не все подряд сообщения в потоке, но как минимум нужные им для конкретной злодейской задачи.
                      Звучит как теория заговора, но здесь можно много всего вспомнить, от наездов федералов на pgp до откровений Сноудена и продуктов жизнедеятельности Яровой.
                      И защита от таких бэкдоров на уровне государства может быть только одна — свои алгоритмы со своими православными бэкдорами.
                        +2
                        Звучит как теория заговора, но здесь можно много всего вспомнить, от наездов федералов на pgp до откровений Сноудена и продуктов жизнедеятельности Яровой.
                        А не проще вспомнить реальную историю?
                      +1
                      Есть хорошее свежее видео " для непосвященных" про алгоритмы ГОСТ — доклад Вартана Хачатурова, OSSDEVCONF-2016. Автор — сборщик дебиана, криптоэнтузиаст и чиновник минкомсвязи :-)
                      Там вопрос мировых аналогов, закладок и всяческих мифов разобран довольно подробно.
                      https://vimeo.com/185219716
                        0
                        Надо спрашивать — чем он лучше предыдущего ГОСТа.

                        В свете сведений, опубликованных Сноуденом (о том, как NSA пропихивает для использования заведомо слабые алгоритмы) вопрос про мировые аналоги лучше не задавать.

                        Он лучше предыдущего ГОСТа (не говоря уж о DES) как минимум тем, что длина ключа намного длиннее, и «подслушать» этот ключ становится намного сложнее (по «колебаниям мирового эфира»). При сертификации аппаратных средств шифрования это один из самых сложных тестов.
                        • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            Сначала для «пешеходов» наверное будет полезно про кузнечик от юного, но уже внятного поколения криптографов, экспертов ТК26 — «ГОСТ Р 34.12–2015: чего ожидать от нового стандарта?» — http://www.itsec.ru/articles2/crypto/gost-r-chego-ozhidat-ot-novogo-standarta/

                            Пару слов про качество СТРИБОГа. На семинаре в Bristol Univ однажды была дискуссия по TUAK,
                            который исходно прописан под KECCAK (SHA-3). Было также краткое обсуждение об инкапсуляции 34.11-2012 в конструкции TUAK = {TOPc; f1; f1*; f2; f3; f4; f5; f5*}, на что Teng Wu (Waterloo) классно заметил, что и SHA-3 и GOST примерно одинаково неидеальны, ну типа mert (fr), но вполне пригодны:-)

                              0
                              Всё стою на камне, —
                              Дай-ка брошусь в море.
                              Что пошлёт судьба мне,
                              Радость или горе?
                              Может, озадачит…
                              Может, не обидит…
                              Ведь кузнечик скачет,
                              А куда — не видит.


                              Козьма Прутков. Пред морем житейским.
                          0
                          большое спасибо за статью! давно увлекаюсь шифрами.
                            –1
                            Если Вы «давно увлекаетесь шифрами», то эта статья для Вас не должна была привнести ничего нового) Она полезна в первую очередь новичкам)
                            +1
                            Попробовал собрать проект под Visual Studio 12 2013 (MSVC 18.0.40629.0), собралось с двумя незначительными правками. В benchmark.cpp добавил:

                            #ifdef _MSC_VER
                            	#include <algorithm>
                            #endif
                            

                            Без него компилятор ругался на std::generate_n… а в optimised.c добавил:

                            #ifdef _MSC_VER
                            	#define restrict __restrict
                            #endif
                            

                            Может быть есть и более «красивое» решение для сборки под MSVC…
                              0

                              Первое исправление надо добавлять независимо от компилятора, потому что функция std::generate_n и правда находится в <algorithm>

                                0

                                @Decker, mayorovp Спасибо, ошибку с <algorithm> исправил.

                            • НЛО прилетело и опубликовало эту надпись здесь
                                0
                                Скорость всё равно печальная.
                                У госта 89 чуточку лучше: http://www.securitylab.ru/analytics/480357.php

                                Автор этой статьи, Андрей Луценко, обладает рядом патентов на скоростную реализацию ГОСТ 28147 '89, ему экономически выгодно пиарить прежний стандарт шифрования.


                                Если же объективно говорить о производительности скоростных версий шифров на одной и той же платформе, то результаты оказались примерно следующие: ~170 МБ/с на поток для Магмы и ~150 МБ/с на поток для Кузнечика.

                                  0
                                  Ещё лучше хотя бы опционально использовать _mm_stream_load_si128() из SSSE3 для загрузки блока данных

                                  За наводку на _mm_stream_load_si128 спасибо, попробую.

                                    0
                                    Рекорд скорости для Кузнечика сейчас — чуть более 330 МБ/с, но это проприетарные решения от вендоров и рассказывать, как это сделано, «они конечно не будут»(с). Так что автору просто мегареспектище за статью. Надеюсь будут еще.
                                      0

                                      @ru_crypt, уточните, 330 МБ/с в одном потоке? Какой процессор? Какой режим? Какой набор инструкций?


                                      Не могу представить себе способа еще почти втрое алгоритмически ускорить базовое преобразование. Думаю, что такие скорости достижимы при


                                      • мощном процессоре с высокой тактовой частотой,
                                      • наличии кэша первого уровня в 64 КБ (тогда в него вся таблица войдет),
                                      • использовании более длинных регистров и конвейерном шифровании.
                                        0
                                        Информация была представлена на CTCrypt, презентация выложена здесь: https://www.slideshare.net/secret/8AC2FSDNCZiyZv

                                        О скоростях слайды начинаются с 45-го (из 55).

                                        Подробности, полагаю, вполне можно запросить у авторов презентации.
                                          0
                                          Режим гаммирования, в одном потоке. Core i5-6500, AVX.

                                          Частота 3.2 GHz, ничего необычного.
                                          64 KB в кэш первого уровня заведомо не войдет.
                                          А насчет длинных регистров и конвейеров — тут уж точно нужно к авторам презентации обратиться за комментариями…
                                            +1

                                            Спасибо, надо будет пореверсить после релиза новой версии криптопровайдера.

                                        0
                                        «гост89 типа вне закона с 1 января этого года,»

                                        Отмечу, что ГОСТ 28147-89 никто не выводил (и пока не собирается) из действия, несмотря на ввод ГОСТ Р 34.12-2015.
                                        +1
                                        Как дела обстоят с закладками в шифре? надеялся увидеть этот пункт есть они или нет.
                                          +1

                                          @shifttstas Если они есть, мы об этом не узнаем ;)

                                            0
                                            https://eprint.iacr.org/2015/812.pdf
                                              +1

                                              @AleksGRV Не осилили пост? В ней про структуру узлов замены написан целый раздел, даже ссылка на более полную работу представлена.


                                              Но даже известное устройство узлов замены не могу назвать закладкой шифра, ведь полученные таким способом узлы обладают действительно хорошими криптографическими свойствами, и очевидным образом использовать эту структуру для дешифрования шифртекста или определения цикловых ключей я не вижу.

                                            0
                                            Со всеми оптимизациями скорости хотелось бы услышать что-нибудь про тайминг-атаки.
                                              0

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

                                                0
                                                По ссылке, как я понял, авторы утверждают, что косяк в самом алгоритме AES, а не в какой-то его конкретной реализации. Мой вопрос относился именно к проблемам, которые всплывают из-за оптимизации/ускорения работы алгоритма.
                                                  +1

                                                  Я вам ответил именно на ваш вопрос ;) ГОСТ во многом похож на AES; можно устроить очень похожие атаки на время загрузки векторов из таблиц, оно прямо зависит от значений байт промежуточного текста. Таблицы появляются только в оптимизированной версии шифра. В теории, при известном открытом тексте и точном способе измерять это время, можно попробовать определить байты первых двух цикловых ключей (половин секретного ключа). Но это тема отдельной статьи.

                                              0
                                              Не очень понятно, зачем было оптимизировать полную схему преобразования на «полноформатном» процессоре, когда давно уже известна оптимизация (от какого-то горячего финского парня, исходники бродят по сети), позволяющая свести операцию к небольшому количеству операций исключающее-или с константами из относительно небольшого массива (64к для шифрования и 192к для дешифрования, если мне не изменяет память).

                                              В таком варианте переложение алгоритма на SSE инструкции дают порядка >200Mb/s на каком-то core i5, на котором я пробовал. Да и то, думаю, скорость упирается в скорость обмена с памятью, сама скорость выполнения операции XOR на порядки выше.

                                              Впрочем, это имеет определённый смысл как упражнение в программировании, а также как тренировку перед имплементацией алгоритма для более слабых процессоров, у которых 256к таблиц не влезает в кэш.
                                                0

                                                Не утрудитесь ссылочкой на оптимизацию, о которой вы говорите? Ведь в посте полный цикл как раз сводится к небольшому количеству (15) операций исключающее ИЛИ (XOR) с константами из небольшого массива (64 КБ для шифрования и 64 КБ для расшифрования).

                                                  0
                                                  Не дочитал Вашу статью до конца, уж извините. Дошёл до формул и подумал что дальше Вы по ними оптимизацию на SSE делаете :)

                                                  Вот исходники, аж от 14го года
                                                  https://github.com/mjosaarinen/kuznechik
                                                  Насчёт 192к я соврал, это суммарный размер таблицы для шифрования и дешифрования.
                                                  Таблицы дешифрования занимают 128к (две таблицы по 64к), таблицы шифрования занимают 64к.
                                                  Шифрование несколько медленнее (но не в два раза, как можно было бы подумать :))
                                                  Если при дешифровании Вы сумели обойтись всего одной таблицой в 64к, тогда Ваша статья заслуживает более глубокого изучения :)
                                                    0
                                                    Кстати, подумалось, что «секретная» структура узла замены на самом деле просто реверс-инжиниринг формулы самопального генератора псевдослучайных последовательностей, которой воспользовались авторы алгоритма для генерации узла замены :)

                                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                Самое читаемое