id: Гость   вход   регистрация
текущее время 18:01 29/03/2024
Владелец: unknown (создано 12/11/2010 11:09), редакция от 13/11/2010 10:34 (автор: unknown) Печать
Категории: криптография, криптоанализ, алгоритмы, симметричное шифрование, атаки
http://www.pgpru.com/Новости/2010/СтатистическийРазличительДляПолнораундовгоAES-128
создать
просмотр
редакции
ссылки

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


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


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


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


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


Атака хорошо работает со 128 ключами (каждый размером 128-бит), хотя достаточно и 70 ключей. С каждым известным ключом связаны 216 пар открытых и шифртекстов. Следовательно, общее число таких пар составляет 216 · 27 = 223 .
Для каждого ключа нужно вычислить 215 рангов матриц. Каждое вычисление ранга матрицы в алгоритме предложенном авторами, потребует 226 шифрований. Таким образом потребуется всего 226 · 215 · 27 = 248 шифрований.


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


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


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


Источник: Cryptography and Security Archive


 
Несколько комментариев (5) [показать комментарии/форму]
Общая оценка документа [показать форму]
средний балл: 0респондентов: 2