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 состоит из двух структурных компонентов, которые объединены в круговую ( англ. round ) функцию: пояс ( англ. belt ) и мельница ( англ. mill ). Мельница ${\displaystyle a}$ состоит из 19 слов ${\displaystyle a[i]}$ , а пояс ${\displaystyle b}$ представляет из себя 13 каскадов ${\displaystyle b[i]}$ по 3 слова ${\displaystyle b[i,j]}$ в каждом. Блок входных даны ${\displaystyle p}$ состоит из 3 слов ${\displaystyle p[i]}$ , в то время как блок выходных данных ${\displaystyle z}$ включает в себя 2 слова ${\displaystyle 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.5 w} . Что соответствует 2 ³⁰⁴ для 32-битной версии и 2 ⁶⁰⁸ для 64-битной.

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

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

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

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

Атака со сложностью 2 ^{11 w} , рассмотренная в статье "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. // Dagstuhl Seminar Proceedings. — Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009. — № 09031 . — ISSN .
• G. Bertoni, J. Daemen, M. Peeters and G. Van Assche. // In Proceedings of Second NIST Cryptographic HashWorkshop. — 2006.
• Dmitry Khovratovich. // 9th International Conference on Cryptology in India. — 2008.
• Dmitry Khovratovich. // Selected Areas in Cryptography pp 108-125. — 2009.
• Charles Bouillaguet, Pierre-Alain Fouque. // Selected Areas in Cryptography pp 245-261. — Canada, 2008. — № 5381 . — ISBN 978-3-642-04158-7 , 978-3-642-04159-4 . — doi : .
• Thomas Fuhr, Thomas Peyrin. . — 2008.
• Vincent Rijmen, Bart Van Rompay, Bart Preneel, Joos Vandewalle. // 8th International Workshop on Fast Software Encryption pp 37-51. — 2001. — ISBN 3-540-43869-6 .

Ссылки

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