Русская Википедия:RadioGatún
RadioGatún - это криптографический примитив, разработанный Гвидо Бертони, Йоан Даймен, Микаэлем Петерсом и Жилем Ван Ассше. Он был впервые представлен на конкурсе криптографических примитивов от Национального института стандартов и технологий США в 2006 году.
RadioGatún является семейством из 64 различных хеш-функций, отличающихся единственным параметром – длиной слова в битах (w), лежащей в диапазоне от 1 до 64. Алгоритм использует 58 слов, каждое длиной w, чтобы хранить свое внутреннее состояние. Так, например, 32-битной версии необходимо 232 байта для хранения своего состояния, а 64-битной 464 байта.
RadioGatún может быть использован и как хеш-функция, и как потоковый шифр; он может выдавать последовательность псевдослучайных чисел произвольной длины. Подобные виды хеш-функций известны как функции расширяемого вывода.[1]
Прародители и потомки
Прообразом для RadioGatún послужила хеш-функция и потоковый шифр конца 90-х годов - Panama, чья хеш-функция к 2001 году уже не являлась криптостойкойШаблон:Sfn. В отличие от своего предка RadioGatún не обладает теми же уязвимостями при использовании его в качестве хеш-функции.
Команда разработчиков, создавшая RadioGatún, продолжила свои исследования и внесла значительные изменения в этот криптографический примитив, что привело к созданию Keccak SHA-3 алгоритма.Шаблон:Sfn
Детали реализации
Функция RadioGatun состоит из двух структурных компонентов, которые объединены в круговую (Шаблон:Lang-en) функцию: пояс (Шаблон:Lang-en) и мельница (Шаблон:Lang-en).Шаблон:Sfn Мельница <math>a</math> состоит из 19 слов <math>a[i]</math>, а пояс <math>b</math> представляет из себя 13 каскадов <math>b[i]</math> по 3 слова <math>b[i,j]</math> в каждом. Блок входных даны <math>p</math> состоит из 3 слов <math>p[i]</math>, в то время как блок выходных данных <math>z</math> включает в себя 2 слова <math>z[i]</math>. Все индексы начинаются с 0.
Круговая функция определена в алгоритме 1 и проиллюстрирована на схеме. Она использует функцию мельницы, которая описана алгоритме 2. Реализация потоков входных и выходных данных представлена в алгоритмах 3 и 4.
Алгоритм 1 Реализация круговой функции R на псевдокоде:
(A,B) = R(a,b)
for all i do
B[i] = b[i + 1 mod 13]
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}
for i = 0 to 2 do
A[i + 13] = A[i + 13] ⊕ b[12, i]
end for{Belt to mill feedforward}
Алгоритм 2 Реализация функции мельницы на псевдокоде:
A = Mill(a)
{all indices should be taken modulo 19,
x ≫ y denotes rotation of bits within x over y
positions
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}
Алгоритм 3 Загрузка входных данных на псевдокоде:
(a, b) ← 0
for i = 0 to 2 do
b[0, i] = p[i]
a[i + 16] = p[i]
end for
Return (a, b)
Алгоритм 4 Выгрузка выходных данных на псевдокоде:
z[0] = a[1]
z[1] = a[2]
Return z
Заявленная надежность
Создатели алгоритма в оригинальной статье утверждают, что первые 19 * w бит (где w – длина используемого слова) выдаваемые RadioGatún это криптографически стойкая хеш-функция.Шаблон:Sfn Другими словами, они утверждают, что первые 608 бит 32-битной версии и 1216 бит 64-битной версии RadioGatún могут быть использованы как криптографические хеш-значения.
В терминах атаки «дней рожде́ния», это означает, что для данной длины слова w, RadioGatún спроектирован так, что он неуязвим для атак со сложностью менее 29.5w. Что соответствует 2304 для 32-битной версии и 2608 для 64-битной.
После публикации статьи разработчики пересмотрели заявленную надежность и теперь утверждают, что RadioGatún обладает криптостойкой функцией губки с мощностью 19w.[2] Это означает, что 32-битная версия RadioGatún может быть использована для создания 304-битного уровня криптостойкости (как от коллизионных атак так и от атак нахождения прообраза), в то же время 64-битная версия обеспечивает 608-битный уровень криптостойкости.
Криптоанализ
В статье "Two attacks on RadioGatún", Дмитрия Ховратовича (Шаблон:Lang-en) демонстрирует две атаки, которые не опровергают заявленной надежности, одна со сложностью 218w, другая со сложностью 223.1w.Шаблон:Sfn Ховратович также написал статью под названием "Cryptanalysis of hash functions with structures", которая описывает атаку со сложностью 218w.Шаблон:Sfn
В статье "Analysis of the Collision Resistance of RadioGatún using Algebraic Techniques", Шарль Буйе и Пьер-Ален Фуке представляют способ генерации коллизий с 1-битовой версией алгоритма, используя атаку, которая требует 224.5 операций.Шаблон:Sfn Рассматриваемая атака не может быть обобщена на более крупные версии, т.к. со слов авторов статьи все возможные решения, которые были получены для 1-битной версии, оказалось невозможно распространить на n-битные версии.Шаблон:Sfn Эта атака является наименее эффективной атакой и также не опровергает заявленной надежности алгоритма.
Атака со сложностью 211w, рассмотренная в статье "Cryptanalysis of RadioGatun" Томаса Фура и Томаса Пейрина, является самой эффективной.Шаблон:Sfn Но даже она не опровергает заявленной надежности.
Тестовые векторы
Единственными вариантами, для которых разработчики предоставили тестовые векторы (опубликованные значения хеш-функции для входных выборок, для которых программисты могут проверить, правильно ли они реализуют алгоритм), являются 32-битные и 64-битные версии.[3]
RadioGatún[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") =
9ABE1E29997540749A440664BFA67909E91B3DC21B0D381F2686067EF5B38F2E
RadioGatún[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
Примечания
Литература
Ссылки
- The RadioGatún Hash Function Family Шаблон:Wayback, официальная веб-страница RadioGatún с официальным описанием хеша, общедоступным ссылочным кодом и векторами испытаний.
- rg32hash Шаблон:Wayback, независимая общедоступная реализация 32-битной версии RadioGatún.
- ↑ Шаблон:Cite web
- ↑ http://radiogatun.noekeon.org/ Шаблон:Wayback "We now prefer to express the security claim for RadioGatún as a flat sponge claim with capacity 19w"
- ↑ Шаблон:Cite web
