Встраиваем бэкдор в 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].


• Вычисляется точка кривой (x₁ ,y₁ ) = k*G


• Вычисляется r = x₁ 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. Назовем его k₁ Получаем пару (r1, s1)

Шаг второй (отправляет биткоины второй раз)

Вычисляем скрытый элемент поля Z = a*k₁ G + b*k₁ V + h*jG + e*uV,

где a, b, h, e < n − фиксированные целые числа; j, u ∈ {0, 1} – случайные.

a, b, h, e можно генерировать детерминировано, например используя хэш от сообщения как seed для ГПСЧ. Это усложнит обнаружение закладки.

k2 у нас выбирается не случайно, а является теперь хэшем от Z. Хэшем от точки кривой будем считать хэш её X координаты.

Далее всё как обычно, получаем пару (r2, s2).

И так, атакующий получил пары (r₁, s₁ ) и (r₂, s₂). Как ему получить закрытый ключ пользователя?

1) Вычисляем R₁′ = s^-1(H(m1)G + r₁Q) = (x₁ ′, y₁ ′). Это мы и так делаем, когда проверяем цифровую подпись.

2) Z₁ = aR₁′ + b * vR₁′, где v — закрытый ключ атакующего

3) Для каждого возможного значения j, u вычисляем:

Z₂ = Z₁ + h * jG + e * uV

k₂′ = H(Z₂)

R₂′ = k₂′G = (x₂′, y₂′)

r₂′ = x₂′ mod n

Если r₂′ = r₂, тогда k₂′ = k₂, мы нашли k, это то, что нам нужно

Закрытый ключ d пользователя = (s₂k₂ − h(m₂)) × r₂^-1 mod n

Как вы понимаете, k₂ тоже можно запомнить и продолжить генерировать k₊₁ по цепочке, давая таким образом атакующему возможность узнать закрытый ключ пользователя по любым двум идущим подряд подписям.

Ничего сверхъестественного тут нет, атакующему лишь нужно заранее выбрать числа a, b, h, e и поместить их в бекдор вместе со со своим открытым ключом. Либо генерировать их на основе подписываемого сообщения.

Сама атака хоть и сильная, но неустойчивая. Это значит, что пользователь, владеющий своим закрытым ключом, теоретически может вычислить, что k2 генерится неслучайным образом. Для этого и вводятся j,u, чтобы разнообразить возможные значения на случай проверки бдительным пользователем. Их можно сделать отличными от 0 и 1, тогда вариантов будет еще больше. Правда, и брутфорсить придется подольше. На самом деле можно особо не беспокоиться, все равно скорей всего наличие закладки выяснится лишь постфактум когда код разберут по косточкам.

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

Recommended article: Chomsky: We Are All – Fill in the Blank.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.