Meet in the middle closure test

Введение

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

Любая криптосистема C характеризуется пятью параметрами: - множество ключей, - множество открытых текстов, - множество шифртекстов, E - преобразование зашифрования, D - преобразование расшифрования. Пространством сообщений в данном случае является $mathcal{M}={0, 1}^{64}$ , а множеством ключей $mathcal{K}={0, 1}^{56}$ , где каждый ключ отвечает какому-либо обратимому преобразованию . Важно, чтобы DES не был замкнутой криптосистемой. Напомню, что криптосистема называется замкнутой, если для любых трёх ключей существуют ключи , такие что , $T_iT_j^{-1}T_k(x)=T_s(x)$ для любого сообщения . Замкнутость в свою очередь влечёт за собой групповую структуру, в этом случае нет смысла проводить операцию зашифрования больше одного раза, так как это будет эквивалентно какому-то единичному зашифрованию. Такая особенность значительно понижает криптостойкость системы. Также, такая она влечёт уязвимость к атаке с известным открытым текстом, которая в среднем будет требовать $2^{28}$ шагов.

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

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

Теорема: если криптосистема C замкнута, то MCT найдёт совпадения с вероятностью не меньше $1 - e^{frac{-3r^2}{|mathcal{K}|}}$ , где 2r - количество ключей, выбранных для проведения теста. Если же C произвольная криптосистема, то вероятность совпадения не более $frac{|mathcal{K}|^2}{|mathcal{M}|!}$ .

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

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

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

begin

Выбираем и $p_1, ... ,p_l xleftarrow{text{R}} mathcal{M}$ . Для вычисляем . Пусть = и .
Для выбираем $a_i, b_i in mathcal{K}$ и вычисляем $x_i=T_{a_i}(p)$ и $y_i=T^{-1}_{b_i}(c)$ .
Сортируем по первой компоненте тройки (, , "A") и (, , "B") для .
Для каждого "совпадения" с , если $T_k=T_{b_j}T_{a_i}$ , то return("Совпадение найдено"). Для проверки, что $T_k=T_{b_j}T_{a_i}$ достаточно проверить, что $c_h=T_{b_j}T_{a_i}(p_h)$ для всех .
return("Совпадений не найдено").

end

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

Гораздо проще сначала доказать вторую часть утверждения. Предположим, что C замкнута, тогда для любого преобразования существует единственное преобразование , такое, что . Тогда всего возможных пар такого вида не более чем $|mathcal{K}|^2$ , и каждая пара даёт преобразование совпадающее с с вероятностью $frac{1}{|mathcal{M}|!}$ . Значит осталось посчитать вероятность наступления хотя бы одного из событий Все события независимы, значит вероятность успеха - их сумма их вероятностей. Т.е. $frac{|mathcal{K}|^2}{|mathcal{M}|!}$ .

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

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

$P((X cap Y)=varnothing)=(1 - frac{r}{k})(1 - frac{r}{k-1})...(1 - frac{r}{k-r+1})=$ $=frac{(k-r)(k-r-1)...(k-2r+1)}{frac{k!}{(k-r)! }}=frac{(k-r)!^2}{k!(k-2r)!}=p$

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

Помним, что

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

$ln(k - r) geq ln(k) - frac{r}{k}$

$ln(k - 2r) geq ln(k) - frac{2r}{k}$

Тогда

$ln(p) geq 2(k-r)(ln(k) - frac{r}{k}) - kln(k) - (k - 2r)(lnk - frac{2r}{k})=frac{-2r^2}{k}$

Т.е. $P((X cap Y)=varnothing) geq e^{frac{-2r^2}{k}}$ .

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

P("не найти совпадений") = P("X без коллизий") P("Y без коллизий").

P("X без коллизий") = P("Y без коллизий") $e^{frac{-r^2}{2k}}$ - вот опять пригодился парадокс дней рождений.

Отсюда P("не найти совпадений") $e^{frac{-3r^2}{|mathcal{K}|}}$ .

Тогда вероятность, что MCU найдёт совпадения $geq 1 - e^{frac{-3r^2}{|mathcal{K}|}}$ . Теорема доказана.

Литература

Автор: Morgana0_0

Источник ^[4]

Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/des/435008

Ссылки в тексте:

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

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

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

[4] Источник: https://habr.com/ru/articles/961090/?utm_campaign=961090&utm_source=habrahabr&utm_medium=rss

Нажмите здесь для печати.