Herbivore (протокол)

Herbivore — это масштабируемый и эффективный peer-to-peer протокол, созданный на базе сети «обедающих криптоаналитиков», используемый для анонимной коммуникации.

Название

Herbivore в переводе с английского означает «травоядное животное», что является намёком на созданную ФБР систему слежения Carnivore (англ. плотоядное животное).

Создание

Эмин Гюн Сирер (Emin Gün Sirer), Марк Робсон (Mark Robson) и Мило Полте (Milo Polte) в 2001 году создали систему для анонимной коммуникации CliqueNet Архивная копия от 6 марта 2015 на Wayback Machine (англ.). Она разбивала глобальную сеть на локальные анонимные DC-сети (dining cryptographers networks). После этого Шарад Гоел (Sharad Goel), используя подход, заявленный в CliqueNet, начал разрабатывать Herbivore. Вскоре после этого все четверо учёных начали сотрудничать и в 2003 году опубликовали документацию по протоколу.

Принцип работы

Иллюстрация проблемы обедающих криптоаналитиков

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

На первом этапе каждая пара криптоаналитиков разделяют однобитовый секрет (например, подбрасывают монетку). Предположим, что у А и B это 1, у B и C это 1, а у C и A это 0.

На втором этапе каждый участник говорит следующее:

• исключающее или(xor) от известных секретов, если за счёт платил не он
• отрицание этого или, если за счёт платил он

В нашем примере, если никто не заплатил, то A объявит $\scriptstyle 1\,\oplus \,0\;=\;1$, B объявит $\scriptstyle 1\,\oplus \,1\;=\;0$, C объявит $\scriptstyle 0\,\oplus \,1\;=\;1$. Если же заплатил криптоаналитик А, то он объявит $\scriptstyle \lnot {(1\,\oplus \,0)}\;=\;0$.

После этого остается только сложить все результаты по модулю 2. Если результат — единица, то заплатил один из криптоаналитиков, если же результат 0, то заплатило АНБ.

Топология сети

Глобальная топология

Вся сеть представляет собой кольцо, созданное из небольших групп из $\sim k$ пользователей.

глобальная топология

Глобальная топология сети описывается протоколом входа. Главная его цель — сохранить анонимность участников, путём лишения каждого права выбирать в какую группу вступать. Это делается для того, чтобы злоумышленники не «захватили» всю группу и, таким образом, не раскрыли анонимность участников. Метод состоит в следующем: у каждого пользователи и у каждой группы есть свой уникальный ключ. Для того, чтобы войти в сеть пользователь должен сгенерировать пару ключей $K_{public}/K_{private}$ - открытый/закрытый ключ. После этого случайно генерируется вектор $Y$, не равный открытому ключу $K_{public}$, такой, что младшие $m$ бит $f(K_{public})$ равны младшим $m$ битам $f(Y)$, где $f$ это необратимая функция. Значение $g(K_{public},Y)$, где $g$ - необратимая функция, становится уникальным ключом пользователя.

После этого участник вступает в группу с ближайшим к своему ключом. Чтобы сделать это, он предоставляет группе пару $(K_{public},Y)$, после чего каждый участник группы проверяет выполнение всех условий, описанных в предыдущем параграфе, и сверяет ключ пользователя с ключом группы. Если в группе уже есть участник с таким ключом, то новый пользователь не принимается в группу (сделано для предотвращения "приглашений" в группу злоумышленников). Если же все подтвердили правильность ключа, то пользователю высылается случайно сгенерированный вектор $V_{chal}$, на который пользователь отвечает вектором $V_{resp}=K_{private}(V_{chal})$. Если группа подтверждает, что $K_{public}(V_{resp})=V_{chal}$, то пользователь принимается в группу.

Группы могут увеличиваться и уменьшаться, поэтому для обеспечения анонимности и быстродействия было решено, что размер группы должен быть больше $k$, но меньше $3k$. Если размер группы стал меньше $k$, она немедленно распускается. Если размер группы стал больше $3k$ и её участники согласны, она разделяется на две с новыми ключами $K_{C1}$ и $K_{C2}$, при этом:

• $K_{C1}=K_{C_{prev}}+1/3(K_{C_{succ}}-K_{C_{prev}})$
• $K_{C1}=K_{C_{prev}}+2/3(K_{C_{succ}}-K_{C_{prev}})$

где $K_{C_{prev}}$ - ключ предшествующей группы,$K_{C_{succ}}$ - ключ следующей группы.

Локальная топология

локальная топология

Внутри группы используется топология «звезда» (каждый с каждым). Для более быстрой работы для передачи каждого бита выбирается "центральный пользователь", которому все остальные передают результаты своих вычислений. Для балансировки нагрузки "центральный пользователь" меняется с каждой новой передачей. Подробнее смотреть документацию Архивная копия от 17 октября 2014 на Wayback Machine (англ.).

Возможные атаки

Захват группы

Если злоумышленники захватят группу, то они могут раскрыть анонимность последнего честного участника. Благодаря протоколу входа для группы размером 128, вероятность захватить более 90% группы составляет всего $\sim 1{,}5\times 10^{-6}$.

Статистический анализ

Если каждая группа, в которую входил пользователь $N$ обращалась к одному и тому же сайту, можно сделать вывод, что это делал пользователь $N$.

Атака "координатором"

Центральный пользователь может изменять отправляемые пакеты. Однако центральный пользователь постоянно меняется, что позволяет минимизировать ущерб.

Ссылки

• Herbivore FAQ Архивная копия от 23 сентября 2015 на Wayback Machine
• Herbivore documentation Архивная копия от 17 октября 2014 на Wayback Machine
• The Dining Cryptographers Problem Архивная копия от 21 декабря 2014 на Wayback Machine