id: Гость   вход   регистрация
текущее время 16:35 23/03/2019
Владелец: unknown (создано 24/04/2010 21:42), редакция от 24/04/2010 22:49 (автор: SATtva) Печать
Категории: криптография, анонимность, протоколы, микс-сети
https://www.pgpru.com/Новости/2010/Dissent--ПротоколАнонимнойСвязиМалыхЗакрытыхСообществ
создать
просмотр
редакции
ссылки

24.04 // Dissent -- протокол анонимной связи малых закрытых сообществ

Предисловие


Для понимания рассматриваемой далее актуальной работы следует сначала вспомнить классическую работу Дэвида Чаума (основоположника идей практической реализации сетевой анонимности), опубликованную в 1988 году (The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of Cryptology, 1(1):65­75, January 1988.) и протокол "обедающих криптографов (dining cryptographers)".


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


Каждый криптограф бросает монету, прикрываясь меню. При этом результат одновременно могут видеть только он и сосед справа, но не третий участник. Затем каждый объявляет по поводу своей монеты и монеты соседа слева — упали монеты разными сторонами кверху или одинаково. Но объявление делается по правилу: тот, кто заплатил, должен утверждать противоположное тому, что видит. Если число различий за столом — нечётное, то обед оплачен кем-то из криптографов, если чётное — то АНБ. При этом если обед всё-таки оплатил криптограф, то двое других на основании сделанных всеми заявлений не могут узнать, что это был он.


Протокол может быть расширен на любое число участников. Представив действия в виде элементарных операций, таких как XOR и инвертирование битов, можно передать сообщение любой длины в сети вида DC-net. Оно будет полностью неотслеживаемо для постороннего наблюдателя. Анонимность отправителя и получателя против пассивного наблюдателя любого типа будет информационно-стойкой — никакие ресурсы (с учётом модели глобального наблюдателя) или криптоаналитические методы не смогут её разрушить (по крайней мере в идеальном случае — когда стороны для эмуляции честного подбрасывания монеты используют накопители с одноразовым ключом или квантовый канал). В реальном случае получаем доказательство стойкости анонимности, равное стойкости используемого протокола криптографической эмуляции "подбрасывания монеты по линии связи". Сообщение может быть зашифровано открытым ключом получателя или быть открытым для всех.


Однако данный протокол непрактичен. Из-за коллизий при попытке одновременно передать сообщения на передачу одного байта может тратиться от 2n до 2n байтов, где n — число участников. Поэтому протокол не масштабируется на большую группу из-за экспоненциального падения пропускной способности. Хуже того, любой или несколько из n участников могут анонимно (без возможности какого-либо отслеживания как изнутри, так и снаружи такой сети) саботировать протокол, выполняя свои действия "нечестным" образом, так что в итоге никакое сообщение не будет собрано или сеть будет выглядеть всё время занятой для участников.


Поэтому данный протокол долгое время не имел никакого практического применения, хотя в течении многих лет предпринимались попытки его улучшения (протоколы "криптографы на дискотеке" и др. ).

Рассмотрение работы


Henry Corrigan-Gibbs и Bryan Ford из Йелльского Университета (США) предоставили открытый доступ к черновому варианту работы Accountable Anonymous Group Messaging"Анонимные групповые сообщения со свойством ответственности", в которой получили развитие идеи Чаума и произведена попытка решения сопутствующих проблем.


В анонимных группах могут часто появляться пользователи, которые рассылают спам или подрывают нормальное функционирование группы, оставаясь анонимными. Протоколы передачи сообщений, такие как Mix-net и DC-net, ставят группы перед проблемой уязвимости к атакам отказа в обслуживании и Sybil-атакам (атакам на подрыв репутации с использованием множества фальшивых идентичностей) при том, что протокол голосования не может быть использован или неэффективен против анонимной отправки сообщений в целом.


Исследователи представили первый протокол общего вида для обмена сообщениями, обеспечивающий доказуемую анонимность с ответственностью для групп умеренного размера, который также эффективно обращается с несбалансированной нагрузкой, когда небольшому числу участников необходимо передать много данных за один раунд. Группа из N участников вначале совместно перемешивает матрицу псевдослучайных начальных значений N x N. Затем использует эти значения в N предварительно спланированных запусках протокола DC-net. Каждый запуск DC-net передаёт объём данных переменной длины, соответствующий одному сообщению пользователя с использованием минимального количества бит, необходимых для достижения анонимности в предложенной модели атаки. Протокол сохраняет целостность сообщения и однозначное соответствие между участниками и сообщениями, делая атаку отказа в обслуживании с их стороны эффективно отслеживаемой до её виновника. Протокол эффективно справляется с большой и несбалансированной нагрузкой. Работающий прототип демонстрирует практичность протокола для групп по крайней мере до сорока с небольшим узлов-участников.


Анонимное участие часто считается основным правом свободных сообществ (авторы ссылаются в этом вопросе на публикацию Йельского журнала права "Конституционное право на анонимность: свобода слова, огласка и дьявол". The constitutional right to anonymity: Free speech, disclosure and the devil". Yale Law Journal, 70(7):1084­1128, June 1961.). Даже ограниченные виды анонимности, возможные в Интернете, являются очень полезной возможностью, позволяющей людям и группам с неоднозначными или непопулярными взглядами осуществлять коммуникации без страха личной ответственности. В ущерб такому своему преимуществу анонимность делает сложным отслеживание и исключение некорректно ведущих себя участников. Он-лайн протоколы, обеспечивающие больший уровень анонимности, такие как mix-сети и DC-net способствуют слабой ответственности и приводят к форумам, в которых никакой контент не может рассматриваться как доверяемый и нет никакой защиты против анонимных злоупотреблений.


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


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


В качестве мотивирующего примера предположим, что группа международных журналистов хочет организоваться для публикации утечек секретных материалов по типу WikiLeaks. Для защиты журналистов и их источников более сильным образом, чем это позволяют любые мировые правовые механизмы, журналисты-участники посылают раскрытые документы и аналогичную информацию анонимно в группу. Участники должны быть уверены, что могущественные организации и правительства не смогут отследить утечку до отдельного журналиста или его источника. Журналисту желательно доказать для читающих, что оглашаемые документы поступили по доверенному каналу, например от кого-то из членов группы, но не от постороннего. Группа должна иметь возможность анализировать и рассматривать каждый документ перед коллективным принятием публикации. Группа должна защищать свои внутренние операции и анонимность своих участников даже если противник помещает внутрь группы противодействующих шпионов. И безопасность такого рода должна обеспечиваться за приемлемое время и ресурсы.


Исследователи представили первый протокол такого рода, удовлетворяющий этим условиям, названный Dissent (Dining-cryptographers Shuffled-Send Network). Dissent обеспечивает доказуемую целостность, анонимность и подотчётность перед лицом угроз мощных методов анализа трафика и наличия скомпрометированных участников. Экспериментальный прототип показывает его эффективность к передаче сообщений, для которых несущественна задержка, среди малых, но широко распределённых групп.


В противоположность mix- и DC-net сетям, Dissent использует shuffled send (примитив перетасованной отправки), делая возможным каждому участнику группы пересылать ровно одно сообщение за раунд и делая возможным голосование с назначением псевдонима для привязки псевдонима для участников группы по принципу "один к одному". В отличие от криптографических перетасовок с проверкой, Dissent использует только широко доступные криптопримитивы (в тестовой реализации были использованы предоставляемые библиотекой OpenSSL 1024-битный RSA-OAEP, AES-256 и SHA-1) и оперирует сообщениями произвольной длины в условиях дисбаланса нагрузки так эффективно, что один журналист может производить утечку многогигабайтного документа в то время, когда другим нечего посылать.


Две стадии Dissent — перемешивание и накопление. Протокол перемешивание основан на работах Брикеля и Шматикова по перемешиванию сообщений фиксированной длины от каждого и анонимной передаче всем участникам группы. Для предотвращения DoS-атак используются техники go/no-go и "осуждения" для отслеживания нечестных участников протокола.


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


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


Исследователи протестировали рабочий прототип Dissent в среде Emulab на группах до 44 участников, соединённых эмулированными каналами передачи. Анонимное распределение сообщений размером до 16 MB на 16 узлов даёт задержку 100 миллисекунд между узлами, перетасовка Dissent и другие стартовые процедуры создают задержку 1.4 минуты, но с учётом использования как сбалансированных так и несбалансированных загрузок большими сообщениями это занимает время в 3.5 большее, чем требуется для неанонимной передачи по TCP всем участникам группы. В зависимости от размера группы, Dissent позволяет отправлять анонимные сообщения размером 1 MB менее, чем за минуту для группы из четырёх участников, 4 минуты для группы из 20 узлов и 14 минут для группы из 40 узлов. Хотя это не годится для интерактивного обмена, но вполне подходит для сценария "WikiLeaks", обеспечивая сильные гарантии анонимности для малых децентрализованных групп.


Источник: ArXiv.org: Computer Science > Cryptography and Security


 
— Гость (24/04/2010 23:59)   <#>
При этом результат одновременно могут видеть только он и сосед справа, но не третий участник.
Кто такой третий участник? Тот кто ещё правее, или тот, кто слева?
Затем каждый объявляет по поводу своей монеты и монеты соседа слева — упали монеты разными сторонами кверху или одинаково. Но объявление делается по правилу: тот, кто заплатил, должен утверждать противоположное тому, что видит.
Значит сосед объявляющего неправильно тоже видит, что тот лжёт и может всем об этом рассказать. Ну и какая после этого анонимность?

Или я совсем дурак, или научно-популярная подача материала потребовала упрощение вплоть до искажения.
— unknown (25/04/2010 03:13, исправлен 25/04/2010 03:21)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Если их всего три, то тот, кто правее правого и есть тот, кто слева :)


Сосед слева (Кэрол) подкидывает монету так что её видит он(а) сам(а) и тот, кто правее его (Алиса). Т.е. Алиса знает как упала монета у кэрол. Затем Алиса подбрасывает свою монету, но соседке слева не показывает, а только соседу справа — Бобу. Боб делает с Кэрол тоже самое. Т.е. каждый знает — как упала его монета и монета соседа слева, но не третьего участника. Но объявляет результат выпадения монет между собой и левым участником, не раскрывая самих значений: только одинаково или по-разному. Участник слева не может разоблачить, если сказать наоборот — он результат того, кто справа бросал уже позднее не видел.


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

— Гость (25/04/2010 09:23)   <#>
Если их всего три, то тот, кто правее правого и есть тот, кто слева :)
Ой, не заметил что их всего три, извиняюсь. Я себе мысленно представлял почему-то что их много и они все сидят за одним круглым столом (симметрично).

unknown, вы по-простому ответье, вот это:
тот, кто заплатил, должен утверждать противоположное тому, что видит
очевидно ещё кому-то кроме самого заплатившего или нет? Я клонил именно к этому.
— unknown (25/04/2010 13:17)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Я себе мысленно представлял почему-то что их много и они все сидят за одним круглым столом

Это уже фуршет после конференции какой-то :) Может быть и много — будет более общий случай. Для простоты сначала объясняют на трёх.
тот, кто заплатил, должен утверждать противоположное тому, что видит

очевидно ещё кому-то кроме самого заплатившего или нет? Я клонил именно к этому.

Только он об этом знает. Другим это не вычислить никак.

Результат своего броска никто не говорит (хотя сосед справа его видит, но для сохранения анонимности они не обмениваются результатами отдельных бросков "орёл-решка", кроме того при такой нечестной попытке обмена данными для раскрытия под принуждением можно врать, если криптографов больше трёх — но это в примере не рассматривается).

В конце все вслух объявляют только выпало с соседом слева "одинаково" или "по-разному". Если сосед слева показал, как у него выпала "решка", а у вас после этого, на вашем броске выпал "орёл", то этого "орла" видит только сосед справа.
Вы можете сказать правду — "по-разному". Но можете сказать и наоборот "одинаково" — если вы единственный, кто платит. Сосед слева и сосед справа ничего не узнают про то, что вы сказали наоборот и что вы платите. После всеобщих объявлений совпадений бросков выясняется, что инвертировал результат кто-то один, но не установить кто. Или никто не инвертировал (тогда платит АНБ).

В общем виде результат сравнения монет — это (A xor B), а заявление обратного сравнения — inv (A xor B). Так передаются потоки битов через пары узлов DC-net.
— Гость (25/04/2010 16:39)   <#>
Гость (25/04/2010 09:23), не читайте unknown-а :) Он мастер в двух словах объяснять сложные вещи. А простые лучше и не объяснять. Возьмите листик и нарисуйте три кружочка, соедините их палочками... заштрихуйте один или два...


Я кстати "открытие" сделал:
Если в графе из каждой вершины выходит четное количество ребер, а вершины могут иметь один из двух цветов (черный или белый), то как бы мы не раскрашивали вершины число ребер соединяющих разноцветные вершины будет четно.
— Paran0ik (26/04/2010 02:30)   профиль/связь   <#>
комментариев: 88   документов: 13   редакций: 3
нет гарантии, что один из участников не расскажет всем, какая у вас монета, тогда один участник (тот, что слева от вас) узнает – правду вы сказали насчет совпадения ваших с ним монет или нет...
— Гость (26/04/2010 03:33)   <#>
При этом результат одновременно могут видеть только он и сосед справа, но не третий участник. Затем каждый объявляет по поводу своей монеты и монеты соседа слева — упали монеты разными сторонами кверху или одинаково
Я, кажется, понял. Дело в том, что сосед справа видит как на самом деле упала монета, но он не может отдетектировать, что чел сынвертирует результат, когда будет рассказывать публично [инвертирование происходит после, а не сразу после броска]. Подмену мог бы заметить только чел слева, но он не знает результат :) Спасибо за разъяснения.
— Гость (26/04/2010 03:40)   <#>
нет гарантии, что один из участников не расскажет всем, какая у вас монета, тогда один участник (тот, что слева от вас) узнает – правду вы сказали насчет совпадения ваших с ним монет или нет...
В данном случае да, но при числе криптографов >> 3, трудно понять кому нужно "рассказывать", т.к. лишь один из всего набора криптографов мог бы "пролить свет". В итоге, рассказывать пришлось бы всем [или большей части], а это можно только по предварительному сговору, но считается что никто не заинтересован нарушать анонимность свою и других такой ценой.

Т.е. если имеется ситуация 1 криптограф и 10 крыс вокруг, которые сразу же рассказывают все свои результаты после голосования, то да, криптогграф бессилен. Именно поэтому берётся 10 криптографов и 0 или "много меньшее" число крыс. Я же правильно понял, unknown?
— unknown (26/04/2010 12:08, исправлен 26/04/2010 12:49)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
сли в графе из каждой вершины выходит четное количество ребер, а вершины могут иметь один из двух цветов (черный или белый), то как бы мы не раскрашивали вершины число ребер соединяющих разноцветные вершины будет четно.

У Чаума в работе рассмотрен пример и на графах.


По поводу разоблачения по сговору кроме тривиального случая из трёх у Чаума как раз построены доказательства на теории графов.
Вот html. Интересно, что первый вариант работы был представлен ещё на Crypto-84.


Кстати, вот картинка — иллюстрация попытки создать проект файлообменной сети Herbivore на этом принципе.


В реальности когда узел хочет передать сообщение скажем размером с байт (10011011), то нужно провести восемь общих раундов. Но ещё момент в том, что никто не знает, можно ли передавать сообщение (сеть свободна, или передаёт кто-то ещё). Если передают скажем двое, то возникает коллизия, они видят, что сообщение не передалось (должны быть коды проверки ошибок) и временно прекращают передачу, но продолжают участвовать в протоколе, генерируя случайные биты для передачи сообщений других участников (не делая инверсии заявлений). Чем больше участников и чем чаще передаются сообщения — тем больше коллизий. Если кто-то нарочно создаёт коллизии в классической DC-net, то оставаясь анонимным делает её совершенно неработоспособной.


В данной работе исходный протокол DC-net попытались довести до практического воплощения.

— unknown (28/04/2010 08:52, исправлен 28/04/2010 09:11)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
2 Paran0ik (26/04/2010 02:30) и Гость (26/04/2010 03:40)
нет гарантии, что один из участников не расскажет всем, какая у вас монета, тогда один участник (тот, что слева от вас) узнает – правду вы сказали насчет совпадения ваших с ним монет или нет...

Кстати, что касается оригинального простейшего протокола DC-net, Чаум предупреждает по крайней мере ещё о двух очевидных недостатках.


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


Во-вторых, тот кто последним объявляет результаты совпадений, может объявить своё совпадение на основании объявлений всех предыдущих участников таким образом, чтобы получить бит по-собственному желанию (например, кто-то из них анонимно хотел заявить, что платит, а получится, что в итоге все остальные будут думать, что за них заплатит АНБ или наоборот).

— poptalk (30/04/2010 01:07)   профиль/связь   <#>
комментариев: 259   документов: 12   редакций: 3
Если я правильно понимаю, Tor увеличивает трафик во столько раз, сколько длина цепочки, а алгоритм Чаума во столько раз, сколько участников сети. Господа, не надо обмениваться пираткой, вы же положите Интернет. :)
— unknown (30/04/2010 09:49, исправлен 30/04/2010 09:52)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Да при обмене пираткой обычный протокол Чаума будет саботироваться анонимами, а Dissent имеет смысл только для закрытых малых групп (дальше не масштабируется, впрочем как и DC-net).


Кстати, Dissent, хотя и использует DC-net, не является информационно-стойким, так как опирается ещё и на стойкость обычных алгоритмов.


Ещё одно интересное свойство (практически полная защита анонимности внутри сети Dissent): в Dissent для раскрытия анонимности пользователя нужно, чтобы все N-2 узлов были злонамеренными (при N-1 узлов требование анонимности становится абсурдом и невыполнимо по определению). Ну и защита против анализа трафика снаружи от глобального наблюдателя практически абсолютная.


Только так ли уж практичен суперанонимный протокол для заведомо малой группы?

— DDRTL2009 (01/05/2010 14:57)   профиль/связь   <#>
комментариев: 115   документов: 19   редакций: 17
Только так ли уж практичен суперанонимный протокол для заведомо малой группы?

в некоторых обстоятельствах пригодится!
— Гость (09/08/2012 14:52)   <#>
так ли уж практичен суперанонимный протокол для заведомо малой группы?
А если предстваить себе малую группу малых групп? И так далее... ;)
— unknown (09/08/2012 15:11, исправлен 09/08/2012 15:20)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

А если он не масштабируется по затратам ресурсов в текущей модели?
А если при смене модели он теряет заявленные анонимные свойства?
И так далее...
Хотя авторы работают над этим.

Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3