Корреляционные атаки. 
Системные и прикладные аспекты

Корреляционные атаки применяют для анализа генераторов гаммы в поточных шифрах. Генератор гаммы представляет собой, как правило, композицию нескольких функциональных блоков и узлов типа ЛРС, булевой функции усложнения и др. Ключом генератора являются начальные состояния элементов памяти, в некоторых случаях — также параметры функциональных блоков.

Идея корреляционных атак заключается в использовании ненулевой взаимной корреляции (если таковая имеется) между выходной гаммой генератора и последовательностью, вырабатываемой некоторым функциональным блоком или узлом. Например, в фильтрующих и комбинирующих генераторах имеется взаимная корреляция между выходной гаммой и последовательностями, генерируемыми некоторыми ЛРС [18, 19]. При наличии корреляции можно поэтапно определить по выходной гамме начальные состояния различных регистров генератора. На каждом этапе, опробуя состояния регистра, отбраковываем как ложные все те состояния, при которых последовательность, вырабатываемая регистром, не коррелирует с выходной гаммой. Отбраковка выполняется с помощью различения статистических гипотез.

Рассмотрим генератор Геффе, использующий комбинацию генерирующих регистров ЛРС-1, ЛРС-2 и управляющего регистра ЛРС-3 длин щ, п₂ и п₃. Комбинирующая функция генератора /(х_{, х₂, х₃) = х_ух₃ © х₂(х₃ © © 1) совпадает с функцией х₁ (а также с функцией х₂) на ¾ всех наборов таблицы. Значит, гамма генератора совпадает с выходом ЛРС-1 примерно для 75% знаков. Опробуем начальные состояния ЛРС-1 и отбракуем «ложные» значения статистическим методом, генерируя знаки выхода ЛРС-1 и наблюдая частоту их совпадения с соответствующими знаками гаммы генератора. При истинном начальном состоянии частота совпадения знаков в последовательностях длины t распределена, но нормальному закону с математическим ожиданием 3t/A и с дисперсией 3^/16. При ложных значениях имеем нормальное распределение с математическим ожиданием tf 2 и с дисперсией t/A. Для отсева одного ложного значения достаточно примерно 16 сравнений знаков. Значит, трудоемкость определения начального состояния одного из генерирующих Л PC равна примерно 16 • 2^Г, где г — minfftj, п₂). Трудоемкость вскрытия остальных элементов ключа незначительна.

Наилучшее противодействие корреляционным атакам достигается при использовании комбинирующих функций с высоким корреляционным иммунитетом. Вместе с тем, Т. Зигенталером показано 1281, что имеется взаимосвязь между корреляционным иммунитетом комбинирующей функции и линейной сложностью гаммы генератора, обусловливающая ослабление одной характеристики при усилении другой.