Радио Гатун
 | |
| Общий | |
|---|---|
| Дизайнеры | Гвидо Бертони Джоан Дэмен Майкл Питерс Жиль Ван Аш |
| Впервые опубликовано | август 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-битные варианты РадиоГатун. Алгоритм использует 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)
for row = 0 to 2 do
for all i do
B[i, row] = b[i + 1 mod 13, row]
end for
end for {Belt function: simple rotation}
for i = 0 to 11 do
B[i + 1, i mod 3] = B[i + 1, i mod 3] ⊕ a[i + 1]
end for {Mill to belt feedforward}
A = Mill(a) {Mill function}
b = B
for i = 0 to 2 do
A[i + 13] = A[i + 13] ⊕ b[12, i]
end for {Belt to mill feedforward}
А функция мельницы Mill(A) выглядит так:
{all indices should be taken modulo 19,
x ≫ y denotes bitwise rotation (rotate x right y bits)
x ⊕ y denotes exclusive or
x |~ y denotes performing a bitwise or between x and the bitwise negation of y}
for all i do
A[i] = a[i] ⊕ (a[i + 1]|~a[i + 2])
end for {γ: non-linearity}
for all i do
a[i] = A[7i] ≫ i(i + 1)/2
end for {π: intra-word and inter-word dispersion}
for all i do
A[i] = a[i] ⊕ a[i + 1] ⊕ a[i + 4]
end for {θ: diffusion}
A[0] = A[0] ⊕ 1 {ι: asymmetry}
Страница Wikibooks на RadioGatun предоставляет полную информацию о реализации, а Module:RadioGatun32 представляет собой реализацию 32-битной версии RadioGatun.
Криптоанализ
[ редактировать ]В статье «Две атаки на РадиоГатун» Дмитрий Ховратович представляет две атаки, не нарушающие заявлений разработчиков о безопасности, одна со сложностью 2. 18 Вт и еще один со сложностью 2 23,1 Вт . [ 11 ] Ховратович также является автором статьи «Криптовалютный анализ хэш-функций со структурами», в которой описана атака сложностью 2 18 Вт . [ 12 ]
В статье «Анализ устойчивости RadioGatún к столкновениям с использованием алгебраических методов» Шарль Буйаге и Пьер-Ален Фук представляют способ генерации коллизий с помощью 1-битной версии алгоритма с использованием атаки, требующей 2 24.5 операции. [ 13 ] Атака не может быть распространена на более крупные версии, поскольку «все возможные следы, которые мы знали для 1-битной версии, оказались невозможными для распространения на n-битные версии». Эта атака менее эффективна, чем другие атаки, а также не нарушает заявлений RadioGatún о безопасности.
Самая эффективная атака на алгоритм, сложность 2. 11 Вт , приведен в статье Томаса Фура и Томаса Пейрина «Криптоанализ RadioGatun». В статье они ломают 2-битную (размер слова два) версию RadioGatún. [ 14 ] Хотя эта атака более эффективна, чем другие атаки, она все же не нарушает требования безопасности.
Разработчики RadioGatun заявили, что их «собственные эксперименты не внушают доверия RadioGatun». [ 15 ]
Тестовые векторы
[ редактировать ]Единственными вариантами RadioGatún, для которых разработчики предоставили тестовые векторы (опубликованные хэш-значения для выборочных входных данных, чтобы программисты могли убедиться, что они правильно реализуют алгоритм), являются 32-битные и 64-битные версии.
Радио Гатун [32]
[ редактировать ]Эти тестовые векторы, сгенерированные с использованием 32-битной версии RadioGatún, показывают только первые 256 бит выходного потока RadioGatún[32] произвольной длины:
RadioGatun[32]("") =
F30028B54AFAB6B3E55355D277711109A19BEDA7091067E9A492FB5ED9F20117
RadioGatun[32]("The quick brown fox jumps over the lazy dog") =
191589005FEC1F2A248F96A16E9553BF38D0AEE1648FFA036655CE29C2E229AE
RadioGatun[32]("The quick brown fox jumps over the lazy cog") =
EBDC1C8DCD54DEB47EEEFC33CA0809AD23CD9FFC0B5254BE0FDABB713477F2BD
Радио Гатун [64]
[ редактировать ]Вот хеши для 64-битной версии:
RadioGatun[64]("") =
64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584
RadioGatun[64]("The quick brown fox jumps over the lazy dog") =
6219FB8DAD92EBE5B2F7D18318F8DA13CECBF13289D79F5ABF4D253C6904C807
RadioGatun[64]("The quick brown fox jumps over the lazy cog") =
C06265CAC961EA74912695EBF20F1C256A338BC0E980853A3EEF188D4B06FCE5
Ссылки
[ редактировать ]- ^ Бертони, Гвидо; Дэмен, Джоан; Питерс, Майкл; Ван Аш, Жиль (2009). «Дорога из Панамы в Кечак через RadioGatun» . Drops-Idn/V2/Document/10.4230/Dagsemproc.09031.17 . Материалы семинара Дагштула (DagSemProc). 9031 : 1–9. дои : 10.4230/DagSemProc.09031.17 . Проверено 20 октября 2009 г.
- ^ Садеги-Насаб, Алиреза; Рэйф, Вахид (2022). «Всесторонний обзор недостатков безопасности алгоритмов хеширования» (PDF) . Журнал компьютерной вирусологии и методов взлома . 19 (2): 287–302. дои : 10.1007/s11416-022-00447-w . S2CID 253033894 .
RadioGatún продолжает оставаться безопасной хэш-функцией
- ^ Кишор, Неха; Райна, Прия (2019). «Параллельное криптографическое хеширование: события за последние 25 лет». Криптология . 43 (6): 504–535. дои : 10.1080/01611194.2019.1609130 . S2CID 201884222 .
RadioGatún (Бертони и др., 2006 г.) по-прежнему в безопасности.
- ^ Томас Порнин (3 апреля 2011 г.). «Нужно предложение по более быстрому сравнению отпечатков пальцев и хэшей Linux» .
Среди тех, что я привожу, функции «Радиогатун» и «Шабал» в настоящее время не нарушены.
- ^ Зуко Уилкокс (24 февраля 2017 г.). «Уроки истории атак на защищенные хэш-функции» . Проверено 28 июня 2018 г.
ни одна новая защищенная хэш-функция (разработанная примерно после 2000 года) также до сих пор не поддалась коллизионным атакам.
- ^ «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 31 января 2017 г. Проверено 17 июля 2017 г.
{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка ) - ^ На странице 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) . 20 июля 2006 г.
- ^ «Дорога из Панамы в Кечак через РадиоГатун» (PDF) . S2CID 2222603 . Архивировано из оригинала (PDF) 5 августа 2018 г.
Поэтому для Keccak мы решили снять пояс и вместо этого увеличить количество слов в мельнице.
- ^ Ховратович, Дмитрий (2008). «Две атаки на РадиоГатун» (PDF) . Прогресс в криптологии — INDOCRYPT 2008 . Конспекты лекций по информатике. Том. 5365. стр. 53–66. дои : 10.1007/978-3-540-89754-5_5 . ISBN 978-3-540-89753-8 . S2CID 6487398 . Архивировано из оригинала (PDF) 7 августа 2018 г.
- ^ https://www.cryptolux.org/images/7/79/Struct.pdf Криптоанализ хэш-функций со структурами - Университет Люксембурга
- ^ Буйаге, Шарль; Фуке, Пьер-Ален (2009). «Анализ столкновительной устойчивости Radio с Gatún использованием алгебраических методов» . Избранные области криптографии . Конспекты лекций по информатике. Том. 5381. стр. 245–261. дои : 10.1007/978-3-642-04159-4_16 . ISBN 978-3-642-04158-7 .
- ^ Фур, Томас; Пейрин, Томас (2008). «Криптоанализ РадиоГатуна» . Архив электронной печати по криптологии .
- ^ «Кечак и стандартизация SHA-3» (PDF) .
Внешние ссылки
[ редактировать ]
- Семейство хеш-функций RadioGatún , официальная веб-страница RadioGatún, с официальным описанием хеша, общедоступным справочным кодом и тестовыми векторами.
- rg32hash , независимая общедоступная реализация 32-битной версии RadioGatún.
