RadioGatún

RadioGatún - это криптографический примитив, разработанный Гвидо Бертони, Йоан Даймен, Микаэлем Петерсом и Жилем Ван Ассше. Он был впервые представлен на конкурсе криптографических примитивов от Национального института стандартов и технологий США в 2006 году.

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

RadioGatún может быть использован и как хеш-функция, и как потоковый шифр; он может выдавать последовательность псевдослучайных чисел произвольной длины. Подобные виды хеш-функций известны как функции расширяемого вывода.

Прародители и потомки

Прообразом для RadioGatún послужила хеш-функция и потоковый шифр конца 90-х годов - Panama, чья хеш-функция к 2001 году уже не являлась криптостойкой. В отличие от своего предка RadioGatún не обладает теми же уязвимостями при использовании его в качестве хеш-функции.

Команда разработчиков, создавшая RadioGatún, продолжила свои исследования и внесла значительные изменения в этот криптографический примитив, что привело к созданию Keccak SHA-3 алгоритма.

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

Круговая функция RadioGatun

Функция RadioGatun состоит из двух структурных компонентов, которые объединены в круговую (англ. round) функцию: пояс (англ. belt) и мельница (англ. mill). Мельница $a$  состоит из 19 слов $a[i]$, а пояс $b$ представляет из себя 13 каскадов $b[i]$ по 3 слова $b[i,j]$ в каждом. Блок входных даны $p$ состоит из 3 слов $p[i]$, в то время как блок выходных данных $z$ включает в себя 2 слова $z[i]$. Все индексы начинаются с 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 это криптографически стойкая хеш-функция. Другими словами, они утверждают, что первые 608 бит 32-битной версии и 1216 бит 64-битной версии RadioGatún могут быть использованы как криптографические хеш-значения.

В терминах атаки «дней рожде́ния», это означает, что для данной длины слова w, RadioGatún спроектирован так, что он неуязвим для атак со сложностью менее 2^9.5w. Что соответствует 2³⁰⁴ для 32-битной версии и 2⁶⁰⁸ для 64-битной.

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

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

В статье "Two attacks on RadioGatún", Дмитрия Ховратовича (англ. Dmitry Khovratovich) демонстрирует две атаки, которые не опровергают заявленной надежности, одна со сложностью 2^18w, другая со сложностью 2^23.1w. Ховратович также написал статью под названием "Cryptanalysis of hash functions with structures", которая описывает атаку со сложностью 2^18w.

В статье "Analysis of the Collision Resistance of RadioGatún using Algebraic Techniques", Шарль Буйе и Пьер-Ален Фуке представляют способ генерации коллизий с 1-битовой версией алгоритма, используя атаку, которая требует 2^24.5 операций. Рассматриваемая атака не может быть обобщена на более крупные версии, т.к. со слов авторов статьи все возможные решения, которые были получены для 1-битной версии, оказалось невозможно распространить на n-битные версии. Эта атака является наименее эффективной атакой и также не опровергает заявленной надежности алгоритма.

Атака со сложностью 2^11w, рассмотренная в статье "Cryptanalysis of RadioGatun" Томаса Фура и Томаса Пейрина, является самой эффективной. Но даже она не опровергает заявленной надежности.

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

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

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

Литература

• G. Bertoni, J. Daemen, M. Peeters and G. Van Assche. The Road from Panama to Keccak via RadioGatún // Dagstuhl Seminar Proceedings. — Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009. — № 09031. — ISSN 1862-4405.
• G. Bertoni, J. Daemen, M. Peeters and G. Van Assche. RadioGatun, a belt-and-mill hash function // In Proceedings of Second NIST Cryptographic HashWorkshop. — 2006.
• Dmitry Khovratovich. Two attacks on RadioGatún // 9th International Conference on Cryptology in India. — 2008.
• Dmitry Khovratovich. Cryptanalysis of hash functions with structures // Selected Areas in Cryptography pp 108-125. — 2009.
• Charles Bouillaguet, Pierre-Alain Fouque. Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques // Selected Areas in Cryptography pp 245-261. — Canada, 2008. — № 5381. — ISBN 978-3-642-04158-7, 978-3-642-04159-4. — doi:10.1007/978-3-642-04159-4_16.
• Thomas Fuhr, Thomas Peyrin. Cryptanalysis of RadioGatun. — 2008.
• Vincent Rijmen, Bart Van Rompay, Bart Preneel, Joos Vandewalle. Producing Collisions for PANAMA // 8th International Workshop on Fast Software Encryption pp 37-51. — 2001. — ISBN 3-540-43869-6.

Ссылки

• The RadioGatún Hash Function Family Архивная копия от 29 декабря 2018 на Wayback Machine, официальная веб-страница RadioGatún с официальным описанием хеша, общедоступным ссылочным кодом и векторами испытаний.
• rg32hash Архивная копия от 21 декабря 2018 на Wayback Machine, независимая общедоступная реализация 32-битной версии RadioGatún.