Атака полным перебором

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

Принцип работы

Атака полным перебором основывается на предположении, что пространство возможных значений (ключей, паролей) конечно. Алгоритм последовательно генерирует и проверяет каждый вариант из этого пространства, пока не будет найден искомый. Проверка может включать:

• Сравнение хеша пароля с эталонным значением.
• Попытку расшифровать блок данных с использованием сгенерированного ключа.
• Попытку аутентификации в системе (ввод логина и пароля).

Успех атаки гарантирован при условии, что истинное значение находится в пределах перебираемого множества. Время, необходимое для взлома, определяется как произведение размера пространства поиска на время проверки одного варианта. Математически это выражается формулой:

\[ T = N \cdot t \] где \( T \) — общее время, \( N \) — количество вариантов, \( t \) — время проверки одного варианта.

Для пароля длиной \( L \) символов из алфавита мощностью \( A \) (например, 26 букв, 10 цифр, 95 печатных символов ASCII) количество вариантов равно \( A^L \). Например, пароль из 8 символов латинского алфавита (только строчные буквы) имеет \( 26^8 \approx 2,09 \times 10^{11} \) вариантов. При скорости перебора 10 миллиардов вариантов в секунду (достижимо на современном GPU) взлом займёт около 20 секунд. Пароль из 12 символов с использованием всех 95 печатных символов ASCII даёт \( 95^{12} \approx 5,4 \times 10^{23} \) вариантов, что при той же скорости потребует более 1,7 миллиарда лет.

История

Метод полного перебора известен с древних времён как способ взлома простых шифров, таких как шифр Цезаря. С появлением механических и электромеханических вычислительных машин в XX веке брутфорс стал применяться для взлома более сложных систем.

• Вторая мировая война: Немецкая шифровальная машина «Энигма» теоретически имела пространство ключей около \( 1,58 \times 10^{20} \) вариантов. Однако благодаря конструктивным особенностям и ошибкам операторов союзники (в частности, польские и британские криптоаналитики) смогли существенно сократить пространство поиска, используя «бомбы» — электромеханические устройства, перебиравшие возможные настройки.
• 1970-е — 1980-е годы: С распространением компьютерных сетей и цифровых шифров (DES, 56-битный ключ — \( 7,2 \times 10^{16} \) вариантов) брутфорс оставался теоретически возможным, но практически нереализуемым из-за ограниченной вычислительной мощности.
• 1990-е — 2000-е годы: Рост производительности процессоров и появление специализированных устройств (FPGA, ASIC) сделали брутфорс реальным для коротких ключей. В 1997 году проект distributed.net организовал распределённый перебор 56-битного ключа DES, завершив его за 39 дней. В 1998 году EFF (Electronic Frontier Foundation) построила специализированное устройство «Deep Crack», взломавшее DES за 56 часов.
• 2010-е — 2020-е годы: Массовое использование графических процессоров (GPU) для параллельных вычислений многократно ускорило перебор. Специализированные программы (Hashcat, John the Ripper) используют GPU для взлома хешей паролей со скоростью до сотен миллиардов вариантов в секунду. Облачные вычисления и аренда мощностей сделали брутфорс доступным для широкого круга лиц.

Классификация методов

По типу перебираемого элемента

• Перебор ключей шифрования: применяется к криптосистемам. Например, перебор 128-битного ключа AES (\( 3,4 \times 10^{38} \) вариантов) считается практически невозможным при современном уровне технологий.
• Перебор паролей: наиболее распространённый вид. Включает как полный перебор всех комбинаций символов, так и более эффективные варианты (см. ниже).
• Перебор PIN-кодов: ограниченное пространство (например, 10 000 вариантов для 4-значного кода).

По стратегии перебора

• Прямой (линейный) брутфорс: последовательный перебор всех вариантов в заданном порядке (например, от «aaaa» до «zzzz»). Простейший, но наименее эффективный метод.
• Словарная атака: перебор не всех возможных комбинаций, а только тех, что содержатся в заранее составленном списке (словаре) наиболее вероятных паролей. Словари могут содержать миллионы записей (например, rockyou.txt). Этот метод значительно быстрее полного перебора, но не гарантирует успех, если пароль отсутствует в словаре.
• Гибридная атака: комбинация словарной атаки и перебора. Например, к каждому слову из словаря добавляются суффиксы (цифры, символы) или изменяется регистр. Позволяет находить пароли, основанные на реальных словах, но с небольшими модификациями.
• Атака по маске: перебор только тех вариантов, которые соответствуют известному шаблону. Например, если известно, что пароль состоит из 8 символов, начинается с заглавной буквы и заканчивается двумя цифрами, пространство поиска резко сокращается.
• Радужные таблицы: метод, использующий предварительно вычисленные цепочки хешей для ускорения поиска. Позволяет взламывать хеши паролей без повторного перебора, но требует больших объёмов памяти.

По способу реализации

• Локальный брутфорс: перебор выполняется на одном устройстве (компьютере, GPU, специализированном оборудовании). Ограничен производительностью этого устройства.
• Распределённый (сетевой) брутфорс: перебор распределяется между множеством устройств (кластеры, ботнеты, добровольные вычислительные сети). Примеры: проекты distributed.net, BOINC.
• Облачный брутфорс: аренда вычислительных мощностей в облачных провайдерах (AWS, Google Cloud, Azure) для выполнения перебора. Позволяет временно получить огромные ресурсы без капитальных затрат.

Применение

В криптоанализе

• Оценка стойкости шифров и хеш-функций. Если алгоритм имеет ключ длиной 40 бит (\( 1,1 \times 10^{12} \) вариантов), он считается нестойким, так как может быть взломан брутфорсом за разумное время.
• Взлом устаревших или ослабленных криптосистем (DES, RC4, MD5, SHA-1).

В компьютерной безопасности

• Восстановление забытых паролей к собственным данным (архивы, документы, базы данных).
• Аудит безопасности: проверка корпоративных паролей на устойчивость к перебору.
• Несанкционированный доступ: взлом учётных записей пользователей, почтовых ящиков, аккаунтов в социальных сетях.

В цифровой криминалистике

• Извлечение данных из зашифрованных устройств (жёсткие диски, смартфоны) при наличии судебного разрешения.

Методы защиты

Ограничение скорости попыток

• Throttling: искусственное замедление ответа сервера после каждой неудачной попытки (например, задержка 1 секунда).
• Rate limiting: блокировка IP-адреса после определённого числа неудачных попыток (например, 5 попыток за 10 минут).
• CAPTCHA: требование ввести код с картинки после нескольких неудачных попыток.

Усложнение пространства поиска

• Увеличение длины пароля: каждый дополнительный символ экспоненциально увеличивает количество вариантов. Рекомендуемая минимальная длина — 12 символов.
• Использование случайных символов: пароль должен содержать буквы разного регистра, цифры и специальные символы. Использование слов из словаря или личных данных (имя, дата рождения) резко снижает стойкость.
• Многофакторная аутентификация (MFA): даже при успешном переборе пароля злоумышленнику потребуется второй фактор (код из SMS, биометрия, аппаратный ключ).

Криптографические методы

• Соло́ное хеширование: добавление к паролю случайной строки (соли) перед хешированием. Делает атаку по радужным таблицам неэффективной, так как для каждого пароля требуется уникальная таблица.
• Key stretching: многократное применение хеш-функции (например, PBKDF2, bcrypt, scrypt, Argon2). Увеличивает время проверки одного варианта, делая перебор непрактичным. Например, bcrypt с коэффициентом стоимости 10 требует около 0,1 секунды для проверки одного пароля на современном CPU, что снижает скорость перебора до 10 вариантов в секунду.

Мониторинг и обнаружение

• Системы обнаружения вторжений (IDS) могут выявлять характерные паттерны брутфорса: множество неудачных попыток аутентификации с одного IP за короткое время.
• Логирование и анализ событий безопасности.

Интересные факты

• Самый длинный пароль, когда-либо взломанный публично с использованием брутфорса, имел длину 18 символов и состоял из строчных букв. Взлом занял несколько месяцев на распределённой сети.
• В 2012 году хакерская группа «Anonymous» (деятельность группы на территории РФ может быть признана нежелательной) опубликовала базу данных из 450 тысяч паролей, взломанных методом словарной атаки. Анализ показал, что наиболее популярными паролями были «123456», «password» и «qwerty».
• Существуют онлайн-сервисы, предоставляющие облачный брутфорс как услугу (Brute Force as a Service, BFaaS). Их использование для взлома чужих аккаунтов является незаконным в большинстве юрисдикций, включая Российскую Федерацию (ст. 272 УК РФ «Неправомерный доступ к компьютерной информации»).

Критика

Основной недостаток атаки полным перебором — её крайне низкая эффективность при работе с большими пространствами поиска. Для ключей длиной 128 бит и более (AES, ChaCha20) прямой перебор считается вычислительно невозможным при современном уровне развития технологий. Даже при использовании всех вычислительных мощностей Земли время взлома 128-битного ключа превышает возраст Вселенной. Однако квантовые компьютеры теоретически могут сократить это время: алгоритм Гровера позволяет найти искомый элемент в неупорядоченной базе данных за время, пропорциональное квадратному корню из числа элементов. Для 128-битного ключа это означает \( 2^{64} \) операций, что всё ещё остаётся практически невозможным, но значительно снижает запас прочности.

Источники

• Шнайер Б. «Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си». — М.: Триумф, 2002.
• Ferguson N., Schneier B., Kohno T. «Cryptography Engineering: Design Principles and Practical Applications». — Wiley, 2010.
• Менезес А., ван Орсхот П., Ванстон С. «Прикладная криптография». — М.: Вильямс, 2005.
• Документация к программам Hashcat и John the Ripper.
• Стандарты NIST (National Institute of Standards and Technology) по управлению паролями (SP 800-63B).