Crowds (сеть анонимности)

Crowds - это предлагаемая сеть анонимности для анонимного просмотра веб-страниц. Основная идея протокола анонимности Crowds состоит в том, чтобы скрыть сообщения каждого пользователя, случайным образом маршрутизируя их внутри группы похожих пользователей. Таким образом, ни участники группы, ни конечный получатель не могут быть уверены, из какого места в группе был получен пакет. Crowds был разработан Майклом К. Рейтером и Эйвиелем Д. Рубином. Он защищает от внутренних злоумышленников и коррумпированного получателя, но не обеспечивает анонимность против глобального злоумышленника или локального перехватчика (см. «Толпы: анонимность для веб-транзакций»). Толпа уязвима для; это обсуждалось в статье Рейтера и Рубина и далее расширено в книге Мэтью К. Райта, Мики Адлера и Брайана Нила Левина «Атака предшественника: анализ угрозы для систем анонимной связи». Crowds представил концепцию смешивания пользователей с толпой компьютеров.

• 1 Как работает толпа
• 2 Определения
• 3 Базовый дизайн
  • 3.1 Алгоритм на каждой машине
• 4 Анализ безопасности
  • 4.1 Локальный перехватчик
  • 4.2 Совместная работа jondos
  • 4.3 Статические пути
  • 4.4 Встроенные изображения и временные атаки
• 5 Масштаб
• 6 Атаки
• 7 См. Также
• 8 Ссылки
• 9 Дополнительная литература
• 10 Внешние ссылки

1. Каждый пользователь присоединяется к толпе других пользователей, регистрируясь в блендере, который является единственным сервером, ответственным за управление членством. Когда пользователь регистрируется, все остальные участники группы получают уведомление. Блендер также отвечает за распределение ключей, поскольку он распределяет симметричные ключи по отдельным парам хондо, используемых для шифрования и дешифрования, соответственно пакетов, маршрутизируемых по виртуальным путям.
2. Каждый пользователь представлен хондо на нем. machine, которая представляет собой приложение, которое запускается на компьютере пользователя.
3. Каждый хондо либо отправляет запрос на конечный сервер, либо пересылает его случайно выбранному хондо (возможно, самому себе). Другой задачей хондо является удаление любой личной информации, такой как файлы cookie, определение полей заголовка.
4. Хондо не может определить, инициирован ли запрос предыдущим хондо или предшествующим ему.
5. Запрос и ответ следует по тем же виртуальным путям, которые построены с использованием алгоритма, включающего вероятности. Виртуальные пути регулярно разрушаются и реконструируются, чтобы обеспечить анонимность для вновь добавленных участников.

Crowds использует и определяет следующие термины:

Отправитель

Инициатор сообщения

Получатель

Конечный получатель сообщения

Вероятная невиновность

Злоумышленник не может иметь более 50% уверенности в том, что какой-либо узел инициировал сообщение (узел с равной вероятностью инициировал сообщение, а не получил - каждый пользователь скорее невиновен, чем нет.)

Локальный подслушивающий

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

Corrupt Node

Узел поврежден, если он использует информацию, полученную при пересылке сообщения, для определения отправителя

$C\; \{\backslash \; displaystyle\; C\}$

Количество поврежденных узлов

$N\; \{\backslash \; displaystyle\; N\}$

Количество узлов ($N\; -\; C\; \{\backslash \; displaystyle\; NC\}$- количество исправных узлов)

$пф\; \{\backslash \; displayst\; yle\; p\_\; \{f\}\}$

Вероятность пересылки

Толпа работает, заставляя каждый узел с одинаковой вероятностью быть инициатором сообщения. Как мы уже говорили, каждый узел присоединяется к сети, начиная jondo (от «John Doe»), который представляет собой небольшой процесс, который пересылает и принимает запросы от других пользователей. Когда хондо запускается, все узлы в сети уведомляются о входе нового узла и начинают выбирать его в качестве пересылки. Для фактической отправки сообщения узел выбирает случайным образом (с одинаковой вероятностью) из всех узлов в сети и пересылает им сообщение. Получив сообщение, узел подбрасывает смещенную монету (с вероятностью $pf>1\; 2\; \{\backslash \; displaystyle\; p\_\; \{f\}>\{\backslash \; frac\; \{1\}\; \{2\}\}\}$) и если это Lands Head пересылает его другому случайному узлу, в противном случае он пересылает его в конечный пункт назначения.Каждый узел при пересылке на другой узел записывает предшественника, и таким образом создается туннель, который используется для связи между отправителем и получателем.

Алгоритм на каждой машине

OnReceive (узел P, сообщение M)

1. Подбросить монету со смещением ($Pr\; (H\; eads)\; =\; pf\; \{\backslash \; displaystyle\; \backslash \; Pr\; (Heads)\; =\; p\_\; \{\; f\}\}$)
   1. If Heads Then Выберите равномерно случайный узел и пересылайте ему
   2. Иначе Переслать адресату
2. Запись P, чтобы можно было построить туннель

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

Локальный перехватчик

Напомним, что каждое сообщение, пересылаемое по пути, за исключением последнего запроса к конечному серверу, зашифровано. Таким образом, хотя перехватчик может просматривать любое сообщение, исходящее с компьютера пользователя, он просматривает только сообщение, отправленное на конечный сервер, если хондо пользователя в конечном итоге сам отправляет запрос пользователя. Поскольку вероятность того, что хондо пользователя в конечном итоге отправит запрос, равна 1 / n, где n - размер толпы на момент создания пути. Таким образом, мы узнаем, что вероятность того, что перехватчик узнает личность получателя, уменьшается в зависимости от размера толпы. Более того, когда хондо пользователя в конечном итоге не отправляет запрос, локальный перехватчик видит только зашифрованный адрес конечного сервера, что, как мы предлагаем, обеспечивает анонимность получателя, которая (неофициально) вне подозрений. (вне подозрений - ни один пользователь не подозрительнее других).

Сотрудничающие хондо

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

1. Пусть Hk, k>= 1, обозначает событие, когда первый участник пути занимает k-ю позицию на пути., где сам инициатор занимает 0-ю позицию (и, возможно, другие).
2. Определим Hk+= Hkили Hk+1или H k + 2 или....
3. Пусть I обозначает событие, когда первому участнику на пути непосредственно предшествует инициатор пути.

Обратите внимание, что H1=>I, но обратное I =>H 1неверно, потому что инициирующее хондо может появляться на пути несколько раз. Возможен случай, когда путь составлен следующим образом:

инициатор jondo (0 - позиция) ---->jondo (1 - позиция) ---->

инициатор jondo (2 - позиция) ---->Сотрудничающее хондо (3 - позиция)

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

4. С учетом этого обозначения участники теперь надеются определить:

P (I | H 1+)- учитывая, что участник находится на пути, какова вероятность того, что инициатор пути является непосредственным непосредственным участником первого сотрудника. предшественник?

Определение: . Инициатор пути имеет вероятную невиновность, если P (I | H 1+)<=1\2.

Чтобы обеспечить вероятную невиновность инициатора пути, в нашей системе должны быть выполнены определенные условия. В частности, let pf>1/2 (вероятность пересылки в системе.)

(c- количество соавторов в толпе)

(n- общее количество участников толпы при формировании пути)

Следующая теорема дает достаточное условие на pf, c и n, чтобы гарантировать вероятную невиновность инициатора пути.

Теорема :Инициатор пути, вероятно, невиновен против c соавторов в случае

$n\; \ge \; pfpf\; -\; 1\; 2\; (c\; +\; 1)\; \{\backslash \; displaystyle\; n\; \backslash \; geq\; \{\backslash \; frac\; \{p\_\; \{f\}\; \}\; \{p\_\; \{f\}\; -\; \{\backslash \; frac\; \{1\}\; \{2\}\}\}\}\; \backslash \; left\; (c\; +\; 1\; \backslash \; right)\}$

Доказательство: мы хотим показать, что pf>1/2 если $n\; \ge \; pfpf\; -\; 1\; 2\; (c\; +\; 1)\; \{\backslash \; displaystyle\; n\; \backslash \; geq\; \{\backslash \; frac\; \{p\_\; \{f\}\}\; \{p\_\; \{f\}\; -\; \{\backslash \; frac\; \{1\}\; \{2\}\}\}\}\; \backslash \; left\; (c\; +\; 1\; \backslash \; right)\}$

обратите внимание, что:

P (H i) = $(pfn\; -\; cn)\; i\; -\; 1\; (cn)\; \{\backslash \; displaystyle\; (\; p\_\; \{f\}\; \{\backslash \; frac\; \{nc\}\; \{n\}\})\; ^\; \{i-1\}\; (\{\backslash \; frac\; \{c\}\; \{n\}\})\}$

для того, чтобы первый соавтор был в с позицией на пути, путь должен сначала каждый раз переходить к i-1 не сотрудникам с вероятностью $n\; -\; cn\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{nc\}\; \{n\}\}\}$, каждый из которых выбирает перенаправить путь с вероятностью pf, а затем соавтору с вероятностью $cn\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{c\}\; \{n\}\}\}$.

Следующие два факта непосредственно следуют из этого

P (H 1+) = $cn\; \sum \; k\; =\; 0\; (pfn\; -\; cn)\; k\; =\; (cn)\; (1\; 1\; -\; pf\; (n\; -\; c)\; n)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{c\}\; \{n\}\}\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; (p\_\; \{f\}\; \{\backslash \; frac\; \{\; nc\}\; \{n\}\})\; ^\; \{k\}\; =\; (\{\backslash \; frac\; \{c\}\; \{n\}\})\; (\{\backslash \; frac\; \{1\}\; \{1\; -\; \{\backslash \; frac\; \{p\_\; \{f\}\; (nc)\}\; \{n\}\})\; \}\})\}$

P (H 2+) = $cn\; \sum \; k\; =\; 1\; (pfn\; -\; cn)\; k\; =\; (cn)\; (pf\; (n\; -\; c)\; n\; 1\; -\; pf\; (\; n\; -\; c)\; n)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{c\}\; \{n\}\}\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; (p\_\; \{f\}\; \{\backslash \; frac\; \{nc\}\; \{n\}\})\; ^\; \{k\}\; =\; (\{\; \backslash \; frac\; \{c\}\; \{n\}\})\; (\{\backslash \; frac\; \{\backslash \; frac\; \{p\_\; \{f\}\; (nc)\}\; \{n\}\}\; \{1\; -\; \{\backslash \; frac\; \{p\_\; \{f\}\; (nc)\}\; \{n\}\}\})\; \})\}$

P (H 1) = $cn\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{c\}\; \{n\}\}\}$

P (I | H 1) = $1\; \{\backslash \; displaystyle\; 1\}$

P (I | H 2) = $1\; n\; -\; c\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{nc\}\}\}$

Теперь P (I) можно записать как

P (I) = P (H 1) P (I | H 1) + P (H 2+) P (IH 2+) = $c\; (n\; -\; npfn\; +\; cpf\; +\; pf)\; n\; 2\; -\; pfn\; (n\; -\; c)\; \{\backslash \; displaystyle\; \{\; \backslash \; frac\; \{c\; (n-np\_\; \{f\}\; n\; +\; cp\_\; \{f\}\; +\; pf)\}\; \{n\; ^\; \{2\}\; -pfn\; (nc)\}\}\}$

, поскольку I =>H 1+

P (I | H 1+) = $P\; (I\; \wedge \; H\; 1\; +)\; P\; (H\; 1\; +)\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{P\; (I\; \backslash \; land\; H1\; +)\}\; \{P\; (H1\; +)\}\}\; \}$= $P\; (I)\; P\; (H\; 1\; +)\; \{\backslash \; di\; splaystyle\; \{\backslash \; frac\; \{P\; (I)\}\; \{P\; (H1\; +)\}\}\}$= $n\; -\; pf\; (n\; -\; c\; -\; 1)\; n\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{n-p\_\; \{f\}\; (nc-1)\; \}\; \{n\}\}\}$

так, если $n\; \ge \; pfpf\; -\; 1\; 2\; (c\; +\; 1)\; \{\backslash \; displaystyle\; n\; \backslash \; geq\; \{\backslash \; frac\; \{p\_\; \{f\}\}\; \{p\_\; \{f\}\; -\; \{\backslash \; frac\; \{1\}\; \{2\}\}\}\}\; \backslash \; left\; (c\; +\; 1\; \backslash \; right)\}$

, затем P (I | H 1+)<=1\2

Например если pf = 3 \ 4, то вероятная невиновность гарантируется, пока n>= 3 (c + 1).

Статические пути

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

Встроенные изображения и временные атаки

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

Как предотвратить?

Когда jondo получает HTML-ответ на запрос, который он либо получил непосредственно от браузера пользователя, либо отправил непосредственно на конечный сервер, он анализирует HTML-страницу, чтобы определить все URL-адреса, которые браузер пользователя будет автоматически запрашивать как в результате получения этого ответа. Последний хондо на пути запрашивает эти URL-адреса и отправляет их обратно по тому же пути, по которому был получен исходный запрос. Хондо пользователя, получив запросы на эти URL-адреса от браузера пользователя, не пересылает эти запросы по пути, а просто ожидает, пока содержимое URL-адресов поступит на путь, а затем передает их в браузер. Таким образом, другие хондо на пути никогда не видят запросы, генерируемые браузером, и поэтому не могут получить от них информацию о времени.

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

Теорема: В толпе размером n ожидаемое общее количество появлений любого хондо на всех путях равно $O\; (1\; (1\; -\; pf)\; 2\; (1\; +\; 1\; n))\; \{\backslash \; displaystyle\; O\; (\{\backslash \; frac\; \{1\}\; \{(1-p\_\; \{f\})\; ^\; \{2\}\}\}\; (1\; +\; \{\backslash \; frac\; \{1\}\; \{n\}\}))\}$

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

Crowds обеспечивает идеальную анонимность против коррумпированного получателя (например, $d\; \leftarrow \; 1\; \{\backslash \; displaystyle\; d\; \backslash \; gets\; 1\}$см. Степень анонимности ), поскольку все участники с одинаковой вероятностью были инициаторами. Как мы показали против сотрудничества коррумпированных узлов Crowds обеспечивает вероятную невиновность, пока $N\; \ge \; pfpf\; -\; 1\; 2\; (C\; +\; 1)\; \{\backslash \; displaystyle\; N\; \backslash \; geq\; \{\backslash \; frac\; \{p\_\; \{f\}\}\; \{p\_\; \{f\}\; -\; \{\; \backslash \; frac\; \{1\}\; \{2\}\}\}\}\; \backslash \; left\; (C\; +\; 1\; \backslash \; right)\}$(вывод этого см. в статье), и обеспечивает степень анонимности $d\; \leftarrow \; N\; -\; pf\; \cdot \; (N\; -\; C\; -\; 1)\; N\; \cdot \; lg\; \; [NN\; -\; pf\; \cdot \; (N\; -\; C\; -\; 1)]\; +\; pf\; \cdot \; N\; -\; C\; -\; 1\; N\; \cdot \; lg\; \; [N\; /\; pf]\; lg\; \; (N\; -\; C)\; \{\backslash \; displaystyle\; d\; \backslash \; gets\; \{\backslash \; frac\; \{\{\backslash \; frac\; \{N-p\_\; \{f\}\; \backslash \; cdot\; (NC-1)\}\; \{N\}\}\; \backslash \; cdot\; \backslash \; lg\; \backslash \; left\; [\{\backslash \; frac\; \{\; N\}\; \{N-p\_\; \{f\}\; \backslash \; cdot\; (NC-1)\}\}\; \backslash \; right]\; +\; p\_\; \{f\}\; \backslash \; cdot\; \{\backslash \; frac\; \{NC-1\}\; \{N\}\}\; \backslash \; cdot\; \backslash \; lg\; \backslash \; left\; [N\; /\; p\_\; \{f\}\; \backslash \; right]\}\; \{\backslash \; lg\; (NC)\}\}\}$. Против толпы терпит поражение в $O\; (N\; C\; lg\; \; (N))\; \{\backslash \; displaystyle\; O\; \backslash \; left\; (\{\backslash \; frac\; \{N\}\; \{C\}\}\; \backslash \; lg\; (N)\; \backslash \; right)\}$; эта атака работает за счет того, что поврежденный узел сохраняет предыдущий переход на пути, так как это будет отправитель больше, чем любой другой узел, в течение раундов восстановления сети станет очевидным, кто является инициатором. Рейтер и Рубин упоминают об этом и рекомендуют длительное (и, если возможно, бесконечное) время между преобразованиями пути (когда узел на пути покидает сеть). Crowds не может защитить от глобального перехватчика, поскольку не может использовать шифрование на ссылках, это связано с тем, что каждый узел в Crowds может взаимодействовать со всеми остальными узлами (полностью подключенный граф), поскольку для настройки симметричных ключей требуется $O\; (N\; 2)\; \{\backslash \; displaystyle\; O\; (N\; ^\; \{2\})\}$попарные ключи; это слишком большое число, чтобы его можно было реализовать. И снова от локального перехватчика Crowds не обеспечивает защиты, поскольку перехватчик увидит сообщение, исходящее от узла, который не вошел, и это положительно идентифицирует узел как отправителя.

• Луковая маршрутизация
• Tor (сеть анонимности)
• Степень анонимности
• Смешанная сеть

1. ^Клаудиа Диаз и Стефаан Сейс, Джорис Классенс и Барт Пренель (апрель 2002 г.). Роджер Дингледин и Пол Сиверсон (ред.). «На пути к измерению анонимности». Труды семинара по технологиям повышения конфиденциальности (ПЭТ 2002). Springer-Verlag, LNCS 2482. Архивировано с оригинального 10 июля 2006 г. Проверено 10 ноября 2005 г.
2. ^Майкл Рейтер и Авиль Рубин (июнь 1998 г.). «Толпы: анонимность для веб-транзакций» (PDF). ACM-транзакции по информационной и системной безопасности. 1 (1). Архивировано из оригинального (PDF) 12 декабря 2005 г. Проверено 23 ноября 2005 г.
3. ^Мэтью К. Райт, Мика Адлер, Брайан Нил Левин и Клэй Шилдс (2004). «Атака-предшественник: анализ угрозы для анонимных систем связи» (PDF). ACM-транзакции по информационной и системной безопасности. ACM Press. 7 (4): 489–522. Архивировано из оригинального (PDF) 24 сентября 2005 г. Проверено 23 ноября 2005 г.
4. ^Мэтью Райт и Мика Адлер, Брайан Нил Левин и Клэй Шилдс (февраль 2002 г.). «Анализ деградации анонимных протоколов» (PDF). Материалы симпозиума по сетевой и распределенной безопасности - NDSS '02. IEEE. Архивировано из оригинального (PDF) 19 февраля 2006 г. Проверено 23 ноября 2005 г.

• Библиография анонимности
• Архив Cryptology ePrint