4.6.4.Силовая атака на основе распределенных вычислений
В конце января 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 | 10 | 28.01.97 | 17.06.97, 10:40 p.m. PST | 140 дней |
RC5-32/12/5 | 1 | 28.01.97 | 28.01.97, 12:30 p.m. PST | 3.5 часа |
RC5-32/12/6 | 5 | 28.01.97 | 10.02.97, 10:00 a.m. PST | 313 часов |
RC5-32/12/7 | 10 | 28.01.97 | 20.10.97, 11:18 a.m. PST | 210 дней |
RC5-32/12/8 | 10 | 28.01.97 | - | - |
RC5-32/12/9 | 10 | 28.01.97 | - | - |
RC5-32/12/10 | 10 | 28.01.97 | - | - |
RC5-32/12/11 | 10 | 28.01.97 | - | - |
RC5-32/12/12 | 10 | 28.01.97 | - | - |
RC5-32/12/13 | 10 | 28.01.97 | - | - |
RC5-32/12/14 | 10 | 28.01.97 | - | - |
RC5-32/12/15 | 10 | 28.01.97 | - | - |
RC5-32/12/16 | 10 | 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 бит.
- Введение
- Часть I основные понятия и положения защиты информации в компьютерных системах
- 1 Предмет и объект защиты
- 1.1. Предмет защиты
- 3. Ценность информации изменяется во времени.
- 4. Информация покупается и продается.
- 5. Сложность объективной оценки количества информации.
- 1.2. Объект защиты информации
- 2 Криптографические системы защиты информации
- 2.1. Одноключевые криптографические системы
- 2.1.1. Блочные шифры
- 2.1.2. Шифры простой перестановки
- 2.1.3. Шифры сложной перестановки
- 2.1.4. Шифры замены (подстановки)
- 2.1.5. Одноалфавитные шифры.
- 2.1.6. Многоалфавитные шифры
- 2.2. Составные шифры
- 2.2.1. Шифры поточного (потокового) шифрования
- 2.2.1.1. Синхронные поточные шифры
- 2.2.1.2. Самосинхронизирующиеся поточные шифры
- 2.2.1.3. Комбинированные шифры
- 2.3. Двухключевые криптографические системы
- 2.3.1. Криптографические системы с открытым ключом
- 2.3.1.1. Метод возведения в степень
- 2.3.1.2. Метод укладки (упаковки) рюкзака (ранца)
- 2.3.1.3. Кодовые конструкции
- 2.4. Составные криптографические системы
- 2.5. Надежность использования криптосистем
- 3 Симметричные криптосистемы и блочные шифры
- 3.1 Определение блочного шифра
- 3.2. Принцип итерирования
- 3.3. Конструкция Фейстеля
- 3.4. Режимы шифрования блочных шифров
- 3.4 Стандарты блочного шифрования
- 3.4.1 Федеральный стандарт сша — des
- 3.4.2. Стандарт России — гост 28147-89
- 3.5 Атаки на блочные шифры
- 3.5.1 Дифференциальный криптоанализ
- 3.5.2. Дифференциальный криптоанализ на основе отказов устройства
- 3.6.3. Линейный криптоанализ
- 4.6.4.Силовая атака на основе распределенных вычислений
- 4.7. Другие известные блочные шифры
- 4 Угрозы безопасности информации в компьютерных системах
- 4.1. Случайные угрозы
- 2.2. Преднамеренные угрозы
- 2.2.2. Несанкционированный доступ к информации
- Направления обеспечения информационной безопасности
- Постулаты безопасности
- 3.1. Правовая защита
- Раздел «Предмет договора»
- Раздел «Порядок приема и увольнения рабочих и служащих»
- Раздел «Основные обязанности администрации»
- 3.2 Организационная защита
- 3.3. Инженерно-техническая защита
- 3.3.1. Общне положения
- 3.3.2. Физические средства защиты
- Охранные системы
- Охранное телевидение
- Запирающие устройства
- 3.3.3. Аппаратные средства защиты
- 3.3.4. Программные средства защиты
- Основные направления использования программной защиты
- Защита информации от несанкционированного доступа
- Защита от копирования
- Защита информации от разрушения
- 3.3.5. Криптографические средства защиты
- Технология шифрования речи
- 4 Способы защиты информации
- 4.1. Общие положения
- 4.2. Характеристика защитных действий
- Защита информации от утечки
- 5.1. Общие положения
- 5.2. Защита информации от утечки по визуально-оптическим каналам
- 5.2.1. Общие положения
- 5.2.2. Средства и способы защиты
- 5.3. Защита информации от утечки по акустическим каналам
- 5.3.1. Общие положения
- 5.3.2. Способы и средства защиты
- 5.4. Защита информации от утечки по электромагнитным каналам
- 5.4.1. Защита утечки за счет микрофонного эффекта
- 5.4.2. Защита от утечки за счёт электромагнитного излучения
- 5.4.3. Защита от утечки за счет паразитной генерации
- 5.4.4. Защита от утечки по цепям питания
- 5.4.5. Защита от утечки по цепям заземления
- 5.4.6. Защита от утечки за счет взаимного влияния проводов и линий связи
- 5.4.7. Защита от утечки за счет высокочастотного навязывании
- 5.4.8. Защита от утечки в волоконно-оптических линиях и системах связи
- 5.5. Защита информации от утечки по материально-вещественным каналам
- 6.1. Способы несанкционированного доступа
- 6.2. Технические средства несанкционированного доступа к информации
- Контроль и прослушивание телефонных каналов связи
- Непосредственное подключение к телефонной линии
- Подкуп персонала атс
- Прослушивание через электромагнитный звонок
- Перехват компьютерной информации, несанкционированное внедрение в базы данных
- 6.З. Защита от наблюдения и фотографирования
- 6.4 Защита от подслушивания
- 6.4.1. Противодействие подслушиванию посредством микрофонных систем
- Некоторые характеристики микрофонов
- Противодействие радиосистемам акустического подслушивания
- Общие характеристики современных радиозакладок
- Содержание введение
- Часть I основные понятия и положения защиты информации в компьютерных системах
- Угрозы безопасности информации в компьютер-ных системах
- Направления обеспечения информационной без-опасности
- 4. Способы защиты информации
- Противодействие несанкционированному досту-пу к источникам конфиденциальной информации