Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Потоковий шифр



План:


Введення

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


1. Історія

Потокові шифри на базі зсувних регістрів активно використовувалися в роки війни, ще задовго до появи електроніки. Вони були прості в проектуванні і реалізації.

У 1965 році Ернст Селмер, головний криптограф норвезького уряду, розробив теорію послідовності зсувних регістрів. Пізніше Соломон Голомб, математик Агентства Національної Безпеки США, написав книгу під назвою "Shift Register Sequences" ("Послідовності зсувних регістрів"), в якій виклав свої основні досягнення в цій галузі, а також досягнення Селмер.

Велику популярність потоковим шифрів принесла робота Клода Шеннона, опублікована в 1949 році, в якій Шеннон довів абсолютну стійкість шифру Вернама (також відомого, як одноразовий блокнот). У шифрі Вернама ключ має довжину, рівну довжині самого переданого повідомлення. Ключ використовується в якості гами, і якщо кожен біт ключа вибирається випадково, то розкрити шифр неможливо (тому що всі можливі відкриті тексти будуть рівноймовірно). До теперішнього часу було придумано чимало алгоритмів потокового шифрування. Такі як: A3, A5, A8, RC4, PIKE, SEAL, eSTREAM.

Режим гамування для поточних шифрів

2. Режим гамування для поточних шифрів

Найпростіша реалізація потокового шифру зображена на малюнку. Генератор гами видає ключовий потік (гаму): k_1, k_2, k_3, \ dots, k_L . Позначимо потік бітів відкритого тексту m_1, m_2, m_3, \ dots, m_L . Тоді потік бітів шіфротекста виходить за допомогою застосування операції XOR : c_1, c_2, c_3, \ dots, c_L , Де c_i = m_i \ oplus k_i .

Розшифрування проводиться операцією XOR між тій же самій гамою і зашифрованих текстом: m_i = c_i \ oplus k_i .

Очевидно, що якщо послідовність бітів гами не має періоду і вибирається випадково, то зламати шифр неможливо. Але у даного режиму шифрування є і негативні особливості. Так ключі, порівнянні по довжині з переданими повідомленнями, важко використовувати на практиці. Тому зазвичай застосовують ключ меншої довжини (наприклад, 128 біт). За допомогою нього генерується псевдослучайная гаммірующая послідовність (вона повинна задовольняти постулатам Голомба). Природно, псевдовипадкових гами може бути використана при атаці на потоковий шифр.


3. Класифікація потокових шифрів

Припустимо, наприклад, що в режимі гамування для поточних шифрів при передачі по каналу зв'язку відбулося спотворення одного знака шіфротекста. Очевидно, що в цьому випадку всі знаки, прийняті без спотворення, будуть розшифровані правильно. Відбудеться втрата лише одного знака тексту. А тепер уявімо, що один із знаків шіфротекста при передачі по каналу зв'язку був втрачений. Це призведе до неправильного розшифрування всього тексту, наступного за втраченим знаком.
Практично у всіх каналах передачі даних для поточних систем шифрування присутні перешкоди. Тому для запобігання втрати інформації вирішують проблему синхронізації шифрування й розшифрування тексту. За способом вирішення цієї проблеми шифросистемамі поділяються на синхронні і системи з самосинхронізації.


3.1. Синхронні потокові шифри

Визначення:

Синхронні потокові шифри (СПШ) - шифри, в яких потік ключів генерується незалежно від відкритого тексту і шіфротекста.

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

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

Зауважимо, що виконуватимуться синхронізація повинна так, щоб жодна частина потоку ключів не була повторена. Тому переводити генератор в більш раннє стан не має сенсу.

Плюси ШПШ:

  • відсутність ефекту поширення помилок (тільки спотворений біт буде розшифрований невірно);
  • оберігають від будь-яких вставок і вилучень шіфротекста, так як вони призведуть до втрати синхронізації і будуть виявлені.

Мінуси ШПШ:

  • уразливі до зміни окремих біт шифрованого тексту. Якщо зловмисникові відомий відкритий текст, він може змінити ці біти так, щоб вони розшифровувалися, як йому треба.

3.2. Самосинхронізуються потокові шифри

Основна ідея побудови була запатентована в 1946 р. в США.
Визначення:
Самосинхронізуються потокові шифри (асинхронні потокові шифри (АПШ)) - шифри, в яких потік ключів створюється функцією ключа і фіксованого числа знаків шіфротекста.

Отже, внутрішній стан генератора потоку ключів є функцією попередніх N бітів шіфротекста. Тому Розшифруйте генератор потоку ключів, прийнявши N бітів, автоматично синхронізується з шифрувальним генератором.
Реалізація цього режиму відбувається наступним чином: кожне повідомлення починається випадковим заголовком довжиною N бітів; заголовок шифрується, передається і розшифровується; розшифровка є неправильною, зате після цих N біт обидва генератора будуть синхронізовані.

Плюси АПШ:

  • Розмішування статистики відкритого тексту. Так як кожен знак відкритого тексту впливає на наступний шіфротекст, статистичні властивості відкритого тексту поширюються на весь шіфротекст. Отже, АПШ може бути більш стійким до атак на основі надмірності відкритого тексту, ніж ШПШ.

Мінуси АПШ:

  • поширення помилки (кожному неправильного биту шіфротекста відповідають N помилок у відкритому тексті);
  • чувствительны к вскрытию повторной передачей.

4. Поточные шифры на регистрах сдвига с линейной обратной связью (РСЛОС)

4.1. Теоретическая основа

Есть несколько причин использования линейных регистров сдвига в криптографии:

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

Определение: Регистр сдвига с линейной обратной связью длины L состоит из L ячеек пронумерованных ~0,1,2,\dots L-1,каждая из которых способна хранить 1 бит и имеет один вход и один выход; и синхросигнала (clock), который контролирует смещение данных. В течение каждой единицы времени выполняются следующие операции:

  • содержимое ячейки ~L-1 формирует часть выходной последовательности;
  • содержимое ~i -той ячейки перемещается в ячейку ~i+1 для будь-якого ~i , ~0<i<L .
  • новое содержимое ячейки ~0 определяется битом обратной связи, который вычисляется сложением по модулю 2 с определёнными коэффициентами битов ячеек ~0,1,2,\dots L-1 .
Регистр сдвига с линейной обратной связью.

На первом шаге: S_L=c_1 \cdot S_{L-1}\oplus c_2 \cdot S_{L-2}\oplus \dots \oplus c_L \cdot S_0.

На втором шаге: S_{L+1}=c_1 \cdot S_L\oplus c_2 \cdot S_{L-1}\oplus \dots \oplus c_L \cdot S_1.

Следующее соотношение описывает в общем виде работу РСЛОС:

S_j=c_1 \cdot S_{j-1}\oplus c_2 \cdot S_{j-2}\oplus \dots\oplus c_L \cdot S_{j-L}.
Если мы запишем во все ячейки биты равны нулю, то система будет генерировать последовательность, состоящую из всех нулей. Если записать ненулевые биты, то получим полубесконечную последовательность. Последовательность определяется коэффициентами c_1,c_2,\dots ,c_L.
Посмотрим, каким может быть период ~T такой системы:
Число ненулевых заполнений: ~2^L-1. Значит, T\leqslant 2^L-1 .
После возникновения одного заполнения, которое было раньше, процесс начнёт повторяться. Процесс заполнения регистра, как показано выше, представим линейным разностным уравнением. Перенесём все члены в одну часть равенства, получим:
S_{j}\oplus c_{1}\cdot S_{j-1}\oplus c_{2}\cdot S_{j-2}\oplus\dots\oplus c_{L}\cdot S_{j-1}=0 .

Обозначим: ~S_j=D^{-j} . Тоді:
(1 \oplus c_1\cdot D \oplus c_2\cdot D^2 \oplus \dots \oplus c_L\cdot D^L )\cdot D^{-j}.

C(D) = 1 \oplus c_1\cdot D \oplus c_2 \cdot D^2 \oplus \dots \oplus c_L\cdot D^L.

Важным свойством этого многочлена является - приводимость.
Определение:
Многочлен называется приводимым, если он может быть представлен как произведение двух многочленов меньших степеней с коэффициентами из данного поля (в нашем случае с двоичными коэффициентами). Если такое представление не имеет место, то многочлен называется неприводимым.
Если многочлен ~C(D) является неприводимым и примитивным, то период будет совпадать с максимально возможным периодом, равным ~2^L-1.

Приклад.

Пример: Возьмём неприводимый примитивный многочлен ~C(D)=D^3+D^2+1 (c_3=1, c_2=1,c_1=0). Этот многочлен можно записать, как ~(3,2,0) выписаны степени, при которых стоят ненулевые коэффициенты.
Запишем в исходном состоянии в ячейки ~0 0 1 и определим длину периода генератора:

Таблиця. Определение периода генератора
Зворотній зв'язок Ячейка0 Ячейка1 Ячейка2
1 0 0 1
0 1 0 0
1 0 1 0
1 1 0 1
1 1 1 0
0 1 1 1
0 0 1 1
1 0 0 1

Период генератора равен ~7 (2^3-1=7). На выходе генератора буде последовательность: 1001011 1001011 1001011\dots
Приведём примеры некоторых примитивных многочленов по модулю 2:

(1,0), (2,1,0), (3,1,0), (4,1,0), (5,2,0), (6,1,0), (7,1,0), (7,3,0), (8,4,3,2,0), (9,4,0)\dots


4.2. Линейная сложность

Линейная сложность бинарной последовательности одна из самых важных характеристик работы РСЛОС. Поэтому остановимся на этой теме поподробнее.
Прежде чем дать определение линейной сложности введём некоторые обозначения.
~S - бесконечная последовательность с членами S1,S2,S3,\dots
~S_n конечная последовательность длины ~ N, членами которой являются S_1,S_2,S_3,\dots,S_{n-1}.
Говорят, что РСЛОС генерирует последовательность ~S, если существует некоторое исходное состояние, при котором выходная последовательность РСЛОС совпадает с ~S . Аналогично, говорят, что РСЛОС генерирует конечную последовательность ~S_n, если существует некоторое начальное состояние, для которого выходная последовательность РСЛОС имеет в качестве первых n членов члены последовательности ~S_n .
Наконец дадим определение линейной сложности бесконечной двоичной последовательности.
Определение: Линейной сложностью бесконечной двоичной последовательности ~S называется число ~L(S), которое определяется следующим образом:

  • Якщо ~S нулевая последовательность ~S=0,0,0,0,\dots, , То ~L(S)=0.
  • Если не существует РСЛОС, который генерирует ~S , То ~L(S) одно бесконечности.
  • Иначе, ~L(S) есть длина самого короткого РСЛОС, который генерирует ~S .

Определение:
Линейной сложностью конечной двоичной последовательности ~S_n называется число ~L(S_n), которое равно длине самого короткого РСЛОС, который генерирует последовательность, имеющую в качестве первых ~ N членов ~S_n .
Свойства линейной сложности: Пусть ~S і ~ K двоичные последовательности. Тоді:
1. Для будь-якого ~n>0 линейная сложность подпоследовательности ~S_n удовлетворяет неравенствам 0\leqslant L(S_n) \leqslant n.
2. ~L(S_n)=0 тоді і тільки тоді, коли ~S_n нулевая последовательность длины ~ N .
3. ~L(S_n)=n тоді і тільки тоді, коли ~S_n=0,0,0, \dots ,1 .
4. Якщо ~S - периодическая с периодом ~N , Тоді ~L(S_n)\leqslant N.
5. L(S \oplus K)\leqslant L(S) + L(K).
Эффективным алгоритмом определения линейной сложности конечной двоичной последовательности является алгоритм Берлекемпа-Месси.


5. Потоковые шифры основанные на РСЛОС. Усложнение

К сожалению, выходная последовательность РСЛОС легко предсказуема. Так, зная 2L знаков выходной последовательности, легко найти исходное заполнение регистра, решив систему линейных уравнений (см. пункт Поточные шифры на регистрах сдвига с линейной обратной связью).
Считается, что для криптографического использования выходная последовательность РСЛОС должна иметь следующие свойства:

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

Существует несколько методов проектирования генераторов ключевого потока, которые разрушают линейные свойства РСЛОС и тем самым делают такие системы криптографически более стойкими:
1. использование нелинейной функции, объединяющей выходы нескольких РСЛОС
2. использование нелинейной фильтрующей функции для содержимого каждой ячейки единственного РСЛОС
3. использование выхода одного РСЛОС для управления синхросигналом одного (или нескольких) РСЛОС.


5.1. Нелинейная комбинация генераторов

Нелинейная комбинация генераторов

Известно, что каждая Булева функция ~f(x_1,x_2, \dots ,x_n) может быть записана как сумма по модулю 2 произведений порядков ~m независимых переменных, 0 \leqslant m \leqslant n . Это выражение называется алгебраической нормальной формой функции ~f . Нелинейным порядком функции f называется максимальный порядок членов в записи её алгебраической нормальной формы.
Например, Булева функция f(x_1,x_2,x_3,x_4 )=x_1 \oplus x_2 \oplus x_4 \oplus x_1 x_3 \oplus x_2 x_3 x_4 имеет нелинейный порядок 3. Максимально возможный нелинейный порядок Булевой функции равен количеству переменных ~n.
Предположим теперь, что у нас ~ N регистров сдвига с линейной обратной связью, их длины L_1, L_2, L_3, \dots , L_n попарно различны и больше двух. Все регистры объединены нелинейной функцией f(x_1,x_2,\dots,x_n), как показано на рисунке. Функція ~f представлена в алгебраической нормальной форме. Тогда линейная сложность потока ключей равна f(L_1,L_2,\dots,L_n) .
Якщо L_1, L_2,\dots, L_n попарно взаимно-простые числа, то длина периода ключевого потока равна: (2^{L_1}-1)\cdot(2^{L_2}-1) \cdots (2^{L_n }-1) . Например, если ~L_i=10 , То (2^{L_1}-1)\approx 10^3 . И длина периода ключевого потока равна ~(10^3)^n .

Генератор Геффа

Пример (генератор Геффа):
В этом генераторе используются три РСЛОС, объединённые нелинейным образом. Длины этих регистров ~L_1, L_2, L_3 попарно простые числа.
Нелинейную функцию для данного генератора можно записать следующим образом:

f(x_1, x_2, x_3 )=x_1 x_2 \oplus (1+x_2 ) x_3=x_1 x_2 \oplus x_2 x_3 \oplus x_3.

Длина периода: (2^{L_1}-1)\cdot(2^{L_2}-1)\cdot(2^{L_3}-1).

Линейная сложность: ~L=L_1\cdot L_2+L_2\cdot L_3+L_3.

Генератор Геффа криптографически слаб, потому что информация о состояниях генераторов РСЛОС 1 и РСЛОС 3 содержится в его выходной последовательности. Для того чтобы понять это, обозначим ~x_1 (t),x_2 (t),x_3 (t),z(t)~t -ые выходные биты РСЛОС 1,2,3 и потока ключей, соответственно. Тоді корреляционная вероятность последовательности x_1 (t) по отношению к последовательности z(t)~ :

~P(z(t)=x_1 (t) )=P(x_2 (t)=1)+P(x_2 (t)=0)*P(x_3 (t)=x_1 (t) )=1/2+1/2*1/2=3/4.

Аналогично, ~P(z(t)=x_3 (t) )=3/4.
По этой причине, несмотря на длинный период и достаточно высокую линейную сложность, генератор Геффа поддаётся корреляционным атакам.

Генератор на нелинейном фильтре

5.2. Генераторы на нелинейных фильтрах

Выход каждой ячейки подаётся на вход некоторой нелинейной булевой фильтрующей функции ~f . Припустимо, що фильтрующая функция порядка ~m, тогда линейная сложность потока ключей не больше L_m=\sum^{m}_{i=1} {L \choose i} .

5.3. Генераторы основанные на управлении синхросигналом

В нелинейных комбинациях генераторов и генераторах на нелинейных фильтрах перемещение данных во всех РСЛОС контролируется одним синхросигналом.
Основная идея функционирования рассматриваемого типа генераторов внести нелинейность в работу генераторов потока ключей, основанных на РСЛОС, путём управления синхросигналом одного регистра выходной последовательностью другого.
Есть 2 типа генераторов основанных на управлении синхросигналом:
1. генератор переменного шага
2. сжимающий генератор.


5.3.1. Генератор переменного шага

Основная идея:
РСЛОС 1 используется для управления передвижением битов двух других РСЛОС 2 и 3.

Генератор переменного шага

Алгоритм роботи:
1. Регистр РСЛОС 1 синхронизован внешним синхросигналом
2. Если на выходе регистра РСЛОС 1 единица, то на регистр РСЛОС 2 подаётся синхросигнал, а РСЛОС 3 повторяет свой предыдущий выходной бит (для начального момента времени предыдущий выходной бит РСЛОС 3 принимается равным 0)
3. Если на выходе регистра РСЛОС 1 ноль, то на регистр РСЛОС 3 подаётся синхросигнал, а РСЛОС 2 повторяет свой предыдущий выходной бит (для начального момента времени предыдущий выходной бит РСЛОС 2 также принимается равным 0)
4. Выходная последовательность битов генератора с переменным шагом является результатом применения операции побитового исключающего ИЛИ к выходным последовательностям регистров РСЛОС 2 и РСЛОС 3.

Увеличение безопасности генераторов с переменным шагом:

  • длины регистров РСЛОС 1, РСЛОС 2, РСЛОС 3 должны быть выбраны попарно простыми числами
  • длины этих регистров должны быть близкими числами.

5.3.2. Сжимающий генератор

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

Контролирующий регистр РСЛОС 1 используется для управления выходом РСЛОС 2. Алгоритм:

  1. Регистры РСЛОС 1 и РСЛОС 2 синхронизованы общим синхросигналом;
  2. Если выходной бит РСЛОС 1 равен 1, выход генератора формируется выходным битом регистра РСЛОС 2;
  3. Если выходной бит РСЛОС 1 равен 0, выходной бит регистра РСЛОС 2 отбрасывается.

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

Для увеличения безопасности сжимающего генератора:

  • длины регистров РСЛОС 1 и РСЛОС 2 должны быть взаимно простыми числами;
  • желательно использовать скрытое соединение между регистрами РСЛОС 1 и РСЛОС 2.

6. Основные отличия поточных шифров от блочных

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

  • важнейшим достоинством поточных шифров перед блочными является высокая скорость шифрования, соизмеримая со скоростью поступления входной информации; поэтому, обеспечивается шифрование практически в реальном масштабе времени вне зависимости от объема и разрядности потока преобразуемых данных.
  • в синхронных поточных шифрах (в отличие от блочных) отсутствует эффект размножения ошибок, то есть число искаженных элементов в расшифрованной последовательности равно числу искаженных элементов зашифрованной последовательности, пришедшей из канала связи.
  • структура потокового ключа може мати вразливі місця, які дають можливість криптоаналітика отримати додаткову інформацію про ключі (наприклад, при малому періоді ключа криптоаналітика може використовувати знайдені частини потокового ключа для дешифрування подальшого закритого тексту).
  • ПШ на відміну від БШ часто можуть бути атаковані за допомогою лінійної алгебри (так як виходи окремих регістрів зсуву зі зворотним лінійним зв'язком можуть мати кореляцію з гамою). Також для злому поточних шифрів досить успішно застосовується лінійний і диференційний аналіз.

Тепер про становище в світі:

  • в більшості робіт з аналізу та злому блокових шифрів розглядаються алгоритми шифрування, засновані на стандарті DES; для поточних ж шифрів немає виділеного напрямку вивчення; методи злому ПШ вельми різноманітні.
  • для поточних шифрів встановлений набір вимог, які є критеріями надійності (великі періоди вихідних послідовностей, постулати Голомба, нелінійність); для БШ таких чітких критеріїв немає.
  • дослідженням і розробкою поточних шифрів в основному займаються європейські криптографічні центри, блочних - американські.
  • дослідження поточних шифрів відбувається більш динамічно, ніж блочних; останнім часом не було зроблено ніяких помітних відкриттів у сфері DES-алгоритмів, в той час як в області поточних шифрів трапилося безліч успіхів і невдач (деякі схеми, що здавалися стійкими, при подальшому дослідженні не виправдали надій винахідників).

7. Проектування потокових шифрів

Згідно Райнеру Рюппелю можна виділити чотири основні підходи до проектування потокових шифрів:

  • Системно-теоретичний підхід заснований на створенні для криптоаналітика складною, раніше недослідженою проблеми.
  • Сложностно-теоретичний підхід заснований на складній, але відому проблему (наприклад, факторизація чисел або дискретне логарифмування).
  • Інформаційно-технічний підхід заснований на спробі приховати відкритий текст від криптоаналітика - незалежно від того скільки часу витрачено на дешифрування, криптоаналітик не знайде однозначного рішення.
  • Рандомізований підхід заснований на створенні об'ємної задачі; криптограф тим самим намагається зробити рішення задачі розшифрування фізично неможливою. Наприклад, криптограф може зашифрувати деяку статтю, а ключем будуть вказівки на те, які частини статті були використані при шифруванні. Криптоаналітика доведеться перебирати всі випадкові комбінації частин статті, перш ніж йому пощастить, і він визначить ключ.

Теоретичні критерії Райнера Рюппеля для проектування потокових систем:

  • довгі періоди вихідних послідовностей;
  • велика лінійна складність;
  • дифузія - розсіювання надмірності в подструктурах, "розмазування" статистики по всьому тексту;
  • кожен біт потоку ключів повинен бути складним перетворенням більшості бітів ключа;
  • критерій нелінійності для логічних функцій.

До цих пір не доведено, що ці критерії необхідні або достатні для безпеки потокової системи шифрування. Варто також зауважити, що, якщо криптоаналітика має необмежені часом і обчислювальною потужністю, то єдиним реалізованим потоковим шифром, захищеним від такого супротивника є одноразовий блокнот.


8. Криптоаналіз. Атаки на потокові шифри

Всі методи криптоаналізу поточних шифрів зазвичай поділяють на силові (атака "грубою силою"), статистичні та аналітичні.

8.1. Силові атаки

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

8.2. Статистичні атаки

Статистичні атаки діляться на два підкласи:

  • метод криптоаналізу статистичних властивостей шифрувальної гами : спрямований на вивчення вихідний послідовності криптосистеми; криптоаналітика намагається встановити значення наступного біта послідовності з вірогідністю вище ймовірність випадкового вибору за допомогою різних статистичних тестів.
  • метод криптоаналізу складності послідовності: криптоаналітик намагається знайти спосіб генерувати послідовність, аналогічну гамі, але більш просто реалізованим способом.

Обидва методи використовують принцип лінійної складності.


8.3. Аналітичні атаки

Цей вид атак розглядається в припущенні, що криптоаналітика відомі опис генератора, відкритий і відповідний закритий тексти. Завдання криптоаналітика визначити використаний ключ (початкове заповнення регістрів). Види аналітичних атак, які застосовуються до синхронних потоковим шифрів:

  • кореляційні
  • компроміс "час-пам'ять"
  • інверсійна
  • "Передбачається і визначай"
  • на ключову завантаження і реініціалізацію
  • XSL-атака

8.3.1. Кореляційні атаки

Є найбільш поширеними атаками для злому поточних шифрів.

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

Існують наступні підкласи кореляційних атак:

  • Базові кореляційні атаки
  • Атаки, засновані на низько-вагових перевірках парності
  • Атаки, засновані на використанні сверточних кодів
  • Атаки, що використовують техніку турбо кодів
  • Атаки, засновані на відновленні лінійних поліномів
  • Швидкі кореляційні атаки.
Базові кореляційні атаки
Схема базової кореляційної атаки

Розглянемо на прикладі базової кореляційної атаки Зігенталера ("розділяй і розтинати"), яка заснована на понятті відстані Хеммінга між двома двійковими послідовностями однакової довжини. Застосовна до комбінують генераторам.

Для виявлення впливу j-го лінійного регістра зсуву (з вихідною послідовністю {x (j)} на гаму шифру {g} моделюється частина генератора як двійковий симетричний канал (ДСК). Алгоритм атаки складається з двох етапів (іноді звані фазами):

  1. обчислення кореляційної ймовірності ~ P_j = P (g = {x ^ {(j)}}) виходячи з комбинирующей функції ~ F і другого етапу.
  2. перебір початкових заповнень регістра. На цьому етапі визначається наявність кореляції даного фрагмента гами ~ G з відповідним фрагментом з ~ X_d ^ {(j)} , Шляхом обчислення функції крос-кореляції ~ C_ {{x ^ {j}, {g}}} (d) = \ frac {1} {n} * \ sum_ {i = 1} ^ n (-1) ^ {g_i} * (-1) ^ {x_ {i + d} ^ {(j)}} і порівняння цього значення з деяким числом ~ T .

У разі успіху при порівнянні, фаза називається вірною і відбувається перехід до наступного регістру ~ J +1 . Інакше, фаза називається невірною і переходять до ~ D = d +1, d = 1,2, \ dots, 2 ^ {L_j} . Вихідними значеннями цього алгоритму є стани ~ {X_0 ^ j} , Що вносять інформацію в гаму.

Тепер трохи про підбір порогового значення ~ T і необхідного для успішного криптоаналізу кількість біт гами ~ N : Задаємо потрібні нам ймовірності "помилкової тривоги" ~ P_f = P (C_ {{x ^ {j}, {g}}} (d) \ ge T | WrongPhase) і пропуску істинного початкового заповнення ~ P_m = P (C_ {{x ^ {j}, {g}}} (d) <T | RightPhase) .

Наприклад, вибрали ~ P_m = 0.01, P_f = 2 ^ {-L} , Де ~ L - Довжина регістра. А потім з цих умов знаходимо ~ T і ~ N .

Атаки, засновані на низько-вагових перевірках парності

Прикладом цього підкласу атак може служити швидка кореляційна атака Майера і Штаффельбаха. Застосовна вона як до фільтр-генераторів, так і комбінують генераторам і є базовою для всіх інших швидких кореляційних атак даного типу. Ідея атаки грунтується на використанні рівнянь перевірки парності для полінома зворотного зв'язку лінійного регістра.

Швидкі кореляційні атаки

Під швидкими кореляційними атаками маються на увазі атаки, обчислювальна складність яких значно менше обчислювальної складності силових атак.
Цей вид атак зводить проблему декодування в двійковому симетричному каналі до проблеми криптоаналізу і моделюється як декодування випадкового ~ (N, l) лінійного коду. Аналогічно базовим кореляційним атакам, цей підклас використовує поняття відстані Хеммінга.


8.3.2. Компроміс "час-пам'ять"

Мета даної атаки - відновлення вихідного стану регістра зсуву (знаходження ключа), використовуючи відому схема пристрою та фрагмент шифрувальної послідовності. Складність атаки залежить від розміру шифру і довжини перехопленої гами.

Складається з двох етапів:

  1. побудова великого словника, в якому записані всілякі пари "стан-вихід";
  2. припущення про початковий заповненні регістра зсуву, генерація виходу, перегляд перехопленої вихідний послідовності і пошук відповідності зі згенерованим виходом. Якщо відбулося збіг, то дане гадане заповнення з великою ймовірністю є початковим.

Прикладами цього класу атак є атака Стіва Беббідж і атака Бірюкова-Шаміра.


8.3.3. "Передбачається і визначай"

Атака грунтується на припущенні, що криптоаналітика відомі гамма, поліном зворотного зв'язку, кількість зрушень регістра між виходами схеми і фільтруюча функція. Складається з трьох етапів:

  1. припущення про заповнення деяких осередків регістра;
  2. визначення повного заповнення регістру на підставі припущення про знання криптоаналітика;
  3. генерація вихідний послідовності; якщо вона збігається з гамою, то припущення на першому етапі було вірно; якщо не збігається, то повертаємося до етапу 1.

Складність алгоритму залежить від пристрою генератора і від кількості припущень.


Література

  • Рябко Б.Я., Фіона А. Н. Криптографічні методи захисту інформації. - Москва. - Вид-во Горяч.Лінія-Телеком, 2005. - ISBN 5-93517-265-8
  • Bruce Schneier Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth). - John Wiley & Sons, Inc. - Вид-во іноземної літератури, 1996. - ISBN 0471128457
  • A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography. - CRC Press, Inc. - 1997.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Шифр
A8 (шифр)
A3 (шифр)
Шифр Плейфера
Шифр Хілла
Шифр Вернама
Книжковий шифр
Шифр Бекона
Шифр підстановки
© Усі права захищені
написати до нас