Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




21.04.2021


21.04.2021


20.04.2021


19.04.2021


16.04.2021





Яндекс.Метрика





RadioGatún

25.02.2021

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). Мельница a {displaystyle a} состоит из 19 слов a [ i ] {displaystyle a[i]} , а пояс b {displaystyle b} представляет из себя 13 каскадов b [ i ] {displaystyle b[i]} по 3 слова b [ i , j ] {displaystyle b[i,j]} в каждом. Блок входных даны p {displaystyle p} состоит из 3 слов p [ i ] {displaystyle p[i]} , в то время как блок выходных данных z {displaystyle z} включает в себя 2 слова z [ i ] {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 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 спроектирован так, что он неуязвим для атак со сложностью менее 29.5w. Что соответствует 2304 для 32-битной версии и 2608 для 64-битной.

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

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

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

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

Атака со сложностью 211w, рассмотренная в статье "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