ECDSA з повторюваним k

ECDSA (Elliptic Curve Digital Signature Algorithm) - це алгоритм еліптичної криптографії, що використовується для цифрових підписів, тобто для підтвердження автентичності та цілісності даних.

Ми не будемо його детально розбирати, для цього напишу окрему статтю. Сьогодні ми лише дізнаємось, як помилка в реалізації призвела до зламу PlayStation 3.

ECDSA

Згадаємо як відбувається підпис за допомогою еліптичних кривих:

$$\begin{gather*} r = (kG)_x \mod n \\ s = k^\text{-1}(\text{Hash}(m) + dr) \mod n \end{gather*}$$

де:

• G — генератор групи точок
• n - кількість точок в групі
• k - випадкове число в діапазоні від 1 до n-1
• m - повідомлення
• d - приватний ключ

Для прикладу розглянем підпис на кривій secp256k1, вона використовується в Bitcoin, але така сама логіка буде використовуватися для інших кривих.

Формула secp256k1 виглядає так:

$$y^2 = x^3 + 7$$

На графіку вона буде виглядати так:

Код на Python, який реалізує підпис на цій кривій, за допомогою бібліотеки ecdsa:

import hashlib
from ecdsa import (
    SigningKey,
    BadSignatureError,
    SECP256k1 as curve
)

k = secrets.randbelow(curve.order)

private_key = SigningKey.generate(curve=SECP256k1)
public_key = private_key.verifying_key

message = "Hello, World!".encode()
message_signature = private_key.sign(
    data=message,
    hashfunc=hashlib.sha256,
    k=k
)

try:
    public_key.verify(
        signature=message_signature,
        data=message,
        hashfunc=hashlib.sha256
    )
    print("Signature is valid")
except BadSignatureError:
    print("Invalid signature")

Якщо цікаво можете ознайомитись, як таку логіку реалізуют за допомогою SageMath - Sage and ECDSA (secp256k1).

ECDSA з повторюваним k

Ми також можемо підписати 2 повідомлення за допомогою одного k:

import secrets
import hashlib
from ecdsa import (
    SigningKey,
    SECP256k1 as curve
)

private_key = SigningKey.generate(curve=curve)
public_key = private_key.verifying_key

k = secrets.randbelow(curve.order)

m1 = "Hello, World!"
s1 = private_key.sign(
    data=m1.encode(),
    hashfunc=hashlib.sha256,
    k=k
)

print("message: ", m1)
print("signature: ", s1.hex())
print()

m2 = "Hello, everyone!"
s2 = private_key.sign(
    data=m2.encode(),
    hashfunc=hashlib.sha256,
    k=k
)

print("message: ", m2)
print("signature: ", s2.hex())

В результаті отримуємо:

message:  Hello, World!
signature:  824f318a374e0c55b0c79f48a44c9971d3e4d2cf87720f3282d98336540f1b8c589259a7ef7873c3adf835e7192544a31a12c5ef1e24d2f7cd7cb5349d8077f0

message:  Hello, everyone!
signature: 824f318a374e0c55b0c79f48a44c9971d3e4d2cf87720f3282d98336540f1b8cfa5dccf2a23a57bc0925046404acec9991246d823741cf20f093515d8f9bc385

І саме тут з’являється проблема.

Відновлення k

Можемо подивитися на підписи більш детально.

У цьому прикладі бібліотека повертає підпис у raw-форматі, а не ASN.1. Тому перші 32 байти це r, а інші s:

Signature for message 1:
r = 824f318a374e0c55b0c79f48a44c9971d3e4d2cf87720f3282d98336540f1b8c
s = 589259a7ef7873c3adf835e7192544a31a12c5ef1e24d2f7cd7cb5349d8077f0

Signature for message 2:
r = 824f318a374e0c55b0c79f48a44c9971d3e4d2cf87720f3282d98336540f1b8c
s = fa5dccf2a23a57bc0925046404acec9991246d823741cf20f093515d8f9bc385

Як ми бачимо, r в них однаковий, він обчислюється за такою формулою:

$$r = (kG)_x \mod n$$

G - точка генератор, задана для кривої, тому вона завжди має однакове значення. Для secp256k1 це:

x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
y = 32670510020758816978083085130507043184471273380659243275938904335757337482424

k це будь-яке випадкове число у діапазоні від 1 до n-1. Якщо для декількох повідомлень k буде однаковим то і r в них буде однаковий, як ми і бачимо в цьому випадку.

Це дозволить нам відновити приватний ключ, сторони яка підписала повідомлення.

Поглянемо на формули:

$$s = k^\text{-1}(\text{Hash}(m) + dr) \mod n \\[6pt] \Downarrow \\[6pt] s = \frac{\text{Hash}(m) + dr}{k} \mod n$$

Позначемо захешований текст за h:

$$s = \frac{h + dr}{k} \mod n$$

Якщо у нас є два підписи, створені одним секретним ключем, то ми маємо два значення:

$$s_1 = \frac{h_1 + dr}{k} \mod n \\[6pt] s_2 = \frac{h_2 + dr}{k} \mod n$$

Розглянемо різницю між двома s:

$$s_1 - s_2 = \frac{h_1 + dr}{k} \ - \ \frac{h_2 + dr}{k} \mod n \\[6pt] \Downarrow \\[6pt] s_1 - s_2 = \frac{h_1 + \cancel{dr} - h_2 - \cancel{dr}}{k} \mod n \\[6pt] \Downarrow \\[6pt] s_1 - s_2 = \frac{h_1 - h_2}{k} \mod n$$

Звідси ми можемо вивести k:

$$k = \frac{h_1 - h_2}{s_1 - s_2} \mod n$$

Оскільки нам відомі всі значення ми можемо обчислити k, зробимо це за допомогою скрипта:

import hashlib
from ecdsa import SECP256k1 as curve

n = curve.order

m1 = "Hello, World!"
h1 = int(hashlib.sha256(m1.encode()).hexdigest(), 16)
s1 = int("589259a7ef7873c3adf835e7192544a31a12c5ef1e24d2f7cd7cb5349d8077f0", 16)

m2 = "Hello, everyone!"
h2 = int(hashlib.sha256(m2.encode()).hexdigest(), 16)
s2 = int("fa5dccf2a23a57bc0925046404acec9991246d823741cf20f093515d8f9bc385", 16)

k = (h1 - h2) * pow(s1 - s2, -1, n) % n

print(k)

В результаті отримаємо:

87688136515905649829754568984911539127435725393107483305970384113687153185889

Відновлення d

Тепер нам залишилось знайти d(приватний ключ):

$$s = \frac{h + d * r}{k} \mod n \\[6pt] \Downarrow \\[6pt] s * k = h + d * r \mod n \\[6pt] \Downarrow \\[6pt] s * k - h = d * r \mod n \\[6pt] \Downarrow \\[6pt] d = \frac{s * k - h}{r} \mod n$$

Обчислимо d також за допомогою скрипта:

import hashlib
from ecdsa import SECP256k1 as curve

n = curve.order

k = 87688136515905649829754568984911539127435725393107483305970384113687153185889

message = "Hello, World!"

h = int(hashlib.sha256(message.encode()).hexdigest(), 16)
r = int("824f318a374e0c55b0c79f48a44c9971d3e4d2cf87720f3282d98336540f1b8c", 16)
s = int("589259a7ef7873c3adf835e7192544a31a12c5ef1e24d2f7cd7cb5349d8077f0", 16)

d = (s * k - h) * pow(r, -1, n) % n

print(d)

В результаті отримаємо:

2172792800192156572712507415018762911524920363390006721668722302964575989331

Це і є приватний ключ іншої сторони.

Можемо перевірити це, підписавши початкове повідомлення:

import hashlib
from ecdsa import SigningKey, SECP256k1 as curve

d = 2172792800192156572712507415018762911524920363390006721668722302964575989331
k = 87688136515905649829754568984911539127435725393107483305970384113687153185889

message = "Hello, World!"

private_key = SigningKey.from_secret_exponent(d, curve=curve)

message_signature = private_key.sign(
    data=message.encode(),
    hashfunc=hashlib.sha256,
    k=k
)

print(message_signature.hex())

На виході отримуємо:

824f318a374e0c55b0c79f48a44c9971d3e4d2cf87720f3282d98336540f1b8c
589259a7ef7873c3adf835e7192544a31a12c5ef1e24d2f7cd7cb5349d8077f0

Цей підпис співпадає з тим що ми отримали від іншої сторони на початку.

Це значить що ми відновили приватний ключ іншої сторони і зрозуміли чому k не можна використовувати повторно.

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

Sony PlayStation 3

Для захисту свого пристрою PlayStation 3, Sony використовувала алгоритм ECDSA для підпису програмного забезпечення, яке дозволене для запуску на консолі.

Будь яка програма підписана Sony могла бути запущена на консолі, а всі інші - не запускалися.

В 2010 хакери знайшли проблему, яку я описав в статті. Sony використовувала статичний k для підписів. Це дозволило відновити приватний ключ.

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

Додаткові ресурси

• Attacking ECDSA with Not Random Keys: The Sony PlayStation 3 Hack
• Криптографічні провали PlayStation, SaltStack та Hyundai: Як помилки інженерів призводять до вразливості систем
• Key Discovery in ECDSA: Understanding Implementation and Security Risk

Резюме

Ми розібралися, як повторне використання значення k в ECDSA дозволяє відновити приватний ключ підписувача.

Щоб уникнути цієї вразливості, для кожного підпису необхідно використовувати унікальне, криптографічно випадкове значення k. Повторення k навіть один раз призводить до повної компрометації приватного ключа.

Більшість сучасних бібліотек ECDSA автоматично генерують k для кожного підпису, однак часто дозволяють розробнику передавати власне значення. Використання цієї можливості потребує особливої обережності, оскільки помилка в генерації k робить алгоритм криптографічно небезпечним.

Це не теоретична проблема, а реальна історична вразливість, яка зустрічається й сьогодні.

Завдання для самоперевірки

Спробуйте самостійно відновити приватний ключ, з підписів де використовується статичний k:

message:  Hello, Bob!
signature:  1d3d045f688100f3096c14a2c491dbccbd3c454ca2b9b0f5077dbf6481158e2f8fca444679e87bd8bef3ac1866135d536af6ef5084a3dd2cd40919437315536c

message:  How are you?
signature:  1d3d045f688100f3096c14a2c491dbccbd3c454ca2b9b0f5077dbf6481158e2f25a9d6e3db52caf51aaef0f205cff190d673f4cb11632cec5768b99f72dec801