Key transparency & Coniks для защиты структур данных
Нас, как организаторов конференций для разработчиков, не обошел стороной мощный поток развивающейся технологии Blockchain. На осеннем Highload++ было несколько докладов, касающихся технологических особенностей и способов применения этой технологии в различных задачах.
Под катом расшифровка доклада Алексея Ермишкина об использовании блокчейна, как математического концепта, для организации базы данных с контролем целостности содержимого.
О спикере и его команде
Алексей Ермишкин представляет компанию Virgil Security, которая занимается разработкой криптографических решений для разработчиков и бизнеса, в частности, в промышленных масштабах внедряет Е2Е-шифрование. Это шифрование «точка-точка», когда отправитель заранее знает публичный ключ получателя, и на их взгляд, это единственно правильный способ обеспечить защищенность передаваемых данных.
Тему этой статьи рассмотрим на примере общения традиционных Алисы и Боба. В данном случае это не люди, а роботы, потому что, когда по защищенному каналу хотят пообщаться, например, какие-то датчики или небольшие девайсы, у них гораздо меньше возможностей для того, чтобы полноценно использовать все то, что уже написано для людей, например, TLS-сертификаты, SSH, VPN и все остальное.
Итак, Алиса хочет пообщаться с Бобом. К сожалению, она знает только его имя или какой-то идентификатор, например, mail или телефон. Чтобы она могла получить его публичный ключ, используется сервер ключей. Но хранить ключи в простом key-value-хранилище абсолютно небезопасно, т. к. их можно оттуда убрать, заменить или вернуть на существующий ключ ответ 404, будто его там нет.
Поэтому сервер должен обладать несколькими очень важными и уникальными свойствами:
1. Наличие/отсутствие ключа
Сервер, конечно, должен уметь возвращать ключи, которые в нем есть, но помимо этого, он должен строго доказать, что в нем какого-то ключа нет. До сегодняшнего дня эта задача была никем не решена.
2. История ключей
Боб и Алиса должны иметь возможность отследить историю ключей. То есть, когда Боб меняет свой ключ на новый, он должен убедиться, что со временем никто с его ключами ничего не делал: не подменял, не удалял.
3. Один результат на всех
Алиса и Боб должны видеть одно и то же состояние, в котором находится база данных. Злонамеренный сервер (если он таковым является) может показать одну историю ключей Бобу, а Алисе — совсем другую, в которой будет совсем другой ключ. Это абсолютно неприемлемо с точки зрения безопасности.
4. Обфускация Identity
И последнее, хоть и не самое важное, мы хотим, чтобы взломщики и просто люди, которые на нее смотрят со стороны, например, аудиторы, ничего не могли узнать о том, чьи идентификаторы и какие данные лежат в базе. Но при этом сервер обязан все строго доказывать именно клиентам, которые пользуются его услугами.
Конечно, после того, как Алиса и Боб узнали ключи друг друга, нужен протокол защищенной связи. На сегодняшний день, если у вас есть только публичные ключи, вы остаетесь сами по себе. Вам придется писать какие-то костыли. Они бывают хорошие и плохие, но чаще всего люди их пишут сами.
Blockchain
Прежде я бы хотел немножко объяснить свое отношение к теме блокчейна. Я очень люблю технологию блокчейн, в последнее время все, что крутится вокруг — SEO, криптовалюта, смарт-контракты — это все прекрасно и отлично, но это далеко не все, что может блокчейн, и это далеко не вся его философия.
Blockchain — это далеко не только смарт-контракты и криптовалюты, которые вообще стали сокращать до слова «крипто». Мне, как человеку, занимающемуся криптографией, это особенно бьет по ушам.
Blockchain — не обязательно распределенные системы. Если посмотреть определение слова «Blockchain», это распределенная база данных с консенсусами и со всем остальным. Нет, это абсолютно не так.
Blockchain-технология существовала за 4 года до Bitcoin. Вы наверняка тоже ею пользуетесь, но не догадываетесь, что это блокчейн. Это Git, и я очень легко это докажу.
Если посмотреть на то, как работает git и на дерево коммитов, то отчетливо видно, что каждый коммит — это, в принципе, блок. В нем есть хэш-ссылка на предыдущий коммит. Пожалуйста, вот Block и вот chain!
Например, если говорить про смарт-контракты, то Git Hooks — это их прообраз, то есть это логика, которая работает в блокчейне и влияет на то, как он формируется. Энтузиасты даже написали шуточную криптовалюту — gitcoin. Это просто git репозиторий с Git Hooks, который добавляет монет тому, кто запушил коммит, хэш которого меньше, чем хэш предыдущего коммита — этакий proof-of-work а-ля Bitcoin.
Таким образом, для меня блокчейн — это больше математический концепт: база данных, не обязательно распределенная, но обязательно c контролем целостности содержимого.
Key transparency & Coniks
Сегодня поговорим о технологии, которая родилась на стыке двух других, Coniks и Certificate transparency.
Coniks — это академический проект исследователей из Принстона и Стэнфорда, которые решили помочь людям безопасно хранить, в частности, публичные ключи (и не только).
Затем к этому проекту присмотрелся Google, и на стадии не очень реализованной концепции форкнул и скрестил со своей технологией Certificate transparency, которая представляет собой большой лог, содержащий все когда-либо выпущенные сертификаты для того, чтобы, как это недавно было, какой-нибудь сотрудник центра сертификации не выпустил бы тестовый сертификат на домен Google.com.
Эти технологии решают задачу безопасного хранения публичных ключей, которые привязаны к идентификаторам пользователей, но помимо публичных ключей на самом деле можно хранить все, что угодно.
Merkle tree
Дальше поговорим об одной алгоритмической структуре, про которую те, кто уже знаком с блокчейном, наверняка слышал — это дерево Меркла. Конечно, эта структура не имеет никакого отношения к канцлеру Германии. Ральф Меркль — это математик.
Мало кто знает, что популярный протокол обмена публичными ключами Диффи-Хеллмана на самом деле имеет полное название — протокол Диффи-Хеллмана-Меркла. Меркль придумал для него всю теоретическую базу, а Диффи и Хеллман написали практическую реализацию. Протокол назван в их честь, но они сами говорят, что это все-таки протокол Диффи-Хеллмана-Меркла.
Что придумал Меркль?
Например, есть массив транзакций (файлов). От каждого из этих файлов (здесь 16) считаются хэши. Затем они берутся попарно и от каждой пары еще раз считаются хэши. Так повторяется до тех пор, пока не получится один хэш, который и называется корнем дерева и зависит от всех хэшей, которые были внизу.
Это структура примечательна тем, что для того, чтобы доказать, что какой-то файл есть в этом дереве, нужно всего 4 промежуточных хэша (на схеме синие блоки). Когда мы их предоставляем клиенту, он их попарно по очереди хэширует и в итоге получает тот самый корень. Этот корень обычно лежит в заголовке блока, а все транзакции вместе с деревом могут быть расположены, в принципе, отдельно.
Еще одно замечательное свойство этого дерева — каким бы оно не было большим, корень (поскольку это хэш) всегда одного и того же размера. Если хэш 256 бит, корень всегда будет 32 байта.
Поэтому чаще всего лайт ноды биткоинов или каких-то других блокчейнов просто обмениваются именно деревьями. Этого достаточно для того, чтобы проследить целостность блоков. Если нужна какая-то конкретная транзакция из блока, нужно скачать этот блок целиком и проверить, есть ли она там, такое дерево отлично работает на доказательство наличия чего-то в нем.
Но что бы нам придумать, чтобы доказать еще и отсутствие?
Немножко расширим сознание и представим, что в дереве лежат вообще все возможные хэши от нулевого до самого последнего, состоящего из всех бинарных единичек.
Если хэш 256 бит, то в дереве лежат все хэши от 0 до 2256 — 1. Это настолько большое число, что думаю, ни один человек, даже занимающийся HighLoad«ом, не способен такое дерево обсчитать. Что же делать, как его использовать.
Разреженное дерево Меркла
По факту, почти все листья такого дерева будут пустыми, то есть в них ничего не будет лежать. Хэши 2-го уровня будут чаще всего хэшами двух 0, хэши 3-го уровня — хэшами от двух хэшей от двух 0. Такое дерево можно сэмулировать, не смотря на его огромный размер, и использовать только те части, в которых реально лежат данные.
Наличие/отсутствие ключа
Как показано на схеме, части, которые не используются, просто не хранятся. Вместо узлов, которые являются пустыми частями дерева, ставится заглушка — например, узел, помеченный как пустой. Когда мы до него доходим, то понимаем, что там ничего нет. Поскольку это сбалансированное двоичное дерево, и в нем зарезервированы места для всех хэшей, путь до каждого хэша и будет этим самым хэшем. Например, первый бит 1 — идем налево, 0 — направо, и т.д.
То, что путь до каждого хэша является самим хэшем позволяет строго доказать не только наличие, но и отсутствие информации в базе. Мы можем предоставить путь до ближайшего пустого узла, и сказать: «У нас есть такой путь и такой корень дерева, дальше ничего нет — можно все провалидировать!» Это будет являться строгим доказательством отсутствия информации в данном узле.
Поскольку дерево огромное, но в то же время в нем ничего нет, оно называется разряженным деревом Меркла и, как мы уже сказали, позволяет доказать наличие и отсутствие информации в базе. Теперь отвечать 404 на запрос публичного ключа просто не честно!
В это дерево можно помещать какую-то информацию и работать с ним с течением времени. В этом нам, конечно, поможет блокчейн.
История ключей
Давайте разобьем время на эпохи. Например, раз в 5 минут будем:
- собирать все изменения, которые пользователи хотят внести в это дерево,
- применять их, заново считая корень дерева,
- подписывать этот корень и предыдущий.
У нас получается тот же самый блокчейн, просто он основан не на множестве блоков, в каждом из которых лежит маленькое дерево, а на одном большом дереве Меркла. Это позволяет построить историю ключей, которую нельзя изменить задним числом.
Один результат на всех
Теперь нужно сделать так, чтобы Алиса и Боб видели одно и то же, т.е. чтобы сервер не предоставлял разные истории разным пользователям. Сделать это очень просто. Во-первых, можно завести сторонних аудиторов, которые бы проверяли базу. В базе лежат обезличенные данные, поэтому с этим проблем нет.
Но также можно использовать публичные блокчейны и, например, просто хэши от каждой эпохи класть в тот же Bitcoin, Ethereum и т.д. Эпоха за эпохой мы будем их туда складывать. Эта технология называется анкоринг (якорение).
Мы предоставляем Алисе доказательство того, что на момент времени X у нас было такое дерево. Она проверяет его хэш в публичном блокчейне, и убеждается, что все хорошо. А мы добиваемся того, что все пользователи в любой момент времени видят одно и то же.
Обфускация Identity
Нам нужно не только доказать, что все всё видят одинаково, но требуется также защитить данные пользователей, которые лежат в нашей базе. В первую очередь мы защищаем сами публичные ключи.
Когда Боб кладет в базу ключ, мы его складываем со случайным набором байт, прогоняем через хэш, и то, что получается, называется дополнением (или commitment). Оно лежит в дереве, и когда кто-то у нас просит доказать, что структура дерева правильно построена, мы ему предоставляем именно это дополнение.
Но когда Алиса просит у нас данные Боба, мы показываем ей «случайную соль», отдаем публичный ключ, она проводит те же самые операции и убеждается, что на месте, где ключ лежит в базе, находится именно то, что туда положил Боб, а не кто-то еще.
Так что, если кто-то хитрый посмотрит на эту базу и надумает узнать, что же там лежит, он ничего не увидит.
Но и это еще не все, мы должны мочь скрыть само имя Боба из базы. Мы не можем это сделать просто с помощью хэширования, потому что перебирать имена пользователей брутфорсом может каждый школьник. Поэтому придумали такую замечательную вещь, как Verifiable Random Function.
Алиса спрашивает у сервера:
— Дай мне, пожалуйста, ключ Боба, и подскажи, по какому индексу ты его в это дерево положил.Сервер ей отвечает какой-то абсолютной белибердой, от которой у Алисы дыбом встают волосы:
— Что же ты мне такое дал, сервер? Как ты можешь вообще такое говорить?
— Все ОК! Вот мое доказательство!
По сути, сервер читает от имени Боба цифровую подпись. Но это не обычная цифровая подпись, которой мы пользуемся каждый день, а детерминированная. Если взять любую OpenSSL или крипто библиотеку и прочитать цифровую подпись от любой строчки 10 раз, получим 10 разных цифровых подписей. Здесь она всегда одна и та же. Там еще есть несколько добавленных элементов, но в принципе это работает именно так.
Затем хэш этой цифровой подписи используется, как индекс в дереве для Боба. Таким образом, не имея приватного ключа, у нас вообще нет теоретической возможности (кроме той, что когда-нибудь взломают асимметричную криптографию) узнать, что и чье имя по этому индексу лежит.
Мы можем даже на каждой итерации (на каждую эпоху) добавлять в базу просто случайные, абсолютно рандомные хэши и скрыть таким образом истинное количество пользователей, которые находятся в базе. Конечно, максимальное количество тот, кто смотрит базу, узнает, но точно, сколько пользователей пришло, и кто из них изменил какие данные, узнать будет невозможно.
Таким образом, и Алиса счастлива, и Боб цел, а мы научились защищать пользовательские данные, которые лежат у нас в базе.
Этот сервер ключей уже есть. Его можно скачать по запросу Key transparency в GitHub Google. Он, конечно, еще в стадии «Proof of concept», но это уже рабочая версия. Мы его у себя уже начинаем использовать для хранения публичных ключей пользователей.
Резюме
Key Transparency и Coniks позволяют:
- Доказывать как наличие, так и отсутствие записей в базе.
- Следить за целостностью информации владельцам аккаунтов и их собеседникам.
- Скрывать данные с помощью Verifiable Random Function.
- Проводить аудит третьим лицам без компрометации данных пользователей.
- В отличие от традиционных блокчейновов иметь очень малый размер доказательства.
Максимальный путь для аудита, состоящий из хэшей, нужных для доказательства наличия элемента в дереве, составляет 256 хэшей. Это пара килобайт, в отличие от тех 150–200 Гб, которые нужно скачивать в биткойне для того, чтобы убедиться, что транзакция есть в таком-то блоке.
Я считаю, это поистине уникальная вещь, которую стоит изучать, развивать и, конечно же, пользоваться.
Правда, как я уже говорил, на сегодняшний день всем, кому приходится работать с чистыми приватными публичными ключами, приходится писать свои костыли. Поэтому, когда WhatsApp выкатил обновление своей криптографии, они, помимо протокола для обмена сообщениями, еще реализовали протокол именно для транспортного уровня под названием Noise. Он нам очень понравился, и мы сделали надстройку над фреймворком Noise Protocol, которую назвали NoiseSocket. О ней мы, вероятно, поговорим в будущих докладах и статьях.
Контакты:
» virgilsecurity.com
» github.com/virgilsecurity
» twitter.com/virgilsecurity
Алексей продолжит тему на грядущей DeCenter TokenConf, на которой будет еще двадцать не менее крутых докладов и докладчиков. Успевайте присоединиться, поезд уже практически тронулся.
