1. Введение

Пароли остаются самым распространённым методом аутентификации пользователей благодаря своей простоте и гибкости. Следовательно, подбор паролей является критически важным компонентом исследований в области кибербезопасности, необходимым как для тестирования на проникновение (например, пентестинг, восстановление паролей), так и для оценки защищённости систем. Традиционные методы, от словарных атак на основе правил до статистических моделей, таких как цепи Маркова и PCFG, имеют внутренние ограничения в масштабируемости и адаптивности. Появление глубокого обучения, в частности авторегрессионных нейронных сетей, обещало смену парадигмы, позволяя изучать сложные распределения паролей непосредственно из данных. Однако сохраняется серьёзное узкое место: стандартный метод генерации случайной выборки, используемый с этими моделями, крайне неэффективен, производит дубликаты и не имеет оптимального порядка, что резко замедляет практические атаки на пароли. В данной статье представлен SOPG (Search-Based Ordered Password Generation — поисковое упорядоченное генерирование паролей), новый метод, предназначенный для генерации паролей из авторегрессионной модели в приблизительном порядке убывания вероятности, что революционно повышает эффективность нейросетевого подбора паролей.

2. Предпосылки и связанные работы

2.1 Традиционные методы подбора паролей

Ранние подходы полагались на словарные атаки и вручную созданные правила преобразования (например, John the Ripper). Хотя они просты, этим методам не хватает теоретической основы, и их эффективность сильно зависит от экспертных знаний. Распространение утечек паролей в крупных масштабах (например, RockYou в 2009 году) позволило использовать вероятностные методы, основанные на данных. Модели Маркова (например, OMEN) и Вероятностные контекстно-свободные грамматики (PCFG) стали значительным шагом вперёд, систематически моделируя структуры и вероятности паролей. Однако они часто страдают от переобучения и с трудом генерируют разнообразный и большой набор правдоподобных паролей, что ограничивает их покрытие.

2.2 Подходы на основе нейронных сетей

Модели глубокого обучения, включая Генеративно-состязательные сети (GAN), такие как PassGAN, и Вариационные автоэнкодеры (VAE), такие как VAEPass, изучают базовое распределение наборов данных паролей. Совсем недавно авторегрессионные модели, особенно основанные на архитектуре Transformer (например, PassGPT), показали превосходную производительность, моделируя пароли как последовательности и предсказывая следующий токен на основе предыдущих. Эти модели эффективнее улавливают дальние зависимости. Фунментальный недостаток всех этих нейросетевых подходов — использование по умолчанию случайной выборки (например, nucleus sampling, top-k sampling) для генерации паролей, что по своей природе неупорядоченно и приводит к повторениям.

3. Метод SOPG

3.1 Основная концепция и мотивация

Ключевая идея SOPG заключается в том, что для эффективной атаки подбора паролей сгенерированный список должен быть без повторов и упорядочен от наиболее вероятных к наименее вероятным. Случайная выборка не соответствует ни одному из этих критериев. SOPG решает эту проблему, рассматривая авторегрессионную модель как вероятностный ориентир для систематического алгоритма поиска, аналогичного поиску по лучу (beam search), но оптимизированного для генерации полного упорядоченного набора уникальных кандидатов, а не одной наилучшей последовательности.

3.2 Алгоритм поиска и упорядоченная генерация

SOPG использует стратегию поиска на основе очереди с приоритетами в пространстве возможных паролей. Он начинается с начального токена (например, начала последовательности) и итеративно расширяет частичные пароли. На каждом шаге он использует нейронную сеть для предсказания вероятностей следующего возможного символа. Вместо случайной выборки он стратегически исследует ветви, отдавая приоритет расширениям, которые ведут к полным паролям с наивысшей вероятностью. Этот процесс систематически перечисляет пароли в почти оптимальном порядке, эффективно выполняя направленный обход вероятностного распределения модели.

3.3 Архитектура модели SOPGesGPT

Авторы реализуют свой метод в SOPGesGPT — модели для подбора паролей, построенной на архитектуре GPT (Generative Pre-trained Transformer). Модель обучается на реальных утечках паролей, чтобы изучить совместное вероятностное распределение $P(x_1, x_2, ..., x_T)$ токенов пароля. Авторегрессионная природа GPT, где $P(x_t | x_{

4. Технические детали и математическая формулировка

Для авторегрессионной модели, определяющей вероятность пароля $\mathbf{x} = (x_1, x_2, ..., x_T)$ как: $$P(\mathbf{x}) = \prod_{t=1}^{T} P(x_t | x_1, ..., x_{t-1})$$ Цель SOPG — сгенерировать последовательность $\mathbf{x}^{(1)}, \mathbf{x}^{(2)}, ...$ такую, что $P(\mathbf{x}^{(1)}) \geq P(\mathbf{x}^{(2)}) \geq ...$ и $\mathbf{x}^{(i)} \neq \mathbf{x}^{(j)}$ для $i \neq j$.

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

5. Результаты экспериментов и анализ

Покрытие

35.06%

Результат SOPGesGPT на тестовом наборе

Улучшение относительно PassGPT

81%

Более высокий процент покрытия

Эффективность вывода

Намного меньше

Требуется паролей по сравнению со случайной выборкой

5.1 Сравнение со случайной выборкой

В статье сначала демонстрируется фундаментальное преимущество SOPG перед случайной выборкой на одной и той же базовой модели GPT. Для достижения того же процента покрытия (доли взломанных тестовых паролей) SOPG требует на порядки меньше сгенерированных паролей и обращений к модели. Это связано с тем, что каждый пароль, сгенерированный SOPG, уникален и имеет высокую вероятность, тогда как случайная выборка тратит вычисления на дубликаты и маловероятные варианты. Это напрямую приводит к более быстрым атакам и снижению вычислительных затрат.

5.2 Сравнение с современными методами

В тесте на одном сайте SOPGesGPT сравнивается с основными эталонными методами: OMEN (Марков), FLA, PassGAN (GAN), VAEPass (VAE) и современным PassGPT (Transformer со случайной выборкой). Результаты однозначны. SOPGesGPT достигает процента покрытия 35.06%, превосходя PassGPT на 81%, VAEPass на 380%, PassGAN на 421%, FLA на 298% и OMEN на 254%. Это устанавливает новый современный уровень, подчёркивая, что метод генерации (SOPG) так же важен, как и архитектура модели.

5.3 Ключевые метрики производительности

Эффективная скорость: Доля сгенерированных паролей, которые являются реальными (совпадают с паролем в тестовом наборе). SOPGesGPT также лидирует по этой метрике, что указывает на генерацию не только большего количества, но и более качественных вариантов.
Эффективность генерации: Измеряется количеством обращений/выводов модели, необходимых для взлома заданного процента паролей. Упорядоченный подход SOPG обеспечивает крутую кривую эффективности, взламывая множество паролей при очень малом количестве обращений.
Описание графика: Гипотетический график показал бы две линии: одна для «Покрытие при случайной выборке vs. #Сгенерированных паролей», медленно растущую и асимптотическую, с длинным хвостом дубликатов. Линия «Покрытие SOPG vs. #Сгенерированных паролей» резко и почти линейно возрастала бы в начале, выходя на плато позже, демонстрируя почти оптимальный порядок подбора.

6. Аналитическая структура и пример

Структура: Квадрант эффективности подбора паролей. Мы можем анализировать любую систему подбора паролей по двум осям: (1) Качество модели (способность изучать истинное распределение паролей) и (2) Оптимальность генерации (способность выводить варианты в порядке убывания вероятности без потерь).

  • Квадрант I (Низкое качество модели, низкая оптимальность): Традиционные атаки на основе правил.
  • Квадрант II (Высокое качество модели, низкая оптимальность): PassGPT, PassGAN — мощные модели, ограниченные случайной выборкой.
  • Квадрант III (Низкое качество модели, высокая оптимальность): Упорядоченные Марковские/PCFG — ограниченные модели, но эффективная генерация.
  • Квадрант IV (Высокое качество модели, высокая оптимальность): SOPGesGPT — целевое состояние, сочетающее высокопроизводительную нейросетевую модель с оптимальным алгоритмом генерации SOPG.

Пример (без кода): Рассмотрим модель, которая знает, что вероятность пароля "password123" равна $10^{-3}$, а "xq7!kLp2" — $10^{-9}$. Случайный выборщик может потребовать миллионов попыток, чтобы попасть на "password123". SOPG, используя свой поиск, определит и выведет "password123" в числе самых первых вариантов, немедленно увеличив покрытие. Это упорядоченное целеполагание является источником его впечатляющего выигрыша в эффективности.

7. Перспективы применения и направления развития

Проактивные проверки стойкости паролей: SOPG может стать основой для нового поколения индикаторов стойкости паролей в реальном времени, которые не просто проверяют словари, а симулируют современную эффективную атаку, давая пользователям более реалистичную оценку риска.
Цифровая криминалистика и законное восстановление: Ускорение восстановления паролей для санкционированных расследований на изъятых устройствах.
Состязательное обучение для систем аутентификации: Использование списков, сгенерированных SOPG, для стресс-тестирования и усиления систем аутентификации против интеллектуальных атак.
Направления будущих исследований:

  • Гибридные модели: Комбинирование упорядоченной генерации SOPG с другими генеративными архитектурами (например, диффузионными моделями) для паролей.
  • Адаптивный/онлайн SOPG: Модификация поиска в реальном времени на основе обратной связи от целевой системы (например, ответов на ограничение скорости).
  • За пределами паролей: Применение парадигмы упорядоченной генерации к другим областям безопасности, таким как генерация вероятных фишинговых URL или вариантов вредоносного ПО.
  • Защитные меры: Исследования по обнаружению и противодействию атакам, использующим стратегии упорядоченной генерации.

8. Ссылки

  1. J. Bonneau, "The Science of Guessing: Analyzing an Anonymized Corpus of 70 Million Passwords," IEEE Symposium on Security and Privacy, 2012.
  2. M. Weir, S. Aggarwal, B. de Medeiros, and B. Glodek, "Password Cracking Using Probabilistic Context-Free Grammars," IEEE Symposium on Security and Privacy, 2009.
  3. A. Radford, K. Narasimhan, T. Salimans, and I. Sutskever, "Improving Language Understanding by Generative Pre-Training," OpenAI, 2018. (Основополагающая статья по GPT)
  4. B. Hitaj, P. Gasti, G. Ateniese, and F. Perez-Cruz, "PassGAN: A Deep Learning Approach for Password Guessing," International Conference on Applied Cryptography and Network Security (ACNS), 2019.
  5. D. Pasquini, G. Ateniese, and M. Bernaschi, "Unleashing the Tiger: Inference Attacks on Split Learning," ACM SIGSAC Conference on Computer and Communications Security (CCS), 2021. (Включает обсуждение вывода паролей).
  6. M. J. H. Almeida, I. M. de Sousa, and N. Neves, "Using Deep Learning for Password Guessing: A Systematic Review," Computers & Security, 2023.

9. Оригинальный анализ и экспертное заключение

Ключевое понимание

Прорыв статьи заключается не в новой нейросетевой архитектуре, а в фундаментальном переосмыслении проблемы. В течение многих лет сообщество, занимающееся подбором паролей, следуя тенденциям в NLP, было одержимо созданием всё более крупных и лучших оценщиков плотности (часть GPT). SOPG правильно определяет, что для конечной задачи взлома стратегия декодирования имеет первостепенное значение. Это разница между наличием идеальной карты минного поля (модель) и знанием того, как пересечь его, не сделав ни одного лишнего шага (SOPG). Это смещает приоритет исследований с чистой ёмкости модели на эффективные алгоритмы вывода поверх этих моделей — урок, который другие области генеративного ИИ усвоили ранее (например, поиск по лучу в машинном переводе).

Логическая последовательность

Аргументация убедительна: 1) Эффективность атаки на пароли определяется кривой попаданий в зависимости от количества попыток. 2) Авторегрессионные модели дают вероятности на токен. 3) Случайная выборка из этого распределения крайне неоптимальна для создания упорядоченного списка попыток. 4) Следовательно, нам нужен алгоритм поиска, который использует модель как оракул для явного построения наиболее вероятных последовательностей в первую очередь. Скачок от осознания проблемы (3) к инженерному решению (4) — вот где заключается новизна. Связь с классическими алгоритмами поиска в информатике (A*, beam) очевидна, но её адаптация к обширному структурированному пространству выходных данных паролей нетривиальна.

Сильные стороны и недостатки

Сильные стороны: Эмпирические результаты ошеломляют и не оставляют сомнений в превосходстве SOPG в стандартной офлайн-оценке на одном сайте. Аргумент эффективности теоретически обоснован и практически подтверждён. Это общий метод, применимый к любой авторегрессионной модели, а не только к их реализации GPT.
Недостатки и вопросы: Оценка, хотя и впечатляющая, всё ещё проводится в лабораторных условиях. Реальные атаки сталкиваются с адаптивной защитой (ограничение скорости, блокировки, honeywords), и в статье не тестируется устойчивость SOPG в таких сценариях. Вычислительные накладные расходы самого алгоритма поиска на один сгенерированный пароль, вероятно, выше, чем для одной случайной выборки, хотя общий выигрыш в эффективности положителен. Также присутствует этический вопрос: хотя авторы позиционируют метод для защитного использования, этот инструмент значительно снижает барьер для высокоэффективных атак. Область должна бороться с двойственным характером таких достижений, подобно дискуссиям вокруг генеративных моделей ИИ, таких как CycleGAN или больших языковых моделей.

Практические выводы

Для специалистов по безопасности: Эта статья — сигнал к пробуждению. Политики паролей должны развиваться дальше простой блокировки слов из словаря. Защитникам необходимо начать стресс-тестировать свои системы против упорядоченных атак, подобных SOPG, которые теперь являются новым эталоном. Инструменты, такие как Have I Been Pwned или zxcvbn, должны включать эти передовые методы генерации для более реалистичной оценки стойкости.
Для исследователей: Эстафета передана. Следующий рубеж — уже не просто модель, а адаптивная и эффективная по запросам генерация. Можем ли мы создать модели, которые учатся на частичной обратной связи от атаки? Можем ли мы разработать защитные модели, которые обнаруживают и сбивают с толку упорядоченную генерацию? Кроме того, как отмечают такие учреждения, как NIST в своих руководствах по цифровой идентичности, долгосрочное решение заключается в переходе за пределы паролей. Это исследование одновременно демонстрирует пик возможностей подбора паролей и подчёркивает его внутренние ограничения, подталкивая нас к аутентификации без паролей. SOPG — это и мастерский завершающий ход в подборе паролей, и веский аргумент за его отмену.