Как протестировать криптосистему на замкнутость?

Введение

23 ноября 1976 года DES или Data Encryption Standart был утверждён правительством США как официальный стандарт шифрования и оставался им до 1980 года. DES является алгоритмом симметричного шифрования, в основе которого лежит сеть Фейстеля. Останавливаться на подробном описании работы DES мы не будем, так как она нас не особо интересует в рамках данной статьи, но почитать подробнее можно, например, тут [1].

Любая криптосистема C характеризуется пятью параметрами: — множество ключей, — множество открытых текстов, — множество шифртекстов, E — преобразование зашифрования, D — преобразование расшифрования. Пространством сообщений в данном случае является , а множеством ключей , где каждый ключ отвечает какому-либо обратимому преобразованию . Важно, чтобы DES не был замкнутой криптосистемой. Напомню, что криптосистема называется замкнутой, если для любых трёх ключей существуют ключи , такие что , для любого сообщения . Замкнутость в свою очередь влечёт за собой групповую структуру, в этом случае нет смысла проводить операцию зашифрования больше одного раза, так как это будет эквивалентно какому-то единичному зашифрованию. Такая особенность значительно понижает криптостойкость системы. Также, такая она влечёт уязвимость к атаке с известным открытым текстом, которая в среднем будет требовать шагов.

Является ли DES группой?

В статье [2] было показано, что DES не является группой. Остановимся более подробно на вероятностном тесте MCT(meet-in-the-middle closure test), предложенном в [2] и основанном на атаке meet in the middle, и вычислим вероятность нахождения совпадения.

Теорема: если криптосистема C замкнута, то MCT найдёт совпадения с вероятностью не меньше , где 2r — количество ключей, выбранных для проведения теста. Если же C произвольная криптосистема, то вероятность совпадения не более .

В чём же суть MCT?

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

input:

; l, r — параметры контроля.

begin

1. Выбираем и . Для вычисляем . Пусть = и .

2. Для выбираем и вычисляем и .

3. Сортируем по первой компоненте тройки (, , «A») и (, , «B») для .

4. Для каждого «совпадения» с , если , то return(«Совпадение найдено»). Для проверки, что достаточно проверить, что для всех .

5. return(«Совпадений не найдено»).

end

Доказательство теоремы

Гораздо проще сначала доказать вторую часть утверждения. Предположим, что C замкнута, тогда для любого преобразования существует единственное преобразование , такое, что . Тогда всего возможных пар такого вида не более чем , и каждая пара даёт преобразование совпадающее с с вероятностью . Значит осталось посчитать вероятность наступления хотя бы одного из событий Все события независимы, значит вероятность успеха — их сумма их вероятностей. Т.е. .

Перейдём к групповому шифру. Для подсчёта соответствующей вероятности будем пользоваться идеей парадокса дня рождений [3]. P(«найти совпадения») это тоже самое, что 1 — P(«не найти совпадений»), а вероятность не найти совпадений посчитать гораздо проще.

Пусть X = {}, Y = {}, . Тогда

Попробуем вычислить эту вероятность приближённо.

Помним, что

Используем разложение в ряд Тейлора:

Тогда

Т.е. .

К сожалению, ещё не всё.

P(«не найти совпадений») = P(«X без повторов») P(«Y без повторов»).

P(«X без повторов») = P(«Y без повторов») — вот опять пригодился парадокс дней рождений.

Отсюда P(«не найти совпадений») .

Тогда вероятность, что MCU найдёт совпадения. Теорема доказана.

Литература

1. https://csrc.nist.gov/files/pubs/fips/46-3/final/docs/fips46-3.pdf

2. https://link.springer.com/article/10.1007/BF00206323

3. https://www.jstor.org/stable/27956609

Источник: habr.com