После прочтения сжечь. Или алгоритмы обработки данных вслепую (oblivious)

Привет, Хабр! Я – Петр, эксперт по ML/AI (и не только) в Skillbox (и не только), а ещё – CEO межбанковской скоринговой платформы Bloomtech. Так уж вышло, что я неплохо разбираюсь в разных PET (Privacy-Enhancing Technologies) и уже писал на хабре про совместные конфиденциальные вычисления. Сегодня повышаю градус и рассказываю про магию следующего порядка: слепую (забывчивую) передачу или oblivious transfer. Как обычно, на примере.    

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

То есть:

1. Неизвестный звонит с номера, которого нет в памяти моего смартфона.

2. Специальное приложение в смартфоне формирует и отправляет запрос в сервис Алисы. Запрос содержит номер телефона, с которого звонит неизвестный.

3. Приложение Алисы, которое работает на её сервере, берёт номер из запроса, ищет его в своей базе данных, находит (или не находит) и возвращает результат: предположим, это потенциальный СПАМ.

4. Приложение в моём смартфоне получает ответ и маркирует входящий вызов: возможно, СПАМ-звонок. И дальше я уже сам решаю: разговаривать или нет.

Отличный, удобный сервис. Прямой как рельса: запрос->поиск->ответ. Все мы делали такие сервисы десятками. И продолжаем делать. Что не так? Конкретно тут вот что: Алиса, которая контролирует сервис, узнает:

1. Кому звонят.

2. Кто звонит.

3. Когда звонят (частично решается кэшированием на клиенте).

4. Сколько раз звонят (частично решается кэшированием на клиенте).

С пунктом 1 ещё можно смириться: звонят мне, это определяет приложение в моем телефоне, и я сам это приложение установил. То есть совершил некоторые осмысленные (как говорят юристы: конклюдентные) действия, и тем самым (вероятно) принял условия использования сервиса. Пункты 2, 3 и 4 оправдать сложнее: эта информация касается третьих лиц, и не все из них телефонные мошенники и навязчивые спамеры.

Например, вы позвонили мне, чтобы поблагодарить за статью, и – бац! – ваш телефон осел в сервисе в связке с моим. А это, между прочим, категорически ценная информация. Называется «окружение пользователя». Платить за окружение (и с удовольствием!) могут разные электронные коммерсанты, кредитные организации (включая микрофинансовые) и даже коллекторы. И вот у Алисы образуется новый рынок. Да такой интересный, что для конечных пользователей (физических лиц) услуга вообще может быть бесплатной. Лишь бы подключались поактивней.

Я не демонизирую существующие определители номеров и тем более не утверждаю, что они хулиганят. Просто рассуждаю теоретически. Описанная архитектура сервиса позволяет накапливать очень ценную персональную информацию, и это плохо. Как сделать лучше?

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

Trusted Execution Environment

Можно, например, подумать в сторону доверенных сред исполнения (TEE, Trusted Execution Environment). Я упоминал такие в своей статье про совместные конфиденциальные вычисления. TEE — это аппаратная технология, которая умеет создавать области памяти, доступа к которой нет даже у того, кто физически контролирует железяку с этой памятью внутри. Такие области называются защищённые анклавы. Внутри анклава могут жить данные и код. Кроме того, предусмотрена процедура (называется аттестация), посредством которой удалённый пользователь может подключиться к анклаву и убедиться, что анклаву можно доверять. А именно:

1. Анклав – действительно анклав, и он защищён соответствующей аппаратной платформой;

2. Код, который выполняется в анклаве, это именно тот код, с которым пользователь хочет взаимодействовать.

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

Тогда сервис Алисы может выглядеть примерно так (очень упрощённо):

1. Алиса создаёт защищённый анклав и загружает в него код сервиса и базу с номерами телефонов.

2. Неизвестный звонит мне с номера, которого нет в памяти моего смартфона.

3. Специальное приложение в моём смартфоне аттестует анклав (и код сервиса в нём) и устанавливает с ним зашифрованное соединение. Как правило, в TEE это происходит при содействии некой третьей доверенной стороны (на картинке — доверенный сервер аттестации).

4. Специальное приложение в моём смартфоне формирует и отправляет зашифрованный запрос в анклав, в котором живёт сервис Алисы. Технология TEE гарантирует, что запрос будет расшифрован только в анклаве, внутрь которого не проберётся даже сама Алиса. 

5. Сервис в анклаве расшифровывает запрос, ищет номер телефона в базе, находит информацию, шифрует её и отправляет в мой смартфон. Тем же путем, но в обратную сторону. И с теми же условиями: расшифровать ответ может только приложение в моём смартфоне. 

6. Приложение в моём смартфоне расшифровывает ответ и предупреждает меня о звонке, который я не захочу принимать.

Выглядит неплохо: сервис работает, услуга оказывается, Алиса сохраняет контроль над своей базой, но не получает информацию об окружении клиентов. Вернее получает, но не может её использовать. Именно этого мы и хотели. Однако есть нюанс: vendor lock-in.

Алиса зависит от конкретного производителя TEE и замыкается на его процессы и инфраструктуру. В частности, на процедуру аттестации. Не будем указывать пальцем, но, скажем так, истории известны примеры, когда вендоры TEE одним днём отключали от своей инфраструктуры целые государства. Это серьёзный риск, его нужно учитывать. Конечно, всегда можно найти «workarounds» и решить проблему условным «параллельным импортом». Впрочем, в моем вокабуляре слова «безопасность» и «workarounds» — это антонимы, поэтому ищем другое решение.  

Слепая (забывчивая) передача     

По-английски это называется Oblivious Transfer (сокращённо, OT). На русский часто переводят как забывчивая передача, хотя мне нравится менее распространённый перевод: слепая передача. Считаю, он лучше отражает происходящее. Как бы там ни было, забывчивая (слепая) передача — это криптографический протокол, с помощью которого одна сторона может передать набор сообщений другой, не имея понятия, какие именно сообщения она передаёт и передаёт ли вообще. В элементарном виде задача формулируется так:

 У Боба (назовём его «получатель» или «receiver») есть бит , а у Алисы («отправитель» или «sender») есть два сообщения и . Алиса должна передать Бобу сообщение так, чтобы:

1. Алиса не узнала значение бита ;

2. Боб получил только сообщениеи ничего не узнал о сообщении ;

Другими словами, у Боба есть номер сообщения, Алиса не знает этого номера, но должна передать сообщение с этим номером и не передать больше ничего. Это и называется слепая передача 1 из 2 или на английский манер – OT 1 out of 2.

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

Протокол Диффи-Хеллмана (Меркла)

Почти 50 лет назад Уитфилл Диффи, Мартин Хеллман и Райф Меркл решили одну из важнейших задач криптографии XX века. Они придумали, как передавать ключ по незащищённому каналу. Их работа лежит в основе множества современных технологий безопасности: HTTPS, VPN, электронная подпись, всё это — следствия элегантного математического алгоритма, который работает так:

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

Важно (на самом деле, категорически важно!) добавить, что число , с которого всё начиналось, — особенное. Это так называемый порождающий элемент циклической группы. Если упрощённо: циклическая группа – это множество чисел  , каждое из которых является степенью числа. Тогда злодей, который прослушивает канал связи между Алисой и Бобом и перехватывает числа и , не сможет вычислить и . Это называется задача дискретного логарифмирования, и в некоторых случаях она не имеет известного быстрого решения. Поэтому Алиса и Боб могут безопасно обменяться A и B даже по публичным каналам связи (есть ещё проблема аутентификации Алисы и Боба, но тут мы её рассматривать пока не будем).

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

Можно утверждать, что этот протокол положил начало асимметричной криптографии (у неё есть два ключа — публичный и приватный), благодаря которой миллионы людей ежедневно покупают вещи онлайн, подписывают электронные документы и просто сёрфят интернет. А ещё – протокол Диффи-Хеллмана (Меркла) легко модифицировать, чтобы получить слепую передачу 1 из 2.

OT 1 out of 2

Благодаря  протоколу Диффи-Хеллмана (Меркла) Алиса и Боб вырабатывают общий секретный ключ. Теперь Алиса может передавать зашифрованные сообщения Бобу, а Боб может их расшифровывать. В слепой передаче 1 из 2 у Алисы – два сообщения. Если Алиса просто зашифрует их и передаст Бобу, он расшифрует и первое, и второе. К счастью, протокол Диффи-Хеллмана (Меркла) можно изменить так, что Боб сумеет расшифровать только одно, причем Алиса не узнает, какое именно.

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

Обратите внимание, Алиса посылает оба зашифрованных сообщения, то есть объём передаваемых данных избыточен. Просто одно сообщение Боб расшифровывает, а второе выкидывает в мусорку. Ничего не поделаешь, накладные расходы. 

OT 1 out of n и другие обобщения

Может показаться, что OT 1 out of 2 не самая практичная штука. Действительно, для нашей задачи с телефонной книгой такое решение не подходит: сложно представить полезный справочник, в котором всего два телефона. Однако OT 1 out of 2 используется в составе других важных протоколов, например, в запутанных логических схемах, о которых я обязательно как-нибудь напишу отдельно. Кроме того, протокол слепой передачи обобщается до OT 1 out ofи даже OT out of . Полагаю, эти названия говорят сами за себя, и для сервиса-определителя номеров нужен OT 1 out of .

Формализуем задачу: у Алисы есть множество сообщений , а у Боба – индекс . Алиса согласна передать Бобу единственное сообщение так, что она, Алиса, не узнает, чему равен индекс , а Боб ничего не узнает о сообщениях , где .

Наивный подход такой: будем делать раз OT 1 out of 2. Боб перебирает все индексы и на каждом шаге:

• Устанавливает битв единицу, если, и в нуль, если нет;

• Вместе с Алисой выполняет протокол OT 1 out of 2, в котором у Боба есть бит, а у Алисы – пара сообщений ;

В результате Боб получит нулей и единственное сообщение . Такой протокол работает, но цена высока:слепых передач 1 из двух, каждая из которых – это обмен хитрыми числами и тяжёлые математические вычисления. К сожалению, если — достаточно велико, то этот протокол совершенно не практичен.

Существуют более сложные схемы OT 1 out of, которые предполагают довольно запутанные битовые манипуляции с индексами и сводят решение к числу OT 1out of. То есть, линейная сложность становится логарифмической. Математика, которая за этим стоит, выходит за рамки этой статьи, но, если себя не жалко интересно, прочитайте, например, тут.

Более современные техники – это так называемые расширения или Oblivious Transfer Extensions, основанные на весьма типичной в криптографии идее: рассчитать что-нибудь заранее и потом использовать при необходимости. Если совсем упростить, в OT Extensions Алиса и Боб выполняют некоторое не очень больше количество OT 1 out of 2 и «заряжаются» специальной энтропией (correlated randomness), благодаря которой могут делать OT 1 out of. Много и быстро.

Ещё можно придумать протокол, который основывается на разделениях секретов передаваемых сообщений вместе с их индексами. Мы в Bloomtech экспериментируем с таким, получается многообещающе. Не без сложностей, потому что требуется много MPC-умножений, но мы умеем делать это довольно эффективно.

В общем, OT 1 out of— это непросто, но возможно. Если постараться и применить известную инженерную смекалку, получится эффективный протокол, который отлично подходит для нашего сервера-определителя номеров и множества других похожих задач.

Сервис-определитель с OT

Итак, сервис Алисы может выглядеть примерно так:

1. Приложение в моём смартфоне и сервис Алисы выполняют процедуру инициализации (её нужно будет периодически повторять) и обмениваются данными, которые впоследствии помогут им быстро делать слепые передачи.

2. Неизвестный звонит мне с номера, которого нет в памяти моего смартфона.

3. Специальное приложение в моём телефоне формирует групповой запрос, в который, кроме номера неизвестного, попадут ещё номеров. Чем больше , тем меньше информации получит Алиса, которая будет трактовать запрос так: звонят с одного из номеров, с какого именно – непонятно. Идеально, если равно размеру базы Алисы, но на практике базы обычно большие, и число как-то ограничивают. Кстати, выбрать, какие именно номеров подмешать в запрос, тоже непросто. Этот выбор часто зависит от специфики задачи и требует отдельного исследования.

4. Сервис Алисы считывает из базы информацию для номеров, маскирует её с помощью данных, полученных во время инициализации, и передает её приложению в моем смартфоне.

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

Таким образом, шаг 0 – это предварительная фаза слепой передачи (например, OT Extension), а шаги 2-4 – оперативная фаза OT 1 out of .

Понятно, что такой дизайн – известное упрощение, остаётся много вопросов, которые нужно проработать. В частности, я бы добавил между приложением в смартфонах и сервисом Алисы дополнительный сервер, пропускающий сквозь себя шифрованный трафик, который не может расшифровать. Цель простая: этот прокси играет роль фасада, который прячет за собой источники запросов. Тогда Алиса не определит не только кто звонит, но и кому звонят. С одной стороны, это повысит конфиденциальность пользователей сервиса, с другой, упростит «подмешивание» номеров в группы запросов.

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

Заключение

Если вы считаете, что сказанное – академическая фантазия, посмотрите, как устроен процесс определения номеров в IOS. Сам механизм отличается, но идея та же: конфиденциальность абонентов. Слово oblivious в тексте по ссылке тоже встречается, но в более широком контексте: oblivious HTTP — это расширение протокола HTTP, который скрывает от сервера его клиентов. По аналогии существует oblivious DNS — очередная попытка исправить один из самых уязвимых протоколов интернета. И тут oblivious — это не протокол в научном криптографическом смысле, а скорее базовый принцип информационного обмена, который, как по мне, напоминает широко распространённый сказочный сюжет: сходи туда – не знаю куда, принеси то – не знаю что. Только это не сказка. Это – математика. 

Берегите себя, берегите свои данные, живите долго и процветайте. До скорого!