Crowds

Crowds (англ. crowd - толпа) — сетевой протокол, предоставляющий анонимный доступ в Интернет. Анонимность достигается посредством смешивания трафика пользователя с трафиком нескольких случайно выбранных пользователей со схожими свойствами, таким образом, чтобы никто не мог определить, от кого исходил тот или иной пакет данных. Crowds был разработан Майклом Райтером и Авилем Рубиным. Как описано в работе «The Predecessor Attack: An Analysis of a Threat to Anonymous Communications Systems», протокол Crowds уязвим для атаки от предшественника.

Виды анонимности

Протокол предполагает три вида анонимности:

• анонимность отправителя
• анонимность получателя
• несвязываемость отправителя и получателя.

Также при анализе протокола полезно знать, от каких видов атак данная анонимность обеспечивает защиту. Еще следует различать разные уровни защиты:

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

Таким образом, если пользователь хочет полной анонимности, ему требуется уровень «вне подозрения». По умолчанию у всех пользователей Интернета нет никакой анонимности.

Действие протокола

Система crowds состоит из динамической группы пользователей, называемой толпой (от англ. «crowd»). Пользователи, которые инициализировали веб-запрос к различным веб-серверам (и получают ответы от них) — «отправители», а серверы - «получатели». На основании представленных пользователю видов анонимности, можно выделить три вида атак:

• Локальный перехватчик — злоумышленник, который может просматривать все приходящие и уходящие сообщения с компьютера пользователя.
• Сотрудничающие участники «толпы» — участники «толпы», которые собирают проходящую через них информацию и могут подменять сообщения.
• Конечный сервер — веб-сервер, с которым установлено соединение.

Эти три определения предназначены для описания всех видов атак. Например, сотрудничающие пользователи толпы и конечный сервер не могут прослушивать коммуникацию между остальными членами группы. Также локальный перехватчик не может перехватывать сообщения, которые не приходят на компьютер пользователя. Локальный перехватчик — это модель перехватчика, который находится в локальной сети пользователя, например, системный администратор, просматривающий все сообщения через локальный firewall. Если же конечный сервер находится в той же подсети, то данный протокол не может обеспечить анонимность подключения.

В таблице ниже приведен предоставляемый уровень защиты для каждого вида анонимности (протокол не предназначен для несвязываемости получателя и отправителя, поэтому последняя колонка упущена)

Вид атаки	анонимность отправителя	анонимность получателя
локальный перехватчик	уязвимый	вне подозрения
C сотрудничающих участника толпы $N\geqslant {\frac {p_{f}}{p_{f}-0.5}}(C+1)$	возможная невиновность	возможная невиновность
Конечный сервер	вне подозрения

N — количество пользователей толпы. $p_{f}$ — вероятность того, что сообщение перенаправится другому пользователю толпы($p_{f}>{\frac {1}{2}}$, подробнее про $p_{f}$ ниже).

Алгоритм работы протокола

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

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

Jodno не знает, был ли пришедший запрос отправлен предыдущим jondo, или за один jondo до него.

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

Crowds работает так, чтобы каждый узел сети казался похожим на изначального отправителя сообщения. Каждый узел входит в сеть, запуская приложение jondo - небольшой процесс, который будет переадресовывать и принимать запросы от пользователей сети. Когда jondo стартует, каждый пользователь сети информируется о вхождении нового узла и теперь рассматривает его как возможный адрес пересылки сообщения. Для отправки сообщения узел выбирает случайным образом (причем равновероятно) узел из всей сети и отправляет ему сообщение. После получения сообщения узел «подбрасывает испорченную монетку» (с вероятностью выпадения одной стороны $p_{f}$), и, если выпало более вероятное событие, отправляет сообщение другому случайному узлу, иначе сообщение отправляется конечному адресату. Каждый узел при отправке сообщения на другой узел записывает предшественника, и, таким образом, туннель фиксирован - последнее используется для коммуникации между отправителем и получателем.

Анализ секретности

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

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

Напоминаем, что каждое сообщение, проходящее по группе узлов засекречено, кроме последнего, отправляемого на конечный сервер. Так как протокол не скрывает связи между входящими и исходящими сообщениями от компьютера пользователя, то перехватчик может заметить, когда пользователь инициирует сообщение. Таким образом, crowds не обеспечивает анонимность отправителя от локального перехватчика. С другой стороны, так как сообщение отправляется другому пользователю crowds зашифрованным, то локальный перехватчик узнает адрес получателя только в том случае, если отправитель посылает сообщение напрямую. Вероятность этого события ${\frac {1}{N}}$, а N - количество пользователей "толпы" на момент создания "виртуального пути". Таким образом, вероятность того, что перехватчик выяснит, куда направляется сообщение, убывает прямо пропорционально уменьшению размера "толпы".

Конечный сервер.

Рассмотрим анонимность, обеспечиваемую от атак конечного сервера. Очевидно, что анонимность по получателю в данном случае невозможна. Для конечного сервера любой участник "толпы" может рассматриваться, как отправитель запроса. Таким образом, анонимность по отправителю имеет уровень «вне подозрений». Интересен тот факт, что результат не зависит от $p_{f}$

(в отличие от связанных jondo). Также, увеличение пути по толпе не влияет на уровень защиты.

Сотрудничающие (связанные) jondo.

Рассмотрим группу jondo, задачей которых является выяснение инициатора соединения (отправителя). Так как каждый jondo может просматривать трафик, проходящий через него, анонимности получателя в данном случае нет.

Отправитель может быть идентифицирован очевидно только в тех случаях, когда сотрудничающие jondo попадаются на пути сообщения в толпе. Так как содержимое сообщение не содержит никакой информации по отправителю, сотрудничающие jondo могут лишь подозревать своего предшественника. Рассмотрим, насколько уверен может быть jondo, что его предшественник отправил сообщение. Введем некоторые термины : $H_{k}$ — событие, когда первый «предатель» находится на позиции k виртуального пути, где отправитель занимает 0 позицию пути. Положим также H_k+ = H_k or H_k+1 or H_k+2 or . . . . $I$ — то событие, когда отправитель отправляет своё сообщение напрямую на «предателя». Выясним, при каком количестве $C$ предателей уровень анонимности отправителя сохраняется на возможной невиновности.

Определение. Отправитель имеет возможную невиновность, если P(I | H_k+) <= 1/2

Теорема. Если $N\geq {\frac {p_{f}}{p_{f}-1/2}}(C+1)$, тогда отправитель имеет возможную невиновность.

Доказательство:

Требуется показать, что P(I | H_k+) <= 1/2, при условии, что $N\geq {\frac {p_{f}}{p_{f}-1/2}}(C+1)$ . Для начала заметим, что

$P(H_{i})=({\frac {p_{f}(N-C)}{N}})^{i-1}({\frac {C}{N}})$ — вероятность того, что прежде чем дойти до предателя, путь прошел по (N — C)

«чистым» jondo (первая скобка) и, затем, попал на предателя (C/N). Откуда следует

P(H₁₊) = ${\frac {C}{N}}\sum _{k=0}(p_{f}{\frac {(N-C)}{N}}={\frac {C}{N}}{\frac {1}{1-{\frac {p_{f}(N-C)}{N}}}}$

P(H₂₊) = ${\frac {C}{N}}\sum _{k=0}(p_{f}{\frac {N-C}{N}})^{k}=({\frac {C}{N}})({\frac {1}{1-{\frac {p_{f}(N-C)}{N}}}})$

Также нам потребуется:

P(H₁) = ${\frac {C}{N}}$

P(I|H₁) = 1

P(I|H₂) = ${\frac {1}{N-C}}$

Теперь P($I$) может быть найден как

P(I) = P(H₁)P($I$ | H₁) + P(H₂₊)P($I$ | H₂₊) = ${\frac {C(N-Np_{f}+cp_{f}+p_{f})}{N^{2}-p_{f}N(N-C)}}$

и т.к. $I$=>H₁₊

P($I$ | H₁₊)= ${\frac {P(I\land H_{1}+)}{P(H_{1}+)}}$ = ${\frac {P(I)}{P(H_{1}+)}}$ = ${\frac {N-p_{f}(N-C-1)}{N}}$

Таким образом, если

$N\geq {\frac {p_{f}}{p_{f}-{\frac {1}{2}}}}\left(C+1\right)$ ,тогда P($I$ | H₁₊)<=1\2

Если взять $p_{f}$=2/3, N $\geq$ 4 (C + 1)

Возможные проблемы

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

Firewalls также представляют собой проблему для crowds. Так как jondo используют определенный порт для работы с сетью, неизвестный файерволлам, то они блокируют внешние попытки соединения к этим портам, что, естественно, мешает работе толпы.

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

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

Также можно измерить нагрузку на каждый jondo: в среднем в "толпе" численностью N на каждого участника будет приходиться по O $({\frac {1}{(1-p_{f})^{2}}}(1+{\frac {1}{N}}))$ появлений на виртуальных путях.