Як я зробив взаємний підпис договорів між двома телефонами без сервера, без інтернету і без центру сертифікації

💡 Усі статті, обговорення, новини про Mobile — в одному місці. Приєднуйтесь до Mobile спільноти!

Уся сучасна інфраструктура електронного підпису тримається на одному припущенні: у вас є інтернет... Мене звати Дмитро, і я зробив застосунок, який дозволяє двом людям підписати документ, маючи лише камери телефонів і нуль байтів інтернет-трафіку.

Я Дійкун Дмитро, розробник. Роблю Pakto — застосунок для підписання документів між двома сторонами, де підпис створюється апаратним ключем пристрою під біометрією. Соло: протокол, криптографія, клієнт під iOS і Android, бекенд, верифікатор. До цього випустив дві невеликі офлайн-штуки — гру Data Human і трекер звичок HabitGrid, обидві без реклами й аналітики; звідти й тягнеться інтерес до того, скільки всього можна зробити взагалі без сервера.

Найцікавіше не сам застосунок, а протокол під ним: взаємний підпис двома телефонами без інтернету, без сервера і без центру сертифікації. Єдиний канал зв’язку між пристроями — екран і камера.

Застосунок вже є в App Store і Google Play. Зараз готую препринт для ePrint (IACR) із формальним аналізом протоколу, а тут покажу технічний розбір: як розривається циклічна залежність у взаємному підписанні, звідки береться довіра до ключа без CA, як повний токен апаратної атестації їде через QR-канал, і що з цього реально доводиться, а що є інженерним компромісом.

Далі — як це влаштовано і де боліло.

Уся сучасна інфраструктура електронного підпису тримається на припущенні, якого ми зазвичай не помічаємо: у момент підписання є зв’язок. Треба сходити до ЦСК за сертифікатом, перевірити список відкликаних, отримати мітку часу, звернутися до хмари. Заберіть мережу — і схема не працює.

Мене зацікавило питання: а що як мережі немає в принципі? Не «поганий інтернет», а взагалі нічого. Двоє людей стоять поруч із телефонами і мають підписати документ так, щоб через рік третя сторона могла перевірити обидва підписи й переконатися, що кожен ключ живе у справжньому апаратному модулі пристрою.

Так з’явився Pakto — протокол і застосунок, де єдиний канал зв’язку між пристроями — це екран і камера.

Три обмеження одночасно

Задача виглядає простою, доки не випишеш обмеження разом:

1. Немає мережі в момент підписання.
2. Немає сервера, через який проходять підписані дані.
3. Немає центру сертифікації, який поручився б за публічний ключ будь-якої зі сторін.

Канал — оптичний: один телефон показує анімований код, інший читає камерою. Односторонній у кожен момент, з втратами кадрів, з дуже обмеженою пропускною здатністю.

Кожне обмеження окремо вирішується. Разом вони створюють дві справжні проблеми.

Проблема перша: циклічна залежність

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

А не може підписати, доки не відомий Б. Б не може бути прив’язаний, доки А не підписав. Класична циклічність.

Рішення — двоетапний геш-якір.

Нехай H : {0,1}* → {0,1}²⁵⁶ — колізійно стійка геш-функція (SHA-256), ⟨RS⟩ — байт-роздільник 0×1E. Спочатку А обчислює перший якір над змістом документа й тільки своїми полями — без Б, без підписів, без публічних ключів:

h₁ = H("v81" ‖ ⟨RS⟩ ‖ C)

де C = enc(C⃗) — канонічна серіалізація вектора полів C⃗. Цей якір А може порахувати ще до того, як дізнається, хто буде другою стороною. Коли Б приєднується, другий якір визначається як детермінована функція від першого та полів Б:

h₂ = H(h₁ ‖ ⟨RS⟩ ‖ nickB ‖ ⟨RS⟩ ‖ avatarB)

Особа Б прив’язується до вже існуючого зобов’язання А — не руйнуючи перший підпис.

І ось практичний наслідок, заради якого все й робилось. Наївна схема потребувала б трьох раундів обміну: А показує документ → Б додає себе → А досогласовує фінальний результат і переподписує. Оскільки h₂ є детермінованою функцією від h₁, підпис А лишається валідним після приєднання Б — переподписувати нічого не треба.

Тому обмін укладається у два QR-переходи:

1. А → Б: А підписує, показує код із документом і підписом А. Б сканує.
2. Б → А: Б підписує власним ключем, показує фінальний код. А сканує — договір готовий.

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

Зчеплення підписів і чому воно несуче

Два підписані повідомлення:

mA = "A:" ‖ id ‖ ":" ‖ h₁ mB = "B:" ‖ id ‖ ":" ‖ h₂ ‖ ":" ‖ pkA ‖ ":" ‖ σA

де σA = Sign(skA, mA), σB = Sign(skB, mB), і обидва підписи створюються всередині апаратного модуля під біометричним контролем.

Зверніть увагу на mB: він містить і публічний ключ А, і сам підпис А.

Тепер формально. Означимо гру co-signature inseparability: супротивник має доступ до оракула O_B, який на запит (id, C, idB, pkA, σA) повертає σB і записує (id, h₂, pkA, σA) у множину Q. Супротивник виграє, якщо видасть запис, який верифікується, але кортеж (id*, h₂*, pkA*, σA*) ∉ Q — тобто підпис Б валідний під комбінацією, яку Б ніколи не засвідчував.

Теорема. Якщо схема підпису EUF-CMA-стійка, то для будь-якого PPT-супротивника Adv^insep ≤ Adv^euf-cma.

Редукція будується так: підставляємо челендж-ключ як pkB, відповідаємо на запити оракула через власний оракул підпису, а на виході супротивника формуємо m*B і віддаємо як підробку. Валідність підробки тримається на одному кроці — треба показати, що m*B не було серед запитаних повідомлень. І тут вирішує однозначна декодованість шаблону: id — UUID без двокрапок, h₂ — hex фіксованої довжини, pkA — два base64-токени відомої довжини, σA- фінальний base64-токен; алфавіти base64 і hex не містять ":". Отже рядок m*Bоднозначно визначає кортеж, і збіг повідомлень означав би збіг кортежів — протиріччя з умовою виграшу.

Найцікавіше в цьому доведенні — що воно ламається, якщо прибрати поля. Редукція використала лише те, що mB ін’єктивно зобов’язується до (id, h₂, pkA, σA). Викиньте pkA або σA з mB — і супротивник зможе пред’явити той самий σB під іншим σA*, не виходячи із засвідченої множини. Крок із протиріччям не проходить. Тобто ланцюг усередині mB — це рівно те, що купує нероз’ємність, а не «про всяк випадок».

Ін’єктивність кодування: лема, без якої нічого не доводиться

Усі доведення спираються на те, що канонічний кодувальник enc ін’єктивний: різні вектори полів завжди дають різні байти. Інакше два різні документи могли б дати один h₁, і зобов’язання А перестало б бути зобов’язанням.

Лема. Зафіксуємо схему арності n (упорядкований список слотів, кожен простий або складений із двох під-полів). Кодувальник застосовує екрануючу мапу f до кожного значення (переписує кожен байт ⟨RS⟩ всередині значення на ⟨US⟩), склеює n токенів через ⟨RS⟩, а під-поля складеного слота — через ⟨US⟩. Тоді на допустимій області enc ін’єктивний.

Доведення через декодованість. Розіб’ємо s = enc(C⃗) по байту ⟨RS⟩. За побудовою ⟨RS⟩ трапляється в s лише між токенами верхнього рівня: усередині кожного значення кодувальник уже переписав ⟨RS⟩ ↦ ⟨US⟩. Отже розбиття дає рівно n токенів f(v₁), …, f(vₙ) у порядку, без неоднозначності щодо їх кількості чи меж — арність фіксована й публічна.

Два різні вектори відрізняються хоча б в одній компоненті i. Якщо f(vᵢ) ≠ f(wᵢ) — відновлені кортежі різні, отже різні й кодування. Лишається випадок vᵢ ≠ wᵢ, але f(vᵢ) = f(wᵢ): оскільки f переписує лише ⟨RS⟩ ↦ ⟨US⟩ і в іншому є тотожністю, це вимагає значень, які відрізняються виключно байтами ⟨RS⟩-проти-⟨US⟩ на тих самих позиціях. На допустимій області схема забороняє сирий ⟨RS⟩ всередині значень, тому там f — тотожність, і f(vᵢ) = f(wᵢ) ⇒ vᵢ = wᵢ. Протиріччя. ∎

Чесна заувага про область. Ін’єктивність тримається на допустимій області — де значення не містять сирого ⟨RS⟩, який хтось очікував побачити як дані. На практиці хешовані поля — це UUID, base64/hex-дайджести, ISO-8601 таймстемпи й короткі людські рядки; жодне з них легітимно не містить керуючих байтів 0×1E/0×1F.

Якщо хочеться безумовного твердження без застережень — треба переходити на length-prefixed (TLV) кодування, де кожне поле кодується як <довжина_в_байтах>:<значення>. Довжина робить розбір однозначним незалежно від вмісту. Саме туди я й перейшов у наступній версії схеми; ціна — несумісність із раніше підписаними документами, тому обидві схеми живуть паралельно з версійним префіксом.

Стійкість до підміни після підписання

Ще одна властивість, яку варто довести, а не постулювати: жодне поле, зобов’язане першим підписом, не можна змінити після підписання.

Теорема. Якщо схема підпису EUF-CMA-стійка і H колізійно стійка, то Adv^tamper ≤ Adv^euf-cma + Adv^cr.

Доведення розпадається на дві взаємно виключні події для m*A:

• E₁: m*A ніколи не було в оракулі. Тоді це свіже повідомлення, яке верифікується — готова EUF-CMA-підробка.
• E₂: m*A збігається з якимось запитаним mA. Шаблон "A:" id ":" h₁ однозначно декодований, отже збіг повідомлень форсує h₁* = h₁, тобто H("v81" ‖ ⟨RS⟩ ‖ C*) = H("v81" ‖ ⟨RS⟩ ‖ C). Але вектори різні за умовою виграшу, а за лемою ін’єктивності різні вектори дають різні рядки. Різні входи, однакові образи — колізія H.

Події вичерпні й неперетинні, сума меж дає теорему. ∎

Практичний зміст: змініть суму, сторону, дату чи геолокацію в підписаному документі — і верифікатор поверне помилку, бо перерахований h₁ не зійдеться з тим, над яким стоїть підпис.

Проблема друга: довіра до ключа без CA

Без мережі й без CA отримувач не може завантажити й перевірити ланцюг сертифікатів для ключа відправника. Звідки впевненість, що на тому боці справжній апаратний ключ, а не програмний на емуляторі?

Заміна сертифікатної довіри — транспортована апаратна атестація.

Ключ ECDSA P-256 генерується всередині захищеного апаратного модуля (Secure Enclave / StrongBox) і ніколи його не покидає. Платформа видає токен атестації τ, який криптографічно засвідчує: цей публічний ключ згенеровано в справжньому апаратному модулі.

Зазвичай такий токен перевіряють на сервері. Тут сервера немає — тому повний токен їде оптичним каналом, а в підписаний якір входить лише його геш із контекстним префіксом:

deviceTokenHashA = H("pakto_device_A:" ‖ τA)

Контекстний префікс тут не декоративний: він розділяє домени, щоб геш токена А не міг бути підставлений як геш токена Б.

І ось де починається інженерія: повний об’єкт атестації не влазить в один статичний QR-код. Тому транспорт зроблено на безрейтовому (fountain) коді.

Fountain-код на оптичному каналі

Структура передачі (поля змісту, h₁, σA, pkA, повний τA, id схеми, id сесії) стискається й ріжеться на k базових фрагментів по ~675 байт. Базові кадри несуть один фрагмент; fountain-кадри несуть XOR псевдовипадкової підмножини:

seed = seq LCG: x ← (1664525·x + 1013904223) mod 2³² degree d = (seq mod k) + 1 frame = ⊕ {fragment[j] : j ∈ subset(seed, d)}

Декодер «відлущує» фрагменти (peeling): кадр ступеня 1 одразу дає фрагмент; відомі фрагменти XOR-яться з кадрами вищого ступеня, знижуючи їх ступінь, і процес повторюється. Завершення підтверджується коротким чексумом — префіксом H(payload).

Ключова властивість: код безрейтовий, тому зворотний канал не потрібен. Не треба просити «повтори кадр 17» — просто крутіть анімацію, доки декодер не збереться. Для односторонньої оптики це критично: зворотного каналу фізично немає, доки інший телефон не почне показувати свій код.

Одразу зазначу чесно: конкретне правило ступеня — інженерний вибір, а не оптимальна конструкція. Оптимальність LT/Raptor доводиться для інших розподілів ступенів; я не претендую на те, що ця схема оптимальна, лише на те, що вона працює на потрібних розмірах.

Практика: те, чого немає в специфікаціях

Apple Secure Enclave видає HIGH-S підписи. Якщо ваш верифікатор строго відхиляє high-S за BIP-62-подібним правилом — ви зламаєте всі підписи з iOS-пристроїв. Довелось нормалізувати, а не відхиляти:

if s > n/2:  s ← n − s

Строгий DER-декодер обов’язковий. Наївний парсер приймає «хвіст» після SEQUENCE, неканонічне кодування довжини, r/s поза діапазоном — це класична DER-malleability: той самий підпис у кількох байтових представленнях. Декодер має відхиляти все, крім єдиного канонічного кодування.

Перевірка точки на кривій. Публічний ключ треба перевіряти на належність P-256 (n·P = O), інакше відкривається invalid-curve attack.

Паритет реалізацій. Ядро протоколу реалізоване двічі — Dart (клієнт) і Python (незалежний верифікатор), збіг підтверджено байт-у-байт. Це не естетика: якщо верифікатор пишеться незалежно іншою мовою й дає ті самі геші, значить доказ не залежить від моєї реалізації.

Чого протокол не робить

Тут намагаюсь бути акуратним, бо спокуса перепродати велика.

Відсутність CA — це компроміс, а не безкоштовний виграш. Довіра до ключа повністю тримається на корені атестації виробника. Зламається він — зламається походження ключа. Ми не позбулись довіреної сторони, ми замінили ЦСК на виробника заліза.

Атестація підтверджує пристрій, а не людину. Криптографічний зв’язок — це зв’язок із ключем у конкретному апаратному модулі. Прив’язка «ключ ↔ фізична особа» потребує окремого кроку і є шаром застосунку, а не властивістю офлайн-ядра.

Сила атестації залежить від платформи. StrongBox, TEE й чистий software — різні рівні гарантій; Android фрагментований.

Поза моделлю загроз: примус користувача, malware з повним контролем над рутованим пристроєм, який може сам натиснути біометричний запит.

Зовнішнього незалежного аудиту всього коду ще не було. Це наступний крок, і я вважаю його обов’язковим до будь-якого серйозного застосування.

Математична стаття

Готую препринт для ePrint (IACR) із формальним аналізом трьох властивостей — anchor binding, co-signature inseparability і attestation-bound key provenance — з редукціями до стандартних припущень (колізійна стійкість H, EUF-CMA-стійкість схеми підпису, апаратний модуль змодельовано як ідеальний підписуючий оракул).

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

Коли препринт буде готовий — опублікую.

Спробувати

Застосунок працює на iOS і Android: pakto.pro. Опис можливостей і сценаріїв — на сторінці функцій.

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

Замість висновку

Я не стверджую, що це замінює PKI. Кваліфікований підпис із ЦСК вирішує іншу задачу й вирішує її добре — там, де є мережа й акредитований провайдер.

Мені було цікаво інше: що залишається від доказовості, коли забрати всю інфраструктуру. Виявилось — залишається досить багато, якщо акуратно розібратися з циклічністю, ін’єктивністю кодування та тим, звідки береться довіра до ключа.

Буду радий критиці, особливо від людей із криптографічним бекграундом. Найцінніше зараз — знайти дірку, якої я не бачу.

P.S. Звісно, за кадром залишилося чимало детальних рішень — наприклад, як реалізована верифікація атестації ключа на сервері та її збереження безпосередньо в апаратному модулі. Якщо такий глибокий технічний розбір вам цікавий — напишіть у коментарях, і я із задоволенням детально розпишу ці рішення в наступному матеріалі!