Це все тому, що у кого-то занадто маленька експонента: атака Хастада на RSA в завданні NeoQUEST-2016

Продовжуємо розбирати завдання online-етапу NeoQUEST-2016 і готуємося до "очній ставці", куди запрошуємо всіх бажаючих! Вас чекають цікаві доповіді, демонстрації атак, конкурси, призи та багато іншого!

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

Крім цього, ми порядком заплутали учасників, не надавши їм (на перший погляд!) жодних вихідних даних до завдання. Про те, де потрібно було шукати, що робити зі знайденим і як реалізувати атаку Хастада – читаємо під катом!

А де завдання?

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



Після прозорих натяків учасники згадували про картці на головній сторінці сайту і йшли вивчати її.



Знайти вихідні дані для завдання можна було кількома шляхами. Дуже уважні везунчики помічали, що якщо поводити по карті курсором мишки, то в деяких точках (а точніше, в трьох!) курсор змінюється на руку, яка зазвичай з'являється при наведенні на посилання. По кліку викачувався файл формату .asn1.



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



Парсим ASN.1

ASN.1 представляє собою стандарт кодування інформації, що широко використовується, зокрема, в криптографії. Детальніше почитати про стандарті можна як на Хабре (детальна, написана зрозумілою мовою стаття), так і на сторонніх ресурсах (тут і там). Будь-які дані в ASN.1 представляються у вигляді послідовності «Тег – Довжина – Значення». При цьому «Тег» визначає тип даних, а «Довжина» задає розмір наступного поля «Значення».

Для того, щоб дізнатися, що ж це за інформація знаходиться в цих трьох .asn1 файлах, їх потрібно розпарсити. Для цього існує безліч програм, наприклад, ASN.1 JavaScript decoder або програму командного рядка dumpasn1.

Використовуємо dumpasn1, відкривши у ньому по черзі всі три файли, бачимо наступне:



Структура всіх трьох файлів однакова, рядок OBJECT IDENTIFIER rsaEncryption у всіх трьох файлах ясно вказує на RSA. Кожен файл містить, мабуть, по 3 параметра RSA, і один параметр у всіх трьох файлів однаковий і дорівнює 3. Починаємо вивчати можливі атаки на RSA (наприклад, Вики), пункт 3, помітно маленький порівняно з двома іншими параметрами, наштовхує на думку про те, що це — ні що інше, як відкрита експонента e! А значить, можна реалізувати атаку Хастада.

Реалізуємо атаку Хастада



Вихідні дані до атаки
Докладно прочитати про атаку Хастада можна здесь. Умови для реалізації атаки наступні: А користувач відсилає зашифроване повідомлення m декільком користувачам. в даному випадку, трьох (за кількістю файлів): P1, P2, P3. У кожного користувача є свій ключ, представлений парою «модуль-відкрита експонента» (nі, eі), причому M < n1, n2, n3. Для кожного з трьох користувачів А зашифровує повідомлення на відповідному відкритому ключі і відсилає результат адресату.

Атакуючий реалізує перехоплення повідомлень і збирає передані шифртексты (позначимо їх як C1, C2, C3), з метою відновити вихідне повідомлення M. Уважно дивимося на наші .asn1 файли: перший параметр, очевидно, модуль RSA n, другий, як ми вже з'ясували — відкрита експонента, а значить, третій параметр і є шифртекст. Отже, за наявними трьом шифртекстам потрібно відновити повідомлення, яке буде ключем. або дасть підказку до того, де шукати ключ до завдання.

Чому точно зможемо її реалізувати?
Як відомо, шифрування повідомлення за схемою RSA відбувається наступним чином: C = Me mod n. У випадку з відкритою експонентою, що дорівнює 3, отримання шифртекстов виглядає так:

C1 = M3 mod n1
C2 = M3 mod n2
C3 = M3 mod n3

Знаючи, що n1, n2, n3 взаємно прості, можемо застосувати до шифртекстам китайську теорему про залишки.

Отримаємо в підсумку деякий C', корінь кубічний з якого і дасть нам шукане повідомлення M!

C' = M3 mod n1n2n13

Згадуємо, що M менше кожного з трьох модулів nі, значить, справедливо рівність:

C' = M3

Так ми і знайдемо наше шукане повідомлення M.

Програмна реалізація атаки Хастада
Один з наших учасників реалізував скрипт на Python, його докладний writeup лежить тут, ми ж наведемо тільки код скрипта звідти:

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 ' 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 < and mid mid**n < x:
low = mid
elif high > and mid 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і, Cі, які з HEX-формату були трансформовані у великі цілі числа. Потім була реалізована китайська теорема про залишки і, нарешті, витягнутий кубічний корінь — для отримання шуканого повідомлення.

key=bff149a0b87f5b0e00d9dd364e9ddaa0

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

висновок

В продовження до завдань NeoQUEST минулих років, де учасникам потрібно було знайти помилку в реалізації схеми RSA або провести атаку розкладання модуля (розбір завдання тут), реалізувати атаку Вінера , була обрана атака Хастада, не заснована на розкладанні на множники.

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

Кращі учасники online-етапу вже зовсім скоро зустрінуться на «очній ставці» 7 липня в Санкт-Петербурзі! А ми запрошуємо всіх — фахівців ІБ-фірм, хакерів і гиків, абітурієнтів та студентів ІТ-спеціальностей — відмінно провести час, слухаючи доповіді та беручи участь у конкурсах, поки хлопці-учасники в поті чола проходять завдання! Вхід вільний, потрібна лише реєстрація на сайт. NeoQUEST — ще одна причина відвідати Пітер цього літа!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.