На пути к Skein: просто и понятно про Blowfish

    «От желудка иглобрюхих рыб отходят мешковидные выросты. При появлении опасности они наполняются водой или воздухом, из-за чего рыба становится похожой на раздувшийся шар
    с торчащими шипиками. Шарообразное состояние делает рыб практически неуязвимыми. Если всё же достаточно крупный хищник попытается проглотить такой шар, то он застревает
    в глотке у хищника, который впоследствии умирает»


                                    Википедия, свободная энциклопедия.

    К концу 1993 года в мире криптографии возникла очень неловкая ситуация. Алгоритм симметричного шифрования DES, со своим слабеньким 56-битным ключом, был близок к фиаско, а существующие
    на тот момент альтернативные варианты, такие как Khufu, REDOC II, IDEA были защищены патентами
    и не доступны для свободного использования. Алгоритмы RC2 и RC4, разработанные в то время компанией RSA Security, также требовали проведение процедуры лицензирования. И в целом, индустрия криптографии в рамках государственных организаций и крупных корпораций была
    обращена в сторону использования секретных алгоритмов, таких как Skipjack.

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

    И он появился.

    В 1994 году, на семинаре Fast Software Encryption в Кембридже, а впоследствии и в журнале «Lecture Notes in Computer Science» (#809, 1994), Брюс Шнайер презентовал свой алгоритм блочного шифра, который был назван Blowfish.

    Отличительными особенностями этого алгоритма стала более высокая степень криптостойкости, нежели алгоритма DES (в том числе за счет использования переменной длины ключа, до 448 бит), высокая скорость шифрации/дешифрации (за счет генерации таблиц замены) и конечно — возможность его свободного применение для любых целей.

    Оригинальная статья Брюса Шнайера от 1994 года из архива:
    Block Ciphers II, Bruce Schneier (внизу страницы):
    Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish). 191-204

    Или в формате PDF

    Введение


    BlowFish — алгоритм 64-битного блочного шифра с ключом переменной длины. Был разработан известным специалистом в области криптографии и защиты информации Брюсом Шнайером (Bruce Schneier) в 1993 году.

    В общем случае алгоритм состоит из двух этапов — расширение ключа и шифрация/дешифрация исходных данных.



    На этапе расширения ключа, исходный ключ преобразуется в матрицу раундовых ключей (P)
    и матрицу подстановки (S, Substitution-box) (или замены), общим объемом в 4168 байт. По всей вероятности, этим «расширением» (от 448 бит до 4168 байт) и объясняется выбор названия
    алгоритма Blowfish.

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

    В процессе, мы реализуем программный код шифратора по алгоритму Blowfish на языке C++. Готовые реализации для языков высокого уровня (такие как C/C++/Haskell/Perl/…) доступны на странице
    с исходными кодами на сайте Брюса Шнайера.


    Сеть Фейстеля


    В 1971 году, «крестный отец» стандарта DES, Хорст Фейстель (Horst Feistel), в стенах корпорации IBM, разработал два устройства, реализовавшие различные алгоритмы шифрования, названные затем общим название «Люцифер». В одной из этих устройств он использовал схему, которую впоследствии назвали Сетью Фейстеля. Эта сеть представляет собой определённую многократно итерированную (повторяющуюся) структуру, которою называют ячейкой Фейстеля.



    Принцип работы сети достаточно прост:

    1. Исходные данные разбиваются на блоки фиксированной длины (как правило кратно степени двойки — 64 бит, 128 бит). В случае если длина блока исходных данных меньше длины разрядности шифра, то блок дополняется каким-либо заранее известным образом.

    2. Блок делится на два равных подблока — «левый» L0 и «правый» R0.
      В случае 64-битной разрядности — на два блока с длиной 32 бита каждый.

    3. «Левый подблок» L0 видоизменяется функцией итерации F(L0, P0) в зависимости от ключа P0,
      после чего он складывается по модулю 2 (XOR) с «правым подблоком» R0.

    4. Результат сложения присваивается новому левому подблоку L1, который становится левой половиной входных данных для следующего раунда, а «левый подблок» L0 присваивается без изменений новому правому подблоку R1, который становится правой половиной.

    5. Эта операция повторяется n-1 раз, при этом при переходе от одного этапа к другому меняются раундовые ключи (P0, P1, P2 и т.д.), где n — количество раундов для используемого алгоритма.

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

    Вернемся к алгоритму Blowfish.

    В общем случае, алгоритм шифрования Blowfish представляет собой сеть Фейстеля, но с некоторыми особенностями генерации и использования раундовых ключей (P0, P1 …).

    Для начала допустим, что функция итерации F в алгоритме Blowfish это некоторый «черный ящик», который принимает на входе и выдает на выходе 32-битное число (DWORD).

    При этом 32-битные раундовые ключи Pn:

    1. вычисляются по некоторому правилу от исходного ключа (длиной до 448 бит);
    2. не являются аргументами для функции итерации F;
    3. непосредственно складываются по модулю 2 (XOR) с «левым блоком».
      Результат этой операции является входящим 32-битным аргументом для функции F.



    В алгоритме Blowfish при шифрации выполняется 16 раундов (внутри сети Фейстеля), а 17-й и 18-й ключи складываются с левым и правым выходным блоком последнего раунда. Такое количество раундов было выбрано, поскольку именно оно определяет длину возможного ключа.

    Но здесь у внимательного читателя может возникнуть вопрос: если используется 18 раундовых ключей, каждый из которых имеет длину 32 бита, то в итоге мы получаем ключ длиной 576 бит (18 ключей × 32 бита). Почему же длина исходного ключа в Blowfish изначально ограничена 448 битами?

    Ответ прост — она не ограничена. Можно использовать ключи до 576 бит. Но! Ограничение было сделано исходя из требований к соблюдению безопасности и криптостойкости алгоритма.

    Давайте реализуем сеть Фейстеля для алгоритма Blowfish на языке C++:

    void swap(unsigned long *a, unsigned long *b)
    {
        unsigned long temp;
        if (a && b) {
            temp = *a, *a = *b, *b = temp;
        }
    }
    
    void blowfish_encrypt_block(blowfish_ctx *ctx, unsigned long *high, unsigned long *low)
    {
        int i;
        for (i = 0; i < 16; i++) {
            *high ^= ctx->p[i];
            *low ^= F(ctx, *high);
            swap(low, high);
        }
        swap(low, high);
        *low ^= ctx->p[16];
        *high ^= ctx->p[17];
    }
    


    Расширение ключа (Blow it up!)


    Подготовительным этапом алгоритма Blowfish является этап расширения ключей. В процессе этого этапа строится матрица раундовых ключей Pn и матрица подстановки — 4 блока замены S-Box (Substitution-box), каждый из которых состоит из 256 32-х битных элементов.



    Элементы этих матриц шифруются (вычисляются) с помощью рассмотренной выше сети Фейстеля для алгоритма Blowfish. Таким образом, сеть Фейстеля в алгоритме Blowfish используется:

    • для шифрации/дешифрации исходных данных;
    • для генерации матрицы раундовых ключей и матрицы подстановки (т.е. расширения ключа).

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

    В процессе расширения ключа обрабатывается
    18 × 32 (P1,P2 …) + 4 × 256 × 32 (S1—S4) = 33344 бит или 4168 байт данных.

    При этом выполняется (18 (Pn) + 4 × 256 (S1—S4)) / 2 = 521 полная итерация сети Фейстеля.

    Всё это является весьма трудозатратной операцией, и именно поэтому алгоритм Blowfish
    не рекомендуется использовать там, где требуется частая смена ключа.

    Опишем алгоритм расширения ключа.

    1. Выбирается «искреннее число» (или иначе — «Nothing up my sleeve number»). Это такое число, которое изначально не содержит каких-либо повторяющихся последовательностей и является известным. Делается это для того, чтобы показать, что константа разработчиками была выбрана без преследования каких-то «гнусных» целей, наприимер для создания лазейки в алгоритме (backdoor).

      В качестве такого искреннего числа в Blowfish обычно используется число PI. Вычислять шестнадцатеричное представление значение числа PI мы не будем, а воспользуемся уже готовым решением: 8366 шестнадцатеричных цифр мантиссы для числа PI.

    2. Значением мантиссы числа PI заполняется матрица раундовых ключей (FIXED_P) и матрицы подстановки (FIXED_S):

      typedef struct _blowfish_ctx
      {
          unsigned long p[18];
          unsigned long sbox[4][256];
      } blowfish_ctx;
      
      const unsigned int FIXED_S[4][256] = {
          {
              0xD1310BA6, 0x98DFB5AC, 0x2FFD72DB, 0xD01ADFB7,
              0xB8E1AFED, 0x6A267E96, 0xBA7C9045, 0xF12C7F99,
              0x24A19947, 0xB3916CF7, 0x0801F2E2, 0x858EFC16,
              0x636920D8, 0x71574E69, 0xA458FEA3, 0xF4933D7E,
              0x0D95748F, 0x728EB658, 0x718BCD58, 0x82154AEE,
              0x7B54A41D, 0xC25A59B5, 0x9C30D539, 0x2AF26013,
              .... Часть значений не указаны ради экономии места ....
              0xB74E6132, 0xCE77E25B, 0x578FDFE3, 0x3AC372E6
          }
      };
      
      const unsigned long FIXED_P[] = {
          0x243F6A88, 0x85A308D3, 0x13198A2E, 0x03707344,
          0xA4093822, 0x299F31D0, 0x082EFA98, 0xEC4E6C89,
          0x452821E6, 0x38D01377, 0xBE5466CF, 0x34E90C6C,
          0xC0AC29B7, 0xC97C50DD, 0x3F84D5B5, 0xB5470917,
          0x9216D5D9, 0x8979FB1B
      };


    3. Значение каждого раундового ключа Pn (P1, P2 …) складывается по модулю 2 (XOR) с соответст- вующим элементами исходного ключа K. Например, выполняется XOR раундового ключа P1
      с первыми 32 битами исходного ключа K, P2 со вторыми 32 битами исходного ключа K и так далее. Если исходный ключ K короче длины всех раундовых ключей (576 бит), то он конкатенируется сам
      с собой: KK, KKK и так далее.

      for(i = 0, k = 0; i < 18; i++) {
          for(j = 0, long_key = 0; j < 4; j++, k++) {
              long_key = (long_key << 8) | key[k % key_len];
          }
          ctx->p[i] ^= long_key;
      }


    4. Далее нам необходимо зашифровать (вычислить новые значения) элементов матрицы раундовых ключей и матрицы подстановки. Для этого мы воспользуемся реализованным нами алгоритмом сети Фейстеля для Blowfish.

      1. Используя текущие раундовые ключи P1—P18 и матрицы подстановок S1—S4 (о том, где именно используются матрицы подстановок будет рассказано ниже), шифруем 64-битную последовательность нуля: 0x00000000 0x00000000, а результат записываем в P1 и P2.

      2. P1 и P2 шифруются изменёнными значениями раундовых ключей и матриц подстановки, результат записывается соответственно в P3 и P4.

      3. Шифрование продолжается до изменения всех раундовых ключей P1—P18 и элементов матриц подстановок S1—S4.

        Т.е. в конечном счете нам надо получить результат вычисления по схеме cети Фейстеля алгоритма Blowfish для (18 Pn + 4 × 256 (S1—S4)) / 2 = 521 итераций. Мы поделили на 2, поскольку за кажду итерацию мы вычисляем сразу два новых значения для элементов матрицы раундовых ключей или матрицы подстановок.


      for (i = 0, k = 0, l = 0; i < 18; i++) {
          blowfish_encrypt_block(ctx, (unsigned long*)&k, (unsigned long*)&l);
          ctx->p[i] = k;
          ctx->p[++i] = l;
      }
      for (i = 0; i < 4; i++) {
          for (j = 0; j < 256; j++) {
              blowfish_encrypt_block(ctx, (unsigned long*)&k, (unsigned long*)&l);
              ctx->sbox[i][j] = k;
              ctx->sbox[i][++j] = l;
          }
      }


    На этом, подготовительный этап алгоритма Blowfish — расширение ключа — завершается. Но перед тем, как рассмотреть этап шифрации/дешифрации, давайте все-таки раскроем наш «черный ящик» — функцию F, исполняемую на каждом раунде внутри итераций сети Фейстеля для алгоритма Blowfish.



    Функция итерации (раунда)


    Функция раунда или итерации (поскольку она общая для всей используемой сети Фейстеля) весьма проста и использует лишь несколько логических операций над матрицей подстановок. Изначально, разрабатывая «Люцифера», Хорст Фейстель даже предполагал использование для матрицы подстановок электронного блока с простой линейной схемой.



    Итак:

    1. Входящий 32-битный блок делится на четыре 8-битных блока, назовем их X1, X2, X3, X4
      (см. рисунок выше).

    2. Каждый каждый из которых является индексом массива таблицы замен S1—S4.
    3. значения S1[X1] и S2[X2] складываются по модулю 232, затем результат складывается
      по модулю 2 (XOR) с S3[X3] и, наконец, складываются с S4[X4] опять же по модулю 232.
    4. Результат вычислений и будет значением функции F(X1—X4).

    Формула функции:


    Всё крайне просто. Функция использует матрицы подстановок S1—S4 для того, чтобы линейно преобразовать входящие 32 бита данных в значение из матрицы подстановки. А сами значения
    в матрицах подстановки вычисляются на рассмотренном нами ранее этапе расширения ключа.

    Реализация функции на языке C++:

    unsigned long F(blowfish_ctx *ctx, unsigned long x)
    {
        return ((ctx->sbox[0][(x >> 24) & 0xFF] + ctx->sbox[1][(x >> 16) & 0xFF]) ^
          ctx->sbox[2][(x >> 8) & 0xFF]) + ctx->sbox[3][(x) & 0xFF];
    }


    А теперь давайте перейдем собственно к процессу шифрации исходных данных.

    Шифрация / дешифрация исходных данных


    Сюрприз! На самом деле алгоритм шифрации и дешифрации исходных данных мы уже рассмотрели. Все дело в том, что как мы заметили в самом начале, шифрация / дешифрация данных, и создание вышеупомянутой матрицы раундовых ключей и матрицы подстановки, происходит с помощью рассмотренной сети Фейстеля для алгоритма Blowfish.

    Т.е. в нашей программной реализации, весь процесс шифрации исходных данных строится по аналогии с процессом шифрации на этапе расширения ключа. Т.е. представляет собой итеративное исполнение функции blowfish_encrypt_block (реализация сети Фейстеля) над каждыми 64 битами исходных данных. Раундовые ключи P (P1, P2, &hellip) и матрицы подстановки S1—S4 являются входными параметрами соответственно для сети Фейстеля и функции F внутри этой сети.



    В итоге, если резюмировать алгоритм шифрации или дешифрации в алгоритме Blowfish,
    то получим следующие шаги:


    1. Выделяем массив из 18 элементов для раундовых ключей сети Фейстеля и 4 матриц подстановки по 256 элементов в каждой.

    2. Заполняем выделенный массив значением мантиссы числа PI.

    3. Делаем итеративный XOR: Pi = Pi XOR Ki (где Pi — раундовый ключ, а Ki — исходный ключ).

    4. Шифруем раундовые ключи и матрицы подстановки с помощью сети Фейстеля (в качестве входящего параметра для функции внутри сети используются матрица подстановки; раундовые ключи внутри сети берутся из матрицы раундовых ключей).

    5. Шифруем/дешифруем блоки исходных данных по 64 бита также с помощью сети Фейстеля.

    Всё просто.

    Резюме


    Дорогие читатели. Уметь описать сложные вещи простыми словами — очень сложно.

    Перед тем, как начать писать данный текст, я попытался поставить себя на место разработчика,
    который хочет попытаться изучить рассмотренный алгоритм Blowfish.

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

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

    Спасибо.
    Yours sincerely, A.B.

    p.s. Планируется продолжение…
    Поделиться публикацией
    Комментарии 28
      +2
      Много исходников есть на сайте автора алгоритма
      www.schneier.com/blowfish.html
      Вообще Blowfish очень простой алгоритм. Как по F, так и по всему.
      Единственный замут — инициализация
        +3
        Самое сложное для понимания -это та самая F, которая позволяет производить обратное преобразование. Какая бы статья полная не была, но мне как человеку увлекающемуся, до сих пор не понятно как она в обратную сторону работает.
          +2
          Функция F в обратную сторону не работает (: Это раундовые ключи местами меняются.
            +2
            p.s. Имеется в виду, что функция F — линейная, и в процессе шифрации, и в процессе дешифрации ее задача одна и та же и принцип работы не меняется. Что касаемо самого алоритма, то в случае дешифрации меняется порядок использования ключей. Просто проследите за логикой работы на схемах шифрации/дешифрации, которая приведена в статье.
              0
              дада, я уже по википедийной статье разобрался в том, что F не должна работать в обратную сторону
                0
                Хорошо. Жаль только, что там нет схемы Фейстеля для процесса расшифровки.
            +2
            Как раз не требуется чтобы она была обратима, у нас есть вход для неё.
              0
              Вообще это все строится на том что сложение по модулю легко обратимо. Т.е. если A xor B = C, то С xor B = A, а С xor A = B. В общем применяем операцию сложения по модулю к одному из операндов и результату их сложения и получаем другой операнд.

              Вас что не учили как правильно верёвку на циферблат часов наматывать?)
              +3
              Вот и пример, когда патенты являлись двигателем прогресса.
                +1
                Хорошая статья, спасибо автору. Но мне кажется, что такие статьи надо сразу копировать на википедию.
                  +2
                  > Ответ прост — она не ограничена. Можно использовать ключи до 576 бит. Но! Ограничение было сделано исходя из требований к соблюдению безопасности и криптостойкости алгоритма.

                  Можно объяснить этот момент?
                    0
                    Со слов Брюса Шнайера:

                    Ограничение размера ключа в 448 бит было сделано для достижения гарантии того, что каждый бит каждого под-ключа (имеются в виду раундовые ключи и элементы матрицы подстановки) непосредственно зависит от каждого бита исходного ключа (в целом), поскольку использование совокупности ключей P15, P16, P17 и P18 не оказывает влияние на каждый бит зашифрованного текста.
                    0
                    Отличная статья, автору спасибо! Реквестирую описание алгоритма AES.
                      +2
                      Спасибо. AES в планах (:
                        +2
                        Такое описание AES видели?
                        www.moserware.com/2009/09/stick-figure-guide-to-advanced.html

                        Мне оно кажется просто восхитительным. Обратите внимание на Foot-shooting Prevention Agreement в начале 3 акта ;)
                        +2
                        Отличная статья. Может, действительно, отредактируете её и на Википедию зальёте?
                          0
                          Природная скромность не позволяет ^^

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

                          А так, Хабрахабр ведь тоже своего рода свободная энциклопедия…
                            0
                            Не-не, это должны увидеть и не хабра-люди.
                            Пожалуйста, залейте на википедию.
                          +2
                          В профессиональных кругах слово «шифрация» не в почёте, вместо него употребляется «шифрование». Аналогично с «дешифрацией». При этом следует иметь в виду, что «дешифрование» — это получение plain text без ключа, т. е. «взлом»; а «расшифровывание» — это получение plain text при знании ключа.
                            0
                            Разумеется, иная терминология никак не уменьшает ценности статьи. :-) Автору спасибо.
                            В своё время пришлось разбираться с алгоритмом IDEA практически по исходникам, текстов мне тогда было доступно мало, поэтому представляю, что это такое. И если сообщество сочтёт нужным, поддержу тему статьёй по этому алгоритму.
                              +1
                              Это банальная грамотность, а не профессиональные круги.
                                0
                                Вопрос терминологии очень часто метит на звание «камня преткновения» в IT-среде. Но, к счастью, достигнуть этого у него не удается, поскольку понимаем мы друг друга зачастую с полуслова :) Контекст всё же первичен, а форма представления вторична.

                                В вопросе шифрации/шифрования я исхожу из следующей логики:

                                «шифрация» — как процесс (as process) — произвести шифрацию входящих данных;
                                «шифрование» — как возможность (as aptitude) — эта программа использует шифрование по алгоритму XXL.

                                По аналогии с «врач сейчас проводит «операцию» и «этот врач может «оперировать».

                                Если относительно дешифрации/взлома/расшифрования — то любой процесс получения plain-text из зашифрованного — это в принципе так или иначе процесс дешифрации (расшифрования как. Просто, если это было сделано без полного ключа, то это еще и «взлом».

                                Но, как Вы правильно заметили ниже, «хоть горшком назови, только в печь не сажай» (:
                                +1
                                Как у Blowfish'a с сертификацией в России?
                                  0
                                  Алексей, вопросами сертификации в конкретных странах из принципа не интересуюсь. У меня характер космополита и поэтому в вопросах разработки я привык доверять мировому опыту в первую очередь.

                                  Думаю, на местах, это скорее правовые и организационные вопросы, на которые лучше ответят юристы.
                                  0
                                  Жаль про Skein ничего нет…
                                    0
                                    На схеме у Вас 17 блоком XOR-ится верхняя половинка, а 18 — нижняя, в коде же наоборот. Это может каким-либо образом повлиять на криптостойкость алгоритма?
                                      0
                                      Пардон, ошибся. Всё верно.
                                      0
                                      p.s. Планируется продолжение…

                                      Продолжения еще не было?

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

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