ЧЕТВЕРКА (шифр)
| Общий | |
|---|---|
| Дизайнеры | Приходите Бербен, Анри Жильбер и Жак Патарен. |
| Впервые опубликовано | 28 мая 2006 г. (в Eurocrypt) |
| Деталь шифрования | |
| Размеры ключей | 80 бит |
| Структура | многомерная система квадратных уравнений |
В криптографии шифр QUAD — это потоковый шифр , который был разработан с учетом доказуемых аргументов безопасности.
Описание [ править ]
QUAD основан на итерации случайно выбранной многомерной квадратичной системы S=(Q 1 , ..., Q m ) m = kn уравнений с n неизвестными над конечным полем GF(q). Процесс генерации ключевого потока просто состоит в итерации трех следующихшагов для создания (k -1) n значений ключевого потока GF(q) на каждой итерации.
- Вычислить набор kn значений GF(q) S(x) = (Q 1 (x),..., Q kn (x)) где x — текущее значение внутреннего состояния;
- Выведите последовательность (Q n+1 (x),..., Q kn (x)) из (k-1)n значений ключевого потока GF(q).
- Обновите внутреннее состояние x с помощью последовательности из n первых сгенерированных значений GF(q) (Q 1 (x),..., Q n (x))
QUAD — это современный поточный шифр, т. е. он использует ключ и значение инициализации (IV) для создания последовательности ключевого потока. Также определены настройки Key и IV, которые также основаны на многомерной квадратичной системе.
Безопасность [ править ]
Безопасность генерации ключевого потока QUAD доказуемо сводится к предполагаемой неразрешимости проблемы MQ, а именно к решению многомерной системы квадратных уравнений. Первое доказательство было сделано для поля GF(2) для старомодного потокового шифра (где ключом является начальное состояние). Позже Бербен и Гилберт расширили его, чтобы учесть процедуру установки современного шифра (со стадией установки, получающей начальное состояние из ключа). Безопасность всего шифра как псевдослучайной функции может быть связана с предполагаемой неразрешимостью проблемы MQ. Авторы также изучили устойчивость шифра против классических атак.
Рекомендуемые параметры [ править ]
Авторы рекомендуют использовать версию QUAD с 80-битным ключом, 80-битным IV и внутренним состоянием n = 160 бит. Он выводит 160 бит ключевого потока (m = 320) на каждой итерации до 2 40 были созданы биты ключевого потока. [1]
На Eurocrypt 2006 отчеты о скорости были представлены для экземпляров QUAD с 160-битным состоянием и выходным блоком в полях GF(2), GF(16) и GF(256). Эти отчеты о скорости были частью анализа «Эффективные реализации многомерных квадратичных систем», который был опубликован Бербеном, Биллетом и Гилбертом на SAC 2006. [2] В этом анализе (который также охватывает несколько многомерных схем с открытым ключом, а также поточный шифр QUAD) частично изучалось влияние изменения размера поля на производительность без учета аспекта безопасности. [2]
Обсуждение параметров [ править ]
Исходная теорема безопасности для QUAD действительна только для поля GF(2), а рекомендуемые параметры не приводят к противоречию с доказательством безопасности. Авторы QUAD, представившие теорему безопасности, признали, что взлом QUAD по предложенным ими параметрам не противоречит теоремам доказательства безопасности, когда они предлагали схему на Eurocrypt 2006. Однако казалось, что авторы посчитали их достаточными для того, чтобы обеспечить желаемый уровень безопасности около 2 80 .
Ян, Чен, Бернштейн и Чен изучили безопасность различных наборов параметров и обнаружили, что некоторые из них очень небезопасны. [3] В их статье обсуждаются как теоретические, так и практические аспекты атаки QUAD и решения основной сложной проблемы. Например, в этой статье показано, как использовать XL-Wiedemann для разрушения экземпляра GF(256) QUAD (256, 20, 20) примерно за 2 66 циклов Оптерона и решить основную сложную проблему примерно за 2 45 циклов, который был проведен успешно. Однако, согласно этой статье, это займет около 2 110 решить экземпляр версии QUAD(2,160,160), рекомендованной авторами QUAD, с использованием XL-Wiedemann.
Исследование Янга и соавт. подчеркнул тот факт, что теоремы безопасности часто опираются на редукции с коэффициентом небрежности, и когда это учитывается, ни один из наборов параметров предложенных версий не является достаточным для доказательства безопасности. Экземпляром, который будет доказуемо безопасным, будет QUAD(2,320,320), то есть в два раза шире, чем первоначально предлагалось. [3]
Теорема безопасности также может быть доказана для GF(q), хотя и с большим коэффициентом слабости; это и расширения QUAD для более эффективных реализаций предложены Лю и др. [4]
Ссылки [ править ]
- ^ Ком Бербен; Анри Жильбер; Жак Патарен. QUAD: Практический потоковый шифр с доказуемой безопасностью (PDF) . Ежегодная международная конференция по теории и применению криптографических методов - EUROCRYPT 2006.
- ^ Jump up to: Перейти обратно: а б Ком Бербен; Оливье Билле; Анри Жильбер. Эффективные реализации многомерных квадратичных систем (PDF) . Международный семинар по избранным областям криптографии — SAC 2006. doi : 10.1007/978-3-540-74462-7_13 . Проверено 18 марта 2008 г.
- ^ Jump up to: Перейти обратно: а б Бо-Инь Ян; Оуэн Чиа-Синь Чен; Дэниел Дж. Бернштейн ; Цзюнь-Мин Чен (3 марта 2007 г.). Анализ QUAD (PDF) . Быстрое программное шифрование: 14-й международный семинар, FSE 2007 . Проверено 5 февраля 2008 г.
- ^ Майкл Фэн-Хао Лю; Чи-Джен Лу; Бо-Инь Ян; Цзиньтай Дин (23 октября 2007 г.). Защитите ГПСЧ из специализированных полиномиальных карт над любым F q (PDF) . Международный семинар по постквантовой криптографии - PQCrypto 2008.
- Ком Бербен; Анри Жильбер. О безопасности IV-зависимых потоковых шифров (PDF) . Международный семинар по быстрому программному шифрованию, 2007 г.
- Жан-Филипп Омассон; Вилли Мейер. Анализ многомерных хэш-функций (PDF) . 10-я Международная конференция по информационной безопасности и криптологии.
| |||||||||||||||||||||
