Sphinx: анонімний формат даних, що лежить в основі Lightning та Nym

Функціональна мікс-мережа, здатна забезпечити вищий рівень конфіденційності на мережевому рівні, ніж Tor, вже давно є мрією захисників приватності, дослідників і шифропанків. Мікс-мережі з’явилися раніше за Tor, а їхнім найефективнішим на сьогодні втіленням став Mixminion — ремейлер «типу 3», призначений для анонімного надсилання електронної пошти. Після того як розробка мікснетів загальмувала — коли двоє провідних розробників Mixminion, Нік Метьюсон і Роджер Дінглдін, перейшли до створення Tor, — з 2003 року майже не велося роботи над проєктами з відкритим кодом, а з 2011 року не було жодного коміту.

Завдяки ініціативі, що розпочалася з PANORAMIX і продовжується в межах Nym, мікснети знову в строю.

Як детально описано в нашій попередній публікації, мікснет Nym складається з мікс-вузлів, які передають пакети один одному. Вузли додають часові затримки, щоб приховати часові метадані транзакцій, а також генерують фіктивний трафік, коли бракує реального трафіку. Отже, мікснет Nym забезпечує вищий рівень конфіденційності для трафіку, що базується на повідомленнях, порівняно з Tor чи VPN (зокрема dVPN).

Справжній секрет ефективності мікснетів полягає у форматі пакетів Sphinx, який використовують як Nym, так і Lightning Network. Sphinx складний для розуміння, і Lightning Network не використовує його в такий спосіб, що гарантував би анонімність. Тож давайте детально розберемося зі Сфінксом і розгадаємо його загадки!

Що таке Sphinx?

Sphinx¹ анонімно направляє повідомлення від відправника до отримувача. Вона забезпечує низку властивостей, необхідних для анонімності відправника в системах із багаторазовою передачею (multi-hop systems):

1. Побітове роз’єднання: будь-який пакет, що надходить у мікс, не може бути співвіднесений з будь-яким вихідним пакетом на основі його двійкового представлення зловмисником, який спостерігає за мережею. Іншими словами, пакети є анонімними.
2. Цілісність: стійкість до активних атак, таких як тегування (tagging) та атаки повторного відтворення (replay attacks), під час яких зловмисник модифікує та повторно вводить повідомлення, щоб отримати інформацію про їхніх одержувачів або вміст.
3. Приховування інформації про маршрутизацію: Жоден змішаний вузол не може визначити кількість переходів, які пройшов пакет, або довжину шляху повідомлення. Конкретному мікс-вузлу відомі лише попередній та наступний мікс-вузли.

У протоколі Sphinx пакети анонімних відповідей можуть забезпечувати анонімність отримувача завдяки використанню блоків відповіді одноразового використання (SURB), які неможливо відрізнити від повідомлень Sphinx, що передаються мережею в прямому напрямку.

Sphinx — коротко й по суті

Пакет Sphinx складається з двох незалежних частин:

1. Заголовок, що містить усю інформацію, необхідну для маршрутизації повідомлення від джерела до пункту призначення; та
2. Корисне навантаження, всередині якого приховано власне зміст повідомлення.

Уявімо світ, у якому Накамото хоче анонімно надіслати повідомлення Гелу Фінні через мікс-мережу, де вузли ідентифікуються за допомогою своїх IP-адрес і відкритих ключів. Накамото має розподілити ключі так, щоб кожен мікс-вузол на маршруті міг розшифрувати необхідну інформацію для пересилання зашифрованого пакета, водночас зберігаючи решту маршруту прихованою.

Структура Sphinx

Спершу Накамото обирає маршрут, знаходячи відкритий ключ кожного мікс-вузла та обчислюючи спільний ключ для кожного з них. Компонент ключ заголовка Sphinx — це єдиний груповий елемент ɑ, який у поєднанні з відкритими ключами вузлів дозволяє обчислювати спільний ключ для кожного за допомогою обміну ключами Діффі-Хеллмана, і таким чином перший вузол на обраному користувачем маршруті може переслати пакет наступному, і лише цей мішаний вузол може його розшифрувати.

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

Елемент групи ɑ криптографічно закривається на кожному кроці змішування, щоб запобігти кореляції пакетів для кожного користувача. Множник засліплення b отримують зі спільного ключа s, завдяки чому і відправник, і відповідний мікс можуть виконувати всі операції, необхідні для пересилання пакетів. Корисне навантаження δ у пакеті Sphinx обчислюється з використанням шифру з широким блоком, щоб гарантувати: якщо зловмисник змінить корисне навантаження на будь-якому етапі, вміст повідомлення буде безповоротно втрачено. Тег цілісності ɣ, закодований у заголовку, дозволяє перевіряти лише те, чи не був також змінений заголовок пакета. Усі пакети на кожному етапі передачі мають бути доповнені до однакової довжини.

Забезпечити постійну довжину заголовка складніше. Sphinx використовує вдосконалений метод доповнення (padding) для забезпечення постійного розміру пакетів із мінімальними додатковими витратами.

Створення пакета Sphinx

Щоб спрямувати повідомлення m через обраний шлях із мікс-вузлів M₀, M₁, M₂, Накамото генерує нове секретне значення x і попередньо обчислює всі групові елементи ɑ, спільні ключі s та фактори засліплення b, використовуючи x і відкриті ключі мікс-вузлів. Він розпочинає кодування заголовка з пошарової інкапсуляції маршрутної інформації (наприклад, IP-адреси) разом із тегом цілісності заголовка для кожного вузла змішування (mix-node) на маршруті — у порядку від останнього вузла до першого.

Найглибший шар сформовано як конкатенацію адреси Фінні ∆*, ідентифікатора I, що використовується для SURB, та послідовності заповнювальних даних, яка гарантує, що довжина шляху не буде випадково розкрита. Потім вони шифруються шляхом виконання операції XOR із вихідними даними генератора псевдовипадкових чисел, ініціалізованого спільним ключем _s_₂. Зрештою результат об’єднується із заповнювальним рядком ɸ; його додавання гарантує, що розмір заголовків пакетів залишається незмінним під час додавання або видалення рівнів шифрування. Коли остаточна зашифрована інформація про маршрутизацію β₂ готова, Накамото обчислює її HMAC як тег цілісності ɣ₂ = HMAC(s₂, β₂) і шифрує цю інформацію про маршрутизацію β, об’єднану з тегом цілісності ɣ. Процес починається знову з β₁, а потім рекурсивно переходить до наступного β, як показано нижче:

Формування пакета Sphinx: що темніший сірий колір, то сильніше шифрування!

Далі Накамото повторно використовує обчислені спільні ключі для багаторівневого шифрування корисного навантаження. Так само, як і у випадку із заголовком, інкапсуляція корисного навантаження виконується у порядку, зворотному до маршруту проходження через мікс-вузли. Початкове значення δ₂ формується шляхом застосування шифру з широким блоком (з використанням ключа s₂) до конкатенації повідомлення m, адреси Фінні ∆ та послідовності нульових байтів (заповнювача); це уможливлює перевірку того, що тіло повідомлення не було змінено під час передачі — якщо зловмисник змінить бодай один біт, шифр із широким блоком розшифрує дані у випадкову послідовність бітів.

Фінні все ще повинен мати змогу відрізнити дійсне повідомлення від випадкового шифротексту, використовуючи додаткове доповнення нульовими байтами за відомою послідовністю. Щойно δ₂ буде готове, Накамото знову шифрує його, використовуючи s₁ та s₀ — одне за одним.

Обробка пакета Sphinx

1. Отримавши пакет, мікс-вузол видобуває елемент групи ɑ із заголовка та поєднує його зі своїм секретним ключем, щоб отримати спільний ключ s.
2. Використовуючи s, мікс обчислює хеш-ключ зашифрованої маршрутної інформації як HMAC(s, β) та порівнює його з тегом цілісності ɣ, доданим до заголовка пакета. Якщо перевірка цілісності не проходить через те, що заголовок було змінено, пакет відкидається. В іншому разі мікс-вузол переходить до кроку 3.
3. Змішаний вузол тепер готовий розшифрувати приєднаний β. Щоб видобути інструкції з маршрутизації, мікс-вузол спочатку додає нульовий байт-заповнювач у кінець β і розшифровує доповнений блок інформації про маршрутизацію B, виконуючи операцію XOR із псевдовипадковим потоком байтів, згенерованим за допомогою s. Обсяг нульового заповнення, що додається до β, дорівнює довжині інструкцій із маршрутизації, які мікс-вузол має вилучити для збереження незмінності довжини. Зверніть увагу, що оскільки відступи хешуються всередині тегу цілісності ɣ, вони мають бути ідентичними відступам, попередньо згенерованими Nakamoto.
4. Мікс-вузол розбирає інструкції з маршрутизації, отримані від B, щоб визначити адресу наступного мікс-вузла (або, у випадку останнього етапу передачі, адресу призначення ∆ та ідентифікатор I), а також нові теги цілісності ɣ’ і β’, які слід передати на наступний етап.
5. Мікс-вузол також виконує розшифрування δ за допомогою шифрування широкими блоками, отримуючи δ’, що буде передано на наступний етап маршруту.
6. Мікс-вузол маскує отримане значення ɑ за допомогою множника маскування, отриманого зі спільного ключа s, щоб отримати новий груповий елемент ɑ’.

Після того як заголовок і корисне навантаження зашифровано, а груповий елемент — засліплено, мікс-вузол може сформувати новий пакет у вигляді ((ɑ’, β’, ɣ’), δ’) і переслати його на наступну адресу.

Оригінальна ілюстрація формату пакетів Sphinx із праці Дейнезіса та Голдберга (2014).

Як Nym протидіє атакам на Sphinx

Однією з найкращих рис Sphinx є те, що він має доведену безпеку: в оригінальній статті наведено доведення безпеки для властивостей, що лежать в його основі. Загалом нам потрібні доведення безпеки — завдання, яке криптографи зазвичай виконують вручну, щоб продемонструвати, що певна схема справді має набір властивостей, які можна логічно обґрунтувати на основі низки математичних припущень. Набагато складніше довести властивості конфіденційності, які зазвичай передбачають симуляцію.

Коли криптографи вручну розробляють доведення безпеки, вони можуть припускатися помилок або просто не врахувати певні аспекти того, що намагаються довести. Робота Куна та ін.² демонструє, що через недостатність формальних властивостей, визначених Каменішем і Лисянською³ для систем на основі цибулевої маршрутизації, у доведенні безпеки, представленому Данезісом і Голдбергом, не було виявлено суттєвого недоліку початкового проєкту пакета Sphinx. Якщо цей недолік не буде усунуто, це може суттєво зашкодити конфіденційності користувачів у системах, що використовують Sphinx.

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

Як було описано раніше, останній мікс-вузол у маршруті отримує найглибший рівень зашифрованої маршрутної інформації β, сформований шляхом шифрування адреси отримувача (∆), ідентифікатора (I) та нульового байта-заповнювача, а також об’єднаний із рядком-заповнювачем ɸ.

Згідно з позначеннями, використаними у статті про Сфінкса, найвнутрішня β створюється як

де |ɸ| = 2(v-1)κ, а κ та r — це відповідно параметр безпеки та максимальна довжина шляху, тоді як v — довжина шляху, пройденого пакетом. Обробка отриманого β мікс-вузлом виконується так:

Отже, як саме останній мікс-вузол отримує інформацію про довжину шляху завдяки цій магічній математиці?

Щоб пояснити, як працює ця атака, ми наведемо простий приклад. Спершу зауважмо, що для значення x = a⊕b величини x, a та b мають однакову довжину, а якщо ми додатково застосуємо операцію XOR до x і b, то отримаємо x⊕b = a⊕b⊕b = a. Для нашого прикладу припустімо, що результатом роботи генератора псевдовипадкових чисел (PRNG), на вхід якого подано спільний ключ вузла v-1, є послідовність 10101010101010101010….

Розгляньмо тепер значення β, отримане в результаті останнього змішування.

Тепер, дотримуючись (2), ми виконуємо ті ж операції, що й вихідний мікснод для розшифрування та розбору β

Згідно з проєктом, останній мікс-вузол на шляху знає загальну довжину очікуваного значення β (у нашому прикладі вона становила 9 бітів), а також те, що за конкатенацією адреси призначення (∆) та ідентифікатора (I) йдуть, відповідно, заповнення нулями та псевдовипадкові біти рядка-заповнювача. Маючи інформацію про точні довжини ∆ та I, останній вузол змішування, що діє за принципом «чесний, але допитливий» (honest-but-curious), перевіряє, де саме після ідентифікатора з’являється перший біт «1», оскільки йому відомо, що рядок-заповнювач починається в цій точці або раніше. Спостереження за тим, де саме розташований перший біт зі значенням «1» після ідентифікатора, дозволяє останньому вузлу змішування визначити нижню межу довжини заповнювального рядка. Оскільки загальна довжина ɸ за проєктом визначається як подвоєна довжина маршруту, помножена на параметр безпеки κ, нижня межа довжини заповнювального рядка розкриває інформацію про нижню межу довжини використаного шляху.

Чому знання довжини шляху є шкідливим

Як показали дослідження,⁴ у мережах з обмеженими або розрідженими топологіями (наприклад, Lightning) знання довжини шляху зменшує множину анонімності, в межах якої може приховатися відправник. Приклад на наведеному нижче рисунку демонструє, як знання нижньої межі довжини шляху може знизити анонімність відправника. Якщо D діє як вихідний мікс-вузол і пересилає пакет Тіммі, то, не знаючи довжини шляху, неможливо визначити, хто саме є відправником — будь-який із вузлів A, B, C, E, G або F. Однак, якщо D може зробити висновок, що довжина шляху становить щонайменше 3, то, аналізуючи граф мережі, ми визначаємо, що відправником може бути лише A або B; отже, множина потенційних відправників суттєво скорочується.

Запобігти цій атаці досить просто. У (1) коли ми створюємо β замість використання нульового доповнення, нам просто потрібно використовувати доповнення випадковими бітами. Насправді, у реалізації на Python від Джорджа Данезіса цей недолік вже враховано.

Рис. 1

Але ця атака не впливає на Nym

1. Nym використовує стратифіковану топологію для максимізації анонімності, тому всі шляхи мають однакову довжину, а кожен мікс-вузол знає свою позицію на шляху. З Lightning ситуація інша. У ньому використовуються шляхи змінної довжини, тому початкова реалізація протоколу Sphinx була вразливою до цієї атаки, хоча наразі цю вразливість вже усунуто.
2. Останній шар кодування Sphinx знімається самим застосунком, а не вихідним вузлом змішування (як у Tor). Однак реалізація Sphinx від Nym на мові Rust (https://github.com/nymtech/sphinx) є стійкою до цієї атаки (вона використовує рандомізоване доповнення), тому її можна безпечно використовувати в будь-яких системах, що базуються на Sphinx.

Що далі для Nym?

Перший анонімний пакет Sphinx від Nym не стане останнім. Мережа Nym поступово перетвориться на стабільний мікснет загального призначення для будь-якого інтернет-застосунку. Наша тестова мережа вже працює, а запуск у промислову експлуатацію має відбутися до кінця 2020 року.

Але кому взагалі потрібна конфіденційність на рівні мережі? Майже всі, як виявилося.

Мережа Lightning Network вже використовує пакети Sphinx, однак у спосіб, що порушує здатність цієї технології забезпечувати конфіденційність транзакцій, як продемонструвала Клаудія Діас на конференції Lightning Conference у листопаді 2019 року. За умови внесення певних змін протокол Lightning можна було б зробити таким, що забезпечує підвищений рівень конфіденційності, оскільки він уже використовує значну частину інфраструктури (наприклад, Sphinx) спільно з Nym. Поєднання Nym і Lightning може стати найбільш життєздатним шляхом до забезпечення конфіденційності біткоїна.

(iframe src="https://www.youtube.com/embed/g55kMhggIBY?feature=oembed" width="700" height="393")(/iframe)

Клаудія Діас розповідає про те, чому Sphinx не сприяє конфіденційності Lightning, і як це можна виправити.

Криптовалюти з підвищеним рівнем конфіденційності та сайдчейни будь-яких криптовалют також повинні використовувати анонімність на мережевому рівні; інакше зловмисники можуть використати дані про час передачі для деанонімізації пакетів і навіть здійснити атаки на внутрішньомережеві методи забезпечення конфіденційності, такі як zk-SNARKs. Ми налагоджуємо зв’язки з низкою спільнот і незабаром повідомимо більше.

І не забуваймо про інтерес до децентралізованих VPN з боку Brave та інших. З якою швидкістю можуть передаватися пакети Sphinx? Sphinx активно використовує асиметричну криптографію та екзотичні шифри з великим розміром блоку для забезпечення неможливості встановлення зв’язку між повідомленнями, однак його можна було б переробити так, щоб досягти швидкості, необхідної для практичної реалізації подібних сценаріїв використання.

Sphinx наділяє звичайні інтернет-пакети властивістю анонімності, але велика сила передбачає й велику відповідальність. Ми з нетерпінням чекаємо, які нові види послуг і застосунків візьмуть на себе цю відповідальність і будуть створені на базі Nym!

Посилання

¹ Джордж Данезіс та Ієн Голдберг. Sphinx: Компактний і доказово безпечний формат мікс-мереж. У збірнику матеріалів симпозіуму IEEE із питань безпеки та конфіденційності (IEEE Symposium on Security and Privacy), с. 269–282. IEEE, 2009.

² Крістіана Кун, Мартін Бек і Торстен Струфе. Злам і (часткове) виправлення доказово захищеної цибулевої маршрутизації. Препринт arXiv arXiv:1910.13772, 2019.

³ Ян Каменіш і Анна Лисянська. Формальний опис цибулевої маршрутизації. У збірнику «Annual International Cryptology Conference», с. 169–187. Спрінгер, 2005.

⁴ Джордж Данезіс. Мікс-мережі з обмеженими маршрутами. У збірнику матеріалів Міжнародного семінару з технологій захисту конфіденційності, с. 1–17. Спрінгер, 2003.