RSA DES Challenge¶

RSA DES Challenge — серия открытых конкурсов по взлому криптографических алгоритмов, организованная американской компанией RSA Data Security (RSA Security) в 1997 году. Задача заключалась в расшифровке сообщений, зашифрованных с помощью устаревшего на тот момент блочного шифра DES (Data Encryption Standard), с использованием ключей различной длины. Конкурс стал важной вехой в истории криптографии, продемонстрировав уязвимость DES перед атаками полным перебором и стимулировав разработку более стойких алгоритмов, таких как AES.

¶История

¶Предпосылки

К середине 1990-х годов алгоритм DES, принятый в 1977 году Национальным институтом стандартов и технологий (NIST) США, считался основным симметричным шифром в коммерческой и государственной сферах. Однако его ключ длиной 56 бит вызывал растущую обеспокоенность. С развитием вычислительной техники полный перебор всех 2^56 возможных ключей (атака «грубой силы») становился теоретически осуществимым. В 1997 году RSA Data Security, стремясь привлечь внимание к этой проблеме и продемонстрировать необходимость перехода на более надёжные алгоритмы, объявила о проведении серии конкурсов.

¶Хронология конкурсов

RSA DES Challenge состоял из трёх раундов, каждый из которых предлагал взломать DES-шифротекст с ключом определённой длины:

• DES Challenge I (январь 1997): ключ длиной 56 бит. Взломан 18 июня 1997 года за 96 дней. Победителем стал проект DESCHALL, координируемый Рокки Керном (Rocky Kern) и использующий распределённые вычисления. Сообщение содержало текст: «The unknown message is: Strong cryptography makes the world a safer place».
• DES Challenge II (февраль 1998): ключ длиной 56 бит. Взломан 24 февраля 1998 года за 39 дней. Победителем стал проект distributed.net, использующий добровольные вычислительные ресурсы. Сообщение: «The secret message is: Many hands make light work».
• DES Challenge III (январь 1999): ключ длиной 56 бит. Взломан 19 января 1999 года за 22 часа 15 минут. Победителем стала коалиция Electronic Frontier Foundation (EFF — организация признана нежелательной в РФ) и distributed.net, использовавшая специализированное устройство Deep Crack. Сообщение: «See you in Rome (second AES conference, March 22-23, 1999)».

Все три раунда подтвердили, что DES с 56-битным ключом не обеспечивает достаточной защиты от современных атак.

¶Устройство и методология

¶Принцип конкурса

Участникам предоставлялся зашифрованный текст (шифротекст) и открытый текст (plaintext) для известной атаки с открытым текстом (known-plaintext attack). Задача заключалась в нахождении 56-битного ключа, который при расшифровке давал осмысленное сообщение. Для проверки правильности ключа использовался контрольный вектор (checksum) или известная часть открытого текста.

¶Методы взлома

Основным методом был полный перебор (brute-force attack) всех возможных ключей. В первых двух раундах использовались распределённые вычисления: тысячи добровольцев по всему миру устанавливали клиентское программное обеспечение, которое перебирало небольшие диапазоны ключей на своих компьютерах. В третьем раунде к распределённым вычислениям добавилось специализированное аппаратное устройство — Deep Crack, разработанное EFF. Оно состояло из 1856 микросхем, способных перебирать до 90 миллиардов ключей в секунду.

¶Роль Deep Crack

Deep Crack, стоимостью около 250 000 долларов США, стал первым в мире устройством, специально спроектированным для взлома DES. Его производительность позволила сократить время взлома с месяцев до часов. Успех Deep Crack продемонстрировал, что даже относительно недорогое специализированное оборудование способно преодолеть защиту DES.

¶Классификация и участники

¶Типы участников

Конкурс привлёк как индивидуальных энтузиастов, так и крупные организации:

• Проекты распределённых вычислений: DESCHALL (основан на ПО для распределённого перебора) и distributed.net (специализированная платформа для добровольных вычислений).
• Электронный фонд защиты гражданских прав (EFF): некоммерческая организация, признанная нежелательной в РФ, которая финансировала создание Deep Crack.
• Корпорации: RSA Data Security выступала организатором, а также предоставляла призы (10 000 долларов США за каждый раунд).

¶Результаты по раундам

¶Применение и значение

¶Демонстрация уязвимости DES

Главным итогом конкурса стало неопровержимое доказательство того, что 56-битный ключ DES не обеспечивает криптографической стойкости. В 1999 году NIST официально рекомендовал прекратить использование DES для новых систем, а в 2005 году стандарт был отозван. Конкурс ускорил процесс принятия нового стандарта шифрования — AES (Advanced Encryption Standard), который был выбран в 2001 году и использует ключи длиной 128, 192 или 256 бит.

¶Влияние на криптографию

RSA DES Challenge стимулировал развитие распределённых вычислений для криптоанализа. Проекты DESCHALL и distributed.net стали прототипами для более масштабных систем, таких как BOINC (Berkeley Open Infrastructure for Network Computing), используемых для научных расчётов. Кроме того, конкурс продемонстрировал эффективность специализированных аппаратных решений (ASIC, FPGA) для взлома шифров, что впоследствии повлияло на проектирование криптостойких систем.

¶Общественный резонанс

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

¶Критика и ограничения

¶Ограничения методологии

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

¶Критика со стороны криптографов

Некоторые специалисты отмечали, что конкурс был частично рекламной акцией RSA Data Security, которая продвигала свои собственные алгоритмы (например, RC5) как альтернативу DES. Однако объективные результаты конкурса подтвердили уязвимость DES, что признаётся криптографическим сообществом.

¶Технические ограничения Deep Crack

Устройство Deep Crack было разработано для одной конкретной задачи — перебора ключей DES. Оно не могло быть использовано для взлома других алгоритмов без значительной модификации. Кроме того, стоимость устройства (250 000 долларов) была доступна лишь крупным организациям, что ограничивало его применение в массовом масштабе.

¶Интересные факты

• Сообщение, расшифрованное в DES Challenge I, содержало фразу «Strong cryptography makes the world a safer place», что стало девизом движения за открытые криптографические стандарты.
• В DES Challenge III участвовало более 100 000 добровольцев, предоставивших вычислительные ресурсы через distributed.net.
• Устройство Deep Crack было выставлено в Музее компьютерной истории в Калифорнии.
• После завершения конкурсов RSA Data Security провела аналогичные соревнования для алгоритма RC5 (RSA RC5 Challenge), который также был взломан с помощью распределённых вычислений.

¶Источники

• RSA Laboratories. «DES Challenge» — официальные результаты конкурсов.
• Electronic Frontier Foundation. «Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design» (1998).
• Distributed.net. «DES Challenge II and III» — архивные данные проекта.
• NIST. «Announcing the Advanced Encryption Standard (AES)» (2001).
• Schneier B. «Applied Cryptography» (2nd ed., 1996).