Кубическая атака

— Атака куба это метод криптоанализа, применимый к широкому спектру алгоритмов с симметричным ключом , опубликованный Итаем Динуром и Ади Шамиром в препринте за сентябрь 2008 года.

Атака

Переработанная версия этого препринта была размещена в Интернете в январе 2009 г. ^{[ 1 ]} и статья также была принята к презентации на Eurocrypt 2009.

Шифр уязвим, если выходной бит может быть представлен как достаточно низкой степени полином над GF(2) ключевых и входных битов; в частности, здесь описаны многие потоковые шифры , основанные на LFSR . ^{[ 2 ]} DES и AES невосприимчивы к этой атаке. Считается, что ^{[ 2 ]} Он работает путем суммирования значений выходных битов для всех возможных значений подмножества общедоступных входных битов, выбранных так, чтобы результирующая сумма представляла собой линейную комбинацию секретных битов; Повторное применение этого метода дает набор линейных отношений между секретными битами, которые можно решить, чтобы обнаружить эти биты. Авторы показывают, что если шифр напоминает случайный полином достаточно низкой степени, то такие наборы общедоступных входных битов будут существовать с высокой вероятностью и могут быть обнаружены на этапе предварительных вычислений путем «исследования черного ящика» отношений между входными и выходными данными для различные варианты открытых и секретных входных битов, не использующие никакой другой информации о построении шифра.

В статье представлена реализованная и протестированная авторами практическая атака на поточный шифр, против которой ни одна известная ранее атака не была бы эффективной. Его состояние представляет собой 10 000-битный LFSR с секретным плотным полиномом обратной связи, который фильтруется массивом из 1000 секретных 8-битных и 1-битных S-блоков , входные данные которых основаны на секретных подключениях к состоянию LFSR и чей выход подвергается операции XOR. вместе. Каждый бит в LFSR инициализируется различным секретным плотным квадратичным полиномом из 10 000 ключевых и IV битов. LFSR тактируется большое и секретное количество раз без каких-либо выходных данных, а затем злоумышленнику становится доступен только первый выходной бит для любого заданного IV. После короткой фазы предварительной обработки, на которой злоумышленник может запросить выходные биты для различных комбинаций ключей и IV, только 2 ³⁰ Для обнаружения ключа этого шифра необходимы битовые операции.

Авторы также заявляют, что атака на версию Trivium сокращена до 735 раундов инициализации со сложностью 2. ³⁰и предположим, что эти методы могут быть расширены до взлома 1100 из 1152 раундов инициализации Trivium и «возможно, даже оригинального шифра». По состоянию на декабрь 2008 г. ^[update] это лучшая атака, известная против Тривиума.

Однако это нападение связано с двумя отдельными противоречиями. Во-первых, Дэниел Дж. Бернштейн. ^{[ 3 ]} оспаривает утверждение о том, что предыдущей атаки на 10 000-битный потоковый шифр на основе LFSR не существовало, и утверждает, что атака на Trivium с сокращенным числом раундов «не дает никаких реальных оснований полагать, что (полный) Trivium может быть атакован». Он утверждает, что в статье Cube не цитируется существующая статья Сюэцзя Лая, подробно описывающая атаку на шифры с полиномами малой степени, и что он считает, что атака Cube является просто новым изобретением этой существующей техники.

» Майкла Вильхабера Во-вторых, Динур и Шамир считают « Алгебраическую IV дифференциальную атаку (AIDA) предшественником атаки Cube. ^{[ 4 ]} Динур заявил на Eurocrypt 2009, что Cube обобщает и улучшает AIDA. Однако Вильхабер утверждает, что атака кубом — это не более чем его атака под другим именем. ^{[ 5 ]} Однако все участвующие стороны признают, что использование Cube эффективного теста на линейность, такого как тест BLR, приводит к тому, что новая атака требует меньше времени, чем AIDA, хотя насколько существенным является это конкретное изменение, остается спорным. Это не единственное отличие Cube и AIDA. Вильхабер утверждает, например, что линейные полиномы в ключевых битах, полученные в ходе атаки, будут необычайно редкими. Он еще не предоставил доказательств этого, но утверждает, что такие доказательства появятся в его предстоящей статье под названием «Дифференциальная атака алгебраической IV: AIDA атакует весь тривиум». (Неясно, применима ли эта предполагаемая разреженность к каким-либо шифрам, кроме Тривиума.)

Ссылки

^ Динур, Итай; Шамир, Ади (26 января 2009 г.). «Атаки куба на настраиваемые полиномы черного ящика» (PDF) . Архив электронной печати по криптологии . ePrint 20090126:174453.
^ Jump up to: ^а ^б Брюс Шнайер (19 августа 2008 г.). «Атаки куба Ади Шамира» . Проверено 4 декабря 2008 г.
^ Дэниел Дж. Бернштейн (14 января 2009 г.). «Почему атаки куба ничего не сломали?» . Проверено 27 февраля 2009 г.
^ Михаэль Вильхабер (28 октября 2007 г.). «Взлом ONE.FIVIUM с помощью AIDA и дифференциальная атака алгебраического IV» . Архив электронной печати по криптологии .
^ Михаэль Вильхабер (23 февраля 2009 г.). «Кубическая атака Шамира: римейк AIDA, дифференциальная атака Algebraic IV» (PDF) . ^{[ постоянная мертвая ссылка ]}

[paper-1] Динур, Итай; Шамир, Ади (26 января 2009 г.). «Атаки куба на настраиваемые полиномы черного ящика» (PDF) . Архив электронной печати по криптологии . ePrint 20090126:174453.

[schneier-2] Jump up to: ^а ^б Брюс Шнайер (19 августа 2008 г.). «Атаки куба Ади Шамира» . Проверено 4 декабря 2008 г.

[djb-3] Дэниел Дж. Бернштейн (14 января 2009 г.). «Почему атаки куба ничего не сломали?» . Проверено 27 февраля 2009 г.

[aida-4] Михаэль Вильхабер (28 октября 2007 г.). «Взлом ONE.FIVIUM с помощью AIDA и дифференциальная атака алгебраического IV» . Архив электронной печати по криптологии .

[AIDA-Shamir-5] Михаэль Вильхабер (23 февраля 2009 г.). «Кубическая атака Шамира: римейк AIDA, дифференциальная атака Algebraic IV» (PDF) . ^{[ постоянная мертвая ссылка ]}

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]