Статистическая атака на генератор гаммы с линейным законом реинициализации начального состояния и функцией усложнения, близкой к алгебраически вырожденной PDF

Автори:А.Н. АЛЕКСЕЙЧУК, С.Н. КОНЮШОК, А.Ю. СТОРОЖУК

А.Н. АЛЕКСЕЙЧУК, С.Н. КОНЮШОК, А.Ю. СТОРОЖУК

 

Одним из требований к современным синхронным поточным шифрам является условие их практической стойкости относительно атак на основе известных или подобранных векторов инициализации. Возможность осуществления таких атак на практике обусловлена особенностями функционирования синхронных поточных шифров (необходимостью синхронизации устройств зашифрования и расшифрования информации путем реинициализации начального состояния генератора гаммы (ГГ) поточного шифра) [1].      

Одна из первых атак на основе известных векторов инициализации предложена в [2]. В этой работе показано, что если закон реинциализации (формирования начального состояния ГГ по ключу и вектору инциализации) является линейным, а функция усложнения зависит от s переменных, то на генератор можно провести алгебраческую атаку со сложностью  операций, где t○ – длина отрезка гаммы, вырабатываемого генератором при каждом запуске (новом значении вектора инициализации), l – длина ключа; при этом требуется, чтобы число запусков было не меньше, чем 2^5.       

Атака из [2] совершенствовалась и обобщалась в различных направлениях [3 – 6]. В [4] показано, что она применима к генератору гаммы с алгебраически вырожденной функцией усложнения порядка n-s (то есть функцией от n>s переменных, линейно эквивалентной функции от s переменных); рассмотрен также случай, в котором указанная функция может быть не известна криптоаналитику. В [5], наряду с другими, описана статистическая атака на ГГ с линейным законом реинициализации начального состояния и произвольной функцией усложнения, близкой к аффинной булевой функции. Отметим также работу [7], в которой предложен алгоритм восстановления начального состояния генератора гаммы по единственному отрезку выходной последовательности в предположении, что криптоаналику доступны знаки этой последовательности в определенных тактах, номера которых экспоненциально зависят от длины начального состояния ГГ.    

В настоящей статье представлена атака на генератор гаммы на основе известных векторов инициализации, которая отличается от алгоритма из [7] и применима при менее жестких ограничениях относительно функции усложнения ГГ по сравнению указанными выше с атаками, описанными в [4, 5]. При общих естественных предположениях получена оценка трудоемкости предложенной атаки. Приведены  результаты численных расчетов и вычислительных экспериментов.

 

 

В статье описана атака на генератор гаммы с линейным законом реинициализации начального состояния и функцией усложнения от n переменных, находящейся на расстоянии не более 2^n-1(1-є) от множества s-мерных булевых функций (є є (0,1), 1<s<n). В отличие от ранее известных [2, 4, 5], предложенная атака применима к более широкому классу генераторов гаммы, при менее жестких ограничениях относительно их функций усложнения. Трудоемкость атаки зависит квадратично от параметра ε^-1 и экспоненциально от параметра s (см. формулы (16), (17)).

Как показывают численные расчеты, при ε>0.05 и s<10 предложенная атака, в принципе, позволяет восстанавливать ключ длины l=128 бит со сложностью не более 2^38 элементарных операций, используя не более 2^15 отрезков гаммы (длины не более 117 знаков каждый) вместе с соответствующими им векторами инициализации.их выводов составляет задачу дальнейших исследований авторов статьи.

References

1. eStream – the ECRYPT stream cipher project / http://www.ecrypt.eu.org/stream.

2. Daemen J. Resynchronization weaknesses in synchronous stream ciphers / J. Daemen, R. Govaerts, J. Vandewalle // Advances in Cryptology – EUROCRYPT’93, Proceedings. Berlin. Springer-Verlag, 1993. – P. 159–167.

3. Borissov Y. On a resynchronization weakness in a class of combiners with memmory / Y. Borissov, S. Nikova, B. Preneel, J. Vandewalle // The 3rd Conf. on Security in Communication Networks, Proceedings. Berlin. Springer-Verlag, 2003. – P. 165–177.

4. Golić J. On the resynchronization attack / J. Golić, G. Morgari // Fast Software Encryption. – FSE’03, Proceedings. Berlin. Springer-Verlag, 2003. – P. 100–110.

5. Armknecht F. Extending the resynchronization attack / F. Armknecht, J. Lano, B. Preneel // Selected Areas in Cryptography – SAC’04, Proceedings. Berlin. Springer-Verlag. 2004. – P. 19–38.

6. Yang W. A resynchronization attack on stream ciphers filtered by Maiorana-McFarland functions / W. yang, Y. Hu // Front. Comput. Sci. China, 2011. – Vol. 5(2). – P. 158 – 162.

7. Алексеев Е.К. Об атаке на фильтрующий генератор с функцией усложнения, близкой к алгебраически вырожденной / Е.К. Алексеев // Сборник статей молодых ученых факультета МВК МГУ, 2011. – Вып. 8. – С. 114–123.