Проблема криптографів, що обідають

Не плутати з проблемою філософів, що обідають.

Проблема криптографів, що обідають присвячена питанню анонімної передачі інформації через публічні повідомлення. Девід Чаум першим визначив цю проблему в 1988 році і використав наочний приклад, який показує, що існує можливість надсилання анонімних повідомлень без обмежень для відправника і з невідстежуваністю адреси одержувача. Анонімні мережі зв'язку, здатні вирішувати цю задачу, часто згадуються як DC-мережі.

Попри подібність назви, проблема криптографів, що обідають, не має стосунку до проблеми філософів, що обідають.

Опис

Ілюстрація проблеми криптографів, що обідають

Три криптографи зібралися за обіднім столом. Офіціант повідомляє їм, що замовлення вже оплачено. Це міг зробити як один із криптографів, так і зловмисник. Криптографи поважають право один одного заплатити анонімно, але хочуть з'ясувати, чи не заплатив бува зловмисник. Для розв'язання цього завдання запроваджується двохетапний протокол.

На першому етапі кожні два криптографи визначають спільний секрет вагою в один біт, домовившись кидати монету. Вони ховаються за меню таким чином, що тільки двоє криптографів, які кидають монету, можуть бачити результат підкидання. Припустимо, після підкидання монети криптографи A і B мають спільний секрет — ${\displaystyle \scriptstyle 1}$, криптографи А і С — ${\displaystyle \scriptstyle 0}$, В і С — ${\displaystyle \scriptstyle 1}$.

На другому етапі кожен криптограф публічно оголошує біт, який обчислює наступним чином:

• якщо він не платив за замовлення, то оголошує результат операції «Виключне АБО (XOR)» тих бітів, які він отримав разом із двома своїми сусідами;
• якщо він заплатив, то оголошує результат, протилежний операції XOR.

Припустимо, що жоден з криптографів не платив. Тоді криптограф А оголосить ${\displaystyle \scriptstyle 1\,\oplus \,0\;=\;1}$, B оголосить ${\displaystyle \scriptstyle 1\,\oplus \,1\;=\;0}$, С — ${\displaystyle \scriptstyle 0\,\oplus \,1\;=\;1}$. Інакше, якщо наприклад криптограф А здійснив оплату, то він оголосить ${\displaystyle \scriptstyle \lnot {(1\,\oplus \,0)}\;=\;0}$.

Після завершенню другого етапу будь-який із криптографів виконує операцію XOR всіх заявлених біт. Якщо в результаті виходить ${\displaystyle \scriptstyle 0}$, то це означає, що ніхто з криптографів не платив (тому можна зробити висновок, що оплата була здійснена зловмисником). В іншому випадку (якщо виходить ${\displaystyle \scriptstyle 1}$), то це означає, що заплатив один із криптографів, однак його особистість залишається невідомою для всіх інших.

Для цієї задачі Девід Чаум придумав назву «Проблема криптографів, що обідають», а також назву для мереж, здатних вирішувати дану проблему — «DC-мережі» (абревіатура від англ. Dining Cryptographers).

Обмеження

В оригінальній роботі Девіда Чаума постулюється кілька обмежень, які можуть впливати на практичне використання протоколу DC-мереж:

Колізії

Якщо два криптографи заплатили за обід, то повідомлення будуть перекривати одне одне, і результат операції XOR для розглянутої пари буде 0. Ця ситуація називається колізією, і в цьому випадку тільки одному з учасників, що платили, дозволено використання цього протоколу для передачі свого повідомлення в рамках поточного раунду.

Порушення

Будь-який зловмисний криптограф, який не хоче, щоб група успішно взаємодіяла, може саботувати протокол так, що остаточний результат операції XOR буде невірний. Зробити це можливо відправивши довільні біти замість правильного результату операції XOR. Ця проблема виникає через те, що оригінальний протокол було розроблено без механізму перевірки того, чи чесно учасники дотримуються протоколу.

Складність

Протокол вимагає попарних спільних секретних ключів між учасниками, що складно реалізувати при великій кількості учасників. Якщо в трьох криптографів таких ключів три, то в 15 криптографів таких ключів буде вже 105.

Узагальнення

DC-мережі узагальнюються для забезпечення передач, більших, ніж розміром в один біт для більш ніж трьох учасників, і для довільних букв алфавіту, відмінних від двійкових 0 і 1.

Передача довгих повідомлень

Для того, щоб анонімний відправник міг передати більше одного біта інформації за один раунд виконання протоколу DC-мережі, група криптографів може просто повторити протокол стільки разів, скільки необхідно, щоб створити потрібну кількість біт (виходячи з пропускної здатності каналу). В DC-мережах пари учасників мають можливість заздалегідь домовитися про один загальний ключ, використовуючи, наприклад, ключ отриманий за допомогою протоколу Діффі-Геллмана. Потім кожен учасник локально встановлює цей загальний ключ в генератор псевдовипадкових чисел для того, щоб зробити якомога більше спільних «кидків монети», що дозволить анонімному відправнику передати декілька біт інформації.

Більша кількість учасників

Протокол може бути застосований до групи, що складається з n-учасників, кожен з яких має спільний секретний ключ з іншими учасниками. У кожному раунді роботи протоколу, якщо учасник хоче передати групі повідомлення, яке не може бути простежено, він інвертує його публічно оголошені біти. Учасники можуть бути представлені у вигляді повного графу, де вершини — учасники, а ребра — їх спільні секретні ключі.

Граф розмежування загального доступу

Протокол може бути запущений з використанням неповного графу загальних ключів, який може поліпшити продуктивність і масштабованість реалізованих на практиці DC-мереж. Однак, у разі використання неповного графу з'являється ризик того, що учасники змови можуть розділити граф спільного доступу на окремі компоненти зв'язності і домогтися порушення анонімності.

Наприклад, для групи з більш ніж трьох учасників привабливим видається варіант з використанням кільцевої топології, де кожен криптограф, що сидить за столом,  має спільний секретний ключ тільки з сусідами (ліворуч і праворуч від нього). Така топологія приваблива, оскільки кожен криптограф має координувати два кидка монети за один раунд, а не n кидків, як у випадку з повним графом ключів. Проте якщо Адам і Чарлі, що сидять ліворуч і праворуч від Боба, таємно змовилися і розкрили свої секретні ключі один одному, то вони могли б упевнено визначити, чи є Боб відправником поточного біта-повідомлення в межах розглянутого раунду, незалежно від загальної кількості учасників. Такий ефект виникає внаслідок того, що учасники, які змовились (Адам і Чарлі), «розбили» граф загального доступу на два незалежних розрізнених компоненти, один з яких складається тільки з Боба, інший — з усіх інших чесних учасників.

Інша топологія DC-мережі загального доступу, яка використовується в системі Dissent для масштабування, може бути описана як клієнт-серверна топологія. У цьому варіанті визначено два типи учасників, які грають різні ролі: потенційно велика кількість користувачів n, які бажають залишитися анонімними, і набагато менше число m довірених осіб, чия роль полягає в забезпеченні анонімності всіх користувачів. У такій топології кожен з n користувачів має спільний секретний ключ з кожним із m довірених осіб, але користувачі не мають спільних секретних ключів один з одним безпосередньо, так само як і довірені особи не мають спільних секретних ключів один з одним — результатом є матриця взаємодії n*m. Якщо кількість довірених осіб m є малою, то кожен користувач повинен володіти інформацією тільки про декілька загальних секретних ключів, що покращує ефективність взаємодії користувачів таким же чином, як це було здійснено у кільцевій топології. Тим не менше, доки хоча б один учасник з числа довірених осіб поводиться чесно і не видає свої секрети, а також не вступає в змову з іншими учасниками, ця чесна довірена особа стає хабом, який єднає всіх чесних користувачів в одну взаємодію з усіма своїми частинами компонент, незалежно від того, чи вступили інші користувачі або довірені особи в нечесну змову. Користувачам не потрібно знати або вгадувати, які довірені особи чесні. Їх безпека, на думку авторів протоколу, залежить тільки від існування принаймні однієї чесної довіреної особи, яка не бере участь у змові.

Альтернативні алфавіти і оператори

Хоча простий протокол DC-мережі використовує двійковий код як алфавіт передачі і оператор XOR для об'єднання шифротексту, основний протокол вводить у вжиток будь-який з алфавітів і використовує оператори, аналогічні XOR, допустимі для використання в шифруванні Вермана. Така гнучкість виникає природно, оскільки секрети розподілені між багатьма парами учасників, які, за фактом, реалізують між собою шифрування Вермана в межах одного раунду DC-мережі.

Одним з альтернативних виборів алфавіту DC-мережі є використання скінченної групи, яка є придатною для використання в криптографії з відкритим ключем. Наприклад, припустимо використовувати або еліптичні криві. Такий вибір алфавіту дозволяє учасникам використовувати доказ з нульовим розголошенням для перевірки виробленого протоколом шифротексту. Зокрема перевіряється, чи не порушує один з учасників протокол, причому при перевірці дотримується анонімність, передбачена DC-мережею. Ця техніка була вперше запропонована Голлем і Джуелсом і реалізована в Verdict, імплементації Dissent.

Запобігання та обробка колізій

В оригінальній роботі Чаума пропонується наступний метод обробки колізій. Користувач, який займається в даний момент відправкою повідомлення DC-мережі, в кожному раунді своєї передачі отримує результуючий біт. Якщо результуючий біт не збігається з тим, який він хоче передати в поточному раунді, то користувач робить висновок, що відбулась колізія. Він чекає випадкове число раундів, і знову пересилає повідомлення. Конкретні параметри пересилання Чаум пропонує вибирати на основі аналізу трафіку в мережі.

Dissent запобігає ненавмисним колізіям в мережі використовуючи розклад передачі повідомлень. Розклад складається за допомогою випадкової перетасовки учасників, причому кожен з учасників знає, які з передбачуваних біт передачі відносяться до його черги, але не знає, кому належать інші біти.

так само пропонує учасникам домовитися про розклад передачі повідомлень в кожному раунді комунікації. Кожен учасник вибирає собі випадковий слот розкладу для передачі, і якщо цей слот використовує хтось інший, то розглянутий учасник відмовляється від передачі. Якщо учасник чекає свого слота занадто довго, він автоматично перепідключається до групи через визначений протоколом відрізок часу. Протоколом передбачена перевірка цілісності даних з використанням алгоритму хешування MD5.

Протидія порушенням протоколу

поділяє DC-мережу на кілька груп, дозволяючи учасникам втікати від порушень. Учасник може покинути свою поточну групу і перевіряти інші до тих пір, поки не знайде групу, вільну від порушень. Такий підхід може призвести до того, що зловмисник, що володіє доступом до багатьох груп DC-мережі, може маніпулювати поведінкою учасника, підводячи його до участі в групі, де всі інші учасники знаходяться в змові.

Dissent імплементує кілька схем для протидії порушенням. Оригінальний протокол використовує випадкові розклади передачі повідомлень і поширює таблицю передачі разом з розміром поточного повідомлення. Такий підхід дозволяє перевірити коректність послідовності шифротексту в DC-мережі за допомогою обчислення хеш-функції. Однак, така техніка веде до великих, за розрахунками авторів, затримок у передачі повідомлень. Пізніше, була запропонована інша схема протидії, яка не здійснює перемішування для побудови розкладу передачі поки порушення відсутні, але у разі, якщо в мережі починаються порушення, перемішування поновлюються, і з'являється можливість вирахувати порушника. Найсучасніші версії Dissent підтримують повну перевірку DC-мережі при значній вартості обчислень через використання криптосистеми з відкритим ключем. У той же час, сучасні версії Dissent можуть працювати в гібридному режимі, який використовує традиційні DC-мережі, засновані на XOR-операції в нормальному випадку, і використовує DC-мережі з перевіркою тільки в разі порушень. На думку авторів протоколу такий підхід дозволяє вирахувати порушника швидше, ніж це можливо за допомогою побудови розкладу передачі на основі перетасовок.

Примітки

1. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988, 1.4. Proof of Security.
2. Шнайер: Прикладная криптография, 2002, 6.3 Анонимная широковещательная передача сообщений.
3. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988, Introduction.
4. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988.
5. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988, 1. Generalizing the Approach.
6. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988, 1.3. Collusion of Participants.
7. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability, 1988, 2.3. Example Key-Sharing Graphs.
8. A 2-Round Anonymous Veto Protocol, 2009, 3. Performance.
9. Dining Cryptographers Revisited, 2004, 2 Background.
10. Dissent in numbers: making strong anonymity scale, 2012, 3.2 Design and Deployment Assumptions.
11. Proactively Accountable Anonymous Messaging in Verdict, 2013, 2.3 Practical Generalizations.
12. Dining Cryptographers Revisited, 2004, 4.1 Intuition and tools.
13. Proactively Accountable Anonymous Messaging in Verdict, 2013, 5.1 Verifiable DC-net Primitive API.
14. Dissent: Accountable Anonymous Group Messaging, 2010, 5.5 End-to-End Reliability.
15. Herbivore: A Scalable and Efficient Protocol for Anonymous Communication, 2003, 4.2 Round Protocol.
16. Eluding Carnivores: File Sharing with Strong Anonymity, 2004, 3 Herbivore.
17. Denial of service or denial of security?, 2004, 1. INTRODUCTION.
18. Dissent: Accountable Anonymous Group Messaging, 2010, 7. RELATED WORK.
19. Proactively Accountable Anonymous Messaging in Verdict, 2013, 4.4 Hybrid XOR/Verifiable DC-Nets.

Література

• David Chaum. The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability // Journal of Cryptology : журнал. — 1988. — Iss. 1. — P. 66—75. — DOI:10.1007/BF00206326.
• David Isaac Wolinsky, Henry Corrigan-Gibbs, Bryan Ford, Aaron Johnson. Dissent in numbers: making strong anonymity scale // OSDI'12 Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation. — USENIX Association Berkeley, CA, USA ©, 2012. — P. 179—192. — .
• Philippe Golle, Ari Juels. Dining Cryptographers Revisited // Advances in Cryptology - EUROCRYPT 2004. — 2004. — P. 456–473. — .
• Henry Corrigan-Gibbs, David Isaac Wolinsky, and Bryan Ford. Proactively Accountable Anonymous Messaging in Verdict // SEC'13 Proceedings of the 22nd USENIX conference on Security. — USENIX Association Berkeley, CA, USA, 2013. — P. 147–162. — .
• Henry Corrigan-Gibbs, Bryan Ford. Dissent: Accountable Anonymous Group Messaging // CCS '10 Proceedings of the 17th ACM conference on Computer and communications security. — ACM New York, NY, USA, 2010. — P. 340–350. — . — DOI:10.1145/1866307.1866346.
• Emin Gün Sirer, Sharad Goel, Mark Robson, Doğan Engin. Eluding Carnivores: File Sharing with Strong Anonymity // EW 11 Proceedings of the 11th workshop on ACM SIGOPS European workshop. — ACM New York, NY, USA, 2004. — No. 19. — DOI:10.1145/1133572.1133611.
• Nikita Borisov, George Danezis, Prateek Mittal, Parisa Tabri. Denial of service or denial of security? // CCS '07 Proceedings of the 14th ACM conference on Computer and communications security. — ACM New York, NY, USA, 2004. — P. 92–102. — ISSN 978-1-59593-703-2. — DOI:10.1145/1315245.1315258.
• Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. 2-е видання. — Триумф, 2002. — .
• Feng Hao and Piotr Zielinski. A 2-Round Anonymous Veto Protocol // Volume 5087 of the series Lecture Notes in Computer Science. — ACM New York, NY, USA, 2009. — P. 202-211. — .
• Sharad Goel, Mark Robson, Milo Polte, Emin G¨un Sirer. Herbivore: A Scalable and Efficient Protocol for Anonymous Communication. — Cornell University, Ithaca NY 14850, USA, 2003.