Особенности криптоанализа блочных шифров

Базовым при использовании блочных шифров является режим простой замены[1].

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

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

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

При случайном выборе блоков открытого текста их повторение является не столь уж редким событием. Напомним известный парадокс «дней рождений», который заключается в том, что если имеется выборка объема, сравнимого с , множества из N элементов, то вероятность того, что в ней окажутся два одинаковых элемента, сравнима с 1/2. Этот парадокс показывает, что при случайном выборе блоков открытого текста для получения повтора достаточно взять в среднем порядка блоков, где N — общее число блоков, которые теоретически могут встретиться в открытом тексте.

Применительно к алгоритмам DES и ГОСТ 28147-89, которые оперируют с двоичными векторами длины 64, это означает, что в среднем, уже среди 232 блоков открытого текста, будут встречаться повторяющиеся.

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

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

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

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

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

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