id: Гость   вход   регистрация
текущее время 22:21 28/03/2024
Владелец: unknown (создано 08/02/2010 11:52), редакция от 08/02/2010 11:52 (автор: unknown) Печать
Категории: криптография, криптоанализ, алгоритмы, симметричное шифрование, атаки
https://www.pgpru.com/Новости/2010/КриптоанализНаОсновевращений--НоваяАтакаПротивThreefish
создать
просмотр
редакции
ссылки

08.02 // Криптоанализ на основе "вращений" -- новая атака против Threefish


На конференции FSE 2010 Dmitry Khovratovich и Ivica Nikolic представили работу по криптонализу ARX алгоритмов (алгоритмов, использующих только сложение, сдвиги-"вращения" и XOR): file"Rotational Cryptanalysis of ARX". В своей работе они представили свою атаку против алгоритма Threefish. Взлом 39 (из 72) раундов Threefish-256 имеет сложность 2252.4, 42 (из 72) раундов Threefish-512 — 2507 и 43.5 (из 80) раундов Threefish-1024 имеет сложность 21014.5. Хотя эти цифры кажутся смехотворно большими, эти атаки формально успешны против сокращённых версий алгоритма, так как они находят результат быстрее перебора грубой силой. При этом шансы распространить их ещё на несколько раундов невелики, не говоря уже о построении полнораундовых атак.


Алгоритм Threefish — блочный шифр нового поколения, основа хэш-функции Skein, разработанный коммандой Брюса Шнайера для конкурса SHA-3. Интерес к этому алгоритму вызван тем, что в нём используются самые амбициозные идеи из последних и в тоже время основанных на опыте многолетних исследований криптографии. Threefish использует простейшую функцию раунда из самых элементарных операций, но при этом использует очень большое число раундов, что даёт небывалые возможности для оптимизированных исполнений по максимуму скорости и минимуму затрат ресурсов. Кроме того Skein создаётся как универсальный симметричный криптопримитив, потенциально заменяющий генераторы псевдослучайных чисел, поточные шифры, функции генерации ключей и многие другие. Для построения такой конструкции использовались методы доказуемой безопасности и модель случайного оракула при участии самих разработчиков этой модели.


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


Источник: Schneier on Security Blog


 
— Гость (14/02/2010 21:47)   <#>
В чём они измеряют сложность?

два в 1014.5 котят?
— unknown (14/02/2010 23:23)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Там приведён общий алгоритм атаки:

  1. Сгенерировать случайный открытый текст P и зашифровать его ключом K
  2. Вычислить P' и зашифровать его на K' — а это ещё отдельный подалгоритм с некоторым числом пунктов.
  3. Проверить, что ( EK ( P ), EK' (P')) является парой вращения.
  4. На основе этого вычислить часть ключа.

Вот посчитали они за сложность атаки количество исполнений всего этого алгоритма или только отдельных шифрований неясно. Но и не так важно, ну будет 21000±4. Поэтому сложность и измеряют в "шагах".
— DDRTL2009 (06/04/2010 23:05)   профиль/связь   <#>
комментариев: 115   документов: 19   редакций: 17
надеемся что "блестящую и лучшую из известных, хотя и не представляющую угрозы для Threefish даже в перспективе её ближайшего улучшения." будет иначе)
— Гость (07/03/2014 04:19)   <#>

Иначе говоря, «алгоритмов, использующих только линейные операции»?
— unknown (07/03/2014 09:50)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Идея ARX в том, что смешение трёх линейных операций даёт нелинейную, за счёт чего можно избавиться от S-блоков (экономия памяти, устойчивость к утечкам по побочным каналам, быстродействие). Выкиньте из ARX одну букву-операцию и всё становится линейным.

Что ещё смущает в ARX — традиционные MD5 и SHA-1, SHA-2 в своём ядре тоже имеют структуру ARX, хотя и не совсем такую, и упакованную снаружи в другую конструкцию, но принципы атаки на ARX — похожи.
— Гость (09/03/2014 01:40)   <#>

Контринтуитивно. Наверно, это чисто булевые извраты. В обычной математике линейность тем как раз и интереса, что смешение любого счётного числа линейных операций есть линейная операция.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3