Конфиденциальный подбор паролей: протокол для безопасного восстановления хэшей

Содержание

Введение

Пароли остаются доминирующей формой аутентификации пользователей, несмотря на стремление отрасли к решениям без паролей. Хранение хэшей паролей является стандартной практикой, но проверка их стойкости путем взлома требует значительных ресурсов. Передача этой задачи сторонним серверам создает серьезные риски для конфиденциальности, поскольку раскрываются как хэш-образ, так и восстановленный открытый текст. В данной статье представлен протокол Privacy-Preserving Password Cracking (3PC), который позволяет клиенту использовать вычислительные мощности третьей стороны для взлома хэшей, не раскрывая целевой хэш или полученный пароль.

Протокол 3PC

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

2.1 Core Mechanism & Predicate Function

Протокол построен на концепции предикатного шифрования, адаптированной для хеш-функций. Клиент не отправляет целевой хеш $H(p)$ напрямую. Вместо этого он отправляет анонимное множество содержащий реальный хэш, смешанный с $k-1$ тщательно сконструированными ложными хэшами. Роль стороннего сервера заключается во взломе все Хэши в этом наборе с использованием предоставленного словаря паролей или набора правил.

Ключом является предикатная функция $f$. Сервер проверяет кандидатный пароль $p'$ по каждому хэшу в анонимном наборе. Функция определена так, что $f(H(p'), H_i) = 1$ тогда и только тогда, когда $H(p')$ совпадает с хэшем $H_i$ в наборе. Сервер возвращает набор кандидатных паролей, удовлетворяющих условию $f=1$ для любой хэш в наборе, не зная, для какого конкретного хэша (реального или ложного) было найдено совпадение.

2.2 Decoy Hash Generation & Anonymity Set

Генерация правдоподобных ложных целей критически важна для безопасности. Ложные хэши должны быть неотличимы от реального хэша для сервера. В статье предлагается генерировать ложные цели из распределения, соответствующего пространству выходных значений целевой хэш-функции (например, NTLM, SHA-256). Это обеспечивает $k$-анонимность для реального хэша. Клиент сохраняет правдоподобное отрицание, поскольку даже клиент не может криптографически доказать, какой хэш был исходной целью после отправки набора.

3. Technical Implementation & Analysis

3.1 Математические основы

Безопасность протокола может быть смоделирована вероятностно. Пусть $S$ — анонимный набор размера $k$, содержащий один реальный хэш $H_r$ и $k-1$ приманок $H_{d1}...H_{d(k-1)}$. Вероятность того, что сервер правильно угадает реальный хэш после наблюдения за набором и результатами взлома, составляет не более $1/k$, при условии идеальных приманок.

Утечка информации $\mathcal{L}$ для сервера может быть количественно оценена с использованием минимальной энтропии: $\mathcal{L} \leq -\log_2(1/k) = \log_2(k)$ бит. Клиент может контролировать утечку, регулируя $k$. Вычисление предикатной функции для кандидата $p'$ по всем $k$ хэшам может быть представлено в виде вектора: $\vec{R} = [f(H(p'), H_1), f(H(p'), H_2), ..., f(H(p'), H_k)]$. Совпадение на любой позиции возвращает $p'$ клиенту.

3.2 Performance & Scalability

В статье утверждается, что основным узким местом являются не криптографические операции, а операции ввода-вывода в секунду (IOPS) в конфигурации сервера для взлома (например, пропускная способность памяти GPU/FPGA). Поскольку сервер должен проверять каждый кандидат в пароли по всем $k$ хэшам, фактор работы теоретически возрастает линейно ($O(k)$). Однако, используя эффективную пакетную обработку на параллельном оборудовании, можно минимизировать фактическое замедление, приближаясь к заявленному поиску за «постоянное время» для практических значений $k$.

4. Experimental Results & Chart Description

Авторы реализовали прототип на архитектуре FPGA. Хотя конкретные показатели производительности не детализированы в предоставленном отрывке, в статье утверждается, что продемонстрирована практическая осуществимость протокола.

5. Пример случая применения аналитической структуры

Сценарий: Внештатный специалист по тестированию на проникновение (Client) извлекает NTLM-хэш из системы клиента. Политика паролей известна: 9-значный буквенно-цифровой состав. У тестировщика недостаточно мощности GPU для своевременного взлома.

Применение протокола 3PC:

1. Настройка клиента: Тестировщик устанавливает параметр конфиденциальности, например, $k=100$. Реальный хэш NTLM — это $H_{real}$. Программное обеспечение клиента генерирует 99 криптографически правдоподобных ложных хэшей NTLM, создавая анонимный набор $S$.
2. Взаимодействие с сервером: Тестировщик отправляет $S$ на коммерческий сервис взлома (Server) с запросом взлома всех хэшей с использованием словаря и правил для 9-символьных буквенно-цифровых паролей.
3. Обработка на сервере: Сервер запускает свои инструменты для взлома. Для каждого сгенерированного кандидата пароля он вычисляет его NTLM-хэш и проверяет соответствие всем 100 хэшам в $S$ в пакетной операции.
4. Возврат результата: Сервер возвращает список всех совпавших паролей. любой Хэш находится в $S$. Не указано, какой именно хэш совпал.
5. Фильтрация на стороне клиента: Тестировщик знает исходный хэш $H_{real}$. Он вычисляет хэш каждого возвращённого пароля, чтобы определить тот, который соответствует $H_{real}$, тем самым восстанавливая целевой пароль. Остальные возвращённые пароли соответствуют взломанным приманкам и отбрасываются.

Сервер узнаёт только то, что один из 100 хэшей принадлежал тестировщику, но не какой именно, и видит множество взломанных паролей, не зная об их значимости.

6. Core Insight & Analyst's Perspective

Ключевое понимание: Протокол 3PC — это остроумный, прагматичный хак, который превращает фундаментальное ограничение криптографии — однонаправленность хеш-функций — в функцию конфиденциальности. Он признаёт, что при взломе паролей цель состоит не в том, чтобы скрыть процесс но чтобы скрыть цель и результат в рамках собственного шума процесса. Речь идет не столько о "непреодолимой" криптографии, сколько о стратегическом сокрытии информации, что по сути аналогично тому, как микшерные сети, такие как Tor, скрывают источник сообщения в толпе.

Логическая последовательность: Логика убедительна, но зависит от критического, часто упускаемого из виду допущения: способности генерировать идеально неотличимые ложные цели. Если сервер может статистически отличить реальные хеши от ложных целей (например, на основе частоты в предыдущих утечках или паттернов в генерации хешей), модель $k$-анонимности рушится. Расширение в статье предикативного шифрования на хеш-функции является новым, но реальная безопасность зависит больше от качества алгоритма генерации ложных целей, чем от самой предикативной функции.

Strengths & Flaws: Его сильная сторона — прямая применимость к реальной, недостаточно охваченной нише (тестировщики на проникновение, заботящиеся о конфиденциальности) и относительно низкие криптографические накладные расходы на стороне клиента. Основной недостаток, как и у многих систем, обеспечивающих конфиденциальность, заключается в trust-but-verify Парадокс. Клиент должен доверять серверу в правильном выполнении протокола и в отсутствии вмешательства в процесс (например, путем логирования промежуточных состояний для корреляции временных меток). В отличие от продвинутых криптографических протоколов, таких как Fully Homomorphic Encryption (FHE), которые обеспечивают более сильные теоретические гарантии, но непрактично медленны (как видно на примере ранних реализаций, таких как основополагающая работа Джентри), 3PC жертвует абсолютной криптографической безопасностью ради практической эффективности. Это оправданный инженерный компромисс, но о нем необходимо четко заявлять.

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

7. Future Applications & Research Directions

• Аудит безопасности на основе соответствия требованиям: Позволяет регулируемым отраслям (финансы, здравоохранение) проводить строгое тестирование надежности паролей для учетных записей сотрудников, никогда не раскрывая хэши паролей, даже внутренним аудиторским группам, что способствует соблюдению GDPR/CCPA.
• Федеративный анализ хэшей: Несколько организаций могут совместно участвовать в усилиях по взлому дампа паролей общего угрозного актора (например, от группы вымогателей), при этом ни один участник не раскрывает свои собственные внутренние хэши и не видит хэши других.
• Интеграция с сервисами оповещения об утечках паролей: Пользователи могут отправлять в сервисы, такие как "Have I Been Pwned", анонимный набор, полученный из хэшей их паролей, не раскрывая фактический хэш, что повышает конфиденциальность при проверке на утечки.
• Направление исследований - Устойчивость к постквантовым атакам: Исследование безопасности протокола в постквантовом контексте. Хотя сами хеш-функции могут быть устойчивы к квантовым атакам, механизмы генерации ложных целей и предикатных функций требуют анализа на устойчивость к квантовым моделям противника.
• Направление исследований - Модели активного противника: Расширение модели безопасности для учета активно злонамеренных серверов, отклоняющихся от протокола (например, путем создания побочных каналов), имеет решающее значение для практического внедрения.

8. References

1. Bonneau, J., Herley, C., van Oorschot, P. C., & Stajano, F. (2012). The quest to replace passwords: A framework for comparative evaluation of web authentication schemes. IEEE Symposium on Security and Privacy.
2. FIDO Alliance. (2022). FIDO: The Future of Fast, Secure, Passwordless Sign-Ins. https://fidoalliance.org/
3. Gentry, C. (2009). A fully homomorphic encryption scheme (Докторская диссертация, Стэнфордский университет). (Для сравнения методов вычислительной конфиденциальности).
4. NIST. (2020). Руководство по цифровой идентификации (NIST Special Publication 800-63B).
5. Weir, M., Aggarwal, S., de Medeiros, B., & Glodek, B. (2009). Password cracking using probabilistic context-free grammars. IEEE Symposium on Security and Privacy.
6. Zhao, F., & Halderman, J. A. (2019). Измерение влияния сложности пароля на атаки методом подбора.USENIX Security Symposium.