Метод «грубой силы»

Метод «грубой силы» (brute-force attack) предполагает перебор всех возможных вариантов ключа шифрования до нахождения искомого ключа. Криптоаналитик должен перебрать все возможные ключи, т. е. применить в качестве ключа значение 0, затем 1, 2, 3 и т. д. до максимально возможного. В результате ключ шифрования обязательно будет найден.

Понятно, что необходим какой-либо критерий корректности найденного ключа. С атакой с известным открытым текстом все достаточно просто — при тестировании каждого ключа шифртекст расшифровывается (в результате получается некое значение АГ) и сравнивается с соответствующим ему открытым текстом, совпадение говорит о том, что искомый ключ найден.

Несколько сложнее с атакой на основе шифртекста. В этом случае необходимо наличие какой-либо дополнительной информации об открытом тексте, например, следующей.

Если открытый текст является осмысленным текстом на каком-либо языке, перехваченный шифртекст должен иметь достаточный размер для однозначного расшифровывания в осмысленный текст (минимально достаточный для этого размер называется точкой единственности). В основополагающей для современных симметричных криптосистем работе точка единственности для английского языка теоретически определена как 27 букв. Если сообщение короче, то при переборе возможно появление нескольких различных осмысленных текстов, каждому из которых соответствует некий кандидат в искомые ключи. При невозможности перехвата дополнительных шифртекстов невозможно определить, какое из осмысленных сообщений является верным, если это не ясно из контекста.

Если открытый текст состоит из бинарных данных, необходима какая-либо информация о том, что он из себя представляет. Если перехватывается архив, то при переборе ключей каждое значение должно рассматриваться как возможный заголовок архива. При другом потенциальном М это может быть РЕ-заголовок исполняемого файла для Windows, заголовок графического файла и т. д.

Стоит отметить, что многие средства шифрования информации внедряют в формат зашифрованного объекта контрольную сумму открытого текста для проверки его целостности после расшифровывания. Это может быть, например, имитоприставка, вычисленная согласно отечественному криптостандарту ГОСТ 28147-89, или просто CRC32. Главное, что такая контрольная сумма может быть идеальным эталоном при криптоанализе, вполне подходящим для определения верного ключа.

Защита от атак, выполняемых методом «грубой силы», весьма проста — достаточно лишь увеличить размер ключа. Понятно, что увеличение размера ключа на 1 бит увеличит возможное количество ключей (и среднее время атаки) в 2 раза.

Несмотря на простоту атаки методом «грубой силы», существуют различные методы улучшения ее эффективности, например, следующие.

Атака методом «грубой силы» простейшим образом распараллеливается: при наличии, скажем, миллиона компьютеров, участвующих в атаке, ключевое множество делится на миллион равных фрагментов, которые распределяются между участниками атаки.

Скорость перебора ключей может быть во много раз увеличена, если в переборе участвуют не компьютеры общего назначения, а специализированные устройства. В приводится пример микросхемы ORCA компании AT&T (технология ПЛИС), которая способна перебрать до 30 миллионов ключей DES в секунду. В той же работе рассмотрено применение для перебора ключей специализированных микросхем, каждая из которых способна перебрать до 200 миллионов ключей DES в секунду. Следует учесть, что приведенные в оценки даны на конец 1995 г. — сейчас перебор может осуществляться несравнимо быстрее.

Все эти методы были опробованы на американском стандарте шифрования DES.

Понятно, что с развитием вычислительной техники требования к размеру ключа шифрования постоянно возрастают. В той же работе был рекомендован 90-битный размер ключа в качестве абсолютно безопасного (причем с 20-летним запасом) на конец 1995 г. Сейчас подавляющее большинство алгоритмов шифрования используют ключи размером от 128 битов, что считается безопасным с примерно 80-летним запасом.

Современная вычислительная техника не позволяет «в лоб» атаковать 128-битный ключ полным перебором. Однако атаки методом «грубой силы» часто используются в контексте других атак — например, с помощью дифференциального криптоанализа (этот метод будет описан далее) сужается область возможных ключей, после чего выполняется перебор оставшихся вариантов.

Алгоритмы шифрования