Вбудовуємо бекдор в Bitcoin (ECDSA) або ще раз про клептографии


Привіт, %username%!
Користуєшся неофіційними bitcoin клієнтами? Є привід придивитися до них уважніше.
Після реалізації бекдор для RSA мені стало цікаво, як йдуть справи з іншими криптографічними примітивами. Виявляється, ціла наука під назвою клептография займається передачею інформації в так званих «підсвідомих» каналах. Таких, про яких нікому не відомо, крім відправника та одержувача. Начебто стеганографії, тільки всередині криптоалгоритов.



Взагалі, такий клас атак на криптоалгоритми називається SETUP (Secretly Embedded Trapdoor with Embedded Protection). Тобто, звичайно є і бекдор і захист, така, що навіть при виявленні бекдор неможливо буде дізнатися що передавалося. Такі атаки вирішують Дилему ув'язненого.

SETUP (буду говорити про SETUP в чоловічому роді) може бути слабким і сильним.

Weak SETUP — Якщо дізнатися згенеровані ключі може не тільки атакуючий, але і власник девайсу, на якому встановлено скомпрометоване.
Відповідно Strong SETUP — якщо дізнатися ключі може тільки атакуючий.

Ще одна характеристика називається Leakage bandwidth, вона показує скільки секретних даних «витікає» при повторюваному процесі шифрування\підпису. Позначається (m,n), що означає витік m секретних повідомлень/ключів за n передаються.

І такі атаки існують практично для всіх схем з відкритим ключем. DSA, ElGamal, Diffie-Helman, скрізь є спосіб хоч один біт да передати потай. Далеко не завжди це виходить так красиво як вийшло з RSA, але при бажанні практичне застосування знайти можна. Наприклад, для ECDSA провести SETUP атаку простіше, тому що параметри генерації ключів (крива, базова точка, порядок кривої) відомі заздалегідь, а в DSA відповідні параметри генеруються випадковим чином для кожної ключової пари.

Як ми всі знаємо, гаманець в Bitcoin — це ключова пара ECDSA.
Сьогодні ми розглянемо сильну SETUP атаку (1,2) на ECDSA, тобто атакуючий може дізнатися секретний ключ користувача за 2 підпису, при чому, крім нього ніхто зробити не зможе.

Для початку коротко згадаємо як генерується підпис ECDSA.

У нас є закритий ключ d — число і відкритий ключ Q — точка еліптичної кривої, рівна dG, де G — базова точка кривої.

  • Для підпису вибирається випадкове число k, у діапазоні [1, n-1].
  • Обчислюється точка кривої (x1 ,y1 ) = k*G
  • Обчислюється r = x1 mod N, де N — порядок кривої.
  • Обчислюється s = k-1(H(m)+rd) mod N, де k-1 — число, протилежне по модулю N на k. H(m) — хеш підписуваного повідомлення.


Підписом є пара (r,s)

Як видно, тут k вибирається випадково. Ми дещо видозмінимо процес так, щоб атакуючий зміг обчислити приватний ключ користувача d.

Закритий і відкритий ключі атакуючого назвемо v і V = vG.

Крок перший. Користувач генерує підпис перший раз (надсилає кому-то биткоины)
Такий ж, як у звичайного підпису. За тим винятком, що нам буде потрібно десь зберегти k. Назвемо його k1 Отримуємо пару (r1, s1)

Крок другий (надсилає биткоины другий раз)

Обчислюємо прихований елемент поля Z = a*k1 G + b*k1 V + h*jG + e*uV,
де a, b, h, e < n — фіксовані цілі числа; j, u ∈ {0, 1} — випадкові.

a, b, h, e можна генерувати детерміновано, наприклад використовуючи хеш від повідомлення як seed для ДПРЧ. Це ускладнить виявлення закладки.

k2 у нас вибирається не випадково, а є тепер хешем від Z. Хешем від точки кривої будемо вважати хеш її координати X.
Далі все як звичайно, отримуємо пару (r2, s2).

І так, атакуючий отримав пари (r1, s1 ) та (r2, s2). Як йому отримати закритий ключ користувача?

1) Обчислюємо R1' = s-1(H(m1)G + r1Q) = (x1 ', y1 '). Це ми і так робимо, коли перевіряємо цифровий підпис.
2) Z1 = aR1' + b * vR1', де v — закритий ключ атакуючого
3) Для кожного можливого значення j, u обчислюємо:
Z2 = Z1 + h * jG + e * uV
k2' = H(Z2)
R2' = k2'G = (x2', y2')
r2' = x2' mod n
Якщо r2' = r2, тоді k2' = k2, ми знайшли k, це те, що нам потрібно

Закритий ключ d користувача = (s2k2 — h(m2)) × r2-1 mod n

Як ви розумієте, k2 теж можна запам'ятати і продовжити генерувати k+1 по ланцюжку, даючи таким чином атакуючому можливість дізнатися закритий ключ користувача з будь-яким двом йдуть підряд підписів.

Нічого надприродного тут немає, атакуючому лише потрібно заздалегідь вибрати числа a, b, h, e і помістити їх в бекдор разом з зі своїм відкритим ключем. Або генерувати їх на основі підписаного повідомлення.

Сама атака хоч і сильна, але нестійка. Це означає, що користувач, що володіє своїм закритим ключем, теоретично може обчислити, що k2 генерується випадковим чином. Для цього і вводяться j,u, щоб урізноманітнити можливі значення на випадок перевірки пильним користувачем. Їх можна зробити відмінними від 0 і 1, тоді варіантів буде ще більше. Правда, і брутфорсить доведеться довше. Насправді можна особливо не турбуватися, все одно швидше за все наявність закладки з'ясується лише постфактум коли код розберуть по кісточках.

Робочий код цієї атаки я додав до кодом атаки на RSA. Не бачу причин за якими б вже не існувало, або не з'явилося б троянів для bitcoin, що реалізують цю техніку. Так, трояни можуть відразу пересилати закритий ключ (і спалитися на першому ж фаєрволі), а можуть взагалі нічого не пересилати, а зловмисник тихо чекати поки на затрояненных гаманцях з'являться серйозні суми.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.