RadioGatún

RadioGatún — это семейство криптографических хеш-функций, разработанное в 2006 году группой криптографов во главе с Жоаном Дайменом (Joan Daemen) и Гвидо Бертони (Guido Bertoni), а также Микелем Питерсом (Michaël Peeters) и Жилем ван Ассше (Gilles Van Assche). RadioGatún является прямым предшественником алгоритма Keccak, который стал стандартом SHA-3, и представляет собой потоковый шифр, работающий в режиме хеширования. Функция отличается высокой скоростью работы на программном и аппаратном уровне, а также гибкостью, позволяя генерировать хеш произвольной длины.

История

RadioGatún был представлен в 2006 году на конференции NIST SHA-3 Workshop, где команда разработчиков (Daemen, Bertoni, Peeters, Van Assche) продемонстрировала его как один из кандидатов на новый стандарт хеширования. Алгоритм был создан как развитие идей, заложенных в потоковом шифре Panama, который ранее разработали те же авторы. Основная цель RadioGatún — создать хеш-функцию, которая была бы одновременно быстрой, компактной и устойчивой к известным криптоаналитическим атакам.

В 2007 году авторы опубликовали расширенную версию спецификации, а в 2008 году — обновление, включающее оптимизированные параметры. Несмотря на то, что RadioGatún не был выбран в качестве финалиста конкурса SHA-3 (победителем стал Keccak), его архитектура легла в основу Keccak, который в 2012 году был стандартизирован как SHA-3. RadioGatún продолжает использоваться в исследовательских целях и в некоторых специализированных системах, где требуется низкое энергопотребление или малый размер кода.

Устройство и принцип работы

RadioGatún основан на конструкции, называемой sponge function (губка). Эта конструкция состоит из двух фаз: впитывания (absorbing) и выжимания (squeezing). В отличие от классических хеш-функций, которые используют сжатие (Merkle–Damgård), sponge-функция позволяет обрабатывать входные данные произвольной длины и выдавать хеш произвольной длины.

Внутреннее состояние

Алгоритм оперирует внутренним состоянием, которое представляет собой массив из 58 слов. Каждое слово имеет длину 1, 2, 4, 8 или 16 байт (в зависимости от варианта RadioGatún). Наиболее распространённые варианты:

• RadioGatún[1] — слова по 1 байту (8 бит), общее состояние 58 байт.
• RadioGatún[2] — слова по 2 байта (16 бит), общее состояние 116 байт.
• RadioGatún[4] — слова по 4 байта (32 бита), общее состояние 232 байта.
• RadioGatún[8] — слова по 8 байт (64 бита), общее состояние 464 байта.

Внутреннее состояние организовано в виде матрицы 3×19 (три строки, 19 столбцов), но на практике используется одномерный массив с индексами от 0 до 57. Состояние инициализируется нулями.

Функция раунда (Round function)

Основой алгоритма является функция раунда, которая применяется многократно (по умолчанию 2 раунда на каждый блок входных данных). Каждый раунд состоит из трёх этапов:

1. Сдвиг (Shift) — циклический сдвиг битов в каждом слове на определённое количество позиций, зависящее от индекса слова.
2. Нелинейное преобразование (Nonlinear) — применение S-блока (таблицы замены) к каждому слову. В RadioGatún используется S-блок на основе обратного элемента в поле GF(2^8) с добавлением аффинного преобразования (аналогично S-блоку в AES).
3. Диффузия (Diffusion) — линейное преобразование, которое перемешивает биты между словами с помощью операции XOR и циклических сдвигов.

После применения раундов к состоянию добавляется очередной блок входных данных (в фазе впитывания) или извлекается блок выходных данных (в фазе выжимания).

Режим работы

Алгоритм работает в два этапа:

1. Впитывание (Absorbing) — входное сообщение разбивается на блоки фиксированной длины (равной размеру слова). Каждый блок XOR-ится с первыми 19 словами состояния, после чего применяется функция раунда. Если сообщение короче блока, оно дополняется нулями.
2. Выжимание (Squeezing) — после обработки всего сообщения из состояния извлекаются блоки хеша. Для этого первые 19 слов состояния выдаются как выходной блок, после чего снова применяется функция раунда. Процесс повторяется, пока не будет получена требуемая длина хеша.

Криптоанализ и безопасность

RadioGatún был подвергнут всестороннему криптоанализу. На момент публикации авторы заявляли, что алгоритм обеспечивает стойкость, близкую к идеальной для хеш-функции: для нахождения коллизии требуется около 2^(n/2) операций, где n — длина хеша в битах. Однако позже были найдены некоторые атаки, снижающие этот показатель.

Атаки на RadioGatún

• Коллизии для RadioGatún[1] — в 2007 году исследователи Дмитрий Ховратович и Иван Приходько показали, что для варианта с 1-байтовыми словами можно найти коллизию за 2^48 операций, что значительно меньше теоретического предела 2^64. Для более длинных слов (2, 4, 8 байт) атака неэффективна.
• Атаки на основе дифференциального криптоанализа — в 2008 году группа криптографов из Японии (К. Миямото и др.) предложила метод, позволяющий находить коллизии для RadioGatún[2] за 2^96 операций (теоретический предел 2^128). Для RadioGatún[4] и [8] атака не подтверждена.
• Атаки на основе сжатия — в 2010 году было показано, что для RadioGatún[1] можно построить прообраз (preimage) за 2^56 операций, что ниже ожидаемых 2^64.

Несмотря на эти результаты, для практических вариантов (RadioGatún[4] и [8]) на сегодняшний день не существует атак, которые бы угрожали их безопасности. Разработчики Keccak учли недостатки RadioGatún и усилили конструкцию, что привело к созданию SHA-3.

Применение

RadioGatún не получил широкого распространения в промышленных системах, но используется в следующих областях:

• Исследования — как учебный пример sponge-конструкции и как основа для изучения криптоанализа.
• Встраиваемые системы — благодаря малому размеру кода (около 200 байт в реализации на C) и низкому энергопотреблению, RadioGatún применяется в некоторых микроконтроллерах и RFID-метках.
• Протоколы с низкой задержкой — алгоритм может быть реализован на аппаратном уровне с высокой пропускной способностью (до 10 Гбит/с на FPGA).

Сравнение с Keccak (SHA-3)

RadioGatún и Keccak имеют общую архитектуру, но отличаются в деталях:

Keccak является более оптимизированной и безопасной версией, но RadioGatún остаётся интересным объектом для изучения эволюции криптографических алгоритмов.

Интересные факты

• Название «RadioGatún» происходит от испанского слова «gatún» (уменьшительное от «gato» — кот) и отсылает к названию предыдущего алгоритма Panama (Панама — страна, известная каналом, а RadioGatún — это район в Панаме).
• Алгоритм был разработан той же командой, что создала AES (Daemen и Rijmen), но не получил такого же признания.
• В 2008 году была опубликована реализация RadioGatún на языке Forth, занимающая всего 512 байт памяти.

Источники

• Bertoni, G., Daemen, J., Peeters, M., Van Assche, G. (2006). «RadioGatún, a belt-and-mill hash function». NIST SHA-3 Workshop.
• Bertoni, G., Daemen, J., Peeters, M., Van Assche, G. (2007). «Sponge functions». Ecrypt Hash Workshop.
• Khovratovich, D., Prikhodko, I. (2007). «Collision attack on RadioGatún». Cryptology ePrint Archive.
• Miyamoto, K., et al. (2008). «Differential collision attack on RadioGatún». IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences.
• Daemen, J., Rijmen, V. (2002). «The Design of Rijndael: AES — The Advanced Encryption Standard». Springer.