28.04.2015 14:56
Yaruson 12 10747 Источник
О реализации этого алгоритма шифрования уже рассказывал FTM: как в общем и целом, так и про режим простой замены. После изучения существующих библиотек и отдельных реализаций этого ГОСТа на C# я решил написать свой велосипед, в первую очередь, ради интереса и опыта. Результатами этой работы мне и хотелось бы поделиться с уважаемым сообществом.

ГОСТ 28147-89 — симметричный блочный алгоритм шифрования с 256-битным ключом, оперирует блоками данных по 64 бита.
Один из режимов его работы, гаммирования с обратной связью, является потоковым режимом блочного шифра.

Описание алгоритма


  1. Исходное сообщение разбивается на блоки по 64 бита
  2. На каждый блок XOR'ом «накладывается» гамма, тоже длиной 64 бита
  3. Гамма формируется шифрованием 64-битного блока «состояния» с помощью ключа в режиме простой замены
    • В момент начала шифрования сообщения блок принимается равным синхропосылке или вектору инициализации
    • В следующей итерации вместо синхропосылки используется зашифрованный блок текста из предыдущей

Обратите внимание, что приведённая последовательность действий справедлива как для шифрования, так и расшифрования. Разница в том, откуда берётся зашифрованный блок текста для обработки следующего блока, это лучше всего видно на картинке:



Реализация


Данный алгоритм был реализован в форме плагина к менеджеру паролей KeePass.
Исходники доступны на GitHub.

Гаммирование с обратной связью


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

public int TransformBlock (byte[] inputBuffer, int inputOffset, int inputCount, byte[] outputBuffer, int outputOffset)
{
  byte[] dataBlock = new byte[inputCount];
  byte[] gamma = new byte[GostECB.BlockSize];
  byte[] result = new byte[inputCount];

  Array.Copy(inputBuffer, inputOffset, dataBlock, 0, inputCount);

  gamma = GostECB.Process(_state, _key, GostECB.SBox_CryptoPro_A, true);
  result = XOr(dataBlock, gamma);

  Array.Copy(result, 0, outputBuffer, outputOffset, inputCount);
  Array.Copy(_encrypt ? result : dataBlock, _state, inputCount);

  return inputCount;
}

Режим простой замены


GostECB.Process — реализация того же ГОСТа в режиме простой замены, или «электронной кодовой книги». Хорошее описание алгоритма есть в соответствующем разделе статьи Википедии, а также в статье ГОСТ 28147-89 (Часть 2. Режим простой замены) на Хабрахабре.

Размер снихропосылки, гаммы и «состояния» равен 64 байтам, поэтому шифрование в режиме простой замены можно рассматривать в рамках одного блока. Впрочем, было бы несколько — они просто шифровались бы по очереди.

Исходный код метода GostECB.Process
public static byte[] Process(byte[] data, byte[] key, byte[][] sBox, bool encrypt)
{
    Debug.Assert(data.Length == BlockSize, "BlockSize must be 64-bit long");
    Debug.Assert(key.Length == KeyLength, "Key must be 256-bit long");

    var a = BitConverter.ToUInt32(data, 0);
    var b = BitConverter.ToUInt32(data, 4);

    var subKeys = GetSubKeys(key);

    var result = new byte[8];

    for (int i = 0; i < 32; i++)
    {
        var keyIndex = GetKeyIndex(i, encrypt);
        var subKey = subKeys[keyIndex];
        var fValue = F(a, subKey, sBox);
        var round = b ^ fValue;
        if (i < 31)
        {
            b = a;
            a = round;
        }
        else
        {
            b = round;
        }
    }

    Array.Copy(BitConverter.GetBytes(a), 0, result, 0, 4);
    Array.Copy(BitConverter.GetBytes(b), 0, result, 4, 4);

    return result;
}


Для работы с 32-битными частями исходного блока очень удобно использовать тип uint.
Так, в функции F() сложение по модулю ключа и части блока, а также циклический сдвиг на 11 бит запишется просто и лаконично:

private static uint F(uint block, uint subKey, byte[][] sBox)
{
    block = (block + subKey) % uint.MaxValue;
    block = Substitute(block, sBox);
    block = (block << 11) | (block >> 21);
    return block;
}

Метод подстановки по S-блокам работает с 4-битными кусочками 32-битного подблока, их достаточно удобно отделять побитовым сдвигом и дальнейшим умножением на 0x0f:

private static uint Substitute(uint value, byte[][] sBox)
{
    byte index, sBlock;
    uint result = 0;

    for (int i = 0; i < 8; i++)
    {
        index = (byte)(value >> (4 * i) & 0x0f);
        sBlock = sBox[i][index];
        result |= (uint)sBlock << (4 * i);
    }

    return result;
}

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

private static int GetKeyIndex(int i, bool encrypt)
{
    return encrypt ? (i < 24) ? i % 8 : 7 - (i % 8)
                   : (i < 8) ? i % 8 : 7 - (i % 8);
}

Источники


Комментарии (12)


  1. milabs
    29.04.2015 00:21
    #8398081
    +3

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


    1. Yaruson Автор
      29.04.2015 10:07
      #8398365
      +2

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


      1. milabs
        29.04.2015 12:25
        #8398621
        +3

        Лучше, но всё-равно с ошибкой. Гамма должна проворачиваться только тогда, когда был обработан блок целиком. У вас тут Array.Copy(_encrypt ? result : dataBlock, _state, inputCount); вообще что-то непонятное выполняется. Проведите простой тест на корректность — зашифруйте 16 байтов в режиме CFB скармливая функции по одному байту и сравните с тем, что получается при шифровании 2-х блоков.


        1. Yaruson Автор
          29.04.2015 12:48
          #8398669

          Да, мне не пришло в голову, что можно TransformBlock можно попытаться использовать для неполного блока.
          В случае с полными работает верно, не так ли?

          Как по вашему мнению, стоит ли следить за количеством обработанных байт и проворачивать гамму только после отработки целого блока, или же просто запретить (плохо звучит, но всё же) обрабатывать TransformBlock неполные блоки?


          1. milabs
            29.04.2015 12:55
            #8398679
            +1

            В случае с полными работает верно, не так ли?

            Не знаю, я не проверял.

            Как по вашему мнению, стоит ли следить за количеством обработанных байт и проворачивать гамму только после отработки целого блока, или же просто запретить (плохо звучит, но всё же) обрабатывать TransformBlock неполные блоки?

            Это зависит от того, что Вы хотите получить и где использовать.


            1. Yaruson Автор
              29.04.2015 14:11
              #8398895

              В описании метода TransformBlock из MSDN ничего не сказано про обработку неполных блоков. Можно предположить, что этот метод предназначен исключительно для преобразования полных блоков, тем более, что с неполными работает TransformFinalBlock:

              TransformFinalBlock is a special function for transforming the last block or a partial block in the stream. It returns a new array that contains the remaining transformed bytes. A new array is returned, because the amount of information returned at the end might be larger than a single block when padding is added.
              В данной реализации последний блок теперь может быть неполным, это мы исправили в прошлый раз. Как я понимаю, под «partial block» имеется в виду последний неполный блок, а не любой неполный блок в исходном сообщении. Итого получается, что TransformBlock должен работать с полными блоками, а TransformFinalBlock — с полным или неполным.

              Выходит, можно ограничиться проверкой размера блока в TransformBlock, чтобы формально соблюсти интерфейс ICryptoTransform.

              Этот класс предполагается использовать в CryptoStream. К сожалению, я не знаю, как он работает внутри с ICryptoTransform, но полагаю, что он принимает во внимание свойства InputBlockSize и OutputBlockSize, определённые в интерфейсе.


              1. milabs
                29.04.2015 14:16
                #8398905

                Здесь я Вам не советчик, руководствуйтесь MSDN.


  1. milabs
    29.04.2015 12:25
    #8398619

    .


  1. avssav
    30.04.2015 07:07
    #8400287
    +1

    FSB certified?


    1. Yaruson Автор
      30.04.2015 07:35
      #8400303

      К сожалению, нет. У меня даже нет лицензии на разработку, производство и распространение криптографических средств :)
      Можно считать, что это исключительно из академического интереса.


  1. vasiatka
    01.05.2015 23:20
    #8402693

    Ради интереса… Не хотите попробовать алгоритм «кузнечик»? Данный ГОСТ доживает последние дни, т.к. был теоретически взломан…


    1. Yaruson Автор
      01.05.2015 23:35
      #8402703

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