Поточный шифр Grain: структура и особенности реализации

Введение

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

Описание

Внутреннее состояние Grain на 160 бит состоит из 80-битного линейного регистра сдвига с обратной связью (LFSR) и 80-битного нелинейного регистра сдвига с обратной связью (NLFSR). Grain обновляет один бит состояния LFSR и один бит состояния NLFSR для каждого бита шифротекста, формируемого нелинейной функцией фильтрации. 80-битный NLFSR обновляется с помощью нелинейной булевой функции 5 к 1 и 1-битного линейного входа, выбираемого из LFSR. Нелинейная функция 5 к 1 принимает в качестве входных данных 5 бит состояния NLFSR. 80-битный LFSR обновляется с помощью линейной функции 6 к 1. Во время операций установки ключа выход шифра дополнительно подается обратно в качестве линейных входов в функции обновления NLFSR и LFSR. В оригинальной версии Grain 0.0 один бит 80-битного NLFSR и четыре бита 80-битного LFSR подаются в нелинейную булеву функцию 5 к 1 (которая выбрана сбалансированной, устойчивой к корреляции первого порядка и имеющей алгебраическую степень 3), а выход линейно комбинируется с 1 битом 80-битного NLFSR и выдается в качестве результата. В обновленной версии Grain 1.0 один бит 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 тактов".

Grain's 160 bit internal state consists of an 80 bit linear feedback shift register (LFSR) and an 80 bit non linear feedback shift register (NLFSR). Grain updates one bit of LFSR and one bit of NLFSR state for every bit of ciphertext released by a nonlinear filter function. The 80 bit NLFSR is updated with a nonlinear 5 to 1 Boolean function and a 1 bit linear input selected from the LFSR. The nonlinear 5 to 1 function takes as input 5 bits of the NLFSR state. The 80 bit LFSR is updated with a 6 to 1 linear function. During keying operations the output of the cipher is additionally fed back as linear inputs into both the NLFSR and LFSR update functions. In the original Grain Version 0.0 submission of Grain, one bit of the 80 bit NLFSR and four bits of the 80 bit LFSR are supplied to a nonlinear 5 to 1 Boolean function (that is chosen to be balanced, correlation immune of the first order and has algebraic degree 3) and the output is linearly combined with 1 bit of the 80 bit NLFSR and released as output. In the updated Grain Version 1.0 submission of Grain, one bit of the 80 bit NLFSR and four bits of the 80 bit LFSR are supplied to a (slightly revised) nonlinear 5 to 1 Boolean function and the output is linearly combined with 7 bits of the 80 bit NLFSR and released as output. To initialize the cipher, the 80 bit key is loaded directly into the 80 bits NLFSR and the 64 bit IV is loaded into the low 64 bits of the LFSR and the remaining 16 high bits of the LFSR are filled with ones. The cipher is sealed for 160 rounds where the 160 bits of keystream generated are fed back linearly into both the LFSR and NLFSR update functions. The cipher releases no keystream output during the initialization process. Grain's authors discuss the complete diffusion rates of Grain initialization process in the Grain Version 1.0 specifications: "For initialization with two different IVs, differing by only one bit, the probability that a shift register bit is the same for both initializations should be close to 0.5. Simulations show that this is achieved after 160 clockings."

Выступление

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

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

Размер ключа составляет 80 бит, а размер IV – 64 бита. Авторы утверждают, что шифр разработан таким образом, чтобы любая атака не могла быть быстрее, чем полный перебор ключа, следовательно, лучшая атака должна требовать вычислительной сложности, ненамного меньшей чем 280. В оригинальных спецификациях Grain Version 0.0 авторы утверждают: «Grain обеспечивает более высокую безопасность, чем несколько других хорошо известных шифров, предназначенных для использования в аппаратных приложениях. Хорошо известные примеры таких шифров – E0, используемый в Bluetooth, и A5/1, используемый в GSM. Эти шифры, несмотря на небольшую аппаратную реализацию, оказались очень небезопасными. По сравнению с E0 и A5/1, Grain обеспечивает более высокую безопасность, сохраняя при этом небольшую аппаратную сложность». Авторы приводят пример атаки на E0, требующей сложности 240 и 235 кадров (кадр длиной 2745 бит). Оригинальный шифр Grain версии 0.0 был взломан атакой восстановления ключа, для которой потребовалось 243 вычислений и 238 бит ключевого потока для определения 80-битного ключа. В пересмотренных спецификациях Grain Version 1.0 шифр имеет незначительно измененную функцию вывода, а функция обратной связи NLFSR претерпела небольшие изменения. В спецификациях указано: «Функция фильтра довольно мала – всего 5 переменных и нелинейность 12. Однако это частично компенсируется тем, что один из входных параметров берется из NLFSR. Входной бит из NLFSR будет зависеть от других битов в состоянии, как из LFSR, так и из NLFSR. Небольшая функция фильтра также компенсируется добавлением 7 бит из NLFSR в подходящие позиции для формирования выходной функции». По состоянию на октябрь 2006 года неизвестно атак восстановления ключа, превосходящих атаку полным перебором, против Grain Version 1.0. Однако в сентябре 2006 года Озгул Кучук опубликовал связанную ключевую атаку в статье «Атака скользящей ресинхронизации на инициализацию Grain 1.0». В статье утверждается: «мы находим связанные ключи и начальные значения потокового шифра Grain 1.0. Для любой пары (K, IV) существует связанная пара (K’, IV’) с вероятностью 1/22, которая генерирует ключевой поток, сдвинутый на 1 бит. Хотя это пока не приводит к эффективной атаке восстановления ключа, это указывает на слабость инициализации, которую можно устранить при небольших усилиях».

The key size is 80 bits and the IV size is specified to be 64 bits. The authors claim that the cipher is designed such that no attack faster than exhaustive key search should be possible, hence the best attack should require a computational complexity not significantly lower than 280. In the original Grain Version 0.0 specifications, the authors claim: "Grain provides a higher security than several other well known ciphers intended to be used in hardware applications. Well known examples of such ciphers are E0 used in Bluetooth and A5/1 used in GSM. These ciphers, while also having a very small hardware implementation, have been proven to be very insecure. Compared to E0 and A5/1, Grain provides higher security while maintaining a small hardware complexity." The authors quote the attack against E0 requiring a complexity of 240 and 235 frames (a frame is 2745 bits long). The original Grain Version 0.0 cipher was broken by a key recovery attack which required a complexity of 243 computations and 238 keystream bits to determine the 80 bit key. In the revised Grain Version 1.0 specifications, the cipher has a slightly revised output function and the NLFSR feedback function received a minor change. The specifications claim: "The filter function is quite small, only 5 variables and nonlinearity 12. However, this is partly compensated by the fact that one of the inputs is taken from the NLFSR. The input bit from the NLFSR will depend on other bits in the state, both from the LFSR and from the NLFSR. The small filter function is also compensated by adding 7 bits from the NLFSR at suitable positions to form the output function." As of October 2006, no key recovery attacks better than brute force attack are known against Grain Version 1.0. However, a related key attack was published in September 2006 by Ozgul Kucuk in the paper "Slide Resynchronization Attack on the Initialization of Grain 1.0". The paper claims: "we find related keys and initial values of the stream cipher Grain 1.0. For any (K,IV) pair there exist related (K’,IV’) pair with probability 1/22 that generates 1 bit shifted keystream. Although this does not result in an efficient key recovery attack yet, it indicates a weakness in the initialization which could be with a little effort."