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

В конце января 1997 г. компания RSA Data Security, Inc. анонсировала новый криптографи­ческий конкурс (табл. 11.20). Цель конкурса — оценка криптостойкости федерального стан­дарта США DES [15] и симметричных криптосистем с переменной длиной ключа на основе криптоалгоритма RC5. Хорошо известно, что 56-битный ключ стандарта DES не гаранти­рует адекватной криптостойкости в случае силовой атаки (исчерпывающий перебор ключа). В 1993 г. Винер (М. J. Wiener) из Bell-Northen Research разработал для силовой атаки на DES специализированный параллельный компьютер, позволяющий раскрывать ключ в те­чение нескольких часов [158]. Попытки устранения основного недостатка DES, связанного с коротким ключом, привели к появлению различных DES-модификаций — метода тройного DES-шифрования [138], метода DESX, предложенного Ривестом (R. Rivest) [140], а также ряда альтернативных криптосистем, таких, как IDEA [164] и RC5 [162). Известно также, что кроме криптостойкости существуют и другие факторы, оказывающие влияние на выбор длины ключа симметричной криптосистемы.

Таблица 11.20. Условия и результаты конкурса компании RSA Data Security, Inc.

Криптосистема DES, RC5	Приз (тыс. долл.)	Начало (9 a.m. PST)	Время завершения	Длительность
DES		28.01.97	17.06.97, 10:40 p.m. PST	140 дней
RC5-32/12/5		28.01.97	28.01.97, 12:30 p.m. PST	3.5 часа
RC5-32/12/6		28.01.97	10.02.97, 10:00 a.m. PST	313 часов
RC5-32/12/7		28.01.97	20.10.97, 11:18 a.m. PST	210 дней
RC5-32/12/8		28.01.97	-	-
RC5-32/12/9		28.01.97	-	-
RC5-32/12/10		28.01.97	-	-
RC5-32/12/11		28.01.97	-	-
RC5-32/12/12		28.01.97	-	-
RC5-32/12/13		28.01.97	-	-
RC5-32/12/14		28.01.97	-	-
RC5-32/12/15		28.01.97	-	-
RC5-32/12/16		28.01.97	-	-

Так, например, в соответствии с законодатель­ством длина ключа для экспортируемых за пределы США и Канады криптографических приложений на основе симметричного криптоалгоритма ограничена 40 битами. Необходи­мость теоретических обоснований в данном случае отпадает, несостоятельность криптогра­фии с 40-битным ключом убедительно продемонстрирована первыми результатами крип­тосистема RC5-32/12/5 была «взломана» через 3,5 часа после объявления в Internet условий криптографического конкурса (см. табл. 11.20). Параметры криптосистемы RC5 в табл. 11.20 обозначаются как RC5-X/Y/Z, где X - разрядность блока в битах, Y - число циклов крипто­графического преобразования, Z — длина ключа в байтах (Z*8—разрядность в битах). Сило­вая атака сводится, по сути, к дешифрованию фиксированного шифротекста на различных ключах при заданном векторе инициализации. Так, для атаки на RC5-32/12/5 был задан шифротекст (в шестнадцатеричном представлении):

12 35 13 64 78 d3 da 08 d9 15 ed 20 89 30 5f 50 68 5c

6c b4 bf 5b 00 38 ff 44 4e d9 d4 9b 46 16 fb 12 92 62

9b d4 7f la 8d 48 fe b6 63 dl d4 c2 eb 19 Od 86 3f f4

43 75 9a 58 06 2c 8b a5 9e 6a 33 30 c3 3e a8 ab 24 25

и вектор инициализации 8а 16 2f 69 e8 37 98.

Секретный ключ считается раскрытым, если результат дешифрования на текущем ключе приводит к содержательному тексту на английском языке. Условия конкурса, а также все необходимые исходные данные могут быть получены с Web-сервера компании RSA Data Security, Inc. но адресу http://www.rsa.com.

Все результаты табл. 11.20 в отличие от идеи Винера получены при помощи программной реализации криптоалгоритма и массированной параллельной атаки с привле­чением десятков, а иногда и тысяч рабочих станций. Сеть Internet, пример практического приложения идеи распределенных вычислений, стала мощным инструментом силовой атаки в руках криптоаналитиков и хакеров. Силовая атака на основе распределенных вычисле­ний имеет свою динамику, связанную с активностью сетевых пользователей. Проанализи­руем возможности распределенной силовой атаки на примере криптосистем RC5-32/12/5 и RC5-32/12/6 [137].

Для решения ряда задач практической криптографии необходимы значительные вычис­лительные ресурсы. При этом некоторые из этих задач поддаются распараллеливанию. Та­ким образом, Internet, объединяющий многие тысячи рабочих станций, позволяет эффектив­но решать трудоемкие задачи путем координированной и одновременной работы большого числа компьютеров. Такой подход, реализующий возможности компьютерных сетей, изве­стен под названием метода распределенных вычислений. Одна из первых успешных попыток использования Internet для факторизации RSA-модуля из 129 десятичных разрядов была предпринята в 1994 г. [147]. Объединенные усилия 600 человек и 1600 компьютеров, включая две факс-машины, координировались при помощи электронной почты. Успешная факторизация RSA-модуля из 130 десятичных разрядов продемонстрировала исключитель­ную эффективность решения, основанного на объединении метода распределенных вычисле­ний, алгоритма обобщенного числового решета и координации работы компьютеров в рамках Web-технологии.

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

В 1992 г. Каронни (G. Caronni) и Алемсбергер (W. Alemsberger) разработали программ­ное обеспечение для координации одновременной работы сетевых компьютеров при поиске «плохих» паролей локальных UNIX-серверов. Программа позволила решить поставленную задачу объединенными усилиями 350 рабочих станций. Объявленный в январе 1997 г. крип­тографический конкурс открыл новую область приложения для программного обеспечения Каронни-Алемсбергера. В течение января программа была переработана под новую задачу. Программная реализация криптоалгоритма RC5, оптимизированная для компьютера Ultra 1/170. позволяла проверять миллион ключей криптосистемы RC5-32/12/5 за 6,15 с. За неде­лю до начала атаки организаторы разослали в ряд университетов США и Европы предло­жения об участии в проекте с просьбой привлечения всех заинтересованных лиц. За три дня до начала атаки стало ясно, что объединенное общей целью сетевое сообщество обладает достаточным потенциалом для решения поставленной задачи. Запуск проекта состоялся в 18:07 по западноевропейскому времени (9:07 PST). Ошибки в работе программного обеспе­чения сервера, обнаруженные Шнайдером (С. Schneider) в 20:30. привели к перезапуску 40 серверов, участвовавших в проекте. Несмотря на сбои, задача была решена объединенными усилиями 800 компьютеров в Швейцарии. Германии, Норвегии и США. Секретный ключ криптосистемы RC5-32/12/5 найден за 231 мин после проверки 51% всех ключей со средней производительностью 40 млн. ключей в секунду. Известно, что аналогичная атака, предпри­нятая ранее Голдбергом (I. Goldberg) из Университета Беркли, успешно завершилась после перебора 31% ключей за 210 мин. Отметим, что с методологической точки зрения различия в организации атаки Каронни и Голдберга мало существенны. В проекте Голдберга было задействовано 259 компьютеров (287 процессоров):

• 97 UltraSPARC;

• 4 UltraSPARC (8 процессоров);

• 120 рабочих станций HP:

• 8 процессоров Pentium;

• 30 SPARCStation 20s.

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

Клиент Сервер

Регистрация/3апрос_задания

Задание/Сброс_чадания/Остановка
Задание_выполнено/3апрос_задания

Задание/Сброс_задания/3апрос_регистрации/Остановка

Рис. 11.23. Протокол взаимодействия по технологии «клиент-сервер»

Молниеносная «расправа» с криптосистемой RC5-32/12/5 стала безусловным стимулом для силовой атаки криптосистемы RC5-32/12/6 с 48-битным ключом (далее в тексте - про­ект RC5-32/12/6). Проект был запущен 29 января в 18:00 по западноевропейскому времени после переработки программного обеспечения и пред-варительного шестичасового тестирова­ния. Существует два подхода к организации силовой атаки на основе метода распределенных вычислений. Первый — цент-рализованное управление процессом поиска при помощи серве­ра. Второй — слу-чайный и независимый выбор стартовой точки в ключевом пространстве каждым из участвующих в проекте компьютером и оповещение в случае раскрытия ключа. Первый подход более предпочтителен, но связан с определенными трудностями. Так,

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

Организаторы проекта намеренно предложили упрощенную схему взаимодейст-вия по тех­нологии «клиент-сервер» [137|. Для регистрации клиента и получения очередного задания от сервера использовался простейший протокол. Типичный протокол обмена между клиентом и сервером представлен на рис. 11.23.

Запрос Регистрация включает номер версии, тип компьютера и другую необходи-мую для начала работы информацию. Запрос_ задания содержит сведения об объе-ме сегмента клю­чевого пространства и оценку времени перебора сегмента указан-ного объема. Клиент может отказаться от участия или приостановить выполнение за-дания. Факт отказа со стороны кли­ента устанавливается по нулевому объему сегмен-та в Запросе_ задания. Сервер подтверждает отказ клиента сообщением Сброс _ зада-ния. В случае раскрытия ключа или возобновления ра­боты клиент уведомляет сервер с помощью специально предусмотренных сообщений. Если сервер по каким-либо причинам завершает свою работу и вместо него включается новый, то в ответ на сообщение клиента Задание_ выполнено новый сервер отвечает сообщением Запрос_ регистрации, чем инициирует регистрацию клиента на новом сервере. Для немед­ленной остановки работы клиентов предусмотрено сообщение Остановка. Сервер управляет сегментированием ключевого пространства, периодически записы-вая текущее состояние на жесткий диск, в целях оперативного восстановления программного обеспечения в случае сбоя или перезагрузки операционной системы. Сервер динамически отслеживает время ра­боты всех зарегистрированных у него клиентов. Если время перебора ключевого сегмента, указанное клиентом в Запросе_задания, истекает, сервер передает сегмент другому клиенту виртуальной сети. По завершении процедуры проверки текущего ключевого сегмента клиен­ту, по соответствующему запросу, передается новый сегмент.

Криптоалгоритм RC5 для программного обеспечения клиента был реализован на язы­ке ассемблера для процессоров Intel и RS6000. Оптимизация на уровне компилятора язы­ка С выполнялась для следующих операционных систем: AIX. FreeBSD, HPUX, IRIX. Linux, NEXTSTEP, NetBSD, OS2, OSF1, OpenBSD, SCO_SV, SunOS, ULTRIX, Windows (NT& 95), AMIGA MacOS MIPS, Alpha, (Ultra) SPARC, 486/586 Intel, Pentium Pro, Paragons. ОС для компьютеров с параллельной архитектурой (до 16 000 процессоров).

Рис. 11.24. Рост производительности при проверке ключей

Лавинообразное вовлечение участников в силовую атаку на криптосистему RC5-32/12/6 позволило задействовать значительные сетевые ресурсы. Отметим, что пиковая производи­тельность тестирования ключей достигала 440 млн. ключей в секунду, а максимальное коли­чество одновременно работающих компьютеров - 4500 единиц.

Рис. 11.24 иллюстрирует закономерность роста производительности при проверке ключей После медленного роста в течение первой недели производительность удвоилась за два дня — с 4 по 6 февраля. Следующее удвоение производительности произошло также через два дня -с 7 по 9 февраля.

Рост производительности в ходе силовой атаки на криптосистему RC5-32/12/6 сравним с производительностью атаки Голдберга на криптосистему RC5-32/12/5 (27 млн. ключей в секунду), в которой было задействовано фиксированное число компьютеров.

На рис. 11.25 представлена закономерность роста количества проверенных ключей в про­центах от объема ключевого пространства.

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

http://www.ee.ethz.ch/challenge/

http://www.42.org/challenge/

http://www.klammeraffe.org/challenge/.

Рассматриваемая организация силовой атаки на основе меюда распределенных вычисле­ний порождает следующий вопрос. В состоянии ли один-единственный центральный сервер справиться с возрастающим потоком запросов, и в какой степени такой рост влияет на эф­фективность распределенных вычислений? Исходя из данных о пиковой нагрузке последних дней проекта можно предположить, что центральный сервер обслуживал 5000 клиентов каж­дые 30 мин. Это, в свою очередь, означает, что каждую секунду к серверу обращалось не более двух клиентов. Производительность современных серверов позволяет легко справлять­ся с подобной нагрузкой при интенсивности трафика порядка 300 байт в секунду. Так, сервер проекта RC5-32/12/6, сконфигурированный на Sun Ultra 1/170, был загружен менее чем на 2%, при этом потребность в оперативной памяти составила менее 6 Мбайт. Таким образом, экспериментальные данные, полученные в ходе проекта, подтверждают, что один сервер без перегрузки может обслужить миллион клиентов. Отметим, что эффективность описанно­го подхода может быть невысокой из-за дополнительных задержек, возникающих в связи с низкой пропускной способностью каналов связи.

Оценим вычислительную производительность проекта. Поскольку для проверки одного ключа по криптоалгоритму RC5 требуется порядка 2000 инструкций, то для нахождения ключа методом силовой атаки понадобится 3.24 х 1017 инструкций. Так как принятая еди­ница измерения вычислительной производительности в один миллион инструкций в секунду (MIPS/Year, MY) оценивается как 3.15 х 1013 инструкций, суммарная производительность проекта составила 104 MY в течение 10 календарных дней. Это свидетельствует о росте вычислительной производительности Internet. Для сравнения: вычислительная производи­тельность при факторизации 129-разрядного RSA-модуля в 1994 г. составила 5 х 103 MY за девять календарных месяцев.

Рис. 11.25. Рост числа проверенных ключей

По результатам проекта RC5-32/12/5 и RC5-32/12/6 в статье [137) представлен прогноз будущего силовой атаки на основе распределенных вычислений. В первую очередь отметим, что производительность проверки ключей, достигнутая в последние дни проекта RC5-32/12/6 (330 млн. ключей в с.), недостаточна для эффективной силовой атаки на криптосистему RC5-32/12/7. Учитывая производительность проекта RC5-32/12/6, для силовой атаки крип­тосистемы RC5-32/12/7 по оценкам [137] потребуется около 255/330 х 220 секунду - при­близительно три с половиной года непрерывной работы. Однако экспериментальные данные (рис. 11.24) свидетельствуют об удваивании производительности каждые три дня. Таким об­разом, ожидаемая производительность при сохранении тенденции может возрасти на поря­док по сравнению с пиковой производительностью проекта RC5-32/12/6. В этом случае для осуществления атаки понадобится не более полугода.

При одинаковой длине ключа криптоалгоритм DES позволяет проверять ключи в 2 - 4 раза быстрее (в зависимости от реализации), чем RC5-32/12/7. Производительность некоторых программных реализаций составляет 500 тысяч ключей в секунду на процессоре Pentium 120. С учетом изложенных выше тенденций для поиска ключа DES методом исчерпывающего перебора понадобится не более нескольких месяцев. Отметим, что прогноз, представленный в статье [137], подтвердился недавно опубликованными результатами (см. табл. 11.20).

Результаты распределенной силовой атаки на криптосистемы RC5-32/12/5 и RC5-32/12/6 продемонстрировали слабость 40- и 48-битных ключей. Известно, что в хо­де обсуждения экспортного законодательства США было предложено ограничить длину ключа в экспортируемых криптографических приложениях 56 битами (см. http://www.bxa.doc.gov/encstart.htm). Однако, учитывая рост производительности ком­пьютеров (удваивается каждые 18 месяцев по закону Мура) и динамику развития Internet. можно предположить, что 56-битный ключ также не гарантирует адекватной криптоетой-кости. По оценкам ведущих криптографов и специалистов по компьютерным технолот-ям, минимальная длина ключа симметричной криптосистемы, гарантирующая криптостой­кость по отношению к силовой атаке, должна колебаться от 75 до 90 бит (см. отчет http://www.bsa.org/policy/encryption). Многие специалисты с консервативными вз!ля­дами придерживаются мнения, что длина ключа должна быть не менее 128 бит.

Дата добавления: 2014-01-05