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 не имеет слабых мест Панамы при использовании в качестве хэш-функции. По состоянию на 2019 год RadioGatún по-прежнему является безопасной хеш-функцией; [2] [3] [4] самая большая версия RadioGatún, которая не работает, - это версия с размером слова в два бита.
RadioGatún может использоваться как хеш-функция или как потоковый шифр; он может выводить произвольно длинный поток псевдослучайных чисел ; этот вид хэш-конструкции теперь известен как «функция расширяемого вывода» (XOF). [5]
Заявленная сила
Разработчики алгоритма в оригинальной статье RadioGatún утверждали, что первые 19 × w битов (где w - используемая ширина слова) вывода RadioGatún представляют собой криптографически безопасную хеш-функцию. [6]
После публикации статьи разработчики пересмотрели свое требование безопасности и теперь утверждают, что RadioGatún обладает безопасностью функции криптографической губки с мощностью 19 Вт . [7] Это означает, что 32-битная версия RadioGatún может быть использована для создания хэша с 304 битами защиты (как от атак столкновений, так и от атак с использованием прообраза ), а 64-битная версия предлагает 608 бит защиты.
Детали реализации
Разработчики называют RadioGatún «идеальной функцией манипуляции». RadioGatún использует «конвейер» и «мельницу» для криптографической обработки двоичных данных, при этом большинство операций по изменению выполняется на «мельничной» части RadioGatún. [8]
Кечак снял ленту, увеличил размер мельницы с 19 до 25 слов и несколько усложнил работу мельницы. [9]
Основная функция ремня выглядит так:
( A , B ) = R ( a , b ) для row = от 0 до 2 do для всех i do B [ i , row ] = b [ i + 1 mod 13 , row ] конец за конец для { функция пояса : простое вращение } для i = от 0 до 11 выполните B [ i + 1 , i mod 3 ] = B [ i + 1 , i mod 3 ] ⊕ a [ i + 1 ] конец для { фрезерования с прямой связью ленты } A = фрезерование ( a ) { мельница функция } Ь = б для я = 0 до 2 сделать А [ я + 13 ] = [ я + 13 ] ⊕ б [ 12 , я ] конец для { пояса для мельницы упреждением }
А функция фрезерования Mill (A) выглядит так:
{ Все индексы должны быть приняты по модулю 19 , х » у обозначает побитовое вращение ( поворот х правый Y бит ) х ⊕ у обозначает исключительные или х | \ у обозначает исполнительский с побитовой или между й и в побитовом отрицании от у } для всех я делать [ я ] = [ я ] ⊕ ( [ я + 1 ] | ~ [ я + 2 ]) конец для { гамма : не - линейность } для всех я делать [ я ] = [ 7 я ] » я ( я + 1 ) / 2 конца для { П : внутри - слова и в том - слово дисперсии } для всех я делать [ я ] = [ я ] ⊕ [ я + 1 ] ⊕ [ я + 4 ] конец для { θ : диффузия } A [ 0 ] = A [ 0 ] ⊕ 1 { ι : асимметрия }
Страница Wikibooks на RadioGatún предоставляет полную информацию о реализации.
Криптоанализ
В статье «Две атаки на RadioGatún» Дмитрий Ховратович представляет две атаки, которые не нарушают требований разработчиков: одна со сложностью 2 18 w и вторая со сложностью 2 23,1 w . [10] Ховратович также является автором статьи «Криптоанализ хеш-функций со структурами», в которой описывается атака со сложностью 2 18 w . [11]
В статье «Анализ сопротивления столкновения RadioGatún с использованием алгебраических методов» Шарль Буйяге и Пьер-Ален Фук представляют способ генерации столкновений с 1-битной версией алгоритма с использованием атаки, требующей 2 операций 24,5 . [12] Атака не может быть расширена на более крупные версии, поскольку «все возможные следы, которые мы знали для 1-битной версии, оказалось невозможным распространить на n-битные версии». Эта атака менее эффективна, чем другие атаки, и также не нарушает требования безопасности RadioGatún.
Наиболее эффективная атака на алгоритм со сложностью 2 11 w дана в статье Томаса Фура и Томаса Пейрина "Криптоанализ RadioGatun". В статье они ломают 2-битную (размер слова два) версию RadioGatún. [13] Хотя эта атака более эффективна, чем другие атаки, она все же не нарушает требования безопасности.
Разработчики RadioGatún заявили, что их «собственные эксперименты не внушают доверия RadioGatún». [14]
Тестовые векторы
Единственные варианты RadioGatún, для которых разработчики предоставили тестовые векторы (опубликованные хеш-значения для примеров входных данных, чтобы программисты могли убедиться, что они правильно реализуют алгоритм), - это 32-битные и 64-битные версии.
RadioGatún [32]
Эти тестовые векторы, сгенерированные с использованием 32-битной версии RadioGatún, показывают только первые 256 битов произвольно длинного выходного потока RadioGatún [32]:
RadioGatun [32] ("") =F30028B54AFAB6B3E55355D277711109A19BEDA7091067E9A492FB5ED9F20117
RadioGatun [32] ( «быстрая коричневая лиса прыгает через ленивый г OG») =191589005FEC1F2A248F96A16E9553BF38D0AEE1648FFA036655CE29C2E229AE
RadioGatun [32] ( «быстрая коричневая лиса прыгает через ленивый гр OG») =EBDC1C8DCD54DEB47EEEFC33CA0809AD23CD9FFC0B5254BE0FDABB713477F2BD
RadioGatún [64]
Вот хеши для 64-битной версии:
RadioGatun [64] ("") =64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584
RadioGatun [64] ( «быстрая коричневая лиса прыгает через ленивый г OG») =6219FB8DAD92EBE5B2F7D18318F8DA13CECBF13289D79F5ABF4D253C6904C807
RadioGatun [64] ( «быстрая коричневая лиса прыгает через ленивый гр OG») =C06265CAC961EA74912695EBF20F1C256A338BC0E980853A3EEF188D4B06FCE5
Рекомендации
- ^ Бертони, Гвидо; Дэмен, Джоан; Петерс, Михаэль; Ван Аше, Жиль. «Дорога из Панамы в Кеччак через RadioGatún» . Проверено 20 октября 2009 .
- ^ Кишор, Неха; Райна, Прия (2019). «Параллельное криптографическое хеширование: изменения за последние 25 лет». Cryptologia . 43 (6): 504–535. DOI : 10.1080 / 01611194.2019.1609130 .
RadioGatún (Бертони и др., 2006) по-прежнему защищен
- ^ Томас Порнин ( 03.04.2011 ). «Требуется предложение для более быстрого сравнения отпечатков / хэшей Linux» .
Среди тех, что я цитирую, функции Радиогатун и Шабал в настоящее время не нарушены.
- ^ Зуко Уилкокс (24.02.2017). «Уроки истории атак на безопасные хеш-функции» . Проверено 28 июня 2018 .
никакие новые безопасные хэш-функции (разработанные примерно после 2000 года) также не поддавались атакам на основе коллизий.
- ^ http://csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents/perlner_XOFs.pdf
- ^ Страница 9 (Раздел 6) «RadioGatún, хэш-функция с конвейерной лентой» утверждает, что «RadioGatún [l w ] предлагает уровень безопасности, обозначенный емкостью c = 19 * w. Для 64-битной версии RadioGatún это имеет емкость 1216 бит, для 32-битной версии и 16-битной версии это дает 608 и 304 бит соответственно ».
- ^ http://radiogatun.noekeon.org/ "Теперь мы предпочитаем выражать требование безопасности для RadioGatún как требование плоской губки мощностью 19 Вт "
- ^ «RadioGatún, хэш-функция ленточно-мельничного оборудования» (PDF) . 2006-07-20.
- ^ «Дорога из Панамы в Кеччак через RadioGatún» (PDF) . Архивировано из оригинального (PDF) на 2018-08-05.
Поэтому для Keccak мы решили удалить ленту и вместо этого увеличить количество слов в мельнице.
- ^ Ховратович, Дмитрий. «Две атаки на RadioGatún» (PDF) . Архивировано из оригинального (PDF) 07.08.2018.
- ^ https://www.cryptolux.org/images/7/79/Struct.pdf
- ^ Буйлаге, Шарль; Фук, Пьер-Ален. «Анализ сопротивления столкновения RadioGatun с использованием алгебраических методов» .
- ^ Фур, Томас; Пейрин, Томас. «Криптоанализ RadioGatun» .
- ^ «Keccak и стандартизация SHA-3» (PDF) .
Внешние ссылки
- Семейство хеш-функций RadioGatún, официальная веб-страница RadioGatún, с официальным описанием хэша, ссылочным кодом общественного достояния и тестовыми векторами
- rg32hash , независимая общедоступная реализация 32-разрядной версии RadioGatún