Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Атака [ править ]

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

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

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

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

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

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

Ссылки [ править ]

  1. ^ Динур, Итаи; Шамир, Ади (26 января 2009 г.). «Атаки куба на настраиваемые полиномы черного ящика» (PDF) . Cryptology ePrint Archive . ePrint 20090126: 174453. Цитировать журнал требует |journal=( помощь )
  2. ^ a b Брюс Шнайер (19 августа 2008 г.). "Атаки куба Ади Шамира" . Проверено 4 декабря 2008 . CS1 maint: обескураженный параметр ( ссылка )
  3. ^ Дэниел Дж. Бернштейн (2009-01-14). "Почему кубические атаки ничего не сломали?" . Проверено 27 февраля 2009 . CS1 maint: обескураженный параметр ( ссылка )
  4. ^ Майкл Вильхабер (2007-10-28). «Взлом ONE.FIVIUM с помощью AIDA с помощью алгебраической IV дифференциальной атаки» .
  5. ^ Майкл Vielhaber (2009-02-23). «Атака куба Шамира»: римейк AIDA, The Algebraic IV Differential Attack » (PDF) . [ постоянная мертвая ссылка ]