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 году уже не являлась криптостойкой[2]. В отличие от своего предка RadioGatún не обладает теми же уязвимостями при использовании его в качестве хеш-функции.

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

Детали реализации[править | править код]

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

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

В терминах атаки «дней рожде́ния», это означает, что для данной длины слова w, RadioGatún спроектирован так, что он неуязвим для атак со сложностью менее 29.5w. Что соответствует 2304 для 32-битной версии и 2608 для 64-битной.

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

Криптоанализ[править | править код]

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

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

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

Тестовые векторы[править | править код]

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

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

Примечания[править | править код]

  1. http://csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents/perlner_XOFs.pdf
  2. Producing Collisions for PANAMA, 2001.
  3. The Road from Panama to Keccak via RadioGatún, 2009.
  4. RadioGatun, a belt-and-mill hash function, 2006, с. 9.
  5. RadioGatun, a belt-and-mill hash function, 2006, с. 9: «We claim that RadioGatun[lw] offers a security level indicated by a capacity lc = 19lw.For the 64-bit version RadioGatun this is a capacity of 1216 bits, for the 32-bit version and 16-bit version this gives 608 and 304 bits respectively».
  6. http://radiogatun.noekeon.org/ "We now prefer to express the security claim for RadioGatún as a flat sponge claim with capacity 19w"
  7. Two attacks on RadioGatún, 2008.
  8. Cryptanalysis of hash functions with structures, 2009.
  9. Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques, 2008, с. 14.
  10. Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques, 2008, с. 17: «All the possible trails we knew for the 1-bit version turned out to be impossible to extend to n-bit versions».
  11. Cryptanalysis of RadioGatun, 2008.
  12. http://radiogatun.noekeon.org

Литература[править | править код]

Ссылки[править | править код]

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