Как был взломан DES

DES имеет 2^56 возможных ключей, то есть примерно 72 квадриллиона (72 057 594 037 927 936) ключей. Хотя это число кажется огромным, пространство конечно, и его можно систематически перебрать при наличии достаточной вычислительной мощности.

Исчерпание пространства ключей (полный перебор) в среднем требует проверки половины пространства ключей, прежде чем будет найден правильный ключ. Для DES это означает около 2^55 пробных расшифрований, каждое из которых на современном оборудовании требует всего нескольких операций.

В 1997 году компания RSA по защите данных предложила приз в 10 000 долларов за взлом сообщения, зашифрованного с помощью DES. Рок Версер координировал распределённые вычисления на десятках тысяч компьютеров, подключённых к интернету.

После 96 дней поиска ключ был найден. Открытый текст гласил: «Сильная криптография делает мир безопаснее». Эта работа продемонстрировала, что DES можно взломать, хотя для этого потребовались месяцы и масштабная координация.

В 1998 году Electronic Frontier Foundation создала Deep Crack стоимостью 250 000 долларов. Он содержал 1 856 специализированных интегральных схем, каждая из которых могла проверять 2,5 миллиона ключей DES в секунду, что обеспечивало Deep Crack общую скорость более 90 миллиардов ключей в секунду.

Deep Crack мог в среднем перебрать всё пространство ключей DES примерно за 9 дней. Это доказало, что решительный злоумышленник, вложивший 250 000 долларов, способен взломать DES менее чем за две недели.

Во время испытания DES II-1 (февраль 1998 года) Deep Crack совместно с волонтёрской вычислительной сетью distributed.net взломал DES всего за 39 дней. Испытание II-2 (июль 1998 года) было завершено за 56 часов.

Стремительное сокращение времени с 96 дней до 56 часов всего за один год продемонстрировало, насколько быстро улучшение аппаратного обеспечения и более эффективная координация могут ускорить атаки полным перебором.

В январе 1999 года Deep Crack от EFF совместно с distributed.net взломал испытание DES III всего за 22 часа 15 минут и получил приз в 10 000 долларов от компании RSA по обеспечению безопасности.

Это убедительное доказательство того, что DES можно взломать менее чем за 24 часа, фактически положило конец любым спорам о безопасности DES. Вскоре после этого NIST начал процесс выбора замены DES, которой стал AES.

Distributed.net организовала вычисления с участием добровольцев: обычные пользователи интернета предоставляли для испытаний DES вычислительные ресурсы своих CPU. На пике в работе участвовали сотни тысяч компьютеров.

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

Исчерпание пространства ключей работает потому, что каждая расшифровка DES выполняется быстро (за микросекунды на аппаратном обеспечении) и независимо от остальных. Между проверкой ключа N и ключа N+1 нет зависимости, поэтому поиск идеально распараллеливается на любом количестве машин.

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

Эли Бихам и Ади Шамир опубликовали метод дифференциального криптоанализа в 1990 году. Он использует закономерности распространения различий во входных парах через раунды шифра. Для DES этот метод теоретически требует 2^47 выбранных открытых текстов.

Впоследствии выяснилось, что S-блоки DES были разработаны с учётом устойчивости к дифференциальному криптоанализу, что указывает на осведомлённость NSA об этом методе ещё в 1970-х годах. Теоретически атака впечатляет, но на практике уступает аппаратному полному перебору.

Мицуру Мацуи опубликовал метод линейного криптоанализа в 1993 году. Для атаки на DES требовалось 2^43 известных открытых текстов. Он реализовал атаку и экспериментально взломал DES в 1994 году, подтвердив теоретический анализ.

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

Дифференциальный криптоанализ был опубликован в 1990 году, но требует выбранных открытых текстов, что непрактично в большинстве реальных сценариев. Линейный криптоанализ был опубликован в 1993 году и работает с известными открытыми текстами, но требует 2^43 таких текстов.

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

Публичный и документированный взлом DES сразу повлиял на политику безопасности. NIST начал конкурс по выбору AES в 1997 году — в том же году, когда завершилось испытание DES I. Конкурс был специально разработан так, чтобы избежать недостатков процесса стандартизации DES.

Банки и государственные учреждения начали переходить на тройной DES в качестве временной меры, пока разрабатывался AES. Хронология взлома DES непосредственно определила срочность и сроки внедрения AES.

Проверьте своё понимание истории взлома DES.

DES взламывали всё быстрее: за 96 дней в 1997 году, за 56 часов в 1998 году и за 22 часа в 1999 году. Deep Crack стоимостью 250 000 долларов, созданный EFF, использовал специализированные интегральные схемы и проверял 90 миллиардов ключей в секунду.

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