Pull to refresh

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

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

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

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

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

Ну, во-первых там несколько типов ключей. Старые, новые и т. д. Нам интересны самые крутые, так называемые Short level V10 ECC signed keys для которых отведена добрая половина сорца с математикой больших чисел и эллиптикой. Так что, будем ломать ECDSA!

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

Но!

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

Матан


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

В ключе лежат параметры ECDSA параметры h,r,s. h — хэш сообщения, r,s — параметры подписи.

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

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

(EC)DSA


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

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

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

  1. Генерируем случайное k
  2. вычисляем r = gk 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 = gk mod p mod q.
Вся проблема тут в k. Если оно известно, то можно вычислить секретный ключ x по формуле
x = ((s * k) – h) * r-1 mod q

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

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

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

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


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

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

Ну а что до армадиллы, мы знатно потроллили разработчиков(кейген работал несколько версий), а потом уязвимость пофиксили (обновленные сорцы кейгена тоже имеются, можете сравнить). Кстати, походу, это эксклюзив, на паблик я этот архив не выкладывал. И было это, кстати, раньше, чем упомянутые взломы PSP и дыра в дебиане.

Надеюсь, было интересно. Берегите свои ГПСЧ.

P.S.

Вот архив с той самой армадиллой и двумя валидными ключами на моё имя. Можете попробовать в качестве задания на дом сгенерить ключик на себя.
Для 80 lvl: обойдитесь одним ключом. А что, вполне себе олимпиадная задачка
Tags:
Hubs:
Total votes 120: ↑117 and ↓3 +114
Views 45K
Comments Comments 17