Атака Исчерпывающего Поиска (Exhaustive Search Attack).

Эта атака также называется атакой полного перебора ключей, а в некоторых иностранных источниках как атака (метод) "грубой силы" (brute force).

Это - наиболее очевидный и простой метод атаки шифров, который может работать при модели угроз (допущении) «только с шифртекстом», если избыточность открытого текста достаточно высокая, или при допущении модели «с известным открытым текстом», в противном случае [224]. Атака состоит из расшифрования заданного шифртекста при каждом возможном ключе до распознавания открытого текста (или его избыточности). Сложность памяти является постоянной. Средняя временная сложность для n-битного блочного шифра с использованием k-битного ключа равна 2^k-1 расшифрований. Сложность данных состоит из блоков известного шифртекста (и соответствующих блоков открытого текста в атаке с известным открытым текстом). Контрмеры включают выбор достаточно длинного ключа (Блейз и др.[36]). Вероятность успеха исчерпывающего поиска ключа пропорциональна найденной (проверенной) части пространства ключей, то есть, для атаки, охватывающей p-тую часть пространства ключей ( ), вероятность нахождения ключа равна p [140].

Эта атака может быть выполнена параллельно на множестве процессоров, каждый из которых расшифровывает известный шифр-текст с различной частью пространства ключей. Существует два подхода для такого параллельного поиска: с использованием распределенного ПО или с использованием специализированных аппаратных средств. Имеется много отчетов по такому виду атак на DES, особенно с использованием последнего подхода, так как структура DES позволяет его очень эффективно осуществить в аппаратной реализации (Смид [214]). В [68] Диффи и Хэллман заявили, что машина стоимостью 20 млн.$ США (при валютном курсе и технологии 1977г.) может быть построена для атаки одного DES ключа, с обесцениванием стоимости машины через пять лет. В 1990 г. Гарон и Отербридж предложили конструкцию машины стоимостью 1 млн.$ США, использующей специализированные чипы, способные находить DES ключ за девять дней с технологией 1995 г., и за 43 часа с технологией 2000 г. В 1992 г. Эберли предложил 1 Гбит/с GaAs DES чип, а также использование чипов стоимостью 1 млн.$ США для исчерпания (просмотра) половины пространства ключей DES за восемь дней.

В 1993 г. Вайнер [227] представил детальное описание атаки с известным открытым текстом с использованием машины стоимостью 1 млн.$ США для нахождения DES ключа в среднем за 3.5 часа. В 1997 г. Вайнер [228] обновил свои оценки 1 млн.$ машины для нахождения DES ключа в среднем за 3.5 мин. В 1998 г. Electronic Frontier Foundation (EFF) завершила построение машины для исчерпывающего поиска ключа [76] для атаки одинарного DES, приблизительно стоимостью 250,000$ США [23]. Атака привела к получению правильного ключа приблизительно за 55 часов, с использованием известного открытого текста.

Исчерпывающий поиск ключа на базе распределенного ПО состоит в разбиении пространства ключей на небольшие части и использовании времени простоя компьютеров добровольцев из сети Internet для параллельного поиска неизвестного ключа. Одним из примеров такой атаки является поиск секретного ключа, проведенный в RSA Лаборатории [133], состоящий из нескольких конкурсов. В каждом конкурсе открытый текст зашифровывался блочным шифром, таким как DES, но открытый текст и ключ не раскрывались. Таким образом, исчерпывающий поиск в этом случае представлял собой атаку с восстановлением ключей и открытого текста. Первый конкурс, DES I, был осуществлен за 96 дней распределенной группой на Internet. DES II-1 был осуществлен за 40 дней также распределенной Internet группой. Конкурс DES II-2 затратил три дня и был осуществлен EFF машиной взлома и группой добровольцев, которые также победили в последнем конкурсе DES III за 22 часа.

Просто, чтобы охарактеризовать современные возможности вычислений, можно сослаться на некоторые числа: 2³⁰ простых операций легко выполняются современным персональным компьютером за несколько минут. Если взять несколько тысяч компьютеров на чистых 10 дней, то можно выполнить 2⁵⁵ шифрований DES. Заметим, что мощность всех компьютеров Internet может быть приблизительно оценена как около 2⁷⁰ простых операций за день.