Как была закейгенена Armadillo, взломана PSP и скомпрометированы все DSA ключи в Debian. Или еще раз о слабых ГПСЧ и (EC)DSA

Лет семь назад попал в руки крякеров архив с сорцом генератора ключей для протектора под названием Armadillo. Просто кое-кому из благодарных пользователей продукта захотелось проверить его на прочность. А где еще получишь бесплатный аудит такого интересного кода, как не на крякерском форуме.

Этот генератор нужен был для того, чтобы при покупке клиентом вашей программы, защищенной Armadillo, мерчант смог сам автоматически сгенерировать для неё лицензионный ключ. Так же, он использовался в самой Armadillo и, если б была возможность узнать секрет, то можно было бы сделать кейген для неё самой. Что делало аудит кода вдвойне интересным.

Итак, вот он ^[1], оригинальный, добытый путём титанических усилий, архив. (исходник на C)

Попробуйте без подсказок понять, в чем именно сокрыта уязвимость. Там хоть и куча кода, но он хорошо читаем. Не получилось? А если глянуть на 528 строчку?

Ну, во-первых там несколько типов ключей. Старые, новые и т. д. Нам интересны самые крутые, так называемые Short level V10 ECC signed keys. А для инициализации самого кейгена используется (если мне не изменяет память) MD5(секрет), так что с этой стороны тоже было не подобраться.

Для Short level V10 добрая половина сорца отведена под математику больших чисел и эллиптических кривых. Так что, будем ломать ECDSA!

Для ECDSA используется кривая в 112 бит, так что размер секретного ключа (x) у нас 112 бит. Это немного многовато для брутфорса.

Но!

Секретные значения берутся из ГПСЧ, который инициализируется… тада! 32 битным числом!

Матан

Чтобы сделать кейген, нужно иметь пару валидных ключей для программы. В принципе, можно обойтись и одним, но первые версии брутфорсилки нуждались в двух ключах, чтобы проверить правильность теории. Ниже будет показано, зачем.
Ох и нелегко их было получить! Ведь когда покупаешь Armadillo, генерится временный ключ. И только потом, лично пообщавшись с разработчиком, получаешь настоящий. Но, я опять отступил от темы, продолжим.

В ключе лежат параметры ECDSA параметры h,r,s. Как их оттуда доставать можно глянуть в сорцах, единственное что r и s называются в них c и d.

Итак, у нас есть две тройки (r, s) h и (r', s') h'

(EC)DSA

Я буду показывать формулы на примере DSA ^[2], т.к. суть уязвимости та же и суть формул та же, просто они гораздо читабельней.

Секретным ключом в (EC)DSA является случайно выбранное число x. Так же (уже только в DSA), выбираются два больших простых числа:
q, размер которого совпадает с размером хэш функции в битах.
p, такого, что (p-1) делится на q.
Еще выбирается число g такое, что его мультипликативный порядок по модулю p равен q (см статью на вики). Но, нам это не интересно, просто это число будет встречаться в формулах.

Чтобы сгенерировать цифровую подпись мы выполняем следующие действия:

1. Генерируем случайное k
2. вычисляем r = g^k mod p mod q
3. вычисляем s = k^-1 (H(m) + x*r) mod q

Где H(m) — хэш сообщения, которое мы подписываем.

Уязвимость

Допустим, нам встретились две подписи с двумя одинаковыми r. s у них считаются следующим образом:
s = k^-1 (H(m) + x*r) mod q
s' = k^-1 (H(m') + x*r) mod q

Вычтем одно из другого (все операции проводятся по модулю)
s – s' = k^-1 (h + x*r) – k^-1 (h'+ x*r)

Теперь, k можно вынести за скобку, раз оно одинаковое
s– s'= k^-1 (h+ x*r – h'– x*r)

x*r сокращаются
s– s' = k^-1 (h– h')

Перенесем k влево

k = (h– h') / (s – s')

а, как мы помним r = g^k mod p mod q.
Вся проблема тут в k. Если оно известно, то можно вычислить секретный ключ x по формуле

x = ((s * k) – h) * r^-1 mod q

Что и было сделано ^[3]группой fail0verflow в 2010 году, т.к. жопорукие кодеры из Sony додумались сгенерить k лишь единожды

С Armadillo всё было не так просто. r были всегда разными, но из-за того, что генератор инициализировался 32битным числом, всего вариантов было 2³², что делало перебор делом нескольких часов.

Алгоритм перебора (все операции по модулю):

1. h' = -h
2. r' = r^-1
3. s' = s*r'
4. h' = h'*r'
5. Запускаем цикл от 0 до 2³² -1 и в нем:
6. Инициализируем счетчиком ГСЧ
7. Генерим число k
8. Вычисляем x = ((s * k) – h) * r^-1 mod q
9. Сохраняем этот x

И так для обоих ключей. Получается на двоих где-то 2.6 гига данных. Потом просто надо найти в них одинаковый x, он и будет секретным ключом.

Точно так же можно было вычислить любую ключевую пару в Debian, когда в 2008м году выяснилось ^[4], что из-за бага в OpenSSL ГПСЧ инициализировался числом в диапазоне 0-2¹⁵. Это еще проще, чем с армадиллой. И все сгенеренные в Debian ключи DSA с 2006 по 2008й год включительно оказались скомпрометированы.

Ну а что до армадиллы, мы знатно потроллили разработчиков(кейген работал несколько версий), а потом уязвимость пофиксили (обновленные сорцы кейгена тоже имеются ^[5], можете сравнить).

Надеюсь, было интересно. Берегите свои случайные данные

P.S.

Вот ^[6] архив с той самой армадиллой и двумя валидными ключами на моё имя. Можете попробовать в качестве задания на дом сгенерить ключик на себя.

Автор: Scratch

Источник ^[7]