openPGP в России

12.11 // Статистический различитель для полнораундового AES-128

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

Новую теоретическую атаку представили Анна Римольди, Массимилиано Сала (кафедра математики университета Тренто, Италия) и Энрико Бертолацци (инженерно-механическая кафедра университета Тренто) в своей работе Do AES encryptions act randomly?^[link1]. Предварительные результаты по этой теме они анонсировали и ранее^[link2], но работа к тому времени опубликована не была.

Они исходили из принципа, известного в других работах как модель идеального шифра (Ideal Cipher Model — ICM). Шифр должен представлять собой набор псевдослучайных перестановок всех возможных открытых текстов во все возможные шифртексты в пределах блока, а смена ключа должна давать новый независимый набор таких перестановок.

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

Атака хорошо работает со 128 ключами (каждый размером 128-бит), хотя достаточно и 70 ключей. С каждым известным ключом связаны 2¹⁶ пар открытых и шифртекстов. Следовательно, общее число таких пар составляет 2¹⁶ · 2⁷ = 2²³ .
Для каждого ключа нужно вычислить 2¹⁵ рангов матриц. Каждое вычисление ранга матрицы в алгоритме предложенном авторами, потребует 2²⁶ шифрований. Таким образом потребуется всего 2²⁶ · 2¹⁵ · 2⁷ = 2⁴⁸ шифрований.

Этого будет достаточно, чтобы получить данные, которые по мнению авторов покажут отличие полнораундового AES-128 от идеального набора псевдослучайных перестановок, что в данной атаке может быть выявлено простым статистическим анализом. Следует отметить, что авторы признают то, что полную корректность своих выкладок они не доказали, также как и не набрали ресурсов для экспериментального подтверждения своих результатов (однако уже проведённые ими вычисления могут свидетельствовать в пользу их гипотезы). При этом все желающие и имеющие необходимые вычислительные ресурсы могут эти результаты проверить на практике и помочь исследователям. Для этого исследователи готовы предоставить созданные ими программы.

Резюмируя кратко можно понять отличие этой работы от предыдущих по нахождению различителей полнораундового AES и понять, почему этот различитель является первым в своём роде:
1. Различитель не дифференциальный, а статистический.
2. Различитель работает не на связанных ключах, и не на подобранно-связанных ключах шифрования, а на случайно выбранных (хотя и известных противнику).
3. Различитель работает с подобранными открытыми текстами, формируя матрицы результатов шифрования на основе алгоритма, учитывающего устройство шифра. И только после этого производится чисто статистический тест на сравнение с идеальными перестановками ("хи-квадрат" тест над рангом матрицы).

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

Источник: Cryptography and Security Archive^[link3]