Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Grain - это потоковый шифр, представленный eSTREAM в 2004 году Мартином Хеллом , Томасом Йоханссоном и Вилли Мейером . Он был выбран для окончательного портфолио eSTREAM для профиля 2 проектом eSTREAM. Grain разработан в первую очередь для ограниченных аппаратных сред. Он принимает 80- битный ключ и 64-битный IV . Спецификации не рекомендуют максимальную длину вывода на пару (ключ, iv). В Grain 128a был выявлен и исправлен ряд потенциальных слабых мест в шифре. который теперь рекомендуется использовать для аппаратных сред, обеспечивающих как 128-битную безопасность, так и аутентификацию.

Описание [ править ]

160-битное внутреннее состояние Grain состоит из 80-битного регистра сдвига с линейной обратной связью (LFSR) и 80-битного регистра сдвига с нелинейной обратной связью (NLFSR). Grain обновляет один бит LFSR и один бит состояния NLFSR для каждого бита зашифрованного текста, выпущенного функцией нелинейного фильтра. 80-битный NLFSR обновляется с помощью нелинейной логической функции 5 к 1 и 1-битного линейного входа, выбранного из LFSR. Нелинейная функция 5-к-1 принимает на вход 5 битов состояния NLFSR. 80-битный LFSR обновляется линейной функцией 6: 1. Во время операций с ключом выход шифра дополнительно возвращается в виде линейных входов в функции обновления NLFSR и LFSR.

В исходной версии Grain Version 0.0 Grain один бит 80-битного NLFSR и четыре бита 80-битного LFSR подаются в нелинейную логическую функцию 5 к 1 (которая выбрана для балансировки, корреляция не зависит от первого порядка и имеет алгебраическую степень 3), и выход линейно комбинируется с 1 битом 80-битного NLFSR и выпускается как выход.

В обновленном представлении Grain Version 1.0 Grain один бит 80-битного NLFSR и четыре бита 80-битного LFSR передаются в (слегка измененную) нелинейную логическую функцию 5-к-1, а вывод линейно комбинируется с 7 битов 80-битного NLFSR и выпущены как выходные.

Для инициализации шифра 80-битный ключ загружается непосредственно в 80-битный NLFSR, а 64-битный IV загружается в младшие 64-битные LFSR, а оставшиеся 16 старших битов LFSR заполняются единицами. Шифр запечатан на 160 раундов, где 160 битов генерируемого ключевого потока передаются линейно обратно в функции обновления LFSR и NLFSR. В процессе инициализации шифр не выводит ключевой поток.

Авторы Grain обсуждают полную скорость распространения процесса инициализации Grain в спецификациях Grain Version 1.0: «Для инициализации с двумя разными IV, отличающимися только одним битом, вероятность того, что бит регистра сдвига одинаков для обеих инициализаций, должна быть близка к 0,5. . Моделирование показывает, что это достигается после 160 часов ».

Производительность [ править ]

Шифр предназначен для параллельного выполнения до 16 раундов, что позволяет ускорить реализацию за счет более широкого использования оборудования.

Безопасность [ править ]

Размер ключа составляет 80 бит, а размер IV определен как 64 бита. Авторы утверждают, что шифр спроектирован таким образом, что невозможна атака быстрее, чем исчерпывающий поиск ключа, следовательно, лучшая атака должна требовать вычислительной сложности не значительно ниже 2 80 .

В исходных спецификациях Grain Version 0.0 [1] авторы заявляют: «Grain обеспечивает более высокий уровень безопасности, чем несколько других хорошо известных шифров, предназначенных для использования в аппаратных приложениях. Хорошо известными примерами таких шифров являются E0, используемые в Bluetooth и A5 / 1. используются в GSM . Эти шифры, хотя и имеют очень небольшую аппаратную реализацию, оказались очень небезопасными. По сравнению с E0 и A5 / 1 , Grain обеспечивает более высокую безопасность при сохранении небольшой аппаратной сложности ».

Авторы цитируют атаку против E0 [2], требующую сложности в 2 40 и 2 35 кадров (длина кадра 2745 бит). Исходный шифр Grain Version 0.0 был взломан атакой восстановления ключа [3], которая потребовала сложности в 2 43 вычислений и 2 38 битов ключевого потока для определения 80-битного ключа.

В пересмотренных спецификациях Grain Version 1.0 [4] шифр имеет слегка измененную функцию вывода, а функция обратной связи NLFSR получила незначительные изменения. В спецификациях утверждается: «Функция фильтра довольно мала, всего 5 переменных и нелинейность 12. Однако это частично компенсируется тем фактом, что один из входных данных берется из NLFSR. Входной бит из NLFSR будет зависеть нелинейно [ sic ] на других битов в состоянии, как из LFSR и от NLFSR. небольшая функция фильтра также компенсируется добавлением 7 битов по линейному закону [ так в оригинале ] из NLFSR в подходящих местах , чтобы сформировать выходной функции «.

По состоянию на октябрь 2006 года не известно ни одной атаки восстановления ключа лучше, чем атака грубой силы против Grain Version 1.0.

Тем не менее, атака с использованием связанных ключей была опубликована в сентябре 2006 года Озгулом Кучуком в статье «Атака повторной синхронизации слайдов при инициализации Grain 1.0». [5] В документе утверждается: «мы находим связанные ключи и начальные значения потокового шифра Grain 1.0. Для любой пары (K, IV) существует связанная пара (K ', IV') с вероятностью 1/22, которая генерирует 1- битовый поток ключей. Хотя это еще не приводит к эффективной атаке восстановления ключа, это указывает на слабость в инициализации, которую можно было бы преодолеть [ sic ] с небольшими усилиями ».

Ссылки [ править ]

  1. ^ Мартин Ад , Томас Йоханссон , Вилли Мейер (2005-04-29). «Grain - потоковый шифр для сред с ограничениями» ( PDF ) . eSTREAM. Цитировать журнал требует |journal=( помощь )CS1 maint: несколько имен: список авторов ( ссылка )
  2. ↑ Yi Lu , http://lasecwww.epfl.ch/~vaudenay/ (2004). «Криптоанализ двухуровневого генератора ключевого потока Bluetooth E0» ( PDF ) . Достижения в криптологии - Asiacrypt 2004, LNCS vol. 3329, стр 483-499, Springer, 2004. Цитировать журнал требует |journal=( помощь )
  3. ^ Ком Бербен , Анри Гильбер , Александр Максимов (2006-01-02). «Криптоанализ зерна» ( PDF ) . eSTREAM. Цитировать журнал требует |journal=( помощь )CS1 maint: несколько имен: список авторов ( ссылка )
  4. ^ Мартин Ад , Томас Йоханссон , Вилли Мейер (2006). «Grain - потоковый шифр для сред с ограничениями» ( PDF ) . eSTREAM. Цитировать журнал требует |journal=( помощь )CS1 maint: несколько имен: список авторов ( ссылка )
  5. ^ Ozgul Кучук (2006-07-16). "Атака повторной синхронизации слайдов при инициализации зерна 1.0" ( PS ) . eSTREAM. Цитировать журнал требует |journal=( помощь )

Внешние ссылки [ править ]

  • Страница eSTREAM на сайте Grain