id: Гость   вход   регистрация
текущее время 16:31 28/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


 
— SATtva (12/11/2010 19:34)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Attacks always get better...
— unknown (12/11/2010 23:02)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
...а нахождение различителя — первый путь к началу любой атаки.
— Гость (13/11/2010 00:27)   <#>
Давно пора. 10 лет
— Гость (13/11/2010 01:46)   <#>
01.06.2009 // Первая атака на полнораундовый AES доказывает его отличие от модели идеального шифра. — Я что-то важное пропустил? Или у кого-то дежавю?
— unknown (13/11/2010 09:41, исправлен 13/11/2010 10:14)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
эта атака лишь возможно первый полнораундовый чисто статистический различитель

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


Чтобы не было недоразумений "статистический" — это не значит, что можно тупо прогнать шифр через статтесты. Здесь сначала проводится подбор открытых текстов и запись результатов шифрования в матрицы, по специальному алгоритму с учётом знания устройства шифра. Затем такие же матрицы заполняются истинно случайными данными, имитирующими идеальный шифр, и сравниваются с aes'овскими путём статистических методов (или просто рассчитываются идеальные теоретические параметры таких матриц, по которым и сравнивают). Т.е. можно даже придраться, что различитель только во второй части статистический (подогнан под различение конкретно AES). Но с теоретической точки зрения — это серьёзное доказательство неидеальности.


Резюмируя кратко отличие этой работы от предыдущих по нахождению различителей полнораундового AES <...> (см. то, что добавлено в текст новости).


DES постарше будет и атаки всевозможные есть. Но даже поломанный DES (в виде 3DES) можно считать практически стойким.

Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3