Information

Founded
Location
Россия
Website
otus.ru
Employees
51–100 employees
Registered
Pull to refresh
604.06
Rating
OTUS. Онлайн-образование
Цифровые навыки от ведущих экспертов

Поговорим о PAKE

OTUS. Онлайн-образование corporate blogInformation SecurityCryptography
Original author: Matthew Green
А сейчас поговорим о информационной безопасности. Данная публикация приурочена к запуску курса «Криптографическая защита информации», который стартует уже 30 мая. Поехали.

Первое правило PAKE: никогда не говорить о PAKE. Второе правило PAKE гласит, что первое правило это нонсенс, поскольку PAKE или же Password Authenticated Key Exchange (рус. Обмен ключами с проверкой подлинности пароля) – это одна из самых полезных технологий, которая практически нигде не используется. Она должна быть внедрена везде, где только возможно, но все не так просто.




Чтобы понять, почему мы говорим о нонсенсе, давайте рассмотрим реальную проблему.

Допустим, я работаю с сервером, который хранит пароли пользователей. Есть традиционный способ хранения – хэшировать каждый пароль пользователя и хранить результат в базе данных паролей. Существует много идей, как обрабатывать процесс хэширования. Наиболее распространенной рекомендацией на сегодняшний день является использование функции хэширования жесткого пароля памяти (memory-hard password hashing function), такой как scrypt или argon2 (c уникальной солью) для каждого пароля), и после этого хранить уже хэшированный результат. Есть разные мнения по поводу того, какую хэш-функцию использовать и сможет ли она использовать некоторое секретное значение (называемое «перец»), но пока мы не будем об этом говорить.

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

Эта необходимость может привести к неприятным последствиям, если ваш сервер когда-либо будет скомпрометирован или если ваши разработчики допустят какую-нибудь глупую ошибку. Например, в начале прошлого года Twitter попросил всех своих пользователей ( а этот330 миллионов!) поменять пароли — потому что оказалось, что компания хранила текстовые (не хэшированные) пароли.

На данный момент проблема входа в систему никоим образом не противоречит преимуществам хэширования паролей. Однако необходимо найти лучшее решение: такое, при котором пароль никогда бы не отправлялся на сервер в открытом виде. Криптографический инструмент, который поможет нам этого добиться – это PAKE, и, в частности, новый протокол под названием OPAQUE, который мы рассмотрим в конце этой статьи.

Что такое PAKE?


Протокол PAKE, впервые предложенный Белловином и Мерриттом, является специфическим видом протокола обмена ключами. Протоколы обмена ключами (или “соглашения о ключах”) предназначены для того, чтобы помочь двум сторонам (назовем их клиентом и сервером) договориться об общем ключе, используя криптографию с открытым ключом. Самые ранние протоколы обмена ключами (например, классический Диффи-Хеллман) были неавторизованными, что делало их уязвимыми для атак типа man-in-the-middle. Отличительной особенностью протоколов PAKE является то, что клиент аутентифицируется на сервере с помощью пароля. По понятным причинам предполагается, что пароль или его хэш уже известны серверу, что и позволяет проводить проверку.

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


Идеализированное представление протокола PAKE. Входные данные с обоих сторон включают в себя некоторую случайность, которая здесь не показана. Подслушивающий не должен узнать общий секретный ключ К, который сам по себе случаен и не является функцией от пароля.

Конечно, очевидная проблема PAKE заключается в том, что многие разработчики не хотят запускать протокол “обмена ключами” в первую очередь! Они просто хотят убедиться, что пользователь знает пароль.

Самое замечательное в PAKE заключается в том, что вариант использования “login only” достаточно легко исполнить. Допустим, у меня есть стандартный протокол PAKE, который позволяет клиенту и серверу договориться об общем ключе К. Если он знает верный пароль (и только в этом случае), то все, что нам нужно осуществить, это простая проверка того, что обе стороны получили один и тот же ключ. (Это можно сделать, например, если стороны вычислят с его помощью некоторой криптографической функции и сверят результаты.) Таким образом, PAKE может быть полезен, даже если вы хотите просто проверить пароль.

SRP: PAKE, о котором забыло само время


Кажется, что концепция PAKE, обеспечивает очевидное преимущество безопасности по сравнению с наивным подходом, который мы используем сегодня для входа на сервер. Да и сами методы-то старые, в том смысле, что PAKE был известен с 1992 года! Несмотря на это, свет его так и не увидел. Почему так происходит?

Есть несколько очевидных причин. Самое очевидное связано с ограничениями Интернета: гораздо проще поместить форму пароля на веб-страницу, чем реализовывать в браузере причудливую криптографию. Однако этого объяснения недостаточно. Даже нативные приложения редко реализуют PAKE для операции логина. Еще одно возможное объяснение связано с патентами, хотя у большинства из них уже истек срок действия. Для меня есть две вероятные причины отсутствия PAKE:

  • Отсутствие качественных реализаций PAKE на популярных языках, что делает его хлопотным в использовании;
  • Специалисты по криптографии плохо передают суть и ценность своей работы, поэтому большинство людей даже не знают, что PAKE вообще существует.

Несмотря на то, что я сказал, что PAKE сейчас не используется, из правил все же бывают исключения.

Есть один замечательный протокол, разработанный в 1998 году Томом Ву (не путать с Тимом Ву), который носит название “SRP” (сокращение от “Secure Remote Password“). По факту это просто трехэтапный PAKE с некоторыми дополнительными функциями, которые не были реализованы в самых первых работах. Насколько мне известно, SRP отличается тем, что является самым распространенным PAKE протоколом в мире. Я приведу два доказательства этого утверждения:

  1. SRP был стандартизирован в качестве TLS ciphersuite и реализован в библиотеках, таких как, например, OpenSSL, хотя никто, похоже, особенно им не пользуется.
  2. Apple широко использует SRP в своем iCloud Key Vault

Второй факт сам по себе мог сделать SRP одним из наиболее широко используемых криптографических протоколов в мире, настолько велико количество устройств, которые штампует Apple. И тут нет ничего смешного.

То, что индустрия приняла SRP безусловно хорошо, но с другой стороны и не очень. В основном, потому что, хоть любое одобрение PAKE – это круто, но SRP сам по себе – это не лучшая реализация PAKE. Я думал уйти в дебри рассуждений об SRP, но эта речь и так уже затянулась, и я отвлекся от рассказа о действительно хорошем протоколе, о котором мы с вами поговорим ниже. Если вам все еще интересна дискуссия об SRP, я вынес ее сюда.

Вместо этих ненужных деталей, позвольте мне написать краткое изложение своих мыслей на тему SRP:

  1. SRP делает некоторые вещи «правильно». Во-первых, в отличие от ранних версий PAKE, вам не требуется хранить необработанный пароль на сервере (или, что эквивалентно, хэш, который может использоваться злоумышленником вместо пароля). Вместо этого сервер хранит «верификатор», который является односторонней функцией от хэша пароля. Это означает, что утечка базы данных паролей не позволяет злоумышленнику незамедлительно заместить пользователя, только если он не проводит дальнейшие дорогостоящие атаки словаря. (Техническое название для этого: «асимметричный» PAKE.)
  2. Есть новость лучше, текущая версия SRP (v4 v6a) еще не взломана!
  3. Однако (чур разработчикам не обижаться) архитектура протокола SRP полностью сумасшедшая, и его более ранние версии были взломаны несколько раз — именно поэтому мы сейчас имеем версию 6a. Плюс «доказательство безопасности» в оригинальной исследовательской статье на самом деле ничего не доказывает.
  4. SRP в настоящее время основывается на целочисленной (конечной) арифметике, и по различным причинам (см. пункт 3 выше) его архитектура явно не может быть перенесена на эллиптическую кривую. Это требует большей пропускной способности и вычислений, поэтому SRP не может воспользоваться многими улучшениями эффективности, которые мы разработали в таких надстройках, как Curve25519.
  5. SRP уязвим для атак до вычислений, из-за того, что он передает “соль” пользователя любому злоумышленнику, который может инициировать сеанс SRP. Это означает, что я могу попросить у сервера вашу соль и построить словарь потенциальных хэшей паролей еще до того, как сервер будет скомпрометирован.
  6. Несмотря на все эти недостатки, SRP крайне прост, и к тому же поставляется с рабочим кодом. Кроме того, в OpenSSL есть рабочий код, который даже интегрируется с TLS, что делает его относительно легким для внедрения.

Из всех этих пунктов последний почти наверняка отвечает за (относительно) высокую степень коммерческого успеха, которого SRP достиг по сравнению с другими протоколами PAKE. Он не идеален, но реален. Это то, что я хотел донести до специалистов по криптографической безопасности.

OPAQUE: PAKE нового поколения


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

Затем в начале прошлого года Ярецки, Кравчик и Сюй явили миру новый протокол под названием OPAQUE. Он имеет ряд существенных преимуществ:

  1. Он может быть реализован даже в случае, если присутствуют проблемы Диффи-Хеллмана и дискретного логарифмирования. Это означает, что, в отличие от SRP, его можно легко инстанциировать с помощью эффективных эллиптических кривых.
  2. Еще лучше: OPAQUE не раскрывает соль злоумышленнику. Он решает эту проблему, используя «забывчивый PRF» для объединения соли с паролем таким образом, чтобы клиент не получал соль, а сервер — пароль.
  3. OPAQUE работает с любой функцией хэширования паролей. Поскольку вся работа по хэшированию выполняется на клиенте, OPAQUE может фактически снять нагрузку с сервера, освободив онлайн — сервис, допустим, чтобы использовать крайне объемные настройки безопасности, например, сконфигурировать scrypt с большим количеством ОЗУ.
  4. С точки зрения количества сообщений и экспонент, OPAQUE не сильно отличается от SRP. Но поскольку он может быть реализован с более эффективными параметрами, он, вероятно, будет работать намного эффективнее.
  5. В отличие от SRP, OPAQUE имеет разумное доказательство безопасности (в очень сильной модели).

Есть даже предложение Internet Draft для OPAQUE, которое вы можете прочитать здесь. К сожалению, на данный момент я ничего не знаю о качестве реализации кода, кроме того, что уже существует несколько потенциальных реализаций. Надеюсь, скоро этот вопрос прояснится.
Полноценный протокол OPAQUE приведен немного ниже. В оставшейся части этого раздела я собираюсь рассказать о том, как он работает.

Проблема 1: Сохранение соли в секрете. Как я уже упоминал выше, основная проблема с более ранними версиями PAKE – это необходимость передачи соли с сервера клиенту (до сих пор не прошедшему проверку подлинности). Это позволяет злоумышленнику выполнять атаки до вычисления, где он может сгенерировать словарь на основе полученных данных.

Проблема здесь в том, что соль обычно передается в хэш-функцию (например, scrypt) вместе с паролем. Интуитивно понятно, что кто-то должен вычислить эту функцию. Если это сервер, то сервер должен увидеть пароль, что убивает всякий смысл. Если это клиент, то ему нужна соль.

Теоретически можно обойти эту проблему, вычисляя функцию хэширования паролей с использованием протокола конфиденциального вычисления (secure two-party computation, 2PC). На практике такие решения почти наверняка будут неэффективными — в первую очередь потому, что функции хэширования паролей оказываются сложными и трудоемкими. Это невероятно повысит сложность любой системы 2PC.

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

Работает это примерно так:
Сервер хранит “salt” (соль), а у клиента есть password.salt2 = PRF(salt, password), это вычисляется между клиентом и сервером с помощью протокола, в котором клиент никогда не узнает соль, а сервер – пароль. Клиент получает salt2K = PasswordHash(salt2, password) – и считается все это на клиенте.

Фактическая реализация забывчивого PRF может быть выполнена с использованием нескольких элементов группы и экспонент. Еще лучше, если клиент вводит неправильный пароль, тогда протокол получает фиктивное значение “salt2”, которое ничего не говорит о реальном значении соли.

Проблема 2: Доказательство того, что клиент получил правильный ключ K. Конечно, на данный момент клиент получил ключ K, но сервер понятия не имеет, какой он. Сервер также не знает, правильный ли это ключ.

В основе решения OPAQUE лежит старая идея Джентри, Маккензи и Рамзана. Когда пользователь впервые регистрируется на сервере, сервер генерирует надежный открытый и закрытый ключи для протокола безопасного соглашения (secure agreement protocol) (например, HMQV) и шифрует полученный закрытый ключ под K вместе с открытым ключом сервера. Полученный аутентифицированный шифр (и открытый ключ) хранится в базе данных паролей.

C = Encrypt(K, client secret key | server’s public key)


Полная версия протокола OPAQUE, выдержка из статьи.

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

Теперь соберем все воедино. Все эти шаги могут быть объединены в один протокол, который имеет такое же количество этапов, как SRP. Если не обращать внимание на шаги проверки, это будет выглядеть как протокол, приведенный выше. В принципе, идея всего в двух сообщениях: одно от клиента, а второе – отправляется обратно серверу.

Последний аспект работы OPAQUE заключается в том, что он имеет хорошее доказательство безопасности, которое говорит нам, что результирующий протокол может считаться безопасным, если мы возьмем один или более дискретный логарифм в модели со случайным оракулом, которая является стандартным предположением, которое, по-видимому, имеет место в настройках, с которыми мы работаем.

Заключение


Итак, вкратце, у нас есть надежная технология, которая может сделать процесс использования паролей намного проще, а также может позволить нам обращаться с ними эффективнее — с большим количеством параметров хэширования и большей нагрузкой на стороне клиента. Почему это используется не везде? Может быть, в ближайшие несколько лет все изменится. Время покажет.

По устоявшейся традиции ждем ваши комментарии и приглашаем посетить день открытых дверей, который 27 мая проведет наш преподаватель — криптоаналитик Елена Киршанова.
Tags:passwordsprotocolsprovable securityкриптографияинформационная безопасность
Hubs: OTUS. Онлайн-образование corporate blog Information Security Cryptography
Rating +15
Views 3k Add to bookmarks 19
Comments
Comments 3