Силовая атака на основе распределенных вычислений

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

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

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

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

Развитию подобной технологии способствовал ряд конкурсов, объяв­ленных известными фирмами – разработчиками криптосистем, в частно­сти компанией RSA Data Secur i ty, с призовой суммой до 10 тыс. долла­ров. Разработано специальное программное обеспечение на основе тех­нологии «клиент-сервер». Центральный сервер выполняет регистрацию клиента и выдает интервал ключей для перебора. Секретный ключ счи­тается раскрытым, если результат дешифрования на нем приводит к со­держательному тексту на английском языке.

Шифры с переменной длиной ключа

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

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

- сложность (количество выполняемых опера­ций) алгоритмов шифро­вания Е_k(т) и дешифрования D _k (m) была полино­миальной:

O (| k | ^т), где | k | — длина ключа k в битах, а m >0 — константа,

- в то время как сложность алгоритма, реализующего любую атаку, была бы не меньше сложности полного перебора ключей, т. е. экспоненци­альной — O (a^{½ k ½}), где a>1 — константа.

Пусть время, которое можно потратить на шифрование или дешиф­ро­вание, равно t₁, а время, которое злоумышленник может позволить себе потратить на атаку, равно t₂. При скоро­сти вычислений, равной v опера­ций в единицу времени, получаем следую­щие ограничения на длину ключа:

log_a c₂^-1 v t₂ < | k | <(c₁^-1 v t₁)^1/m.

Здесь с₁ и с₂ – константы, определяющие сложность данного алгоритма.

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

Алгоритм RC2

Криптоалгоритм R C2 представляет собой блочный шифр с ключом переменной длины. Рaзработан Ривестом по заказу компании RSA Data Secur i ty, I nc. Аббревиатура «R C» означает «код Рональда» (R on's Code), или «шифр Ривеста» (Rivest's Ciрher).

Криптоалгоритм разрабатывался как альтернатива криптостандарта DES. R C2 работает с блоками по 64 бита, программная реализация криптоалгоритма приблизительно в два-три раза быстрее, чем DES.

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

Правительство США не запрещает экспортировать аппаратные и прог­раммные реализации криптоалгоритмов R C2 и RC4 (поточный шифр, он будет рассмотрен далее) — при соблюдении ограничения на длину ключа (40 бит). Американские компании за пре­делами США и Канады могут использовать криптоалгоритмы с длиной ключа 65 бит. При шифровании по криптоалгоритму R C2 к секретному ключу методом конкатенации добавляется некоторый вспомогательный ключ от 40 до 88 бит. Для выполнения дешифрования вспомогательный ключ передается получателю зашифрованного сообщения в открытом виде.

Алгоритм RC5

Криптоалгоритм RC5 также разработан Ривестом по заказу компа­нии RSA Data Secur i ty, I nc. Это блочный шифр с переменными длина­ми блока, ключа и числом циклов криптографического преобразова­ния. Параметрами алгоритма являются следующие величины:

• Размер слова в битах w Î{32,64,128}. RC5 является блочным шифром с размером блока 2w битов.

• Количество итераций R Î (0,...,255}.

• Длина ключа в байтах b Î(0,..., 2048}.

Выбранный вариант алгоритма обозначается R C5-w/r/b. Возмож­ность параметризации позволяет гибко настраивать криптоалгоритм с учетом конкретных требований по криптостойкости и эффективности реализации. He все вари­анты алгоритма стойки, и для практического использования рекомендуются RC5-32/12/16 или RC5-64/16/16.

Конструкция алгоритма RC5 представляет собой модифицирован­ную сеть Фейстеля, в которой для прибавления ключа и сложения подбло­ков ис­пользуются различные операции (как в алгоритме ГОСТ), а вместо таблицы замен использован параметризованный циклический сдвиг.

Крипто­алгоритм RC5 состоит из трех основных процедур: расшире­ния ключа, шифрования и де­шифрования.

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

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

Исследования криптостойкости RC5 показали, что вариант кри­пто­алгоритма с разрядностью блока 64 бита и двенадцатью (и бо­лее) циклами преобразования гарантирует адекватную криптостой­ко­сть по отношению к дифференциальному и линейному криптоанализу.

1.8. Поточные шифры