6.5. Методы анализа алгоритмов блочного шифрования

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

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

Показательно, что при случайном выборе блоков откры­того текста их повторение является не столь уж редким со­бытием. Напомним известный парадокс "дней рождений", который заключается в том, что если имеется выборка объема, сравнимого с N , из множества из N элементов, то ве­роятность того, что в ней окажутся два одинаковых элемента, сравнима с 1/2. Этот парадокс показывает, что при случайном выборе блоков открытого текста для получения повтора достаточно взять в среднем порядка N блоков, где N – общее число блоков, которые теоретически могут встретить­ся в открытом тексте. Применительно к алгоритмам DES и ГОСТ, которые оперируют с двоичными векторами длины 64, это означает, что в среднем, уже среди 2³² блоков откры­того текста, будут встречаться повторяющиеся. Следует отметить, что при шифровании осмысленных текстов на есте­ственных языках повторения будут появляться еще чаще, поскольку в осмысленных текстах в силу используемой лексики и грамматических правил встречаются далеко не вес сочетания букв и знаков алфавита.

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

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

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

Отдельно остановимся на методах анализа криптографических алгоритмов, основанных на принципе многократного использования блочных шифров. Р.Меркль и М.Хеллмнп на примере DES показали, как, используя метод встречи посередине, можно вскрыть схему двукратного шифрования.

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

Предположим, что известны блок М открытого текста и соответствующий ему блок С шифрованного текста. Алго­ритм вскрытия неизвестных ключей k₁ и k₂ состоит из двух этапов.

На первом этапе перебираются все возможные варианты ключа k₁. Для каждого варианта k ключа k₁ вычисляются значения ADR(k) =Е_k(М), после чего значения k поме­щаются в память по адресу ADR(k).

На втором этапе опробуются возможные варианты ключа k₂. Для опробуемого варианта k' ключа k₂ вычисляются значения ADR(k') = D_k’(C) и производится обращение в память по адресу ADR(k'). Если по этому адресу памяти записи отсутствуют, то происходит переход к опробованию следующего варианта k' ключа k₂. Если же по адресу ADR(k') в памяти хранится ключ k, то образуется допусти­мая пара ключей (k,k'), удовлетворяющая равенству С=Е_k’(Е_k(М)).

Заметим, что в ячейку памяти с номером ADR(k') могут попасть несколько вариантов ключа k (для этого память необходимо соответствующим образом организовать). Для каждого из них пара (k,k') является допустимым ключом. Несложно заметить, что для реализации данного алгоритма требуется 2К опробований и столько же операций обращения к памяти, где К — общее число ключей шифра. Таким образом, вместо К² операций, требуемых при полном переборе ключей, затраты метода встречи посередине составляют порядка 4К операций (операции опробования и обращения к памяти для простоты считают приблизительно равносильными по сложности). Заметим, что такой резкий эффект снижения трудоемкости достигается за счет использова­нии большой (и специальным образом организованной) памяти.

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

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

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

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

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

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