Петров А.А. Комп без-ть

Рис. 19

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

Таблица 1.2. Начальная перестановка

В случае использования начальной перестановки после завершения 16 раундов к полученному блоку применяется обратная перестановка.

Работа алгоритма заключается в следующем:

1.Входной блок разбивается на две части по 32 бита в каждой (Ц - ле­ вая половина, К| - правая половина).

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

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

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

Таким образом, в регистре оказывается следующая последовательность:

и- ъ-1

К.)

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

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

Таблица 1.3. Завершающая перестановка

санного в два 28-битных циклических регистра сдвига, которые перемеща­ ют содержимое в каждом такте на количество битов, зависящее от номера раунда (табл. 1.5).

Таблица 1.5. Таблица зависимости количества сдвигаемых битов от номера раунда

Результирующая ключевая последовательность получается путем вы­

борки 48 бит из содержимого регистров в соответствии с подстановкой

(табл. 1 .6 ).

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

Выход 3-боксов поступает на Р-блок, где происходит перестановка (табл. 1 .8 ).

Таблица 1.8. Перестановка в Р-блоке

Расшифрование в алгоритме БЕЗ происходит аналогично зашифрова­ нию с той только разницей, что выборка ключевой последовательности в раундах расшифрования будет обратная, то есть К 16, К^.-.К^ если в про­ цессе зашифрования выборку ключевой последовательности обозначать К ь К 2...К15, К 16.

Стойкость 0Е8

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

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

•наличие слабых ключей, вызванное тем, что при генерации ключевой последовательности используются два регистра сдвига, которые ра­ ботают независимо друг от друга. Примером слабого ключа может служить 1Р1Р1Р1Р 0Е0Е0Е0Е (с учетом битов контроля четности),

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

одного бита);

• небольшая длина ключа 56 бит (и ли 64 бита с контролем четности). На современном уровне развития микропроцессорных средств данная длина ключа не может обеспечивать должной защиты для некоторых типов информации (табл. 1.1 и 1.10). Применение тройного БЕЗ (Тпр1е БЕЗ, схема его реализации приведена на рис. 1.12) не дает ощ у­ тимого результата, хотя в новой версии используются три разных клю ­ ча (К !, К 2, К3). Дело в том, что в конечном итоге работа с тремя ключа­ ми эквивалентна зашифрованию на другом ключе К 4, то есть для любых К ь К 2, К 3 найдется такой ключ К4, что:

Е Кз(Б К 2(Е К 1(Р ) ) ) - ЕК 4(Р );

•избыточность ключа, обусловленная контролем четности для каждого в отдельности байта ключа. Бихам и Шамир предложили достаточно эффективную атаку на реализацию БЕЗ в смарт-картах или банковс­ ких криптографических модулях, использующих ЕЕРКОМ -память для хранения ключей. Эта методика наглядно высветила еще одну очевидную слабость БЕЗ, заключающуюся в наличии контроля четно­ сти каждого байта ключа, в силу которой и создается его избыточность, что позволяет восстанавливать ключи, хранящиеся в памяти устрой­ ства, при сбое в данном участке памяти;

•использование статических подстановок в 3-боксах, что, несмотря на большое количество раундов, позволяет криптоаналитикам проводить атаки на этот алгоритм.

Рис. 1.12. Схема Тпр1е йЕ5

Здесь следует заметить, что на сегодняшний день автору неизвестны ус­ пешные атаки на 16-раундовый БЕЗ, проведенные на основании последне­ го в списке факта, однако успешные атаки на неполнораундовые схемы БЕЗ имели место. Так, Мартин Хэллман предложил атаку на 8 -раундовый БЕЗ. Она позволяет восстанавливать на рабочей станции 51ЛЧ-4 10 бит ключа за десять секунд. В случае выбора 512 открытых текстов вероят­ ность успеха составляет 80%, а при выборе 768 открытых текстов - 95%. Восстановив 10 бит ключа, можно воспользоваться алгоритмами перебора всех оставшихся вариантов, сводя таким образом задачу нахождения 56-битного ключа к поиску 46-битного ключа.

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

1.2.3. Алгоритм блочного шифрования

Отечественным аналогом БЕЗ является алгоритм блочного шифрования, специфицированный в ГОСТ 28147-89. Разработчики данного алгоритма сумели органично соединить в нем две важные, но трудносочетающиеся друг с другом характеристики:

Для всех четырех режимов применяется одно общее преобразование, которое можно записать в следующем виде:

П = Км

где Ь и К - соответственно левая и правая часть 64-битного блока.

Это преобразование характерно для всех раундов (всего их 32), кроме последнего. Для него преобразование будет иметь вид:

П = Ьи 0 ДКИ, ко

К; = Ки 1 = 32

Для каждого раунда функция 1 остается неизменной. Перед началом преобразования блок открытого текста разбивается на две 32-битные по­ ловины Ь и К, которые помещаются в два 32-разрядных регистра иЫ 2 соответственно. Также перед началом зашифрования 256-битный ключ, разбитый на восемь частей по 32 бита каждая (К 0...К7), помещается в клю­ чевое запоминающееся устройство (К З У ). Далее содержимое регистра И) суммируется по модулю 2 32 с очередным заполнением устройства, а клю ­ чевые последовательности выбираются из К З У в следующем порядке:

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

7, 10, 13, 1, 0, 8 , 9, 15, 14, 4, 6 , 12, 4, И , 2, 5, 3

Числовое представление битового входа однозначно определяет после­ довательный номер числа в подстановке и битовое представление соответ­ ствующего числа; таким же оно будет и на выходе 3-бокса. Для каждого 3-бокса задается своя подстановка, которая является долговременным сек­ ретным ключом. Генерация подстановок в 3-боксах является сложной ма­ тематической задачей, от решения которой как раз и зависит стойкость этого алгоритма. Подобный прием служит также для развязывания раз­ личных сетей передачи данных - очевидно, что расшифрование будет успешным, если принимающая и передающая стороны используют оди­ наковые подстановки. Таким образом, в сети передачи данных абоненты с одинаковыми подстановками имеют возможность обмениваться за­ шифрованной информацией, что позволяет создавать выделенные группы пользователей с засекреченной связью.

После 3-боксов последовательность поступает в циклический регистр сдвига, который осуществляет смещение на 1 1 шагов влево. Использование

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

Далее происходит поразрядное суммирование по модулю 2 содержимо­ го регистра циклического сдвига с содержимым регистра N 2. Результат суммирования записывается в регистр N 4, а содержимое регистра N 2 при­ нимает предыдущее значение N 1.

Все эти операции составляют один раунд преобразования (реализация функции Г) очередного блока открытого текста. Специфика различных типов применения ГО С Т вносит свои дополнения в раунды зашифрова­ ния и соответственно расшифрования.

Режим простой замены

В данном режиме блок открытого текста шифруется описанным выше ме­ тодом без каких-либо добавлений. Результат зашифрования после прохож­ дения 32 раундов находится в регистрах К, и N 2.

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

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

Режим гаммирования

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

Выработка гаммы происходит следующим образом:

1. В накопители N 1 и N 2 записывается синхропосылка 8 длиной 64 бита.

2 . 8 шифруется в режиме простой замены, и результат зашифрования из регистров Ы! и N 2 записывается в регистры N 3 и N 4 соответственно.

ветственно, и их содержимое образует первый 64-битный блок гаммы.

5.Алгоритм генерации остальных блоков гаммы заключается в сумми­ ровании содержимого регистров N 3 и N 4 с содержимым регистров N 5

и N 6 соответственно, с сохранением результата в N3 и N4, переписыва­

нием содержимого N 3 и N 4 в N 1 и N 2 соответственно и последующем шифровании в режиме простой замены содержимого регистров ^ и N 2.

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

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

Режим гаммирования с обратной связью

Шифрование в этом режиме производится путем суммирования по моду­ лю 2 блоков открытого текста с блоками выработанной гаммы. Синхро­ посылка 3 зашифровывается в режиме простой замены, и полученный результат из регистров N 1 и N 2 является первым блоком гаммы, которая суммируется по модулю 2 с первым блоком открытого текста. Блок зашиф­ рованного текста одновременно является заполнением регистров и N 2

для шифрования следующего блока открытого текста.

Режим выработки имитовставки

Данный режим предназначен для защиты от навязывания ложных сооб­ щений во время передачи информации по открытым каналам. Защита обеспечивается путем генерации имитовставки - отрезка информации фиксированной длины, полученного по определенному правилу из откры­ тых данных и ключа и добавленного к зашифрованным данным для обес­ печения имитозащиты. Его длина Б выбирается в зависимости от требова­ ний, выдвигаемых к системам имитозащиты в конкретных сетях передачи данных, при этом необходимо учитывать, что вероятность навязывания ложных сообщений обычно принимается равной 2~Ч