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


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

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

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

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

Ссылки
[link1] http://cist.korea.ac.kr/~fse2010/index.php

[link2] http://www.skein-hash.info/sites/default/files/axr.pdf

[link3] http://www.pgpru.com/novosti/2008/heshfunkcijaskeiniblochnyjjshifrthreefish

[link4] http://www.schneier.com/blog/archives/2010/02/new_attack_on_t.html