Введение
Криптографическое оборудование
В криптографии, EFF DES-крекер (прозвище "Deep Crack") – это машина, созданная Electronic Frontier Foundation (EFF) в 1998 году для проведения перебора всех возможных ключей в ключевом пространстве шифра Data Encryption Standard (DES), то есть для расшифровки зашифрованного сообщения путем перебора всех возможных ключей. Целью этого было доказать, что размер ключа DES недостаточен для обеспечения безопасности. Подробные технические данные об этой машине, включая блок-схемы, принципиальные схемы, исходный код VHDL специализированных микросхем и его эмулятор, были опубликованы в книге Cracking DES. Лицензия, позволяющая свободное использование и распространение, дает каждому право свободно копировать, использовать или модифицировать её конструкцию. Чтобы избежать экспортного контроля над криптографией со стороны правительства США, исходный код распространялся не в электронном виде, а в виде печатной книги, открытая публикация которой защищена Первой поправкой к Конституции. Для облегчения переноса кода в компьютер с помощью OCR читателям предоставляются машиночитаемые метаданные.
Предыстория
DES использует 56-битный ключ, что означает, что существует 2^56 возможных ключей, под которыми сообщение может быть зашифровано. Это ровно 72 057 594 037 927 936, или приблизительно 72 квадриллиона возможных ключей. Одной из основных критических замечаний в адрес DES, когда он был предложен в 1975 году, было то, что длина ключа была недостаточной. Мартин Хеллман и Уитфилд Диффи из Стэнфордского университета оценили, что машина, достаточно мощная для перебора всех этих ключей за один день, стоила бы около 20 миллионов долларов в 1976 году – сумма, доступная национальным разведывательным службам, таким как Агентство национальной безопасности США. Последующий прогресс в соотношении цены и производительности микросхем постоянно снижал эту стоимость, пока, через двадцать лет, даже небольшая некоммерческая организация, такая как EFF, не смогла организовать реалистичную атаку.
Проблемы DES
DES был федеральным стандартом, и правительство США поощряло использование DES для всех неклассифицированных данных. Компания RSA Security стремилась продемонстрировать, что длины ключа DES недостаточно для обеспечения безопасности, поэтому в 1997 году они запустили серию соревнований DES Challenges, предлагая денежный приз. Первый DES Challenge был взломан за 96 дней проектом DESCHALL под руководством Рока Версера в Лоуленде, штат Колорадо. RSA Security организовала DES Challenge II 1, который был решен с помощью distributed.net за 39 дней в январе и феврале 1998 года. В 1998 году EFF построила Deep Crack (названный в отсылке к шахматному компьютеру Deep Blue от IBM) менее чем за 250 000 долларов. В ответ на DES Challenge II 2, 15 июля 1998 года Deep Crack расшифровал сообщение, зашифрованное DES, всего за 56 часов работы, выиграв 10 000 долларов. Атака полным перебором показала, что взлом DES был вполне реальной задачей. Большинство правительств и крупных корпораций могли бы разумно построить машину, подобную Deep Crack. Спустя шесть месяцев, в ответ на DES Challenge III от RSA Security и в сотрудничестве с distributed.net, EFF использовала Deep Crack для расшифровки еще одного сообщения, зашифрованного DES, выиграв еще 10 000 долларов. На этот раз операция заняла менее суток – 22 часа 15 минут. Расшифровка была завершена 19 января 1999 года. В октябре того же года DES был повторно утвержден в качестве федерального стандарта, но на этот раз стандарт рекомендовал использование Triple DES. Небольшое пространство ключей DES и относительно высокие вычислительные затраты Triple DES привели к его замене на AES в качестве федерального стандарта, вступившего в силу 26 мая 2002 года.
Технология
Deep Crack был разработан компаниями Cryptography Research, Inc., Advanced Wireless Technologies и EFF. Главным разработчиком был Пол Кохер, президент Cryptography Research. Advanced Wireless Technologies создала 1856 специализированных ASIC-чипов DES (называемых Deep Crack или AWT 4500), размещенных на 29 печатных платах по 64 чипа на каждой. Платы были затем установлены в шесть шкафов и смонтированы в шасси Sun 4/470. Поиском координировал один ПК, который назначал диапазоны ключей чипам. Вся машина была способна проверять более 90 миллиардов ключей в секунду. При такой скорости для проверки всех возможных ключей потребовалось бы около 9 дней. В среднем, правильный ключ находился за половину этого времени. В 2006 году была разработана другая аппаратная машина для взлома, основанная на FPGA. COPACOBANA (COst optimized PArallel COdeBreaker) способен взламывать DES при значительно меньших затратах. Это преимущество обусловлено главным образом прогрессом в технологии интегральных схем. В июле 2012 года исследователи в области безопасности Дэвид Хултон и Мокси Марлинспайк представили инструмент облачных вычислений для взлома протокола MS CHAPv2 путем восстановления ключей шифрования DES протокола методом полного перебора. Этот инструмент позволяет любому восстановить ключ DES из известной пары открытого и зашифрованного текста примерно за 24 часа.