Difference between revisions of "Криптографические генераторы. Поточные шифры и их криптоанализ"

From CryptoWiki
Jump to: navigation, search
(Каскадные генераторы Гольмана (Gollman))
(Регистр сдвига с обратной связью с переносом)
Line 124: Line 124:
 
Важной особенностью РСОСП является то, что для их анализа неприменим традиционный математический аппарат конечных полей. Поэтому для изучения схем с переносом разработана теория, основанная на 2-адических числах [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ke76|[Ke76]]].
 
Важной особенностью РСОСП является то, что для их анализа неприменим традиционный математический аппарат конечных полей. Поэтому для изучения схем с переносом разработана теория, основанная на 2-адических числах [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Ke76|[Ke76]]].
  
Использование в криптосхемах РСОСП заметно усложняет криптоаналитические атаки на основе корреляционного анализа последовательностей [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Go93|[Go93]]]. В связи с этим, представляются перспективными схемы типа каскадных [[Криптографический генератор|генераторов]] Гольмана, построенных на базе нескольких РСОСП.
+
Использование в криптосхемах РСОСП заметно усложняет криптоаналитические атаки на основе корреляционного анализа последовательностей [[Список литературы к разделу Криптографические генераторы. Поточные шифры и их криптоанализ#Go94|[Go94]]]. В связи с этим, представляются перспективными схемы типа каскадных [[Криптографический генератор|генераторов]] Гольмана, построенных на базе нескольких РСОСП.
  
 
== Поточные шифры и их криптоанализ ==
 
== Поточные шифры и их криптоанализ ==

Revision as of 10:46, 8 December 2013

Contents

Криптографические генераторы

Криптографические генераторы используются для выработки ключей криптосистем и гаммы для поточного шифрования.

Элементная база криптографических схем генераторов

Базовым элементом криптосхем многих генераторов является линейный регистр сдвига с максимальной длиной периода, выходная гамма которого (линейная рекуррентная последовательность) имеет хорошие статистические свойства. В силу того, что линейная рекуррентная последовательность не обладает нелинейными свойствами, возможно восстанавливать всю последовательность по ее сравнительно небольшому отрезку. Следовательно, линейный регистр сдвига нельзя рассматривать как хороший криптографический генератор, и использование линейного регистра сдвига при построении схем следует сочетать с различными функциональными узлами и элементами памяти.

Фильтрующие генераторы

Один из простейших способов усложнения последовательности над конечным множеством заключается в отображении ее n-грамм в знаки другой последовательности с помощью так называемой фильтрующей функции.

Пусть P – конечное поле. Фильтрующим генератором [Ф10] называется автономный автомат Формула 1.gif, где h – линейная подстановка векторного пространства Формула 2.gif, реализуемая линейным регистром сдвига длины n над полем P c функцией обратной связи f'(x),Формула 3.gif – фильтрующая функция.

Фильтрующий генератор называется нелинейным, если нелинейна фильтрующая функция. Криптографическая схема фильтрующего генератора изображена на рисунке 1.

Рисунок 1. Криптографическая схема фильтрующего генератора

Фильтрующий генератор имеет наилучшие характеристики тогда, когда используется линейный регистр сдвига максимального периода и сбалансированная фильтрующая функция. Это гарантирует длину периода гаммы, равную Формула 4.gif, где k=|P|, и сбалансированность числа единиц и числа нулей на периоде.

Нелинейные свойства гаммы обеспечиваются выбором нелинейной фильтрующей функции. Обозначим через d степень нелинейности фильтрующей функции. Известно [Ф10], что линейная сложность гаммы фильтрующего генератора Формула 5.gif, где Формула 6.gif – число различных конъюнкций от n переменных ранга от 0 до d.

Оценка снизу линейной сложности гаммы фильтрующего генератора зависит от более глубоких свойств фильтрующей функции. Например, для булевых бент-функций [KiSc83] при n, кратных 4, Формула 7.gif.

Известна [BeGu85] нижняя оценка для другого класса булевых функций, которая говорит о том, что для получения гаммы с высокой линейной сложностью необходимо использовать фильтрующую функцию достаточно большой степени нелинейности.

Известно [Ru85], что доля фильтрующих генераторов, построенных на базе линейного регистра сдвига максимального периода длины n, где n – простое, у которых линейная сложность достигает наибольшего значения, стремится к 1 с ростом n.

Комбинирующие генераторы

Комбинирующий генератор является усложнением фильтрующего генератора. Он построен на основе m>1 линейных регистров сдвига над полем P и комбинирующей функции Формула 8.gif, на вход которой поступают знаки линейных рекуррентных последовательностей, вырабатываемые линейными регистрами. Обозначим Формула 9.gif – длина ЛРС-j, Формула 10.gif. Криптографическая схема комбинирующего генератора на основе двух ЛРС изображена на рисунке 2.

Рисунок 2. Криптографическая схема комбинирующего генератора

Комбинирующий генератор называется нелинейным, если нелинейна комбинирующая функция.

Начальные состояния всех линейных регистров сдвига составляют начальное состояние генератора. Если начальное состояние каждого ЛРС отлично от нулевого, то соответствующее начальное состояние комбинирующего генератора называется неособенным.

Каждому полиному Формула 11.gif над конечным полем P можно поставить в соответствие полином Формула 12.gif над кольцом целых чисел, полученный из Формула 13.gif заменой всех ненулевых коэффициентов на 1 и заменой сложения и умножения в поле P сложением и умножением в кольце Формула 14.gif. Линейная сложность гаммы комбинирующего генератора Формула 15.gif [Ф10].

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

Если P – простое поле, и характеристические многочлены всех линейных регистров сдвига комбинирующего генератора примитивны и имеют попарно взаимно простые степени, то Формула 16.gif [А05].

При определенных линейных регистрах сдвига и комбинирующей функции можно обеспечить хорошие статистические свойства гаммы комбинирующего генератора и большую длину ее периода. В частности, если ЛРС-1,…,ЛРС-m генерируют последовательности, длины периодов которых Формула 17.gif попарно взаимно просты, и комбинирующая функция биективна по каждой переменной, то Формула 18.gif.

Примеры комбинирующих генераторов:

1) генератор Геффе (Geffe);

2) пороговый генератор.

Генератор Геффе использует комбинацию 3 регистров. Комбинирующая функция Формула 19.gif. Если все линейные регистры сдвига имеют максимальные периоды, и их длины Формула 20.gif попарно взаимно просты, то период гаммы равен произведению периодов линейных регистров сдвига, а линейная сложность гаммы генератора равна Формула 21.gif.

Пороговый генератор использует комбинацию нечетного числа регистров. Комбинирующая функция, называемая функцией мажорирования, равна Формула 22.gif. Длина периода гаммы порогового генератора равна произведению периодов линейных регистров сдвига, а линейная сложность гаммы генератора равна Формула 23.gif.

Генераторы гаммы с неравномерным движением

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

Построенные по такому принципу генераторы гаммы называются генераторами гаммы с неравномерным движением. Изменение закона движения регистра приводит к изменению исходной гаммы.

Широко используемый способ достижения эффекта неравномерного движения – последовательное соединение m автоматов, где каждый предыдущий автомат называют управляющим по отношению к следующему, последний автомат – генерирующим. Если m>2, то такое соединение автоматов называется каскадным. Другой способ – это несколько взаимно управляемых автоматов, совместно генерирующих гамму.

Генераторы «Формула 24.gif шагов»

Если в двухкаскадной схеме управляющий автомат есть фильтрующий генератор на базе линейного регистра сдвига длины n c фильтрующей функцией f(x), а генерирующий автомат есть линейный регистр сдвига длины m, отрабатывающий каждый такт в зависимости от управляющего знака Формула 25.gif или Формула 26.gif шагов, Формула 27.gif, то такой автомат называется генератором «Формула 28.gif шагов» [Ф10]. При Формула 29.gif, Формула 30.gif генератор «Формула 31.gif шагов» называется генератором «стоп-вперед». Криптографическая схема генератора «Формула 32.gif шагов» дана на рисунке 3.

Рисунок 3. Криптографическая схема генератора «Формула 24.gif шагов»

Пусть линейные регистры сдвига имеют максимальные длины периодов. Обозначим Формула 33.gif и Формула 34.gif – состояния соответственно ЛРС-1 и ЛРС-2 в i-м такте, i=1,2,… Уравнения гаммообразования генератора имеют вид:

Формула 35.gif

где Формула 36.gif – суммарная глубина продвижения ЛРС-2 после первых i тактов функционирования Формула 37.gif.

Величина Формула 38.gif не зависит от x Формула 45.gif число i кратно длине периода управляющей гаммы [Ф10]. При i, кратных Формула 39.gif, используем обозначение Формула 40.gif. Длина периода гаммы, вырабатываемой генератором «Формула 41.gif шагов», равна Формула 42.gif.

Верхняя оценка линейной сложности гаммы генератора имеет вид [Ny75]:

Формула 43.gif

где Формула 44.gif – длина периода выходной последовательности ЛРС-1.

Генераторы с перемежающимся шагом

Усложнением генератора «стоп-вперед» является генератор с перемежающимся шагом [Ф10]. Его гамма образуется как сумма гамм двух генераторов «стоп-вперед» с генерирующими линейными регистрами сдвига ЛРС-2 и ЛРС-3 длины m и r соответственно. Оба генерирующих регистра имеют общий управляющий блок – фильтрующий генератор с фильтрующей функцией f(x) на базе линейного регистра сдвига длины n. Если в i-м такте управляющий знак равен 1, то ЛРС-2 продвигается на 1 шаг, а ЛРС-3 простаивает, и при управляющем знаке 0 – наоборот. Ключом генератора являются начальные состояния всех линейных регистров сдвига.

Пусть все три регистра имеют максимальные длины периодов. Обозначим Формула 46.gif, Формула 47.gif и Формула 48.gif – состояния соответственно ЛРС-1, ЛРС-2 и ЛРС-3 в i-м такте, i=1,2,… Тогда суммарная глубина продвижения ЛРС-2 после первых i тактов функционирования Формула 49.gif.

Уравнения гаммообразования генератора имеют вид:

Формула 50.gif

Длина периода гаммы генератора с перемежающимся шагом равна Формула 51.gif.

Если характеристические многочлены ЛРС-2 и ЛРС-3 различны и неприводимы, длины периодов выходных последовательностей ЛРС-2 и ЛРС-3 взаимно просты, то длина периода гаммы генератора с перемежающимся шагом равна [Ф10] произведению длин периодов выходных последовательностей линейных регистров сдвига, а линейная сложность гаммы подчиняется оценкам:

Формула 52.gif

И генератор «Формула 53.gif шагов», и генератор с перемежающимся шагом вскрывается опробованием начального состояния управляющего линейного регистра сдвига. В силу этого эффективная длина ключа генератора близка к длине управляющего регистра.

Каскадные генераторы Гольмана (Gollman)

Каскадный генератор Гольмана [Ф10], построенный на основе m линейных регистров сдвига с максимальными длинами периодов, привлекателен тем, что может быть использован для генерации гаммы с огромной длиной периода и линейной сложностью. В этой конструкции первый регистр управляет вторым, второй – третьим и т. д.

Если все линейные регистры сдвига имеют длину n и различные примитивные характеристические многочлены [GoCh89], то длина периода гаммы m-каскадного генератора равна Формула 54.gif, а линейная сложность равна Формула 55.gif.

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

Сжимающие генераторы

Другой принцип управления движением использован в сжимающем генераторе [Ф10], который построен на основе параллельно работающих линейных регистров сдвига с максимальными длинами периодов. Знаками гаммы являются выходные значения, снимаемые с ячейки ЛРС-2, но только в те такты, когда управляющий знак ЛРС-1 равен 1, в остальные такты оба бита, генерируемые регистрами, игнорируются.

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

Генераторы с дополнительной памятью

При конструировании генераторов для уменьшения корреляции между гаммой и некоторыми промежуточными последовательностями генератора, вырабатываемыми автономными автоматами (в простейшем случае линейными регистрами сдвига) используются дополнительные регистры памяти. Имеется несколько способов использования дополнительной памяти в криптографических схемах.

Генераторы Макларена-Марсальи (MacLaren-Marsaglia)

В генераторах Макларена-Марсальи [Ф10] исходная последовательность усложняется с помощью регистра памяти и управляющих последовательностей.

Пусть имеется регистр памяти длины m, в который записываются элементы n-множества X. Для отображения входной последовательности над X в выходную последовательность над X используются 2 управляющие последовательности над кольцом Формула 56.gif – для управления записи в память членов входной последовательности и управления считыванием из памяти членов выходной последовательности.

Обозначим Формула 57.gif – длины периодов входной, выходной и управляющих последовательностей соответственно. Последовательность над множеством X называется полной, если она содержит все элементы множества X.

Если входная и управляющие последовательности являются периодическими, при этом управляющие последовательности полны [Ф10], то выходная последовательность также периодическая, причем Формула 58.gif, где Формула 59.gif.

Регистр сдвига с обратной связью с переносом

Другой способ использования дополнительной памяти для усложнения характеристик гаммы связан с конструкцией, получившей название регистра сдвига с обратной связью с переносом (РСОСП) [Ф10]. РСОСП – это автономный регистр сдвига, имеющий несколько ячеек дополнительной памяти, образующих регистр переноса. Наиболее простая разновидность РСОСП строится на базе двоичного линейного регистра сдвига и ячейки дополнительной памяти для записи целых чисел от 0 до Формула 60.gif, где r – число ячеек регистра, содержимое которых используется для вычисления обратной связи.

Пусть в ячейках регистра записаны биты Формула 61.gif, а в дополнительной памяти записано число Формула 62.gif. В следующем такте содержимое регистра сдвигается, крайний бит поступает на выход, при этом содержимое памяти и свободной после сдвига ячейки обновляется следующим образом:

1) вычисляется Формула 63.gif, где Формула 64.gif – двоичные коэффициенты, из которых r коэффициентов равны 1;

2) вычисляется Формула 65.gif;

3) младший бит числа Формула 66.gif записывается в свободную ячейку регистра сдвига, а набор остальных битов, соответствующий числу Формула 67.gif, является новым содержимым памяти.

Длина периода гаммы, вырабатываемой РСОСП, Формула 68.gif [Ф10].

Важной особенностью РСОСП является то, что для их анализа неприменим традиционный математический аппарат конечных полей. Поэтому для изучения схем с переносом разработана теория, основанная на 2-адических числах [Ke76].

Использование в криптосхемах РСОСП заметно усложняет криптоаналитические атаки на основе корреляционного анализа последовательностей [Go94]. В связи с этим, представляются перспективными схемы типа каскадных генераторов Гольмана, построенных на базе нескольких РСОСП.

Поточные шифры и их криптоанализ

Поточный шифр – это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. Поточные шифры это одна из составляющих схем симметричного шифрования, общий вид которых, обычно, представлен в виде одного или нескольких регистров сдвига и нелинейной функции[С13]. Так как сам по себе линейный рекуррентный регистр (ЛРР) – линейное устройство, задача нелинейной функции (НЛФ) – внесение нелинейности в выходную последовательность. Поточные шифры преобразуют открытый текст в шифртекст побитово. Простейшая реализация представлена на рисунке 4. Генерируется поток битов: Form2.jpg, называемый гаммой. Поток битов открытого текста Form3.jpg и поток гаммы подвергаются операции XOR, в результате получается поток битов шифртекста Form4.jpg , где Form5.jpg, такой режим шифрования называется гаммированием. Для расшифрования используется аналогичная формула Form6.jpg.

Рисунок 4. Процесс зашифрования и расшифрования

Различают синхронные и самосинхронизирующиеся поточные шифры.

Синхронные поточные шифры

Для синхронных поточных шифров (СПШ) характерна независимость последовательности гаммы от открытого текста при зашифровании и шифртекста при расшифровании.

Рисунок 5. Шифрование с использованием с СПШ

Плюсы СПШ:

  • не размножают искажений знаков текста, которые довольно часто имеют место при передаче по каналам связи.

Если при отправке сообщения был искажен знак mi или при передаче по каналу связи был искажен знак ci, то при синхронной работе генераторов эти искажения не повлияют на правильность расшифрования всех знаков, кроме i-того.

  • защищает передаваемый текст от несанкционированных вставок и удалений, так как в этих случаях произойдет рассинхронизация, и вмешательство немедленно обнаружится.

Минусы СПШ:

  • не защищает от умышленной подмены отрезка сообщения на другой отрезок той же длины.

Известный отрезок открытого текста нарушитель может легко подменить другим, который расшифруется в заранее заданный отрезок текста той же длины.

Условия для обеспечения высокого уровня защиты информации с помощью СПШ, управляющая гамма должна иметь [Ф10] :

  • большую длину периода;
  • высокую линейную сложность;
  • статистические характеристики мультиграмм близкие к соответствующим характеристикам идеальных случайных последовательностей.

Самосинхронизирующиеся поточные шифры

Самосинхронизирующиеся поточные шифры (ССПШ), для них характерна зависимость генерируемой гаммы от предшествующих битов шифртекста [Ф10]. Каждое шифруемое сообщение начинается со случайного отрезка из n знаков, который не несет содержательной нагрузки, он шифруестя, передается и затем расшифровывается. В силу несовпадения начальных состояний генераторов, этот отрезок расшифровывается некорректно, но после передачи n знаков генераторы синхронизируются.

Рисунок 6. Шифрование с использованием ССПШ

Плюсы ССПШ:

  • размешивание статистики открытого текста;

Минусы ССПШ:

  • размножение ошибок

Единичная ошибка в шифртексте порождает n ошибок в открытом тексте.

  • уязвимы по отношению к имитации сообщений

Нарушитель может записать какой-то перехваченный им отрезок шифрованного текста и позже отправить его в адрес. После нескольких нестыковок в начале сообщения (до n знаков) посланный отрезок расшифруется верно, и получатель не сможет определить, что принял устаревшее сообщение. Чтобы защититься от имитации сообщений необходимо использовать метки времени или менять ключи при каждом новом сообщении.

Криптоанализ

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

Методы криптоанализа схем поточного шифрования можно разделить на три класса:

  • аналитические атаки;
  • статистически атаки;
  • силовые атаки.

Силовые атаки

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

Корректность найденного ключа при знании открытого и шифрованного текстов проверяется достаточно просто – при тестировании открытый текст зашифровывается, и результат сравнивается с шифртекстом. Совпадение говорит о том, что искомый ключ найден.

Несколько сложнее с атакой на основе только лишь шифртекста. В этом случае необходимо наличие какой-либо дополнительной информации об открытом тексте, например [П09]:

1) если открытый текст является осмысленным на каком-либо языке, шифртекст должен иметь длину, превышающую расстояние единственности (число знаков шифртекста, необходимое для однозначного восстановления ключа);

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

Аналитические атаки

Аналитические атаки – это такие атаки, в которых алгоритм построения атаки основан на аналитических принципах вскрытия криптосхемы. Этот класс можно разбить на два подкласса [С13]: методы криптоанализа шифрующей гаммы и методы криптоанализа процедуры ключевой инициализации и реинициализации. В первом подклассе, в силу специфики принципов построения поточных шифров, основным видом атак на данные схемы являются корреляционные атаки, основная идея которых состоит в нахождении корреляции между шифрующей гаммой и различными линейными комбинациями ключа (регистра сдвига). Объектом исследования в корреляционных атаках выступают нелинейные функции, вносящие нелинейность в выходную последовательность регистра сдвига – таким образом, каждый раз, в зависимости от устройства применяемой нелинейной функции, реализации корреляционных атак будут различны и будут основаны на специфическом устройстве анализируемой функции.

Предполагается, что криптоаналитику известно описание генератора (образующие полиномы, вид нелинейного преобразования), он обладает открытым и соответствующим ему закрытым текстом. Задача криптоаналитика – определение применяемого ключа (начального заполнения). На рисунке 7 показаны самые известные аналитические атаки к СПШ.

Рисунок 7. Аналитические атаки
  • Корреляционные атаки (КА)

КА наиболее распространенные и используют корреляцию выходной последовательности схемы шифрования с выходной последовательностью регистров для восстановления начального заполнения последних.

Среди атак данного класса выделяют следующие атаки:

1. Базовые КА.

2. Атаки, базирующиеся на низковесовых проверках четности.

3. Атаки, базирующиеся на использовании конволюционных кодов.

4. Атаки, использующие технику турбо кодов.

5. Атаки, базирующиеся на восстановлении линейных полиномов.

6. Быстрая КА Чепыжова, Йоханссона, Смитса (Johansson, Smits).

Под быстрыми КА понимают атаки, вычислительная сложность которых значительно меньше вычислительной сложности силовых атак.

Коррелляционная атака достаточно легко применима в случае, если булевы функции усложнения, используемые в генераторах (фильтрующие функции, комбинирующие функции, функции мажорирования) имеют хорошие линейные приближения. Считается, что она эффективна, если существует линейное приближение, верное для δ всех наборов таблицы истинности функции, где δ>0,5.

  • Компромисс «время-память»

Предполагается, что криптоаналитику известна схема устройства и некоторый фрагмент шифрующей гаммы, тогда целью данной атаки является восстановление начального состояния сдвигового регистра по фрагменту шифрующей гаммы. Сложность атаки зависит от длины перехваченной гаммы и размера внутреннего состояния шифра. Такая атака была успешно применима к криптоалгоритму А5/1. В общем случае атака включает следующие этапы:

1. Строится большой словарь, включающий все возможные пары «состояние-выход».

2. Делается предположение, что шифр находится в каком-то фиксированном состоянии (предположение об определенном заполнении всех ячеек памяти). На основе этих входных данных генерируется выходная последовательность и далее просматривается перехваченная выходная последовательность с целью нахождения соответствия со сгенерированным выходом. В случае соответствия, фиксированное состояние с большой вероятностью считается начальным заполнением регистра, в противном случае алгоритм продолжает работать.

  • «Предполагай и определяй»

Предполагается, что криптоаналитику известны шифрующая гамма, количество сдвигов регистра между выходами схемы и полином обратной связи. В общем виде атака состоит из следующих шагов:

1. Предполагается содержимое ячеек регистра.

2. Определяется полное заполнение регистра путем применения линейной рекурренты регистра на основе принятых допущений.

3. Генерируется выходная последовательность. Если она эквивалентна шифрующей гамме, предположение считается верным, иначе – переход к шагу 1.

  • Инверсионные атаки

Предполагается, что известен полином обратной связи, фильтр-функция и последовательность точек съема. Цель данной атаки – восстановление начального состояния сдвигового регистра по фрагменту шифрующей последовательности.

  • Ключевая загрузка, инициализация/реинициализация

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

Существенно проще решается задача криптоанализа для двух открытых текстов, отличающихся лишь вставкой одного или нескольких символов. В этом случае для восстановления используется следующая аналитическая атака.

Атака с помощью вставки символа. Пусть открытый текст X.jpg c помощью гаммы K.jpg преобразуется в шифртекст Y.jpg в соответствии с вышеуказанными уравнениями шифрования. Криптоаналитику известен шифртекст, но не известны открытый текст и гамма. Предположим также, что криптоаналитик располагает криптограммой, полученной зашифрованием с помощью той же гаммы видоизмененного открытого текста вставкой в некоторой позиции известного бита x′. Пусть видоизмененный открытый текст есть Seq1.jpg и соответствующий шифртекст есть Seq2.jpg По двум шифртекстам можно определить, начиная с момента вставки, и гамму, и открытый текст.

Позицию вставки символа можно определить, сравнивая видоизмененный и оригинальный шифртексты. Если значение вставленного символа неизвестно, то варианты его значения перебираются. Для защиты от атаки с помощью вставки символа достаточно не использовать одинаковые отрезки гаммы.

Статистические атаки

Статистические атаки основаны на оценке статистических свойств шифрующей гаммы. Этот класс делится на два подкласса: методы криптоанализа сложности последовательности и методы криптоанализа свойств шифрующей гаммы. Методы первого подкласса направлены на выявление возможности генерации последовательности, аналогичной шифрующей гамме, каким-либо другим способом, сложность реализации которого была бы меньшей по сравнению со способом генерации шифрующей гаммы; в идеале, найденный способ должен быть применимым на практике. Данные методы используют концепции линейной сложности, профиля линейной сложности, квадратичного размаха. Методы второго подкласса направлены на выявление возможного дисбаланса в выходной последовательности криптосхемы с целью нахождения способа предположения следующего бита выходной последовательности с вероятностью лучшей, чем при случайном выборе. Данные методы оперируют различными статистическими тестами, выбор необходимого и достаточного количества тестов – прерогатива криптоаналитика.

Управляющая гамма должна иметь большую длину периода (многократно превосходящую длину открытого текста) и не содержать длинных повторяющихся отрезков. В противном случае криптоанализ значительно упрощается.

Анализ шифров, использующих гамму с одинаковыми повторяющимися отрезками.

Рассмотрим поточный шифр, реализующий модульное гаммирование с уравнениями шифрования

1x.jpg, i=1,2,…

Пусть криптоаналитик располагает криптограммами 2.jpg и 3.jpg, соответствующими открытым текстам 4.jpg и 5.jpg при использовании одинаковых отрезков гаммы. Требуется восстановить открытые тексты.

Разность данных криптограмм не зависит от гаммы:

6.jpg, i=1,2,…

Следовательно, решение задачи сводится к подбору двух открытых текстов, разность которых задана. Угадав фрагмент одного открытого текста (используя заранее известные стандарты или тематику, свойственную данному источнику открытых сообщений), можно вычислить фрагмент другого открытого текста.

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

Данный метод не всегда приводит к успеху. Однако если правильно восстановить части текстов, то это позволяет криптоаналитику восстановить гамму и решать задачу определения ключа по известным знакам гаммы.

Минимальные требования криптографически стойкого поточного шифра

Минимальные требования для противостояния криптоаналитическим атакам при построении схем поточного шифрования[С13]:

  • Каждый бит начального состояния регистра должен являться функцией от нелинейного преобразования всех бит ключа
  • При построении нелинейных функций данные функции должны удовлетворять критериям стойкости: быть сбалансированными, обладать высокой нелинейностью, иметь высокую алгебраическую степень.
  • При длине ключа k бит внутренне состояние генератора (внутренняя память) должно быть не менее k бит.
  • Минимальная длина регистра должна быть не менее l=100 бит, образующий полином иметь приблизительно l/2 ненулевых коэффициентов обратной связи.
  • Для достижения максимальной линейной сложности степень образующего полинома должна быть простым числом.
  • Для генерации регистром последовательности максимальной длины и высокой линейной сложности данный регистр должен быть основан на примитивном полиноме обратной связи, кроме того, длина l ЛРР и алгебраический порядок d нелинейной функции должны быть достаточно велики, чтобы величина Form1.jpg была значительно больше, чем длина шифрующей гаммы.
  • При использовании нескольких регистров их длины должны быть взаимно-простыми.

Глоссарий

Библиографический указатель

Перейти к списку литературы по разделу "Криптографические генераторы. Поточные шифры и их криптоанализ".


Авезова Я.Э., Гендугова Д.В., 2013 г.

Назад