Математические основы криптологии и криптографические методы и средс

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

Некоторые системы хранят скомпрометированные ключи в ра­ бочих списках (hotlists) - атака на такие списки может быть очень плодотворной. Другие системы могут быть взломаны посредством replay-атак: повторным использованием старых сообщений или их частей с целью обмана различных механизмов.

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

Меры по защите:

1)все временные значения должны уничтожаться;

2)в процессе работы их желательно хранить не на постоянно запоминающих носителях, а в оперативной памяти;

3)ключи шифрования и пароли должны проходить проверку на сложность;

4)не допускать их повторение;

5)хранить ключи и пароли в шифрованном виде в разных спи­ сках, которые также шифруются (с учетом пункта 4).

2.1.3. Криптостойкость алгоритмов шифрования

Криптостойкость является количественной характеристикой алгоритмов шифрования - для вскрытия конкретного алгоритма шифрования при определенных условиях (в том числе определенным криптоаналитическим методом) требуется определенное число ре­ сурсов. Ресурсами в данном случае являются следующие величины:

1)количество информации, необходимое для осуществления атаки, - сколько необходимо пар известных или выбранных текстов-

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

3)память, необходимая для хранения используемой при ата^е информации. Является также немаловажной характеристикой, П о ­ скольку многие атаки могут предъявлять весьма существенные тре­ бования к памяти.

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

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

Существует немало алгоритмов шифрования, которые являются криптографически стойкими. В работе Шеннона понятие стойкого ал­ горитма определено так: «Алгоритм является криптографически стой­ ким, если не существует каких-либо методов его вскрытия, кроме ме­ тода «грубой силы». Кроме того, размер ключа алгоритма является достаточно большим для того, чтобы метод грубой силы стал невоз­ можным при текущем уровне развития вычислительной техники».

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

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

вкаждом из которых повторяются одни и те же (или схожие) преоб­ разования над шифруемыми данными. Для определения запаса крип­

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

Другой вариант определения запаса криптостойкости - анализ модификаций исследуемого алгоритма с незначительными измене­ ниями структуры раунда. Один из наиболее ярких примеров ~ вскры­ тие алгоритма Skipjack - 3XOR при наличии всего 29 выбранных от­ крытых текстов и соответствующих им шифртекстов выполнением всего около миллиона тестовых операций шифрования. По совре­ менным меркам, благодаря данной атаке, Skipjack- 3XOR можно считать весьма слабым алгоритмом, а ведь он отличается от извест­ ного и достаточно распространенного алгоритма шифрования Skipjack всего лишь тем, что из структуры последнего удалены всего 3 конкретных операции XOR (побитовая логическая операция ИС­ КЛЮЧАЮЩЕЕ ИЛИ) из предусмотренных алгоритмом Skipjack 320 подобных операций. Соответственно, были (однако недоказанные) предположения о недостаточном запасе криптостойкости у алгоритма Skipjack. Впрочем, в случае анализа алгоритмов с подобными модифи­ кациями запас криптостойкости можно рассматривать только как ка­ чественную характеристику, имеющую достаточно косвенное отно­ шение к исследуемому алгоритму шифрования.

2.1.4. Типы криптостойких систем шифрования

Абсолютно стойкие системы. Доказательство существования абсолютно стойких алгоритмов шифрования было выполнено К. Шенноном и опубликовано в работе «Теория связи в секретных системах». Там же определены требования к такого рода системам:

♦ключ генерируется для каждого сообщения (каждый ключ используется один раз);

♦ключ статистически надежен (т.е. вероятности появления ка­ ждого из возможных символов равны);

♦длина ключа равна или больше длины сообщения;

♦исходный (открытый) текст обладает некоторой избыточностью

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

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

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

Достаточно стойкие системы

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

♦вычислительная сложность полного перебора;

♦известные на данный момент слабости (уязвимости) и их

влияние на вычислительную сложность.

В каждом конкретном случае могут существовать дополнитель­ ные критерии оценки стойкости.

Оценка криптостойкости систем шифрования Начальная оценка. Поскольку атака методом грубой силы (пол­

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

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

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

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

Еще один способ сокрытия информации - стеганография. Ино­ гда бывает проще скрыть сам факт наличия секретной информации, чем надеяться на стойкость криптоалгоритма. Используемые методы зависят от технических возможностей и фантазии автора. Примером стеганографии могут служить «случайные» точки на изображении, «шум» в звуковой информации и т.д., в которые вкрапляется важная и секретная информация. Можно комбинировать стеганографию и шифрование.

2.1.5. Симметрические системы шифрования

Приведем наиболее известные симметрические алгоритмы шифрования.

Lucifer. Первый (опубликованный в открытой печати) блочный алгоритм. Предтеча DES. Авторы: Horst Feisstel, Walter Tuchman (IBM). Тип - сеть Файстеля.

Параметры:

-размер блока 128 бит; -размер ключа 128 бит;

-число раундов 16.

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

2.1.6. Стандарт DES

Американский стандарт криптографического закрытия данных DES (.Data Encryption Standard), принятый в 1978 году, является ти­ пичным представителем семейства блочных шифров и одним из наи­ более распространенных криптографических стандартов на шифрова­ ние данных, применяемых в США. Этот шифр допускает эффектив­ ную аппаратную и программную реализацию, причем возможно дос­ тижение скоростей шифрования до нескольких мегабайт в секунду.

Первоначально метод, лежащий в основе .данного стандарта, был разработан фирмой IBM для своих целей. Он был проверен Агентством национальной безопасности США, которое не обнару­ жило в нем статистических или математических изъянов.

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

DES имеет блоки по 64 бит и основан на 16-кратной переста­ новке данных, также для шифрования использует ключ в 56 бит. Су­ ществует несколько режимов DES: Electronic Code Book (ЕСВ) и Ci­ ph er Block Chaining (CBC).

56 бит-это 8 семибитовых ASCII символов, т.е. пароль не мо­ жет быть больше, чем 8 букв. Если вдобавок использовать только буквы и цифры, то количество возможных вариантов будет сущест­ венно меньше максимально возможных 256

Сначала над 64-битным блоком данных выполняется начальная перест ановка согласно фиксированной таблице. Все определенные в стандарте DES таблицы не приведены здесь из-за их громоздкости.

После начальной перестановки блок данных делится на 2 суб­ блока по 32 бита (начальные значения которых обозначаются А0 и Во), над которыми выполняется 16 раундов преобразований:

A*^ &i-l9

© f[ B i_i, А/),

где Ai и Bj - соответственно значения левого и правого субблока по­ сле выполнения i-го раунда (i = 1... 16), А/ - фрагмент расширенного ключа для /-го раунда (расширение ключа будет описано ниже), © - побитовая логическая операция ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR).

Структура алгоритма приведена на рис. 34.

Функция Д6, к) предусматривает выполнение следующих дейст­

вий:

1.Над 32-битным входным значением Ъ выполняется расши­ ряющая Перестановка (ЕР), которая дает 48-битное значение be.

2.be складывается с ключом раунда А/ операцией XOR; обозна­ чим результат этой операции как Ък.

3.Ьк разбивается на 8 фрагментов по 6 бит, каждый из которых

прогоняется через соответствующую таблицу замен (S\ S%). Каж­ дая таблица содержит по 4 строки, содержащих по 16 значений от О до 15. Входное значение интерпретируется следующим образом: два крайних бита формируют номер строки (от 0 до 3), из которой выби­ рается число, расположенное в столбце, номер которого соответству­

После 16 раундов преобразований (последний раунд несколько от­ личается от предыдущих - в нем субблоки не меняются местами) вы­ полняется еще одна табличная перестановка, называемая финальной.

Схема процедуры расширения ключа показана на рис. 35. Ее за­ дача-формирование подключей для 16 раундов, которое выполня­ ется следующим образом.

*СР - сжимающая перестановка

Рис. 35. Процедура расширения ключа в алгоритме DES

Прежде всего, из 64-битного ключа выбираются (в определен­ ном порядке, т.е. с перестановкой относительно их исходного распо­ ложения) 56 значащих бит. 56-битный ключ делится на два 28-бит­ ных фрагмента, которые обозначаются как С и D.

Затем выполняется 16 раундов процедуры расширения ключа. Каждый раунд дает один из требуемых фрагментов К; и состоит из следующих преобразований:

1. Текущие значения С и D циклически сдвигаются влево на пе­ ременное число бит п, которое зависит от номера текущего раунда.

2. С и D объединяются обратно в 56-битное значение, к которо­ му применяется сжимающая перестановка, результатом которой яв­ ляется 48-битный ключ раунда К-,.

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

Дешифрование шифрованного посредством DES текста осуще­ ствляется с использованием тех же блоков благодаря обратимости преобразования.

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

Однако данный алгоритм, являясь первым опытом стандарта шифрования, имеет ряд недостатков. За время, прошедшее после создания DES, компьютерная техника развилась настолько быстро, что оказалось возможным осуществлять исчерпывающий перебор ключей и тем самым раскрывать шифр. Стоимость этой атаки посто­ янно снижается. В 1998 году была построена машина стоимостью около 100 000 долларов, способная по данной паре «исходный текст, шифрованный текст» восстановить ключ за среднее время в трое су­ ток. Таким образом, DES, при его использовании стандартным обра­ зом, уже стал далеко не оптимальным выбором для удовлетворения требований скрытности данных.

Рассмотрим другие варианты современных симметричных ситем шифрования.

BlowFish. Блочный алгоритм, построенный на сбалансиро­ ванной сети Файстеля, 16 итераций простого криптографического преобразования. Длина ключа 40-448 бит, отсюда - сложная фаза инициализации до операций шифрования. Разработан в 1993 году. Автор: Брюс Шнайер (Bruce Schneier).

Параметры:

-размер блока 64 бита;

-размер ключа 32-448 бит;