Сервер для незаметного подбора паролей: Комбинация таблиц Хеллмана и протоколов PIR

Содержание

• 1. Введение
• 2. Предварительные сведения
  • 2.1 Таблицы обратного хеширования
  • 2.2 Приватный информационный поиск (PIR)
• 3. Обзор решения
• 4. Технические детали и построение алгоритма
• 5. Протоколы PIR и анализ сложности
• 6. Результаты экспериментов
• 7. Заключение и дальнейшая работа
• 8. Оригинальный анализ и экспертное мнение
• 9. Технические детали и математическая формулировка
• 10. Структура анализа и пример использования
• 11. Будущие применения и направления
• 12. Ссылки

1. Введение

В данной статье рассматривается важная проблема конфиденциальности в операциях наступательной безопасности: выполнение подбора паролей через сторонний сервер без раскрытия целевых хешей. Сценарий предполагает наличие пентестера с ограниченными локальными ресурсами (например, смартфоном), которому необходимо отправлять запросы к большим предварительно вычисленным таблицам хешей (таким как Rainbow или Hellman tables), размещённым удалённо. Ключевая проблема заключается в построении сервера для незаметного подбора паролей, где сервер не может узнать, какие пары пароль-хеш пытается подобрать клиент, тем самым сохраняя операционную секретность.

2. Предварительные сведения

2.1 Таблицы обратного хеширования

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

• Таблицы Хеллмана (1980): Компромисс между временем и памятью с использованием цепочек хешей и паролей, хранятся только начальные и конечные точки цепочек.
• Выделенные точки Ривеста (1982): Оптимизация с использованием специальных «выделенных» значений хешей в качестве конечных точек цепочек для уменьшения количества поисков.
• Радужные таблицы (Оешлин, 2003): Используют разные функции редукции на каждом шаге цепочки, обычно быстрее, но менее подходят для предложенной модели запросов на основе PIR.

В статье утверждается, что для данного конкретного применения таблицы Хеллмана (или их варианты с выделенными точками) более совместимы с протоколами PIR, чем радужные таблицы.

2.2 Приватный информационный поиск

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

1. Генерация запроса (Клиент)
2. Передача запроса
3. Обработка запроса (Сервер)
4. Передача ответа
5. Декодирование ответа (Клиент)

Сложность измеряется как $O_C$ (обработка клиентом), $O_S$ (обработка сервером) и $O_T$ (передача). Фундаментальная нижняя граница заключается в том, что $O_S$ должно быть как минимум $O(n)$ для обеспечения приватности, что означает, что сервер должен выполнять работу, пропорциональную размеру базы данных.

3. Обзор решения

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

4. Технические детали и построение алгоритма

Построение сосредоточено на адаптации таблиц Хеллмана для PIR. Таблица Хеллмана определяется криптографической хеш-функцией $H$ и функцией редукции $R$. Цепочка начинается с открытого текста $SP_i$ и итеративно вычисляется: $X_0 = SP_i$, $X_{j+1} = H(R(X_j))$, сохраняя только $(SP_i, EP_i)$, где $EP_i$ — конечное значение после $t$ шагов. Чтобы проверить хеш $h$, клиент вычисляет цепочку длиной $t$, начиная с $h$, проверяя на каждом шаге, совпадает ли промежуточное значение с сохранённой конечной точкой. Протокол PIR используется для приватного получения этих сравнений конечных точек из таблицы сервера.

5. Протоколы PIR и анализ сложности

В статье анализируются вычислительные и коммуникационные накладные расходы. Используя стандартный вычислительный протокол PIR (например, основанный на предположении о квадратичной вычетности), стоимость обработки на стороне сервера $O_S$ масштабируется с размером таблицы. Стоимость клиента $O_C$ и объём передачи данных $O_T$ значительно ниже, но не тривиальны. Анализ показывает, что хотя PIR вносит накладные расходы по сравнению с запросом в открытом виде, это необходимая цена за сильную приватность запросов. Выбор таблиц Хеллмана вместо радужных таблиц здесь оправдан, поскольку радужные таблицы требуют проверки нескольких столбцов с разными функциями редукции, что приводит к большему количеству PIR-запросов и более высокой общей стоимости.

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

Прототип был реализован на Python. Эксперименты продемонстрировали осуществимость подхода. Ключевые метрики включали:

• Время запроса: Общее время для попытки незаметного подбора с учётом вычислений PIR и задержки связи.
• Нагрузка на сервер: Вычислительная нагрузка на сервер на один запрос, подтверждающая теоретическую границу $O(n)$.
• Процент успеха: Вероятность успешного подбора хеша при заданном покрытии таблицы, что соответствует стандартным вероятностям успеха для таблиц Хеллмана.

Результаты подтвердили работоспособность системы, но подчеркнули компромисс производительности: приватность достигается ценой увеличения вычислений на сервере на один запрос по сравнению с не-приватным сервисом.

7. Заключение и дальнейшая работа

В статье успешно продемонстрирована новая архитектура сервера для незаметного подбора паролей. Направления для будущей работы включают:

• Исследование более эффективных протоколов PIR для снижения $O_S$ и $O_T$.
• Изучение использования доверенных сред исполнения (TEE), таких как Intel SGX, в качестве альтернативы или дополнения к криптографическому PIR.
• Расширение модели на распределённые или многосерверные настройки PIR для потенциального улучшения производительности.

8. Оригинальный анализ и экспертное мнение

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

Логическая последовательность: Аргументация логически обоснована. 1) Определение модели угроз: ненадёжный сторонний сервер. 2) Выбор подходящего криптографического примитива: вычислительный PIR для одиночной базы данных, что является единственным жизнеспособным вариантом для этого сценария с одним сервером без сговора. 3) Адаптация примитива подбора: выбор таблиц Хеллмана вместо радужных таблиц, потому что их структура требует меньше, более детерминированных PIR-запросов на попытку подбора. Это важное инженерное решение, демонстрирующее глубокие знания предметной области. Последовательность от проблемы к криптографическому инструменту и системной интеграции является последовательной.

Сильные стороны и недостатки: Основная сила — новизна и прямая применимость. Прототип доказывает жизнеспособность концепции. Однако недостатки практические. Накладные расходы PIR на производительность огромны. Как отмечают авторы, работа сервера составляет $O(n)$. Для больших таблиц (терабайты) это неприемлемо для коммерческого сервиса. Это решение, которое ставит идеальную приватность выше какой-либо видимости эффективности. Кроме того, оно защищает только запрос. Сервер всё ещё знает, что клиент выполняет операцию подбора, чего может быть достаточно для срабатывания тревог в некоторых юрисдикциях. По сравнению с появляющимися подходами на основе полностью гомоморфного шифрования (FHE), этот метод на основе PIR проще, но гораздо менее гибок.

Практические выводы: Для специалистов по безопасности это план для создания инструментов наступательной безопасности с высокой степенью гарантии и сохранением приватности. Для исследователей это открывает направление работ по эффективному, пригодному к использованию PIR. Следующий непосредственный шаг — сравнить производительность этого подхода с подходом на основе TEE (например, запуск логики подбора внутри анклава SGX). TEE обрабатывал бы вычисления приватно с потенциально меньшими накладными расходами, чем криптографический PIR, хотя это вводит доверие к производителю оборудования. Долгосрочное видение должно быть гибридной моделью: использовать PIR для начального, наиболее чувствительного поиска по индексу, а, возможно, доверенное оборудование для последующих шагов, балансируя предположения о доверии и производительности. Эта работа, подобно основополагающей статье CycleGAN, которая творчески объединила сети для непарного перевода изображений, показывает, как объединение двух зрелых технологий (таблиц Хеллмана и PIR) может создать новое решение для узкой, но важной проблемы.

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

Основа цепочки Хеллмана для хеш-функции $H$ и функции редукции $R$ определяется итеративно. Для заданного начального открытого текста $P_0$: $$X_0 = P_0$$ $$X_{k+1} = H(R(X_k)) \quad \text{для } k = 0, 1, ..., t-1$$ Конечная точка цепочки — $X_t$. Таблица хранит пары $(P_0, X_t)$. Чтобы обратить хеш $h$, вычисляют пробную цепочку от $h$: $Y_0 = h$, $Y_1 = H(R(Y_0))$, ..., $Y_t = H(R(Y_{t-1}))$. На каждом шаге $j$ проверяют, является ли $R(Y_j)$ выделенной точкой или совпадает ли $Y_j$ с сохранённой конечной точкой $X_t$, что запускает пересчёт цепочки для нахождения прообраза. В версии, адаптированной для PIR, проверка против списка сохранённых конечных точек сервера выполняется через PIR-запрос по индексу, соответствующему $R(Y_j)$ или $Y_j$.

10. Структура анализа и пример использования

Пример использования: Безопасное тестирование на проникновение как услуга (PTaaS)
Представьте облачную платформу PTaaS, предлагающую аудит паролей. Компания-клиент загружает список хешей паролей из своей собственной системы для проверки безопасности. Используя стандартный сервис, облачный провайдер узнаёт, каким конкретным хешам соответствуют пароли компании, что является потенциальной утечкой. Используя структуру незаметного сервера:

1. Инструмент аудита клиента предварительно обрабатывает каждый целевой хеш $h$.
2. Для каждого $h$ он локально вычисляет необходимые индексы $i_1, i_2, ... i_k$ в таблицах Хеллмана провайдера.
3. Он использует протокол PIR для генерации зашифрованных запросов для этих индексов и отправляет их на сервер PTaaS.
4. Сервер обрабатывает все запросы (выполняя работу над всей своей базой данных) и возвращает зашифрованные блоки данных.
5. Клиент расшифровывает ответы и обрабатывает их локально, чтобы увидеть, были ли найдены совпадения цепочек, восстанавливая открытые тексты паролей.

На протяжении всего этого процесса провайдер PTaaS видит только зашифрованные, похожие на случайные запросы и ничего не узнаёт о том, какие хеши тестировал клиент, тем самым сохраняя конфиденциальность внутреннего набора паролей клиента.

11. Будущие применения и направления

Принципы этого исследования выходят за рамки подбора паролей:

• Приватный поиск в базах данных угроз: Запрос индикаторов компрометации (IOC) из общей базы данных без раскрытия собственных активов.
• Конфиденциальное сопоставление последовательностей ДНК: Больница могла бы запрашивать геномную базу данных на наличие маркеров заболеваний, не раскрывая полный геном пациента.
• Приватная фильтрация при анализе логов: Поиск шаблонов атак в общих журналах безопасности без раскрытия конкретных шаблонов, к которым уязвима ваша организация.
• Сближение с полностью гомоморфным шифрованием (FHE) является ключевым направлением. В то время как PIR скрывает шаблон доступа, FHE могло бы позволить серверу выполнить всё вычисление подбора на зашифрованных данных, возвращая только зашифрованный результат. Проекты, такие как Microsoft SEAL и OpenFHE, делают это более практичным.
• Интеграция с дифференциальной приватностью могла бы добавить слой статистической приватности, гарантируя, что даже успех или неудача запроса не раскрывают слишком много информации.

12. Ссылки

1. Calvo, A., Futoransky, A., & Sarraute, C. (2013). An Oblivious Password Cracking Server. arXiv preprint arXiv:1307.8186.
2. Hellman, M. (1980). A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory, 26(4), 401-406.
3. Rivest, R. L. (1982). How to reuse a "write-once" memory. (MIT Laboratory for Computer Science Technical Report).
4. Oechslin, P. (2003). Making a faster cryptanalytic time-memory trade-off. Advances in Cryptology - CRYPTO 2003 (pp. 617-630). Springer.
5. Chor, B., Goldreich, O., Kushilevitz, E., & Sudan, M. (1995). Private information retrieval. Proceedings of IEEE 36th Annual Symposium on Foundations of Computer Science (pp. 41-50). IEEE.
6. Zhu, J. Y., Park, T., Isola, P., & Efros, A. A. (2017). Unpaired image-to-image translation using cycle-consistent adversarial networks. Proceedings of the IEEE international conference on computer vision (pp. 2223-2232). (Цитируется как аналогичный пример творческого объединения технологий).
7. Microsoft Research. (n.d.). Microsoft SEAL (Simple Encrypted Arithmetic Library). Retrieved from https://www.microsoft.com/en-us/research/project/microsoft-seal/