Рейтинг:0

Подвержено ли множественное шифрование в режиме XTS атакам Meet-in-the-middle?

флаг pf

Предположим, я что-то шифрую с помощью AES-256 в XTS режим два раза (будет 4 четыре ключа, по 2 на каждую операцию шифрования), желая достичь 512-битной безопасности.

Будет ли эта схема подвержена Атаки типа «встреча посередине»?

Я спрашиваю об этом, потому что в режиме XTS больше операций, чем просто прямое шифрование открытого текста.

Рейтинг:2
флаг cn

Короткий ответ: «Да, эта установка уязвима». Если вам нужна математика, вы можете прочитать объяснение ниже.

В XTS два ключа независимы, поэтому он уже имеет 512-битную защиту (пока нет атак, уменьшающих это число*). Итак, объясню, зачем использовать двойное шифрование в режиме XTS не увеличивается безопасность.

Давайте внимательно посмотрим на уравнение шифрования в режиме XTS: $$ c_i = f(m_i, (K_1, K_2)) = T_i\oplus E_{K_1}(m_1)\oplus T_i \ T_i=E_{K_2}(SN)\otimes\alpha^{i-1} $$ куда $SN$ номер сектора, $(К_1,К_2)$ - ключи шифрования, $м_я, с_я$ - блоки открытого текста и зашифрованного текста соответственно и $\альфа$ является примитивным элементом $GF(2^l)$ ($|m_i|=l$).

Теперь давайте рассмотрим функцию шифрования блочного шифра: $$ E_K=\pi_{q_{r+1}}\circ\varphi_{q_r}\circ... \circ\varphi_{q_1}\circ\delta_{q_0} $$ куда $г$ количество раундов, $q_i,i=\overline{1,r}$ являются круглыми ключами (полученными из ключа шифрования с использованием специального набора функций, называемого «расписанием ключей»), $\varphi_{q_i},i=\overline{1,r}$ круглые функции, $\pi_{q_{r+1}}, \delta_{q_0}$ являются функциями вывода и ввода со своими ключами соответственно (эти две функции могут не зависеть от ключа).

Наличие этих функций ввода и вывода является ключом к вашему вопросу. Давайте рассмотрим блочный шифр со следующим уравнением шифрования: $$ E_{K_1,K_2} = \underbrace{\pi'_{q_{r+1}}\circ \pi^{\varepsilon}_{q_{r+1}}}_{\pi_{q_{r+1}}} \circ\overbrace{\varphi^{\varepsilon}_{q_r}\circ... \circ\varphi^{\varepsilon}_{q_1}}^{\varphi_{q_r}\circ... \circ\varphi_{q_1}} \ circ \ underbrace {\ delta ^ {\ varepsilon} _ {q_0} \ circ \delta'_{q_0}}_{\delta_{q_0}},\ q_0=q_{r+1}=(K_2,SN) $$ куда $\varphi^{\varepsilon}_{q_i}=\varphi_{q_i}, i=\overline{1,r}$ - округление функций базового блочного шифра $\varepsilon$ (AES в вашем случае), $\pi^{\varepsilon}_{q_{r+1}}, \delta^{\varepsilon}_{q_0}$ - функции вывода и ввода базового блочного шифра и $\pi'_{q_{r+1}}(x)=E_{K_2}(SN)\oplus x$, $\delta'_{q_0}(x)=E_{K_2}(SN)\oplus x$.

Есть некоторые проблемы с этим уравнением в случае реальной зависимости от $\pi^{\varepsilon}_{q_{r+1}}$ и $\дельта^{\varepsilon}_{q_0}$ на свои клавиши (которые разные), но их можно легко устранить правильным выбором функций расписания клавиш. Я пока не буду этого делать, чтобы избежать излишней сложности.

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


В простейшем случае атаки Meet-in-the-middle вы создаете две таблицы: $$ s_i = E_{K_1,K_2}(m_i) \ s'_i = E^{-1}_{K'_1,K'_2}(c_i) $$

После этого вы ищете равные значения $s_i=s'_i$. Этот алгоритм подходит для любого блочного шифра и для нашего тоже, поэтому построенная прямо сейчас конструкция уязвима для этой атаки, как раз потому, что XTS ничего особенного не добавляет к блочному шифру, т.е. можно считать шифрование в режиме XTS блочным -мудрое шифрование, когда каждый блок шифруется своим ключом.

Зная номер сектора и позицию блока, вы строите две таблицы, как описано выше, для этого конкретного блока и узнаете ключи шифрования. В худшем случае вам нужно перечислить все пары ключей $(К_1, К_2)$ дважды. Так что асимптотически нет повышения безопасности.


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

phantomcraft avatar
флаг pf
Спасибо за объяснение.

Ответить или комментировать

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