RadioGatún: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Орфографи |
Добавил больше информации об АИ в сноске 7 Метка: визуальный редактор отключён |
||
Строка 77: | Строка 77: | ||
В статье "Two attacks on RadioGatún", Дмитрия Ховратовича ({{lang-en|[[:en:Dmitry Khovratovich|Dmitry Khovratovich]]}}) демонстрирует две атаки, которые не опровергают заявленной надежности, одна со сложностью 2<sup>18''w''</sup>, другая со сложностью 2<sup>23.1''w''</sup>.{{sfn|Two attacks on RadioGatún|2008}} Ховратович также написал статью под названием "Cryptanalysis of hash functions with structures", которая описывает атаку со сложностью of 2<sup>18''w''</sup>.{{sfn|Cryptanalysis of hash functions with structures|2009}} |
В статье "Two attacks on RadioGatún", Дмитрия Ховратовича ({{lang-en|[[:en:Dmitry Khovratovich|Dmitry Khovratovich]]}}) демонстрирует две атаки, которые не опровергают заявленной надежности, одна со сложностью 2<sup>18''w''</sup>, другая со сложностью 2<sup>23.1''w''</sup>.{{sfn|Two attacks on RadioGatún|2008}} Ховратович также написал статью под названием "Cryptanalysis of hash functions with structures", которая описывает атаку со сложностью of 2<sup>18''w''</sup>.{{sfn|Cryptanalysis of hash functions with structures|2009}} |
||
В статье "Analysis of the Collision Resistance of RadioGatún using Algebraic Techniques", Шарль Буйе и Пьер-Ален Фуке представляют способ генерации коллизий с 1-битовой версией алгоритма, используя атаку, которая требует 2<sup>24.5</sup> operations.{{sfn|Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques|2008}} Рассматриваемая атака не может быть обобщена на более крупные версии, т.к. со слов авторов статьи все возможные решения, которые были получены для 1-битной версии, оказалось невозможно распространить на n-битные версии. Эта атака является наименее эффективной атакой и также не опровергает заявленной надежности алгоритма. |
В статье "Analysis of the Collision Resistance of RadioGatún using Algebraic Techniques", Шарль Буйе и Пьер-Ален Фуке представляют способ генерации коллизий с 1-битовой версией алгоритма, используя атаку, которая требует 2<sup>24.5</sup> operations.{{sfn|Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques|2008|с=14}} Рассматриваемая атака не может быть обобщена на более крупные версии, т.к. со слов авторов статьи все возможные решения, которые были получены для 1-битной версии, оказалось невозможно распространить на n-битные версии.{{sfn|Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques|2008|с=17|quote=All the possible trails we knew for |
||
the 1-bit version turned out to be impossible to extend to n-bit versions}} Эта атака является наименее эффективной атакой и также не опровергает заявленной надежности алгоритма. |
|||
Атака со сложностью 2<sup>11''w''</sup>, рассмотренная в статье "Cryptanalysis of RadioGatun" Томаса Фура и Томаса Пейрина.{{sfn|Cryptanalysis of RadioGatun|2008}} Но даже она не опровергает заявленной надежности. |
Атака со сложностью 2<sup>11''w''</sup>, рассмотренная в статье "Cryptanalysis of RadioGatun" Томаса Фура и Томаса Пейрина.{{sfn|Cryptanalysis of RadioGatun|2008}} Но даже она не опровергает заявленной надежности. |
||
Строка 154: | Строка 155: | ||
| издательство = Selected Areas in Cryptography pp 245-261 |
| издательство = Selected Areas in Cryptography pp 245-261 |
||
| год = 2008 |
| год = 2008 |
||
| номер = 5381 |
|||
| ISBN = 978-3-642-04158-7, 978-3-642-04159-4 |
|||
| место = Canada |
|||
| DOI = 10.1007/978-3-642-04159-4_16 |
|||
| ссылка = https://hal.archives-ouvertes.fr/inria-00417797/en/ |
| ссылка = https://hal.archives-ouvertes.fr/inria-00417797/en/ |
||
| ref = Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques |
| ref = Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques |
Версия от 15:08, 23 декабря 2018
RadioGatún - это криптографический примитив, разработанный Гвидо Бертони, Йоан Даймен, Микаэлем Петерсом и Жилем Ван Ассше. Он был впервые представлен на конкурсе криптографических примитивов от Национального института стандартов и технологий США в 2006 году.
RadioGatún является семейством из 64 различных хеш-функций, отличающихся единственным параметром – длиной слова в битах (w), лежащей в диапазоне от 1 до 64. Алгоритм использует 58 слов, каждое длиной w, чтобы хранить свое внутреннее состояние. Так, например, 32-битной версии необходимо 232 байта для хранения своего состояния, а 64-битной 464 байта.
RadioGatún может быть использован и как хеш-функция, и как потоковый шифр; он может выдавать последовательность псевдослучайных чисел произвольной длины. Подобные виды хеш-функций известны как функции расширяемого вывода.[1]
Прародители и потомки
Прообразом для RadioGatún послужила хеш-функция и потоковый шифр конца 90-х годов Panama. Но в отличие от своего предка RadioGatún не обладает теми же уязвимостями при использовании его в качестве хеш-функции.
Далее команда разработчиков, создавшая RadioGatún, продолжила свои исследования и внесла значительные изменения в этот криптографический примитив, что привело к созданию Keccak SHA-3 алгоритма.[2]
Детали реализации
Функция RadioGatun состоит из двух структурных компонентов, которые объединены в круговую (англ. round) функцию: пояс (англ. belt) и мельница (англ. mill).[3] Мельница состоит из 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 это криптографически стойкая хеш-функция.[3] Другими словами, они утверждают, что первые 608 бит 32-битной версии и 1216 бит 64-битной версии RadioGatún могут быть использованы ка криптографические хеш-значения.
В терминах атаки «дней рожде́ния», это означает, что для данной длины слова w, RadioGatún спроектирован так, что он неуязвим для атак со сложностью менее 29.5w. Что соответствует 2304 для 32-битной версии и 2608 для 64-битной.
После публикации статьи разработчики пересмотрели заявленную надежность и теперь утверждают, что RadioGatún обладает криптостойкой функцией губки с мощностью 19w.[4] Это означает, что 32-битная версия RadioGatún может быть использована для создания 304 защищенных бит (как от коллизионных атак так и от Атак нахождения прообраза), в то же время 64-битная версия предоставляет 608 защищенных бит.
Криптоанализ
В статье "Two attacks on RadioGatún", Дмитрия Ховратовича (англ. Dmitry Khovratovich) демонстрирует две атаки, которые не опровергают заявленной надежности, одна со сложностью 218w, другая со сложностью 223.1w.[5] Ховратович также написал статью под названием "Cryptanalysis of hash functions with structures", которая описывает атаку со сложностью of 218w.[6]
В статье "Analysis of the Collision Resistance of RadioGatún using Algebraic Techniques", Шарль Буйе и Пьер-Ален Фуке представляют способ генерации коллизий с 1-битовой версией алгоритма, используя атаку, которая требует 224.5 operations.[7] Рассматриваемая атака не может быть обобщена на более крупные версии, т.к. со слов авторов статьи все возможные решения, которые были получены для 1-битной версии, оказалось невозможно распространить на n-битные версии.[8] Эта атака является наименее эффективной атакой и также не опровергает заявленной надежности алгоритма.
Атака со сложностью 211w, рассмотренная в статье "Cryptanalysis of RadioGatun" Томаса Фура и Томаса Пейрина.[9] Но даже она не опровергает заявленной надежности.
Тестовые векторы
Единственными вариантами, для которых разработчики предоставили тестовые векторы (опубликованные значения хеш-функции для входных выборок, для которых программисты могут проверить, правильно ли они реализуют алгоритм), являются 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
Примечания
- ↑ http://csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents/perlner_XOFs.pdf
- ↑ The Road from Panama to Keccak via RadioGatún, 2009.
- ↑ 1 2 RadioGatun, a belt-and-mill hash function, 2006, с. 9.
- ↑ RadioGatun, a belt-and-mill hash function, 2006, с. 9: «We claim that RadioGatun offers a security level indicated by a capacity c = 19*w».
- ↑ Two attacks on RadioGatún, 2008.
- ↑ Cryptanalysis of hash functions with structures, 2009.
- ↑ Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques, 2008, с. 14.
- ↑ 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».
- ↑ Cryptanalysis of RadioGatun, 2008.
Литература
- 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. — Canada: Selected Areas in Cryptography pp 245-261, 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.
Ссылки
- The RadioGatún Hash Function Family, официальная веб-страница RadioGatún с официальным описанием хеша, общедоступным ссылочным кодом и векторами испытаний.
- rg32hash, независимая общедоступная реализация 32-битной версии RadioGatún.