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

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

генерирует по некоторому закону один бит шифрующей последовательности;

каким-либо обратным преобразованием накладывает на один бит от крытого потока этот шифрующий бит и получает зашифрованный бит.

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

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

NOT (a XOR b) = a XOR (NOT b) = (NOT a) XOR b.

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

p XOR F(gi,g2,gs),

где р - исходный бит (от англ. "plain" - "открытий"), g - шифрующие биты, F

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

с = p XOR g

где с - зашифрованный бит (от англ. "ciphered" - "зашифрованный").

Общая схема шифрования поточным шифром представлена на рис. 5.4 [16].

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

Тремя основными компонентами, над которыми вычисляется функция, порождающая гамму, являются:

ключ;

номер текущего шага шифрования;

ближайшие от текущей позиции биты исходного и/или зашифрованного текста.

Ключ является необходимой частью гаммирующего шифра. Если ключ и схема порождения гаммы не являются тайными, то поточный шифр превращается в обычный преобразователь - кодер - скремблер (от англ. "scramble" - "перемешивать"). Скремблеры широко применяются в системах телекоммуникаций для улучшения статистических характеристик передаваемого сигнала. Частота появления "0" и "1" необходима во многих системах синхронизации - по моменту изменения значения (фронта) сигнала с "0" на "1" или с "1" на "0" принимающая сторона корректирует свои генераторы синхроимпульсов. Часто в отношении поточных шифров по аналогии с подобными кодерами применяется термин "скремблер".

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

Матрица зависимости основных свойств поточных шифров от идеологии их построения представлена в табл. 5.1.

Таблица 5.1. Свойства различных поточных шифров

Гамма зависит от бита исходного или зашифрованного текста Гамма не зависит от бита исходного или зашифрованного текста
Г амма зависит от номера текущего такта шифрования (-) дешифратор теряет синхронизацию при ошибке "вставка/пропуск бита" в канале связи.

(-) дешифратор размножает ошибки "искаженного бита" в канале связи

(+) схема устойчива к атаке по известному исходному тексту

(-) дешифратор теряет синхронизацию при ошибке "вставка/пропуск бита" в канале связи (+) дешифратор не размножает ошибки "искажения бита" в канале связи

(+) схема устойчива к атакам по известному исходному тексту

Гамма не зависит от номера текущего такта шифрования (+) дешифратор не теряет синхронизацию при ошибке "вставка/пропуск бита" в канале связи (-) дешифратор размножает ошибки "искажение бита" в канале связи

(-) схема неустойчива к атаке по известному исходному тексту

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

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

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

} XOR g) XOR (Р2 XOR g) = Р i XOR Р2

полностью избавиться от гаммирующей последовательности. А это уже дает возможность при удачном стечении обстоятельств с помощью специальных методов, включая подбор букв и статистические исследования, получить из (Р i XOR Р2) отдельно Рi и отдельно Р2

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

гамма, порождаемая шифром, должна иметь очень хорошие стохастические характеристики;

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

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

Наиболее простыми схемами, которые используются в качестве базовых при построении других, более устойчивых поточных шифров, являются линейные регистры сдвига - ЛРС (англ. Linear Feedback Shift Registers - LFSR). Их строение очень простое: устройство представляет собой несколько (20-100) ячеек памяти, в каждой из которых может храниться один бит информации. Совокупность бит, которая находится в данный момент в ЛРС, называют его состоянием. Для выработки очередного бита шифрующей последовательности (то есть, гаммы), ЛРС выполняет один цикл преобразований, носящий название такта, по следующему алгоритму:

1. Первый (скажем, крайний справа) бит из последовательности поступает на вход ЛРС - это очередной бит гаммы.

2. Содержимое всех промежуточных ячеек памяти сдвигается на одну позицию вправо.

3. В пустую ячейку памяти, которая появилась в результате сдвига с левого края ЛРС, размещают бит, рассчитываемый как операция XOR над значениями из ячеек ЛРС с заданными номерами.

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

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

Пример работы ЛРС разрядности 3 с установкой ключа 011 показан на рис.

5.6.

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

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

5.7.

Цикл "000" характерен для всех графов вследствие строения ЛРС. На рис. 5.7

а) мы видим, кроме "нулевого" цикла, еще два: 3-х и 4-х состояний. На рис. 5.7

б) цепочка сходится к циклу 3-х этапов и уже никогда оттуда не выходит. И, наконец, на рис. 5.7 в) все возможные состояния, кроме нулевого, объединены в один замкнутый цикл.

Очевидно, что как раз в этом случае, когда все 2N-1 состояний системы (где N

- разрядность ЛРС), кроме нулевого, образуют единый цикл, период повторения гаммы максимальный, а корреляция между длиной цикла и начальным состоянием регистра (то есть, ключом), которая привела к появлению более слабых ключей, отсутствует [16].

Схемы с выбранными по данному закону обратными связями называют генераторами последовательностей наибольшей длины (ПНД). Существует большое количество публикаций с рекомендациями относительно таблиц номеров ячеек, от которых необходимо выбрать отводы обратной связи для получения ПНД. В целом проблема порождения последовательностей наибольшей длины на ЛРС тесно связана с математическим понятием неприводимых и примитивных полиномов над полем Галуа GF(2). [16]

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

Более того, восстановление битов гаммы возможно и в обратном направлении вследствие строения ЛРС. Это позволяет злоумышленнику записывать весь передаваемый шифротекст и одновременно выполнять попытки подобрать соответствующий ему открытий текст на основе набора высоковероятных для данного контекста фраз или данных. Если в любой момент времени открытий текст длиной N будет успешно подобран, то и весь шифрованный поток, следующий за ним, будет успешно дешифрован. Параллельно (возможно, на другой ЭВМ) весь законспектированный до точки взлома шифротекст будет прочитан в обратном направлении.

Во-вторых, оказалось, что неустойчивыми к атаке на основе открытого текста являются ЛРС с тайной структурой отводов обратной связи. Алгоритм, который предложили Э. Берлекамп и Дж. Месси, позволяет на основе беспрерывной последовательности из 2xN бит построить ЛРС разрядности N, порождающий такую последовательность. Таким образом, если даже злоумышленнику неизвестна структура ЛРС, то путем перебора сначала из начальной позиции известных слов или данных в открытом тексте, а потом - по разрядности регистра сдвига (если она неизвестна) возможно построить ЛРС, который зашифровал этот текст. При этом восстанавливается как структура ЛРС, так и его текущие состояния, что позволяет выполнить последующую дешифровку, как и в случае с известным видом обратной связи ЛРС. Для устранения этих недостатков были созданы нелинейные поточные шифры. [16]

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

Фильтрующие шифры имеют наиболее простую структуру из нелинейных поточных шифров. Их строят на базе одного ЛРС путем создания от его ячеек дополнительных отводов, никак не связанных с отводами обратной связи. Значения, получаемые по этим отводам, уменьшают на основе некоторой нелинейной функции - фильтра (рис. 5.8). Бит - результат этой функции - подают на выход схемы как очередной бит гаммы.

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

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

g = а е (b & с)

Несмотря на то, что такая гамма является сбалансированной (то есть, вероятность появления "О" и "1" в ней совпадают), в нее с недопустимо большой вероятностью проходит поток битов, порожденный первым ЛРС. Действительно, вероятность

Это позволяет при достаточно большом объеме перехваченной информации, чем это было раньше, осуществлять на первый ЛРС все те же атаки, что и на одиночный ЛРС. А получив всю необходимую информацию по первому ЛРС, можно или непосредственно воспользоваться ею для прочтения с "догадкой" открытого текста, или попытаться получить больше информации о втором и третьем ЛРС. [16]

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

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

Динамические шифры строятся также на базе нескольких ЛРС, однако объединяют их не на равных основаниях, а по схеме "начальник-подчиненный". Так, например, в схеме, представленной на рис. 5.12, бит, порождаемый управляющим регистром, определяет, бит какого из подчиненных ЛРС (первого или второго) будет подан на выход всего алгоритма. Бит из регистра, противоположного выбранному, отбрасывается.

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

Классификация шифров | Защита информации в телекоммуникационных системах | Основы блочного шифрования


Защита информации в телекоммуникационных системах



Новости за месяц

  • Июль
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс