Это все потому, что у кого-то слишком маленькая экспонента: атака Хастада на RSA в задании NeoQUEST-2016

Продолжаем разбирать задания online-этапа NeoQUEST-2016 и готовимся к "очной ставке ^[1]", куда приглашаем всех желающих! Вас ждут интересные доклады, демонстрации атак, конкурсы, призы и многое другое!

Редкий хак-квест обходится без криптографии, ну и NeoQUEST-2016 не стал исключением! В задании online-этапа наш выбор пал на криптосистему RSA, о безопасности которой можно говорить много и долго. В образовательно-познавательных целях, мы взяли не самую популярную атаку на RSA – атаку Хастада.

Кроме этого, мы порядком запутали участников, не предоставив им (на первый взгляд!) никаких исходных данных к заданию. О том, где нужно было искать, что делать с найденным и как реализовать атаку Хастада – читаем под катом!

А где задание?

… с таким вопросом обращались на support@neoquest.ru наши участники. Их можно было понять: тексты обеих легенд толком не говорили ничего.

После прозрачных намеков участники вспоминали о карте на главной странице сайта и шли изучать ее.

Найти исходные данные для задания можно было несколькими путями. Очень внимательные везунчики замечали, что если поводить по карте курсором мышки, то в некоторых точках (а точнее, в трёх!) курсор меняется на руку, которая обычно появляется при наведении на ссылку. По клику скачивался файл формата .asn1.

Другие участники решили не напрягать глаза и просматривали сайт «инспектором», и вскоре где-то под копирайтом обнаруживали те самые три спрятанные файла: cert1_f2ad1569.asn1, cert2_512243c0.asn1, cert3_126ec46b.asn1.

Парсим ASN.1

ASN.1 представляет собой стандарт кодирования информации, широко используемый, в том числе, в криптографии. Подробнее почитать о стандарте можно как на Хабре ^[2](детальная, написанная понятным языком статья), так и на сторонних ресурсах (тут ^[3]и там ^[4]). Любые данные в ASN.1 представляются в виде последовательности «Тэг – Длина – Значение». При этом «Тэг» определяет тип данных, а «Длина» задает размер следующего поля «Значение».

Для того, чтобы узнать, что же за информация находится в этих трех .asn1 файлах, их нужно распарсить. Для этого существует множество программ, например, ASN.1 JavaScript decoder ^[5] или приложение командной строки dumpasn1 ^[6].

Используем dumpasn1, открыв в нем по очереди все три файла, видим следующее:

Структура всех трех файлов одинакова, строка OBJECT IDENTIFIER rsaEncryption во всех трех файлах ясно указывает на RSA. Каждый файл содержит, по-видимому, по 3 параметра RSA, и один параметр у всех трех файлов одинаковый и равный 3. Начинаем изучать возможные атаки на RSA (например, на Вики ^[7]), и параметр 3, заметно маленький по сравнению с двумя другими параметрами, наталкивает на мысль о том, что это — ни что иное, как открытая экспонента e! А значит, можно реализовать атаку Хастада.

Реализуем атаку Хастада

Исходные данные к атаке

Подробно прочитать про атаку Хастада можно здесь ^[8]. Условия для реализации атаки следующие: пользователь А отсылает зашифрованное сообщение m нескольким пользователям. в данном случае, трём (по числу файлов): P₁, P₂, P₃. У каждого пользователя есть свой ключ, представляемый парой «модуль-открытая экспонента» (n_i, e_i), причём M < n₁, n₂, n₃. Для каждого из трех пользователей А зашифровывает сообщение на соответствующем открытом ключе и отсылает результат адресату.

Атакующий же реализует перехват сообщений и собирает переданные шифртексты (обозначим их как C₁, C₂, C₃), с целью восстановить исходное сообщение M. Внимательно смотрим на наши .asn1 файлы: первый параметр, очевидно, модуль RSA n, второй, как мы уже выяснили — открытая экспонента, а значит, третий параметр и есть шифртекст. Значит, по имеющимся трем шифртекстам нужно восстановить сообщение, которое либо будет ключом. либо даст подсказку к тому, где искать ключ к заданию.

Почему точно сможем ее реализовать?

Как известно, шифрование сообщения по схеме RSA происходит следующим образом: C = M^e mod n. В случае с открытой экспонентой, равной 3, получение шифртекстов выглядит так:

C₁ = M³ mod n₁
C₂ = M³ mod n₂
C₃ = M³ mod n₃

Зная, что n₁, n₂, n₃ взаимно просты, можем применить к шифртекстам китайскую теорему об остатках ^[9].

Получим в итоге некоторое C^', корень кубический из которого и даст нам искомое сообщение M!

C^' = M³ mod n₁n₂n₁₃

Вспоминаем, что M меньше каждого из трёх модулей n_i, значит, справедливо равенство:

C^' = M³

Так мы и найдем наше искомое сообщение M.

Программная реализация атаки Хастада

Один из наших участников реализовал скрипт на Python, его подробный writeup лежит тут ^[10], мы же приведем только код скрипта оттуда:

import math
c_flag1 = 258166178649724503599487742934802526287669691117141193813325965154020153722514921601647187648221919500612597559946901707669147251080002815987547531468665467566717005154808254718275802205355468913739057891997227
N1=770208589881542620069464504676753940863383387375206105769618980879024439269509554947844785478530186900134626128158103023729084548188699148790609927825292033592633940440572111772824335381678715673885064259498347
 
c_flag2 = 82342298625679176036356883676775402119977430710726682485896193234656155980362739001985197966750770180888029807855818454089816725548543443170829318551678199285146042967925331334056196451472012024481821115035402
N2=106029085775257663206752546375038215862082305275547745288123714455124823687650121623933685907396184977471397594827179834728616028018749658416501123200018793097004318016219287128691152925005220998650615458757301
 
c_flag3 = 22930648200320670438709812150490964905599922007583385162042233495430878700029124482085825428033535726942144974904739350649202042807155611342972937745074828452371571955451553963306102347454278380033279926425450
N3=982308372262755389818559610780064346354778261071556063666893379698883592369924570665565343844555904810263378627630061263713965527697379617881447335759744375543004650980257156437858044538492769168139674955430611
 
 
def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
 
    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod
 
 
def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a / b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1
def find_invpow(x,n):
    """Finds the integer component of the n'th root of x,
    an integer such that y ** n <= x < (y + 1) ** n.
    """
    high = 1
    while high ** n < x:
        high *= 2
    low = high/2
    while low < high:
        mid = (low + high) // 2
        if low < mid and mid**n < x:
            low = mid
        elif high > mid and mid**n > x:
            high = mid
        else:
            return mid
    return mid + 1
 
flag_cubed = chinese_remainder(  [N1, N2, N3],   [c_flag1, c_flag2, c_flag3] )
flag=find_invpow(flag_cubed,3)
 
print hex(flag)[ 2 : -1 ].decode("hex") 

Как видно из кода, сначала из файлов были получены параметры n_i и C_i, которые из HEX-формата были трансформированы в целые большие числа. Затем была реализована китайская теорема об остатках и, наконец, извлечен кубический корень — для получения искомого сообщения.

key=bff149a0b87f5b0e00d9dd364e9ddaa0

Полученное сообщение содержит в себе ключ, задание пройдено!

В заключение

В продолжение к заданиям NeoQUEST прошлых лет, где участникам требовалось найти ошибку в реализации схемы RSA или провести атаку разложения модуля (разбор задания здесь ^[11]), реализовать атаку Винера ^[12], была выбрана атака Хастада, не основанная на разложении на множители.

Как показала статистика обращения участников online-этапа NeoQUEST-2016 в support, основную проблему для них представила непонятная формулировка задания и спрятанные исходные данные. Однако формат файлов также поставил в тупик некоторых участников.

Лучшие участники online-этапа уже совсем скоро встретятся на «очной ставке» 7 июля в Санкт-Петербурге! А мы приглашаем всех — специалистов ИБ-фирм, хакеров и гиков, абитуриентов и студентов IT-специальностей — отлично провести время, слушая доклады и участвуя в конкурсах, пока ребята-участники в поте лица проходят задания! Вход свободный, нужна только регистрация на сайте ^[1]. NeoQUEST — еще одна причина посетить Питер этим летом!

Автор: НеоБИТ

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