08.02 // Криптоанализ на основе "вращений" -- новая атака против Threefish
На конференции FSE 2010 Dmitry Khovratovich и Ivica Nikolic представили работу по криптонализу ARX алгоритмов (алгоритмов, использующих только сложение, сдвиги-"вращения" и XOR): "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
два в 1014.5 котят?
комментариев: 9796 документов: 488 редакций: 5664
Вот посчитали они за сложность атаки количество исполнений всего этого алгоритма или только отдельных шифрований неясно. Но и не так важно, ну будет 21000±4. Поэтому сложность и измеряют в "шагах".
комментариев: 115 документов: 19 редакций: 17
Иначе говоря, «алгоритмов, использующих только линейные операции»?
комментариев: 9796 документов: 488 редакций: 5664
Что ещё смущает в ARX — традиционные MD5 и SHA-1, SHA-2 в своём ядре тоже имеют структуру ARX, хотя и не совсем такую, и упакованную снаружи в другую конструкцию, но принципы атаки на ARX — похожи.
Контринтуитивно. Наверно, это чисто булевые извраты. В обычной математике линейность тем как раз и интереса, что смешение любого счётного числа линейных операций есть линейная операция.