openPGP в России

24.03 // Riposte: первый практичный протокол анонимной публикации сообщений

Исследователей давно интересовали способы анонимной публикации сообщений. Одним из самых последних эффективных протоколов такого рода считался Dissent^[link1]. Однако, для заполнения L-битной базы данных для публикации он требует отправки от всех клиентов L-битовой строки, что требовало около часа времени проверок от 1000 клиентов для исключения единственного саботажника. После внесения защиты против клиентов, саботирующих выполнения протокола, скорость Dissent для протокола «точка-точка» не превышает 30 KB/s. Попытки разделения пользователей Dissent-подобных протоколов на малые подгруппы закономерно приводили к дроблению множества анонимности на подмножества.

Создатели нового протокола Riposte (Henry Corrigan-Gibbs^[link2] — один из соавторов протокола Dissent, Dan Boneh^[link3] и David Mazires^[link4], Стэнфордский университет, США) смогли добиться скорости 450+ MB/s при способности обслуживать миллионы пользователей одновременно, не разделяя их на анонимные подмножества. Нарушить анонимность в таком большом едином множестве — сложная задача для противника. Таких успехов удалось достичь за счёт многолетних исследований в области протоколов приватного получения информации (Private Information Retrieval — PIR^[link5] ). PIR-протоколы позволяют клиентам получать значения из базы данных сервера, не раскрывая перед сервером самих запрашиваемых значений. В Riposte был эффективно применён обратный PIR-протокол: запись значений в базу таким образом, что сервер не может определить в какую строку данная запись была произведена.

Иллюстрацией протоколов неотслеживаемой записи является следующий «игрушечный» модельный пример.

Пусть есть два недоверяемых, но и несотрудничающих между собой сервера A и B, которые открывают запись в некоторый интервал времени. Пусть клиент хочет записать "1" в l-строку базы данных. Для этого клиент генерирует случайную L-битовую строку r. Используя операцию XOR, клиент посылает строку r на сервер A и r ⊕ e_l на сервер B, где e_l — L-битовый вектор из нулей с единицей в позиции l. После n записей база данных сервера A будет иметь вид d_A = r₁ ⊕ … ⊕ r_n. На сервере B будет: d_B = (e_l1 ⊕ … ⊕ e_ln ) ⊕ (r₁ ⊕ … ⊕ r_n ) = (e_l1 ⊕ … ⊕ e_ln ) ⊕ d_A. По истечении интервала времени серверы A и B раскрывают друг другу d_A и d_B, что позволяет вычислить значения заполненной базы данных в открытом виде. Такой протокол является лишь иллюстрацией принципа. На практике он неэффективен из-за линейной зависимости размера базы данных от числа клиентов и нестойкости к саботажу со стороны любого из клиентов, проводящего запись.

В протоколе Riposte исследователи, объеденив PIR и DPF (distributed point function — функции с распределённой точкой), смогли добиться эффективного исключения DoS-атак (саботажа выполнения протокола пользователями путём анонимного внесения записей, разрушающих базу данных) и максимально полной защиты от анализа трафика полностью глобальным наблюдателем: противник не может нарушить анонимность пользователя ни наблюдая за точками входа и выхода трафика в систему, ни проводя активные атаки по его модуляции, видоизменению или переотправке сообщений. Это выгодно отличает Riposte от универсальных протоколов реального времени, таких как Tor. В Riposte сообщения собираются в течении определённого интервала-эпохи (например, 4 часа) за который любой пользователь, не скрывая своего IP-адреса, может внести запись в базы данных серверов. После завершения эпохи базы объединяются и сообщение псевдонима пользователя оказывается опубликованным в ленте новостей, твит-ленте, списке рассылок, WikiLeaks-сервисе и др. Разумеется, пользователь может опубликовать сообщение, зашифрованное открытым ключом получателя для осуществления оконечной связи, если сервис позволяет создавать рассылки и для сообщений такого рода. Наблюдатель может статистически вычислять пользователя по 4-часовым эпохам, но ничто не мешает пользователю регулярно отправлять пустые сообщения, которые не могут быть отличаемы от содержательных на стороне сервера. Более того, квота под заведомо пустые сообщения может быть открыта и для анонимных пользователей без риска саботажа системы. Отдельными серверами такие сообщения не могут быть различимы от настоящих, но они отбрасываются при финальном объединении данных так, что не занимают квоту содержательных сообщений.

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

Из-за размера запроса всего O(L^1/2) для первого варианта в твиттер-подобном сервисе (160 байт поля записи) на 2.3 миллиона пользователей для создания одного твита пользователю требуется отправить всего 1MB запрос. Размер базы данных на одну эпоху времени такого анонимного твиттера — 377 MB, что потребовало бы отправки 750 MB данных от каждого пользователя на один твит в DC-net сетях, или 377 MB в сетях гарантированного совместного перемешивания, наподобие Dissent. Так в Riposte в течении 4-часовой эпохи могут быть собраны твиты от 50000 пользователей, каждый из которых останется абсолютно анонимным среди этого множества. Эпохи Riposte могут быть уменьшены или увеличины по времени в зависимости от набранного минимального числа пользователей.

Клиенты в Riposte являются полностью недоверенными и могут пытаться посылать злонамеренные запросы. Серверы могут быть злонамеренными, но не сотрудничающими между собой до заданных пороговых лимитов t (treshhold). Серверы могут выдать и опубликовать свои секретные ключи, но до момента их записи с целью выдачи соблюдается свойство совершенной наперёд заданной секретности (PFS). Никаких особых требований к злонамеренным серверам не предполагается — протокол не допускает возможности существования какой-либо особенно эффективной злонамеренной стратегии, которая бы позволяла преодолевать лимит допустимого количества злонамеренных серверов t. Размер лимита t определяет вычислительные затраты и размер запроса. Серверы могут осуществлять атаки саботажа, но при этом они не могут снизить анонимность пользователей. Поскольку серверы неанонимны, то после таких атак они могут быть легко выявлены и исключены из сети. Некорректные попытки клиентов повредить своими запросами выполнению протокола отсеиваются ещё на этапе распределённого сбора записей в базу.

Анонимность пользователей (клиентов) остаётся высокой, если:

1. Пользователей много.
2. Они часто читают твиты, но редко пишут ("read-only" пользователи).
3. Регулярно подключаются к анонимному твиттеру, отправляя пустые покрывающие (имитирующие запись) сообщения (которые обнуляются при объединении распределённых баз). Это могут делать и незарегистрированные "read-only" пользователи.

Пользователи могут использовать Tor для связи с серверами Riposte, чтобы использовать комбинированные типы анонимности.

Для воссоздания полной копии сервиса Twitter в показателях нагрузки за 2013 год по мнению авторов потребуется 5250 Riposte-серверов, которые объединены минимум в три несотрудничающих кластера. За счёт того, что один из кластеров занимается лишь проверкой при объединении баз данных из первых двух, общее число серверов м.б. уменьшено до 4000.

Стойкость протокола Riposte опирается на известные базовые примитивы — AES и совместное выведение секрета по Диффи-Хеллману в эллиптических кривых. Исследователи оставляют открытыми вопросы по возможности исключения всех асимметричных криптопримитивов из криптопротокола DPF, чтобы оставить асимметричные алгоритмы только для аутентификации связи с серверами.

Спонсорами и заказчиками исследования выступили: корпорация Google, национальный научный фонд (NSF), агентство перспективных оборонных исследований (DARPA), агентство перспективных исследований в области разведки и национальной безопасности (IARPA), министерство внутренних дел (DoI), центр исследований военно-морского флота (ONR), научно-техническое сообщество министерства обороны (NDSEG), национальный бизнес центр (NBC) в составе МВД США.

Работа будет представлена на 36 симпозиуме по вопросам безопасности и приватности^[link6], проводимом институтом инженеров электротехники и электроники (IEEE) при содействии международной организации криптологических исследований (IACR) 18 мая 2015 года.

Источник: arXiv.org/1503.06115, Computer Science > Cryptography and Security^[link7].
См. также: Dissent — протокол анонимной связи малых закрытых сообществ^[link1].