RadioGatún - RadioGatún

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

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

Хотя RadioGatún является производным от Панама, а потоковый шифр и построение хэша конца 1990-х годов, построение которого было нарушено, RadioGatún не имеет слабых мест Панамы при использовании в качестве хеш-функции. По состоянию на 2019 год RadioGatún по-прежнему является безопасной хеш-функцией;[2][3][4] самая большая версия RadioGatún, которая не работает, - это версия с размером слова два бита.

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

Заявленная сила

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

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

Детали реализации

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

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

Страница Wikibooks на RadioGatún предоставляет полную информацию о реализации.

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

В статье «Две атаки на RadioGatún», Дмитрий Ховратович представляет две атаки, которые не нарушают заявлений разработчиков о безопасности, одна со сложностью 218ш и еще один со сложностью 223.1ш.[10] Ховратович также является автором статьи «Криптоанализ хеш-функций со структурами», в которой описывается атака со сложностью 218ш.[11]

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

Самая эффективная атака на алгоритм со сложностью 211ш, приводится в статье Томаса Фура и Томаса Пейрина "Криптоанализ 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] («Быстрая коричневая лисица перепрыгивает через ленивого dog ") = 191589005FEC1F2A248F96A16E9553BF38D0AEE1648FFA036655CE29C2E229AE
RadioGatun [32] («Быстрая коричневая лисица перепрыгивает через ленивого cog ") = EBDC1C8DCD54DEB47EEEFC33CA0809AD23CD9FFC0B5254BE0FDABB713477F2BD

RadioGatún [64]

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

RadioGatun [64] ("") = 64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584
RadioGatun [64] («Быстрая коричневая лисица перепрыгивает через ленивого dog ") = 6219FB8DAD92EBE5B2F7D18318F8DA13CECBF13289D79F5ABF4D253C6904C807
RadioGatun [64] («Быстрая коричневая лисица перепрыгивает через ленивого cog ") = C06265CAC961EA74912695EBF20F1C256A338BC0E980853A3EEF188D4B06FCE5

Рекомендации

  1. ^ Бертони, Гвидо; Дэмен, Джоан; Пеэтерс, Михаэль; Ван Аше, Жиль. «Дорога из Панамы в Кеччак через RadioGatún». Получено 2009-10-20.
  2. ^ Кишор, Неха; Райна, Прия (2019). «Параллельное криптографическое хеширование: изменения за последние 25 лет». Криптология. 43 (6): 504–535. Дои:10.1080/01611194.2019.1609130. RadioGatún (Бертони и др., 2006) все еще в безопасности
  3. ^ Томас Порнин (2011-04-03). "Требуется предложение для более быстрого сравнения отпечатков пальцев / хэшей Linux". Среди тех, что я цитирую, функции Радиогатун и Шабал в настоящее время не нарушены.
  4. ^ Зуко Уилкокс (2017-02-24). «Уроки истории атак на безопасные хэш-функции». Получено 2018-06-28. никакие новые безопасные хэш-функции (разработанные примерно после 2000 года) также не поддались атакам на основе коллизий.
  5. ^ http://csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents/perlner_XOFs.pdf
  6. ^ На странице 9 (Раздел 6) «RadioGatún, хэш-функция с конвейерной лентой» говорится, что «RadioGatún [lш] предлагает уровень безопасности, обозначенный емкостью c = 19 * ш. Для 64-битной версии RadioGatúnt это емкость 1216 бит, для 32-битной версии и 16-битной версии это дает 608 и 304 бит соответственно ».
  7. ^ http://radiogatun.noekeon.org/ "Теперь мы предпочитаем выражать требование безопасности для RadioGatún как требование плоской губки вместимостью 19ш"
  8. ^ "RadioGatún, хеш-функция ленточно-фрезерного станка" (PDF). 2006-07-20.
  9. ^ «Дорога из Панамы в Кеччак через RadioGatún» (PDF). Поэтому для Keccak мы решили удалить ремень и вместо этого увеличить количество слов в мельнице.
  10. ^ Ховратович, Дмитрий. "Две атаки на RadioGatún" (PDF).
  11. ^ https://www.cryptolux.org/images/7/79/Struct.pdf
  12. ^ Буйлаге, Шарль; Фук, Пьер-Ален. «Анализ сопротивления столкновения RadioGatun с использованием алгебраических методов».
  13. ^ Фур, Томас; Пейрин, Томас. «Криптоанализ RadioGatun».
  14. ^ «Keccak и стандартизация SHA-3» (PDF).

внешняя ссылка

  • Семейство хеш-функций RadioGatún, Официальная веб-страница RadioGatún с официальным описанием хэша, общедоступным ссылочным кодом и тестовыми векторами
  • rg32hash, независимая общедоступная реализация 32-разрядной версии RadioGatún