РадиоGatún
Криптографический примитив хэша
РадиоGatún
Общий
ДизайнерыГвидо Бертони,
Жоан Даемен,
Микаэль Питерс,
Жиль Ван Аш
Впервые опубликованоАвгуст 2006 г.
Получено изПанама
ПреемникиКеччак (SHA-3)
Детали шифра
Размеры блоков19 слов в слове мельница; 39 слов в слове ремень
Лучший публичный криптоанализ
Фур/Пейрин 2008, сложность 2 11 Вт (352/704 бита)

RadioGatún — это криптографический примитив хэша, созданный Гвидо Бертони, Джоан Дэмен , Михаэлем Петерсом и Жилем Ван Ашем . Впервые он был публично представлен на Втором семинаре по криптографическому хэшу NIST, который состоялся в Санта-Барбаре, Калифорния , 24–25 августа 2006 года в рамках конкурса хэш-функций NIST . Та же команда, которая разработала RadioGatún, внесла значительные изменения в этот криптографический примитив , что привело к появлению алгоритма Keccak SHA-3. [1]

RadioGatún — это семейство из 64 различных хэш-функций, отличающихся одним параметром, шириной слова в битах ( w ), регулируемой от 1 до 64. Единственными размерами слов с официальными тестовыми векторами являются 32- и 64-битные варианты RadioGatún. Алгоритм использует 58 слов, каждое из которых использует w бит, для хранения своего внутреннего состояния, поэтому 32-битной версии требуется 232 байта для хранения своего состояния (поскольку каждое слово требует 32 бита или четыре байта, а 58, умноженное на четыре, равно 232), а 64-битной версии — 464 байта (каждое слово использует восемь байтов).

Хотя RadioGatún является производным от Panama , потокового шифра и хэш-конструкции конца 1990-х годов, хэш-конструкция которой была взломана, RadioGatún не имеет недостатков Panama при использовании в качестве хэш-функции. По состоянию на 2022 год RadioGatún по-прежнему является безопасной хэш-функцией; [2] [3] [4] [5] самая большая версия RadioGatún, которая была взломана, — это версия с размером слова в два бита. RadioGatún имеет заявленную прочность безопасности 304 бита для 32-битной версии и 608 бит для 64-битной версии. Самый известный криптоанализ не нарушил это утверждение: для 32-битной версии требуется 352 бита работы, а для 64-битной версии — 704 бита работы.

RadioGatún может использоваться как хэш-функция или потоковый шифр; он может выводить произвольно длинный поток псевдослучайных чисел ; этот тип хэш-конструкции теперь известен как « функция с расширяемым выходом » (XOF). [6]

Заявленная прочность

Разработчики алгоритма в оригинальной статье RadioGatún утверждали, что первые 19 × w бит (где w — ширина используемого слова) выходных данных RadioGatún представляют собой криптографически безопасную хеш-функцию. [7]

После публикации статьи разработчики пересмотрели свои заявления о безопасности и теперь утверждают, что RadioGatún обладает безопасностью криптографической губчатой ​​функции с емкостью 19 Вт . [8] Это означает, что 32-битная версия RadioGatún может использоваться для создания хэша с 304 битами безопасности (как от атак столкновений , так и от атак прообразов ), а 64-битная версия обеспечивает 608 бит безопасности.

Подробности реализации

Разработчики называют RadioGatún «идеальной функцией искажения». RadioGatún использует «ленту» и «мельницу» для криптографической обработки двоичных данных, при этом большинство операций искажения выполняется в «мельничной» части RadioGatún. [9]

Кеччак убрал ремень, увеличил размер мельницы с 19 до 25 слов и несколько усложнил ее работу. [10]

Основная функция пояса выглядит следующим образом:

( A , B ) = R ( a , b ) для строки = от 0 до 2 сделать для всех i сделать B [ i , строка ] = b [ i + 1 mod 13 , строка ] конец для конец для { Функция ленты : простое вращение } для i = от 0 до 11 сделать B [ i + 1 , i mod 3 ] = B [ i + 1 , i mod 3 ] ⊕ a [ i + 1 ] конец для { Прямая связь от мельницы к ленте } A = Мельница ( a ) { Функция мельницы } b = B для i = от 0 до 2 сделать A [ i + 13 ] = A [ i + 13 ] ⊕ b [ 12 , i ] конец для { Прямая связь от ленты к мельнице }

А функция мельницы Mill(A) выглядит так:

{ все индексы должны быть взяты по модулю 19 , x ≫ y обозначает побитовое вращение ( поворот x вправо на y битов ) x ⊕ y обозначает исключающее ИЛИ x | ~ y обозначает выполнение побитового ИЛИ между x и побитовым отрицанием y } для всех i do A [ i ] = a [ i ] ⊕ ( a [ i + 1 ] | ~ a [ i + 2 ] ) end для { γ : нелинейность } для всех i do a [ i ] = A [ 7 i ] ≫ i ( i + 1 ) / 2 end для { π : дисперсия внутри слова и между словами } для всех i do A [ i ] = a [ i ] ⊕ a [ i + 1 ] ⊕ a [ i + 4 ] end для { θ : диффузия } A [ 0 ] = A [ 0 ] ⊕​​ 1 { ι : асимметрия }

Полные сведения о реализации RadioGatún приведены на странице Wikibooks, а Module:RadioGatun32 представляет собой реализацию 32-разрядной версии RadioGatún.

Криптоанализ

В статье «Две атаки на RadioGatún» Дмитрий Ховратович представляет две атаки, которые не нарушают заявлений разработчиков о безопасности, одна со сложностью 2 18 w , а другая со сложностью 2 23,1 w . [11] Ховратович также является автором статьи под названием «Криптоанализ хэш-функций со структурами», в которой описывается атака со сложностью 2 18 w . [12]

В статье «Анализ устойчивости к коллизиям RadioGatún с использованием алгебраических методов» Шарль Буйаге и Пьер-Ален Фук представляют способ генерации коллизий с 1-битной версией алгоритма с использованием атаки, требующей 2 24,5 операций. [13] Атака не может быть распространена на более крупные версии, поскольку «все возможные пути, которые мы знали для 1-битной версии, оказались невозможными для распространения на n-битные версии». Эта атака менее эффективна, чем другие атаки, и также не нарушает требования безопасности RadioGatún.

Наиболее эффективная атака на алгоритм, со сложностью 2 11 w , приведена в статье "Криптоанализ RadioGatun" Томаса Фура и Томаса Пейрина. В статье они взламывают 2-битную (размер слова два) версию RadioGatún. [14] Хотя эта атака более эффективна, чем другие атаки, она все еще не нарушает требования безопасности.

Разработчики RadioGatún заявили, что их «собственные эксперименты не внушили доверия к RadioGatún». [15]

Тестовые векторы

Единственными вариантами RadioGatún, для которых разработчики предоставили тестовые векторы (опубликованные значения хэш-функции для образцов входных данных, чтобы программисты могли проверить правильность реализации алгоритма), являются 32- и 64-битные версии.

РадиоГатун[32]

Эти тестовые векторы, сгенерированные с использованием 32-битной версии RadioGatún, показывают только первые 256 бит произвольно длинного выходного потока RadioGatún[32]:

РадиоГатун[32]("") =F30028B54AFAB6B3E55355D277711109A19BEDA7091067E9A492FB5ED9F20117
РадиоГатун[32]("Быстрая коричневая лиса перепрыгивает через ленивую собаку ") =191589005FEC1F2A248F96A16E9553BF38D0AEE1648FFA036655CE29C2E229AE
РадиоГатун[32]("Быстрая коричневая лиса прыгает через ленивый козел ") =EBDC1C8DCD54DEB47EEFC33CA0809AD23CD9FFC0B5254BE0FDABB713477F2BD

РадиоГатун[64]

Вот хеши для 64-битной версии:

РадиоГатун[64]("") =64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584
РадиоГатун[64]("Быстрая коричневая лиса перепрыгивает через ленивую собаку ") =6219FB8DAD92EBE5B2F7D18318F8DA13CECBF13289D79F5ABF4D253C6904C807
РадиоГатун[64]("Быстрая коричневая лиса перепрыгивает через ленивый козел ") =C06265CAC961EA74912695EBF20F1C256A338BC0E980853A3EEF188D4B06FCE5

Ссылки

  1. ^ Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; Ван Аш, Жиль (2009). «Дорога из Панамы в Кечак через RadioGatun». Drops-Idn/V2/Document/10.4230/Dagsemproc.09031.17 . Материалы семинара Дагштуля (DagSemProc). 9031 : 1–9. дои : 10.4230/DagSemProc.09031.17 . Проверено 20 октября 2009 г.
  2. ^ Садеги-Насаб, Алиреза; Рафе, Вахид (2022). «Комплексный обзор недостатков безопасности алгоритмов хеширования» (PDF) . Журнал компьютерной вирусологии и хакерских технологий . 19 (2): 287–302. doi :10.1007/s11416-022-00447-w. S2CID  253033894. RadioGatún продолжает оставаться безопасной хеш-функцией
  3. ^ Кишор, Неха; Райна, Прия (2019). «Параллельное криптографическое хеширование: разработки за последние 25 лет». Cryptologia . 43 (6): 504–535. doi : 10.1080/01611194.2019.1609130. S2CID  201884222. RadioGatún (Bertoni et al.2006) по-прежнему безопасен
  4. ^ Томас Порнин (2011-04-03). "Нужно предложение для более быстрого сравнения отпечатков пальцев/хэшей Linux". Среди тех, что я цитирую, функции Radiogatun и Shabal в настоящее время не сломаны.
  5. ^ Zooko Wilcox (24.02.2017). «Уроки истории атак на безопасные хэш-функции» . Получено 28.06.2018 . Ни одна из новых безопасных хэш-функций (разработанных примерно после 2000 года) до сих пор не поддалась коллизионным атакам.
  6. ^ "Архивная копия" (PDF) . Архивировано из оригинала (PDF) 2017-01-31 . Получено 2017-07-17 .{{cite web}}: CS1 maint: архивная копия как заголовок ( ссылка )
  7. ^ На странице 9 (раздел 6) «RadioGatún, хэш-функция конвейерного типа» указано, что «RadioGatún [l w ] обеспечивает уровень безопасности, обозначенный емкостью c = 19 * w. Для 64-битной версии RadioGatún это емкость 1216 бит, для 32-битной и 16-битной версий это дает 608 и 304 бита соответственно».
  8. ^ http://radiogatun.noekeon.org/ "Теперь мы предпочитаем выражать требование безопасности для RadioGatún как требование плоской губки мощностью 19 Вт "
  9. ^ "RadioGatún, хэш-функция конвейерного типа" (PDF) . 2006-07-20.
  10. ^ "Дорога из Панамы в Кеккак через РадиоГатун" (PDF) . S2CID  2222603. Архивировано из оригинала (PDF) 2018-08-05. Поэтому для Кеккак мы решили убрать ремень и вместо этого увеличить количество слов в мельнице
  11. ^ Ховратович, Дмитрий (2008). "Две атаки на RadioGatún" (PDF) . Прогресс в криптологии - INDOCRYPT 2008. Конспект лекций по информатике. Том 5365. С. 53–66. doi :10.1007/978-3-540-89754-5_5. ISBN 978-3-540-89753-8. S2CID  6487398. Архивировано из оригинала (PDF) 2018-08-07.
  12. ^ https://www.cryptolux.org/images/7/79/Struct.pdf Криптоанализ хэш-функций со структурами - Университет Люксембурга
  13. ^ Буйаге, Шарль; Фуке, Пьер-Ален (2009). «Анализ коллизионной устойчивости радио Gatún с использованием алгебраических методов». Избранные области криптографии . Конспект лекций по информатике. Том 5381. С. 245–261. doi :10.1007/978-3-642-04159-4_16. ISBN 978-3-642-04158-7.
  14. ^ Фур, Томас; Пейрин, Томас (2008). «Криптоанализ РадиоГатун». Архив Cryptology ePrint .
  15. ^ «Keccak и стандартизация SHA-3» (PDF) .
В Wikibooks есть книга по теме: Криптография/РадиоГатун
  • Семейство хэш-функций RadioGatún, официальная веб-страница RadioGatún, с официальным описанием хэша, общедоступным кодом ссылки и тестовыми векторами
  • rg32hash, независимая общедоступная реализация 32-битной версии RadioGatún
Взято с "https://en.wikipedia.org/w/index.php?title=RadioGatún&oldid=1238774948"