О вероятности вскрытия потоковых шифров методом перекрытия

Пусть имеется обруч или круг, окружность которого — L сантиметров. На этот обруч наклеивается полоска бумаги длиной l₁, сантиметров. После этого обруч поворачивается на случайный угол и на него наклеивается другая полоска бумаги длиной l₂ сантиметров. Определить вероятность наложения Мух полосок бумаги друг на друга более, чем на s сантиметров.
В решении этой, на первый взгляд «детской», задачи содержатся ответы наряд серьезных вопросов, возникающих при создании, взломе и оценке стойкости потоковых шифров.

Определения и постановка задачи

Принцип потокового шифрования заключается в наложении гаммы шифра на открытые данные. Под гаммой шифра понимается последовательность случайных бит {Г_i}, вырабатываемая генератором R(k) по некоторому алгоритму (в данном случае неважно, действительно случайным или псевдослучайным образом работает генератор R(k)). Параметр генератора k называется ключом, он определяет стартовое значение генератора и выбирается случайно из достаточно большого ключевого множества К. Зная алгоритм работы генератора и его начальное состояние (ключ), можно легко вычислить шифровальную гамму.

Если разрядность R(k) составляет n бит, то максимальный период последовательности, порождаемый таким генератором, — 2n-1 бит, после выдачи которых происходит повторение последовательности битов гаммы [ 1 ].

Обозначим через L = 2n-1 длину цикла такой последовательности.

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

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

Дешифрование сообщений методом перекрытий

Опишем вкратце принцип дешифрования информации методом перекрытий.

Пусть имеются две криптограммы (шифртекст 1 и шифртекст 2), зашифрованные на компьютере.

1. Предположим, что в данной криптограмме с первой позиции было зашифровано некоторое Слово 1. Из соотношения шифртекст = открытый текст + гамма, учитывая кодировку ASCII, вычисляем вероятную гамму Г_{вероятн}. Вычисленный отрезок гаммы Г_{вероятн} снимаем с шифртекста 2 с первой позиции и проверяем по словарю получившийся текст — соответствует ли он какомулибо слову или части слова. В случае неуспеха снимаем гамму Г_{вероятн} со второй позиции шифртекста 2, затем с третьей и т.д. до конца шифртекста 2.

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

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

4. Если в результате описанного процесса ничего путного не вышло, то есть в результате исполнения п. 1, 2,3 смысловой текст извлечь не удается, значит, данные криптограммы не имеют пересечений. В этом случае можно либо прекратить криптоанализ, либо выбрать следующую пару криптограмм (шифртекстов). Для п криптограмм количество возможных парных выборок выражается «числом сочетаний»; В случае появления на каком-либо этапе криптоанализа смыслового текста можно продолжить описанным выше образом криптоанализ оставшейся части текста. Обычно знание расшифрованных слов помогает предположить следующее подходящее по смыслу слово, а также подобрать слова, часть слова и пробел, фразу или группу слов, входящих в нерасшифрованную часть текста. Можно также попробовать проанализировать отрезок получившейся гаммы Г_{вероятн} на предмет выяснения алгоритма работы генератора R(k) — аналитическим путем определить закон образования псевдослучайных бит и таким образом расшифровать оставшуюся часть сообщения.

Вероятность

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

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

В русском языке средняя длина одного слова составляет 7-8 знаков, затем обычно следует один пробел. Таким образом, s ~ 8 или 9 бит. Очевидно, что установление значения этого параметра требует специального лингвистического исследования для каждого языка, на котором ведется шифрованная переписка.

В коде ASCII один знак сообщения кодируется 8 битами, следовательно, допустимое значение перекрытия двух текстов, зашифрованных на компьютере, составляет 64-72 бита. В коде МТК-2 знак сообщения кодируется пятью битами, поэтому допустимое значение перекрытия для телеграфных сообщений составит 40-45 бит. Можно даже немного увеличить это значение в первом случае на 7, а во втором на 4 бита, чтобы последний символ был неполный.

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

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

С учетом изложенного, искомая вероятность должна рассчитываться по следующей формуле: Рассчитать примерное количество сообщений, зашифрованных за «время жизни» шифра, можно следующим образом. Пусть предполагается произвести N экземпляров шифровальных средств, «срок жизни» которых — М лет. Тогда, если обозначить срок действия сеансового ключа (в секундах) Т_k, за время существования аппаратуры на сеансовых ключах будет сгенерировано m = N*M*(C₀/T_k) кусочков гаммы, где С₀=31 558 153 — количество секунд в году. Параметр m обратно пропорционален сроку действия ключа. Длина сеансовой гаммы l тоже зависит от Т_k. Если обозначить через V скорость генерации гаммы шифраппаратурой, то l = V_a*T_k

Таким образом, формулу (2) можно переписать в следующем виде: Из выражения (3) можно вывести формулу срока действия сеансового ключа T_k если задать остальные параметры криптосистемы (Р, N, M, L, s, V_a, р). В частности, для этого необходимо задать численное значение вероятности Р, гарантирующее, что стойкость потоковых шифров превышает возможности противника по их взлому.

В данном случае возможны два подхода:

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

Рекомендации

Формула (2) позволяет осуществить анализ параметров шифровального алгоритма L, l (Т_k, V_a ), s, m (N, М, Т_k), р, от которых зависит стойкость потокового шифра, и дать рекомендации по повышению стойкости шифровальных систем данного типа.

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

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

Увеличить L. Поскольку L = 2n, то для увеличения L необходимо увеличить разрядность генератора R(k), что аналогично замене шифра.

Для увеличения криптографической стойкости шифра можно, например, использовать комбинацию нескольких различных генераторов (R = R₁+R₂+R₃+...) с различными периодами. В этом случае общая длина периода равна произведению длин периодов отдельных генераторов. Для затруднения работы криптоаналитика не мешает придумать и более сложную комбинацию разных генераторов.

Поскольку обычно Т_k составляет сутки, неделю, месяц, а скорость аппаратуры фиксирована, то из соотношения L/(l-2s) можно определить минимальное значение L, что даст минимальное значение разрядности R(k). Практически это соотношение для увеличения стойкости шифра предписывает увеличивать L при прочих равных условиях.

Уменьшить l. Поскольку l = Т_k*V_a , то уменьшение l означает уменьшение срока действия сеансового ключа или уменьшение скорости выдачи гаммы в канал связи. Однако уменьшение срока действия сеансового ключа приводит к увеличению количества сеансов связи m, что приводит к увеличению вероятности перекрытий. Таким образом, пользоваться этим параметром бесполезно.

Уменьшить m. Поскольку m = N*M*(C₀/T_k), это означает уменьшить количество аппаратов, реализующих данный шифр (N), или уменьшить срок жизни данного шифровального средства (М).

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

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

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

Литература

1.Жельников В. Криптография от папируса до компьютера.
2.Кузьминов Т. В. Криптографические методы защиты информации. Новосибирск. Институт систем информатики СО РАН, 1998.
3. Гнеденко Б. В. Основы теории вероятностей. М., 1989.
4.Баричев С. Основы криптографии.
5.Сапегин, Вегнер. Защита программного обеспечения персональных ЭВМ.

Статья опубликована на сайте: 01.08.2000