dxdt.ru: занимательный интернет-журнал

Сокрытие “статистики” входного потока данных – основная характеристика, связанная со стойкостью шифра. Собственно, в обобщённом смысле, цель использования шифра состоит именно в том, что, после обратимого преобразования, всякая “статистика”, порождающая различительные характеристики для входных сообщений, оказалась вычислительно эквивалентна случайной. Именно так нужно представлять эффект действия современного шифра. Можно представить, что есть некая “коробочка”, которая получает на вход открытый текст (исходное сообщение), а выводит либо результат зашифрования (с некоторым секретным ключом, который, для простоты, каждый раз новый), либо случайную, равновероятную последовательность битов (подходящую по длине). Тогда, для стойкого шифра, внешний наблюдатель, передающий в “коробочку” открытый текст, не может с высокой вероятностью определить, что именно пришло в ответ – результат зашифрования или случайные биты (тут нужно учитывать повторные попытки, свойства ключей, делать оговорки про вычислительные возможности и т.д., но это всё детали).

Так, если взять в качестве примера привычную запись текста на естественном языке, то простой шифр алфавитной замены (“А” -> “Д”, “Б” -> “Э” и т.д.: буквы заменяются на буквы по перестановке того же алфавита, ключом является перестановка) не обладает только что описанным свойством: если попросить “коробочку” зашифровать слово “длинношеее”, то результат, очевидно, получится угадываемым (ну, конечно, в той степени, в какой вообще можно поверить в случайные биты).

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

Интересно, что внесение дополнительного слоя сохранения некоторых статистических характеристик является одной из теоретических областей создания алгоритмических закладок/бэкдоров в шифрах. Представьте блочный шифр. То есть, такой шифр, который на вход получает, предположим, строго 256 битов и 256-битный ключ, а выводит тоже строго 256 битов шифротекста. Многие современные шифры так работают. Если шифр идеальный, то вывод будет равновероятным, а для успешного поиска нужно будет перебирать, хотя бы, 2^255 вариантов.

Однако можно предположить, что специальный дефект в алгоритме создаёт недокументированное разбиение всего пространства шифротекстов на некоторые интервалы (даже не обязательно, чтобы на непересекающиеся). Попадание шифротекста в тот или иной интервал связано со значением некоторых битов ключа. Тогда, если проверка свойств шифра проводится для нескольких случайных входных блоков, даже при использовании одного значения ключа, обнаружить какие-то подозрительные разбиения не получится. Однако сторона, знающая о недокументированном дефекте алгоритма, может передать кортеж специально подготовленных блоков открытого текста, прочитать вывод шифра, определить последовательность интервалов, в которые попали блоки шифротекста, и вычислить интервал возможных значений ключа (ключ использовался один и тот же). Этот вычисленный интервал для ключа может быть небольшим, – например, 2^32 значений, – что позволяет найти ключ перебором.

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

Адрес записки: https://dxdt.ru/2023/07/19/10567/