MUGI

MUGI
[[Изображение: Файл:51210.jpg MUGI мини| 200px| изображение]]
Опубликован:	Февраль 2002
Размер ключа:	128 bits
Число раундов:	32

MUGI это генератор псевдослучайных чисел, который был разработан для того, чтобы использоваться как потоковый шифр. Он был рекомендован проектом CRYPTREC для использования правительством Японии. ^{[1] [2]}

Принцип работы

Входными параметрами MUGI являются 128-битный секретный ключ и 128-битный вектор инициализации (initialization vector). После того, как ключ и вектор инициализации получены, MUGI генерирует 64-битные блоки основываясь на внутреннем состоянии, которое изменяется после каждого блока. Размер внутреннего состояния MUGI составляет 128 бит. Оно состоит из трёх 64-битных регистров состояния (регистры "состояния") и 16 64-битных регистров ("буферные" регистры). ^[3] MUGI использует нелинейные S-блоки изначально возникшие в Advanced Encryption Standard (AES).

Разработчики определили семейство шифров, схожих с Panama, как Panama-like keystream generator (PKSG). Рассмотрим конечный автомат с двумя внутренними состояниями a, буфером b и их обновляющих функций $\rho$ и $\lambda$ . Шифр считается принадлежащим к семейству PKSG, если:

• $\rho$ включает в себя преобразование SPN и использует части буфера б как параметр. $a^{(t+1)} = \rho(a^{(t)},b^{(t)})$

• $\lambda$ - линейное преобразование и использует части а как параметр $b^{(t+1)} = \lambda(b^{(t)}, a^{(t)})$

• f выводит часть состояния (обычно не более 1/2)

Основное состояние работы данного псевдослучайного генератора состоит из множества $(S, F, f)$ где S - внутреннее состояние, F - функция его обновления и f - фильтр, изолирующий выходную последовательность от внутреннего состояния S. В сущности, набор (S, F) является конечным автоматом внутренних состояний шифра. В случае шифра Panama, внутреннее состояние разделено на две части, состояние a и буфер b. Функция обновления так же разделена на 2 части. Выходной фильтр f отбирает примерно половину битов состояния a на каждом раунде.

MUGI это ГПСЧ со 128-битным секретным ключом K (секретный параметр) и 128-битным инициализирующим вектором I (публичный параметр). Минимальный объем данных, с которым работает шифр слово - 64 бита.

В данном алгоритме функции обработки работают в конечное поле галуа GF(2^8) над полиномом 0x11b.

Алгоритм

 Входные данные: Секретный ключ К, инициализующий вектор I, число выходных слов n (по 64 бита)
 Выходные данные: Последовательность случайных чисел Out[i] (0<=i<n)
 Инициализация
 Шаг 1: Поместить секретный ключ К в состояние a. Затем инициализировать буфер b через функцию $\rho$
 Шаг 2: Добавить инициализующий вектор I к состоянию а и обновить состояние а функцией $\rho$
 Шаг 3: Запускать обновление внутреннего состояния запуская обновляющую функцию MUGI до завершения инициализационных прогонов
 Генерация случайных чисел
 Шаг 4: Запустить N раундов обновляющей функции и выводить часть внутреннего состояния каждый раунд.

Обновляющая функция, упомянутая выше это комбинация функций $\rho$ и $\lambda$ следующего вида: $(a^{(t+1)}, b^{(t+1)}) Update(a^{(t)},b^{(t)} = (\rho(a^{(t)},b^{(t)}),(\lambda(a^{(t)},b^{(t)})))$

Фукнция F это композиция сложения (из буфера), нелинейной трансформации S-box, линейной трансформаци с использованием MDS матрицы M и перемешивания байт. Следует отметить, что преобразования S и матрица M могут быть просто реализованы поиском по таблице.

Преобразование S - битовая замена - S-box в MUGI такая же как в шифре AES. Это значит, что замена S-box это композиция инверсии x -> x^-1 в GF(2^8) и афинного преобразования.

Функция обновления $\rho$: $a^{(t+1)}_0 = a^{(t)}_1$

$a^{(t+1)}_1 = a^{(t)}_2\bigoplus F(a^{(t)}_1,b^{(t)}_4)\bigoplus C_1$

$a^{(t+1)}_2 = a^{(t)}_2\bigoplus F(a^{(t)}_0,b^{(t)}_10 <<< 17)\bigoplus C_2$

В алгоритме MUGI используются три константы: C0 для инициализации, и C1, C2 в функции ρ. Они принимают следующие значения:

• C0 = 0x6A09E667F3BCC908

• C1 = 0xBB67AE8584CAA73B

• C2 = 0x3C6EF372FE94F82B

Это шестнадцатеричные значения √2, √3, and √5 умноженные на 264.

Разработка

Шифр был разработан чтобы быть удобным в реализации как программно, так и апппаратно. За основу разработчики взяли шифр Панама, который мог быть использован как хэш функция и потоковый шифр. Разработчики шифра Панама не ухватились за использование регистров сдвига с линейной обратной связью (LFSR). Вместо этого они применили принципы разработки потоковых шифров к разработке блочных.

Достоинства

Шифр MUGI был разработан для того, чтобы быть простым в реализации и программно и аппаратно. По сравнению с шифрами RC4, E0, A5 MUGI показывает лучшие результаты в аппаратной реализации на FPGA. Максимальная скорость кодирования достигает 7 Gbps для частоты микросхемы 110 MHz. ^[4]

Применение

MUGI может быть просто использован как потоковый шифр. Для этого необходимо разделить открытый текст на блоки по 64 бита. Затем провести операцию XOR каждого из этих блоков с выходными блоками шифра MUGI с использования секретного ключа и инициализующего вектора каждый раунд.

Безопасность

Полный перебор ключей для данного алгоритма занимает в среднем $2^{127}$ шагов.

Безопасность ГПСЧ определяется зависимостью между входными и выходными потоками бит (или зависимостью между выходными битами последовательности). Все атаки на ГПСЧ которые могут предоставлять злоумышленнику информацию менее чем за количество шагов, необходимое для полного перебора ключей или внутренних состояний генератора, используют эти зависимости. Таким образом выходная последовательность бит ГПСЧ должна быть непредсказуемой. Таким образом можно выделить 3 класса уязвимостей ГПСЧ:

• Нарушение случайности. Атакующий фиксирует секретный ключ и инициализующий вектор и наблюдает нарушение случайности в выходной последовательности.
• Повторная синхронизация. Атакующий фиксирует секретный ключ и наблюдает корреляцию между инициализующими векторами и выходными последовательностями.
• Основанные на ключе атаки. Атакующий фиксирует инициализующий вектор и наблюдает корреляцию между секретными ключами и выходными последовательностями.

Линейно обновляемый компонент (буфер) MUGI был теоретически анализирован ^[5] и было обнаружено, что внутренняя реакция буфера, без обратной связи на нелинейно обновленные компоненты, состоит из двоичных линейных рекуррентных последовательностей с очень малым периодом 48, что может стать источником уязвимости. Показано, как эта слабость в принципе может быть использована для восстановления секретного ключа и нахождения линейных статистических зависимостей.

Так же был проведен предварительный анализ нелинейной компоненты MUGI ^[6] где были обнаружены возможные уязвимости. Хотя и не было обнаружено существенных уязвимостей в общей структуре шифра, но было обнаружено, что отдельные его части очень чувствительны к малым изменениям. В частности можно восстановить все 1216-битное состояние шифра и 128-битный секретный ключ используя только 56 слов из канала за 2¹⁴ шагов анализа этой информации. Если исключить из этого анализа линейную часть MUGI, секретная 192-битное состоянияе может быть восстановлено с использованием лишь 3 слов из канала за 2³² шагов анализа.

Тем не менее, по состоянию на 2011 год, известных атак, которые быстрее атак полным перебором пространства ключей или внутренних состояний, на алгоритм MUGI в целом не было обнаружено.

Ссылки

• MUGI homepage

Примечания

1. ↑ Официальный сайт CRYPTREC  (англ.). Архивировано из первоисточника 3 сентября 2012. Проверено 10 ноября 2011.
2. ↑ Dai Watanabe, Soichi Furuya, Kazuo Takaragi, Bart Preneel, (February 2002). "A New Keystream Generator MUGI" (PDF). 9th International Workshop on Fast Software Encryption (FSE 2002): 179–194, Leuven: Springer-Verlag. Проверено 2007-08-07. 
3. ↑ Hitachi, Ltd MUGI Pseudorandom Number Generator Specification Ver. 1.2  (англ.) (2001-12-1). Архивировано из первоисточника 3 сентября 2012. Проверено 10 ноября 2011.
4. ↑ Paris Kitsos and Athanassios N. Skodras On the Hardware Implementation of the MUGI Pseudorandom Number Generator  (англ.). Hellenic Open University (21-Mar-2007). Архивировано из первоисточника 3 сентября 2012. Проверено 10 ноября 2011.
5. ↑ Jovan Dj. Golic (February 2004). "A weakness of the Linear Part of Stream Cipher MUGI". 11th International Workshop on Fast Software Encryption (FSE 2004): 178–192, Delhi: Springer-Verlag. 
6. ↑ Alex Biryukov, Adi Shamir (February 2005). "Analysis of the Non-linear Part of Mugi" (PostScript). 12th International Workshop on Fast Software Encryption (FSE 2005): 320–329, Paris: Springer-Verlag. Проверено 2007-08-07.