QUAD (шифр) - QUAD (cipher)

QUAD

Общий
Дизайнеров	Ком Бербен, Анри Жильбер и Жак Патарен
Впервые опубликовано	28 мая 2006 г. (в Eurocrypt)
Деталь шифра
Ключевые размеры	80 бит
Структура	многомерная система квадратных уравнений

В криптография, то QUAD, шифр - относительно новый потоковый шифр, который был разработан с учетом аргументов доказуемой безопасности.

Описание

QUAD опирается на итерацию случайно выбранной многомерной квадратичной системы S = (Q₁, ..., Q_м) m = kn уравнений от n неизвестных над конечным полем GF (q). Процесс генерации ключевого потока просто состоит в повторении трех следующих шагов для получения (k -1) n значений ключевого потока GF (q) на каждой итерации.

• Вычислить набор из узлов GF (q) значений S (x) = (Q₁(х), ..., Q_кн(x)) где x - текущее значение внутреннего состояния;
• Выведите последовательность (Q_{п + 1}(х), ..., Q_кн(x)) из (k-1) n значений ключевого потока GF (q)
• Обновите внутреннее состояние x последовательностью n GF (q) первых сгенерированных значений (Q₁(х), ..., Q_п(Икс))

QUAD - это современный потоковый шифр, то есть он использует ключ и значение инициализации (IV) для создания последовательности ключевого потока. Также определены параметры Key и IV, которые также основаны на многомерной квадратичной системе.

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

Безопасность ключевой поток генерация QUAD доказуемо сводится к предполагаемой неразрешимости проблемы MQ, а именно к решению многомерной системы квадратных уравнений. Первое доказательство было проведено над полем GF (2) для старомодного потокового шифра (где ключ - это начальное состояние). Позже он был расширен Бербеном и Гилбертом, чтобы учесть процедуру настройки современного шифра (с этапом настройки, выводящим начальное состояние из ключа). Безопасность всего шифра как псевдослучайной функции может быть связана с предполагаемой неразрешимостью проблемы MQ. Авторы также изучили устойчивость шифра к классическим атакам.

Рекомендуемые параметры

Авторы рекомендуют использовать версию QUAD с 80-битным ключом, 80-битным IV и внутренним состоянием n = 160 бит. Он выводит 160 бит потока ключей (m = 320) на каждой итерации до 2⁴⁰ биты ключевого потока были созданы.

На Eurocrypt 2006 отчеты о скорости были представлены для экземпляров QUAD с 160-битным состоянием и блоком вывода по полям GF (2), GF (16) и GF (256). Эти отчеты о скорости были частью анализа «Эффективных реализаций многомерных квадратичных систем», который был опубликован Бербеном, Биллетом и Гилбертом на SAC 2006. Этот анализ (который также охватывает несколько многомерных схем с открытым ключом, а также поточный шифр QUAD ) частично изучили влияние изменения размера поля на производительность без учета аспекта безопасности.

Обсуждение параметров

Начальная теорема безопасности для QUAD действительна только для поля GF (2), и рекомендуемые параметры не достигают противоречия с доказательством безопасности. Авторы QUAD, которые дали теорему безопасности, признали, что нарушение QUAD при их предложенных параметрах не противоречит теоремам о доказательстве безопасности, когда они предложили схему на Eurocrypt 2006. Однако казалось, что авторы считали их достаточными для предоставить желаемый уровень безопасности около 2⁸⁰.

Ян, Чен, Бернштейн и Чен изучали безопасность различных наборов параметров в документе «Анализ квадроцикла» и обнаружили, что некоторые из них очень небезопасны. В их статье обсуждаются как теоретические, так и практические аспекты атаки на QUAD и решения основной сложной проблемы. Например, в этой статье показано, как с помощью XL-Wiedemann разбить экземпляр GF (256) QUAD (256, 20, 20) примерно на 2⁶⁶ Opteron циклов, и решить основную сложную проблему примерно за 2⁴⁵ циклов, который был успешно проведен. Однако, согласно этой статье, на это потребуется около 2¹¹⁰ для решения экземпляра версии QUAD (2,160,160), рекомендованной авторами QUAD, с использованием XL-Wiedemann.

Исследование Yang et al. подчеркнули тот факт, что теоремы безопасности часто полагаются на сокращения с коэффициентом слабости, и когда это принимается во внимание, ни один из наборов параметров предлагаемых версий не является достаточным для доказательства безопасности. Экземпляр, который будет доказуемо защищенным, будет иметь QUAD (2 320 320), то есть в два раза шире, чем предлагалось изначально.

Теорема безопасности также может быть доказана для GF (q), хотя и с большим коэффициентом неплотности; это и расширения QUAD для более эффективных реализаций предложены Liu et al. (см. ссылку "Безопасные PRNG из специализированных полиномиальных отображений над любым F_q").

Рекомендации

• «QUAD: практичный потоковый шифр с надежной защитой» (PDF). Получено 2008-03-18.
• «Эффективные реализации многомерных квадратичных систем» (PDF). Получено 2008-03-18.
• «О безопасности IV зависимых потоковых шифров» (PDF). Получено 2008-03-18.
• «Анализ QUAD» (Формат Adobe Acrobat). 2007-03-03. Получено 2008-02-05.
• «Анализ многомерных хэш-функций» (PDF).
• "Защитите ГПСЧ из специализированных полиномиальных отображений над любым $ F_q $" (PDF).