Как работают атаки перебором

Атака методом полного перебора на шифр проверяет каждый возможный ключ, пока не будет найден правильный. Для ключа длиной n бит существует 2^n возможных ключей. Для 3-битного ключа существует всего 8 вариантов, а для 56-битного — более 72 квадриллионов. Основная защита от полного перебора заключается в выборе ключей такого размера, чтобы исчерпывающий поиск был вычислительно невыполним за сколько-нибудь значимый срок.

DES (стандарт шифрования данных) использует 56-битный ключ, что даёт пространство примерно из 7,2 * 10^16 ключей. В 1977 году это казалось огромным пространством. В 1998 году машина Deep Crack, созданная EFF, взломала DES за 56 часов при стоимости 250 000 долларов. К 2006 году специализированный кластер мог взломать DES менее чем за 9 дней при стоимости ниже 10 000 долларов. Вывод был очевиден: 56 бит больше не обеспечивали достаточную защиту от мотивированного противника.

AES-128 использует 128-битные ключи, что даёт 2^128 возможных ключей — примерно 3,4 * 10^38. Если бы каждый атом наблюдаемой Вселенной был компьютером, выполняющим миллиард проверок ключей в секунду начиная с Большого взрыва, поиск даже не приблизился бы к завершению. Даже при экспоненциально более быстром оборудовании будущего 128-битные ключи, как ожидается, останутся защищёнными от классического полного перебора в обозримом будущем.

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

Современные GPU содержат тысячи ядер параллельной обработки, оптимизированных для арифметики с плавающей точкой. Hashcat — ведущий инструмент для взлома хешей с помощью GPU — может проверять более 100 миллиардов хешей MD5 в секунду на одном высокопроизводительном GPU. Установка с восемью GPU может проверять более 800 миллиардов вариантов в секунду. Поэтому неудачно выбранные пароли и слабые хеш-функции становятся уязвимыми для быстрого офлайн-взлома.

Интегральные схемы специального назначения — это микросхемы, разработанные исключительно для одного вычисления. Майнеры Bitcoin используют ASIC, которые вычисляют хеши SHA-256 со скоростью десятки терахешей в секунду, значительно опережая любой GPU. Хотя ASIC для Bitcoin выполняют операцию, отличающуюся от взлома паролей, принцип остаётся тем же: специализированное оборудование обеспечивает многократное ускорение по сравнению с оборудованием общего назначения при выполнении конкретных криптографических вычислений.

Закон Мура утверждал, что плотность транзисторов примерно удваивается каждые два года, что исторически приводило к сопоставимому росту вычислительной мощности. Длина ключа, считающаяся безопасной сегодня, должна оставаться безопасной на протяжении десятилетий будущего развития оборудования. Поэтому рекомендации по безопасности предусматривают значительный запас прочности. Для того чтобы AES-128 стал уязвимым для классического перебора, потребовалось бы ускорение вычислений в 2^64 раза, что намного превосходит любые правдоподобные прогнозы, основанные на законе Мура.

NIST SP 800-57 определяет уровни стойкости для криптографических алгоритмов. Стойкость 112 бит — текущий минимальный уровень для новых систем. Для долгосрочной защиты рекомендуется стойкость 128 бит. Симметричные ключи длиной 256 бит обеспечивают запас прочности по сравнению с классическими вычислительными угрозами, которые можно предвидеть сегодня. NIST не рекомендует уровни стойкости 80 бит и ниже: они считаются недостаточными для любого нового приложения.

Квантовый алгоритм поиска Гровера обеспечивает квадратичное ускорение неструктурированного поиска: это означает, что пространство ключей из N элементов можно просмотреть примерно за sqrt(N) шагов вместо N. Для AES-128 это фактически снижает стойкость до 64 бит против квантового противника. Для AES-256 эффективная стойкость против алгоритма Гровера составляет 128 бит, поэтому для постквантовой безопасности рекомендуются симметричные ключи длиной 256 бит.

Чтобы сохранить стойкость 128 бит против квантового компьютера, выполняющего алгоритм Гровера, симметричные ключи должны иметь длину не менее 256 бит. AES-256 уже имеет такую длину и считается устойчивым к квантовым атакам в симметричном шифровании. Для сравнения: удвоение длины ключа со 128 до 256 бит не удваивает объём вычислений для пользователя, работающего по назначению (оно добавляет лишь несколько раундов AES), но требует возведения в квадрат квантовых ресурсов злоумышленника.

Команды по безопасности используют инструменты перебора во время санкционированных аудитов паролей, чтобы выявлять слабые учётные данные раньше злоумышленников. Hashcat и John the Ripper запускают против экспортированных баз данных хешей паролей, чтобы определить, какую долю паролей можно взломать. Результаты аудита помогают улучшать политику паролей: устанавливать требования к минимальной длине, правила сложности и внедрять современные алгоритмы хеширования паролей, такие как bcrypt или Argon2.

Как квантовый алгоритм Гровера влияет на эффективную стойкость AES-128?

Перебор проверяет каждый возможный ключ; для защиты пространство ключей должно быть настолько большим, чтобы его практический перебор был невозможен. DES с длиной ключа 56 бит был взломан в 1998 году. Перебор 2^128 ключей AES-128 невозможен для классических компьютеров. Кластеры GPU офлайн взламывают хеши со скоростью сотни миллиардов в секунду. Квантовый алгоритм Гровера уменьшает битовую стойкость вдвое, поэтому для постквантовой стойкости 128 бит требуются ключи длиной 256 бит. NIST рекомендует для новых систем минимальную стойкость 128 бит.