SOPG: Поисковое упорядоченное генерирование паролей для авторегрессионных нейронных сетей

Содержание

1. Введение

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

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

2.1 Эволюция методов подбора паролей

Подбор паролей прошёл через различные этапы. Ранние методы полагались на атаки по словарю и вручную созданные правила модификации (например, John the Ripper), которые были эвристическими и зависели от опыта. Распространение утечек паролей в крупных масштабах (например, RockYou в 2009 году) позволило использовать статистические подходы, основанные на данных. Модель Маркова (Weir et al., 2009) и Вероятностная контекстно-свободная грамматика (PCFG) (Ma et al., 2014) предоставили более систематическую, основанную на вероятностях структуру для генерации, хотя они рисковали переобучением и не могли моделировать сложные, дальнодействующие зависимости в структурах паролей.

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

Модели глубокого обучения, в частности Генеративно-состязательные сети (GAN), такие как PassGAN (Hitaj et al., 2017), и авторегрессионные модели, такие как модели на основе архитектур LSTM или GPT, изучают распределение вероятностей паролей непосредственно из данных. Они могут генерировать высокоразнообразные и реалистичные пароли. Однако они обычно используют случайную выборку (например, полиномиальную выборку) из изученного распределения на каждом шаге генерации. Этот фундаментальный процесс не учитывает глобальный рейтинг полных вероятностей паролей, что приводит к неэффективности, которую SOPG призван решить.

3. Метод SOPG

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

SOPG переосмысливает генерацию паролей, превращая её из задачи стохастической выборки в задачу направленного поиска. Вместо случайного выбора следующего символа он использует алгоритм поиска (вероятно, вариант поиска по лучу или поиска по первому наилучшему совпадению) для исследования пространства возможных продолжений пароля, отдавая приоритет путям, ведущим к полным паролям с более высокой предполагаемой вероятностью. Цель — вывести список паролей в порядке, максимально приближенном к истинной сортировке по убыванию $P(пароль|модель)$.

3.2 Алгоритм поиска

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

3.3 Модель SOPGesGPT

Авторы реализуют свой метод на архитектуре на основе GPT, создавая SOPGesGPT. Модель GPT (например, трансформер только с декодером) обучается на наборах данных с утёкшими паролями для предсказания следующего символа в последовательности. Затем SOPG применяется как метод генерации/вывода поверх этой обученной модели, заменяя стандартную выборку.

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

Авторегрессионная модель определяет вероятность пароля $\mathbf{x} = (x_1, x_2, ..., x_T)$ как произведение условных вероятностей: $$P(\mathbf{x}) = \prod_{t=1}^{T} P(x_t | x_1, ..., x_{t-1})$$ где $x_t$ — символ на позиции $t$, а $T$ — длина пароля. Стандартная выборка выбирает $x_t \sim P(\cdot | x_1, ..., x_{t-1})$.

SOPG, концептуально, стремится находить и выводить последовательности $\mathbf{x}$ в порядке убывания $P(\mathbf{x})$. Это можно рассматривать как задачу поиска кратчайшего пути в дереве, где узлы — это префиксы, стоимость рёбер связана с $-\log P(x_t | префикс)$, а цель — перечислить пути (пароли) в порядке возрастания общей стоимости (т.е. убывания вероятности). Алгоритмы, такие как Поиск по единой стоимости (UCS) или его ограниченный вариант, Поиск по лучу с большой шириной луча и динамическим отсечением, могут достичь этого приблизительного упорядочивания. Ключевой момент заключается в том, что граница поиска приоритизируется по вероятностной оценке текущего пути.

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

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

В статье представлены убедительные результаты сравнения SOPG со стандартной случайной выборкой на одной и той же базовой модели. Ключевые выводы:

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

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

SOPGesGPT сравнивался с основными моделями подбора паролей: OMEN (Марков), FLA, PassGAN (GAN), VAEPass (VAE) и современным PassGPT. В односайтовом тесте:

• Процент покрытия: SOPGesGPT достиг 35.06%, превзойдя OMEN на 254%, FLA на 298%, PassGAN на 421%, VAEPass на 380% и PassGPT на 81%.
• Эффективность: В статье также заявляется о лидерстве по «эффективности», вероятно, метрике, связанной с качеством или результативностью рано сгенерированных паролей, что является основной силой SOPG.

Это демонстрирует, что метод генерации (SOPG) так же критичен для производительности, как и архитектура модели.

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

Структура для оценки моделей подбора паролей:

1. Архитектура модели и обучение: Какая лежащая в основе нейронная сеть (GAN, VAE, Авторегрессионный трансформер)? Как она обучается?
2. Метод генерации: Как пароли производятся из обученной модели? (например, Случайная выборка, Поиск по лучу, SOPG). Это ключевой фокус статьи.
3. Упорядочивание и эффективность: Производит ли метод пароли в полезном порядке (убывание вероятности)? Какова вычислительная/подборочная эффективность?
4. Разнообразие и дублирование: Генерирует ли он новые пароли или много дубликатов?
5. Производительность на тестах: Процент покрытия, Эффективность и скорость на стандартных наборах данных (например, RockYou).

Пример без кода: Рассмотрим двух злоумышленников, Алису и Боба, использующих одну и ту же обученную GPT-модель для паролей. Алиса использует стандартную случайную выборку. Боб использует SOPG. Чтобы взломать тестовый набор из 1000 паролей, программному обеспечению Алисы может потребоваться сгенерировать 10 миллионов предположений, из которых 30% — дубликаты, чтобы взломать 350. Программному обеспечению Боба, управляемому SOPG, может потребоваться сгенерировать всего 1 миллион уникальных предположений в оптимальном порядке, чтобы взломать те же 350. Атака Боба в 10 раз более эффективна по ресурсам и завершается быстрее.

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

Непосредственные применения:

• Проактивное тестирование стойкости паролей: Команды безопасности могут использовать модели, усиленные SOPG, для более эффективного аудита предлагаемых политик паролей, сначала генерируя наиболее вероятные векторы атаки.
• Криминалистическое восстановление паролей: Законные инструменты восстановления паролей могут интегрировать SOPG для увеличения успешности в рамках ограниченных временных/вычислительных бюджетов.

Направления будущих исследований:

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

8. Ссылки

1. Weir, M., Aggarwal, S., Medeiros, B., & Glodek, B. (2009). Password Cracking Using Probabilistic Context-Free Grammars. In IEEE Symposium on Security and Privacy.
2. Ma, J., Yang, W., Luo, M., & Li, N. (2014). A Study of Probabilistic Password Models. In IEEE Symposium on Security and Privacy.
3. Hitaj, B., Gasti, P., Ateniese, G., & Perez-Cruz, F. (2017). PassGAN: A Deep Learning Approach for Password Guessing. In International Conference on Applied Cryptography and Network Security.
4. Goodfellow, I., et al. (2014). Generative Adversarial Nets. Advances in Neural Information Processing Systems.
5. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., & Sutskever, I. (2019). Language Models are Unsupervised Multitask Learners. OpenAI Blog.
6. Melicher, W., et al. (2016). Fast, Lean, and Accurate: Modeling Password Guessability Using Neural Networks. In USENIX Security Symposium.

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