ZKP не только в криптовалюте. Часть 1
Писать про Zero knowledge proof всегда тяжело, ведь какой нибудь plonk из крипты понять не каждый сможет, тем более описать простым языком. При этом сам zkp есть идея, имеющая определенные необходимые условия, при этом оставляющая реализацию на выбор.
Проблемы начинают возникать еще на подступах, ведь почти весь zkp держится на конечных полях (не путать с конченными), эллиптических кривых и теории групп.
Вот тут есть неплохой вводный материал для понимания идеи zkp https://teletype.in/@chpotl/zkp, мы же постараемся погрузиться чуть глубже.
Secure remote password
Проблема работы с паролями известна давно: компании как хотят хранят ваши пароли, довольно часто в plaintext - обычном тексте, не хешируя. Те же, кто хранят в хэше, часто передают по небезопасному протоколу данные вида (логин, пароль) и существует определенная атака под название MITM - man in the middle.
MAN IN THE MIDDLE
Смысл атаки «Человек посередине (от англ. Man-in-the-middle, MITM) заключается в том, что злоумышленник «пропускает» веб-трафик жертвы (возможно, путем изменения параметров DNS-сервера или файла hosts на машине жертвы) «через себя». В то время пока жертва считает, что работает напрямую, к примеру, с веб-сайтом своего банка, трафик проходит через промежуточный узел злоумышленника, который таким образом получает все отправляемые пользователем данные (логин, пароль, ПИН-код и т. п.).
Определение взято отсюда - https://encyclopedia.kaspersky.ru/glossary/man-in-the-middle-attack/
У данной проблемы существует давно решение, которое почти никто не использует - secure remote password.
Суть метода в том, что сервер не хранит пароль в отдельном хеше, а еще с определенными модификациями поверх, позволяющими скрыть пароль в момент передачи, делая его недоступным для "человека между". А также две итерации происходит, никаких non-interactive proofs. При этом метод достаточно простой и даже не нужны эллиптические кривые. Почему никто не использует - это другой вопрос.
Алгоритм srp
Обозначения
Соль - случайная строка, нужна для добавления сложности в перебор паролей
Хэш функция - криптографическая хэш функция, а-ля всем известные sha256, keccak и т.д.
SRP группа - состоит из одного простого очень большого числа и генератора - конечное поле.
Verifier - Сгенерированное число в SRP группе, которое будет хранить сервер и в котором спрятан пароль.
Регистрация
- Клиент генерирует случайную строку - соль. Нужна она для того, чтобы было сложнее перебрать пароли по хэшу, используется как приставка.
- Клиент передает логин, пароль и соль в хэш функцию чтобы получить х - временное поле.
- Потом генерирует кое-что, называемое verifier, используя полученный сверху x и SRP группу.
- После отправляет verifier, соль и srp группу с юзернеймом на сервер и сервер будет хранить эти данные (username, verifier, salt).
Аутентификация
- Клиент
- Отправляет запрос на соль и SRP группу под определенный логин.
- Создает случайное а - приватное, и на основе него A - публичное, уже в SRP группе. Хранит у себя в памяти a, A - отправляет на сервер.
- Сервер
- Генерирует случайное число b- приватное, а на его основе B публичное, уже в SRP группе (Аналогично с клиентом). Отправляет Соль, SRP группу и B клиенту.
- Что происходит
Верификация вычислений
- Клиент проводит вычисления поверх хэша от пароля с солью, используя общий ключ (хэш от A и B) и отправляет результат на сервер
- Сервер проверяет результат и верифицирует его. Если не проходит проверку, то отменяет аутентификацию.
- Если же все успешно, то отправляет клиенту другие вычисления поверх пароля и уже с полученным результатом от клиента.
- Клиент проверяет полученные данные и может удостовериться, что это тот сервер.
В итоге они проверили друг друга, совершили небольшое количество итераций и могут использовать общий ключ, полученный от A и B, как симметричный ключ.
Вот тут есть реализации на вики https://en.wikipedia.org/wiki/Secure_Remote_Password_protocol#Implementations
Вот тут моя на Rust, склоненная от другого проекта https://github.com/valpaq/srp6-rs