Внебрачная статья. Криптография. Часть 3. Конец Начала.

Добрый день/вечер/ночь. Вы этого не просили и даже Мынка нас не уговаривал, но сегодня мы тут. Сегодня будет весело и интересно, но не факт, это же Мы. Советуем вам перед прочтением ознакомится с прошлыми статьями. Ну и желательно запостись Мынками, но это не обязательно. Ну что, готовы посмотреть в современность?

Стандарт шифрования DES

Одним из самых распространенных алгоритмов шифрования конца прошлого века является DES - алгоритм (Data Encryption Standard), разработанный в 1977 г. и рекомендованный Национальным бюро стандартов США совместно с АНБ в качестве основного средства криптографической защиты информации как в государственных, так и в коммерческих структурах. Однако в 1988 г. АНБ рекомендовало использовать DES только в системах электронного перевода. В последнее время, с учетом выявленных слабостей DES, появляются изменения в начальном варианте стандарта и новые алгоритмы, использующие в качестве основы DES - NewDes, TripleDES и др.

Появление новых алгоритмов было обусловлено развитием за многолетнее существование данного алгоритма большого количества атак на DES. Кроме того, бурное развитие производительности и быстродействия средств вычислительной и микропроцессорной техники привело к тому, что 56 битного ключа используемого в оригинальном варианте DES стало недостаточно, чтобы противостоять атаке методом грубой силы(ЕЕЕ Brute force). Тем не менее, DES и на сегодняшний день он остается одним из самых применяемых алгоритмов блочного шифрования в коммерческой сфере и в системах электронных расчетов.

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

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

В некоторых реализациях DES блоки открытого сообщения перед тем как будут загружены в регистр сдвига длиной равной 2 ячейки и размером ячейки 32 бита, проходят процедуру начальной перестановки, которая применяется для того, чтобы провести начальное рассеивание статистической структуры сообщения.

DES предусматривает 4 режима работы:

• ECB (Electronic Codebook) электронный шифрблокнот;
• CBC (Cipher Block Chaining) цепочка блоков;
• CFB (Cipher Feedback) обратная связь по шифртексту;
• OFB (Output Feedback) обратная связь по выходу.

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

Среди основных недостатков DES существенно снижающих уровень безопасности при использовании данного алгоритма можно выделить следующие:

• наличие слабых ключей, вызванное тем, что при генерации ключевой последовательности используются 2 регистра сдвига, которые работают независимо друг от друга. Примером, слабого ключа может служить 1F1F1F1F 0E0E0E0E (с учетом битов контроля четности). В данном случае результатом генерации будут ключевые последовательности одинаковые с исходным ключом во всех 16 раундах. Существуют также разновидности слабых ключей, которые дают при генерации всего лишь 2 (4) ключевые последовательности. Так же для неполнораундовых схем DES характерно наличие связанных ключей, например, ключ полученный из другого ключа посредством инверсии одного бита;
• небольшая длина ключа 56 бит (или 64 бита с контролем четности). При современном уровне развития микропроцессорной средств данная длина ключа не может обеспечивать должный уровень защиты для некоторых типов информации. Применение тройного DES (TripleDES) не дают ощутимого результата хотя и используются 3 разных ключа (К1, К2, К3). В конечном итоге эквивалентно зашифрованию на другом ключе К4, т.е. для любых К1, К2, К3 найдется ключ К4 такой, что: ЕК3(EК2(ЕК1(Р)))=ЕК4(Р);
• наличие избыточности ключа, обусловленное контролем четности для каждого байта ключа отдельно. Бихам и Шамир предложили достаточно эффективную атаку на реализацию DES в смарт-картах или банковских криптографических модулях, использующих EEPROM память для хранения ключей. Данная атака демонстрирует очередную слабость DES, состоящую в наличие контроля четности каждого байта ключа, который создает избыточность ключа и позволяет восстанавливать ключи, хранящиеся в памяти устройства, в случае сбоя в данном участке памяти;
• использование статических подстановок в S-боксах, что несмотря на большое количество раундов позволяет криптоаналитикам проводит атаки, учитывающие данный факт. Хотя на сегодняшний день автору не известно успешных атак на 16 раундовый DES, основанных на данном факте. Но успешные атаки на неполнораундовые схемы DES имеют место быть. Так Мартин Хэллман предложил атаку на 8 раундовый DES. Предложенная атака позволяет успешно восстанавливать 10 бит ключа за 10 сек. на рабочей станции SUN-4 и имеет вероятность успеха 80% в случае выбора 512 открытых текстов и 95% в случае выбора 768 открытых текстов. Восстановив 10 бит ключа можно воспользоваться алгоритмами перебора всех оставшихся вариантов, и свести таким образом задачу нахождения 56- битного ключа к нахождения 46-битного ключа

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

Стандарт шифрования ГОСТ-28147-89

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

Более эффективным является отечественный стандарт шифрования данных ГОСТ-28147-89(О ну классика, у них на западе всё плохо, а у нас всё хорошо. Слышали уже).

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

Введем ассоциативную операцию конкатенации, используя для нее мультипликативную запись. Кроме того, будем использовать следующие операции сложения:

Алгоритм криптографического преобразования предусматривает несколько режимов работы. Во всех режимах используется ключ W длиной 256 бит, представляемый в виде восьми 32-разрядных чисел x(i):

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

Самый простой из возможных режимов - замена.

Пусть открытые блоки разбиты на блоки по 64 бит в каждом, которые обозначим как T(j).

Очередная последовательность бит T(j) разделяется на две последовательности B и A по 32 бита (правый и левый блоки). Далее выполняется итеративный процесс шифрования описываемый следующими формулами, вид который зависит от i:

• Для i=1, 2, ..., 24, j=(i-1) mod 8;

• Для i=25, 26, ..., 31, j=32-i
  

• Для i=32
  

Здесь i обозначает номер итерации. Функция f – функция шифрования, включающая две операции над 32-разрядным аргументом.

Первая операция является подстановкой K. Блок подстановки К состоит из 8 узлов замены К(1)...К(8) с памятью 64 бита каждый. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4-разрядных вектора, каждый из который преобразуется в 4-разрядный вектор соответствующим узлом замены, представляющим из себя таблицу из 16 целых чисел в диапазоне 0...15. Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем 4-разрядные векторы последовательно объединяются в 32-разрядный выходной.

Вторая операция - циклический сдвиг влево 32-разрядного вектора, полученного в результате подстановки К. 64-разрядный блок зашифрованных данных Т представляется в виде:

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

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

Другой режим шифрования называется режимом гаммирования.

Открытые данные, разбитые на 64-разрядные блоки T(i) (i=1,2,...,m), где m определяется объемом шифруемых данных, зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 с гаммой шифра

, которая вырабатывается блоками по 64 бит, т.е.

Уравнение шифрования данных в режиме гаммирования может быть представлено в следующем виде:

В этом уравнении Ш(i) обозначает 64-разрядный блок зашифрованного текста, А - функцию шифрования в режиме простой замены, аргументами этой функции являются два 32-разрядных числа. С1 и С2 - константы, заданные в ГОСТ 28147-89.

Величины Y(i) и Z(i) определяются итерационно по мере формирования гаммы следующим образом:

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

Режим гаммирования с обратной связью очень похож на режим гаммирования. Как и в режиме гаммирования открытые данные, разбитые на 64-разрядные блоки T(i), зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра

, которая вырабатывается блоками по 64 бит:

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

Следует отметить, что в отличие от DES, у ГОСТ 28147-89 блок подстановки можно произвольно изменять, то есть он является дополнительным 512-битовым ключом.

В ГОСТ 28147-89 определяется процесс выработки имитовставки, который единообразен для всех режимов шифрования. Имитовставка - это блок из р бит

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

Для получения имитовставки открытые данные представляются также в виде блоков по 64 бит. Первый блок открытых данных Т(1) подвергается преобразованию, соответствующему первым 16 циклам алгоритма режима простой замены. Причем в качестве ключа используется тот же ключ, что и для шифрования данных. Полученное 64-разрядно число суммируется с открытым блоком Т(2) и сумма вновь подвергается 16 циклам шифрования для режима простой замены. Данная процедура повторятся для всех m блоков сообщения. Из полученного 64-разрядного числа выбирается отрезок

длиной р бит.

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

Блочные шифры

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

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

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

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

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

• Режим простой замены или режим электронной кодовой книги (Electronic Codebook Mode - ECB)
• Режим гаммирования
• Режим гаммирования с самовостановлением или шифрование с обратной связью (Cipher-Feedback mode - CFB)
• Режим гаммирования с обратной связью по выходу (Output-Feedback mode - OFB)
• Режим шифрования со сцеплением блоков (Cipher Block Chaining mode - CBC)

Блочные шифры бывают двух основных видов:

• шифры перестановки (transposition, permutation, P-блоки);
• шифры замены (подстановки, substitution, S-блоки).

Шифры перестановок и шифры замены были рассмотрены в прошлых статьях.

Блочное шифрование можно осуществлять двояко:

1. Без обратной связи (ОС). Несколько битов (блок) исходного текста шифруются одновременно, и каждый бит исходного текста влияет на каждый бит шифртекста. Однако взаимного влияния блоков нет, то есть два одинаковых блока исходного текста будут представлены одинаковым шифртекстом. Поэтому подобные алгоритмы можно использовать только для шифрования случайной последовательности битов (например, ключей). Примерами являются DES в режиме ECB и ГОСТ 28147-89 в режиме простой замены.
2. С обратной связью. Обычно ОС организуется так: предыдущий шифрованный блок складывается по модулю 2 с текущим блоком. В качестве первого блока в цепи ОС используется инициализирующее значение. Ошибка в одном бите влияет на два блока - ошибочный и следующий за ним. Пример - DES в режиме CBC.

Генератор ПСЧ(Кто не помнит прошлые статьи это псевдо случайные числа) может применяться и при блочном шифровании:

1. Поблочное шифрование потока данных. Шифрование последовательных блоков (подстановки и перестановки) зависит от генератора ПСЧ, управляемого ключом.
2. Поблочное шифрование потока данных с ОС. Генератор ПСЧ управляется шифрованным или исходным текстом или обоими вместе.

Блочные алгоритмы могут использоваться и для выработки гаммы. В этом случае гамма вырабатывается блоками и поблочно складывается по модулю 2 с исходным текстом. В качестве примера можно назвать BCrypt, DES в режимах CFB и OFB, ГОСТ 28147-89 в режимах гаммирования и гаммирования c обратной связью.

Вывод

На этом мы заканчиваем первую часть(Так. Стоп это же третья часть?) где мы вам рассказали о симметрических криптосистемах. И нас интересует вопрос, хотите ли вы узнать о других симметрических криптосистемах или же мы расскажем вам о криптосистемах с открытым ключом. Нам было интересно вам это рассказывать(Мынка нам так и не заплатил) и надеемся что вы ответите на наш вопрос чтобы мы продолжили это делать.

Если у вас появились вопросы мы с радостью ответим на них в комментариях или сообщениях группы.