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




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

Это - наиболее очевидный и простой метод атаки шифров, который может работать при модели угроз (допущении) «только с шифртекстом», если избыточность открытого текста достаточно высокая, или при допущении модели «с известным открытым текстом», в противном случае [224]. Атака состоит из расшифрования заданного шифртекста при каждом возможном ключе до распознавания открытого текста (или его избыточности). Сложность памяти является постоянной. Средняя временная сложность для n-битного блочного шифра с использованием k-битного ключа равна 2k-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 часа.

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






Дата добавления: 2016-09-26; просмотров: 1125; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2022 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.018 сек.