Атака «компромисс время-память»

В 1980 г. Хэллман [90] представил вероятностную атаку на DES, которая обеспечивает компромисс между вычислительным временем и емкостью памяти, балансируя преимуществами исчерпывающего поиска ключей и атаки со словарем, то есть, затрачивая меньше интерактивной обработки и меньше памяти, соответственно. Такая атака с компромиссом между временем и памятью (TMT - time-memori-time) имеет стадию предварительных вычислений, которая может выполняться автономно злоумышленником. Это атака с выбранным открытым текстом.

Хэллман применил этот метод для DES, а также к другим шифрам, для которых Расширение атаки для шифров, для которых , было предоставлено Кусуда и Мацумото в [132, 131]. Они получили более строгие границы для вероятности успеха и представили зависимости между сложностью памяти и временной сложностью и вероятностью успеха. В [75] Фиат и Наор представили вариантную атаку, которая применима к любому шифру за счет более высокой временной сложности и сложности памяти.

В [5] Амиразизи и Хэллман пересмотрели атаку с компромиссом между временем и памятью, аргументируя тем, что она не обеспечивает никакого асимптотического преимущества по сравнению с атакой исчерпывающего поиска и атакой с табличным поиском при использовании для решения задачи поиска одного ключа. Вместо этого, они предложили добавить множество процессоров как другой компромиссный элемент, создавая атаку с компромиссом между временем-памятью-процессором. Главным моментом спора была стоимость решения по отношению к стоимости машины (или процессоров). Этот новый подход предназначался для уменьшения стоимости одного решения путем решения многих задач поиска сразу. Подход был использован для атаки двойного DES с использованием процессоров и слов памяти, для а также особой архитектуры из группы процессоров, разделяющих большую память через сортирующе-коммутирующую сеть, ответственную за ускорение сопоставления частных значений результатов шифрования/расшифрования и кандидатов ключа. Было заявлено, что вообще с помощью нового подхода многократное шифрование с m независимыми ключами является менее защищенным, чем схема шифрования с использованием единственного ключа с такой же полной длиной как длина m ключей.

Другое усовершенствование по компромиссному решению между временем-памятью-процессором было заявлено в [189] Квингвеном и Янху, которое состояло в перераспределении рабочей нагрузки каждого параметра атаки m, l и t.

В [42] Борц и др. представили описание атаки с компромиссом между временем и памятью с использованием отличительных точек. Эта атака является разновидностью атаки Хэллмана и разработана независимо от атаки Стандерта и др. в [215]. Главным преимуществом метода Борца по сравнению с методом Хэллмана является значительное уменьшение числа доступов к памяти. Атака Борца была построена на идее Риверса [66, стр. 100].