Введение #
Сегодня на повестке дня: Умеет ли Габен считать до трех?, разбор криптографической базы, а именно парсинг .pem файлов, а также решение простой задачи на RSA с TamuCTF.
Что такое крипта и почему это важно? #
За крипто может следовать: аналитик, граф и инвестор.
- Криптоаналитик - специалист, который ищет уязвимости в шифровании, то есть своего рода рыв йор сер. Именно его навыки всегда проверяются на жопарди.
- Криптограф - специалист, который создает шифры, которые позволят людям безопасно обмениваться информацией.
- Криптоинвестор - Макс Максбетов.
Первые два заботятся о том, чтобы ваши персональные данные оставались в безопасности, даже если они попадут злоумышленнику в руки.
Тасоки и решения #
Разберемся зачем нужен .pem файл. PEM - это де-факто формат файла для хранения и отправки криптографических ключей, сертификатов и других данных, основанный на наборе стандартов IETF 1993 года, определяющих “почту с улучшенной конфиденциальностью” ( Ссылка ).
Truncated 1: #
Условие задачи #
- Дан зашифрованный флаг
- Дан открытый ключ шифрования
- Дана часть приватного ключа шифрования
Решение #
Oh no! У нас не полный приватный ключ, чтобы сдать тасоку налегке. Поищем, что должно лежать в PEM файле. Сам по себе pem файл - таблица ASN.1, которая закодирована с помощью протокола der, а после еще вдобавок - base64.
Как работает DER? #
DER, по сути дела, берет все чиселки переводит их в хексы(hexadecimal), приписывая поля, также в хексах ( Читать подробнее).
Пример DER кодирования #
Пример 1: #
02 03 01 00 01
- 02 - означает, у нас число типа integer
- 03 - длина нашего числа в байтах
- 01 00 01 - наше число, а именно 65537 (популярная открытая константа)
Пример 2: #
02 81 FF 03 ..
02 82 01 01 00 ..
- 02 - означает, у нас число типа integer
- 81, 82 - числа, которые обозначают, что у нас будет большое число. Если у нас выпало 81, то длина числа определяется одним последующим байтом, 82 - 2 байтами, и так далее.
Нас интересуют поля 02, и за ними следующие байты.
Напишем свой декодер для файлов (main.py)
Обратимся к нотации ASN.1 для RSA и увидим передаваемые параметры приватного ключа:
- N
- e
- d
- p
- q
- dQ
- dP
- qInv
Посчитаем количество полей 02. Их оказалось четыре, а так как у нас дан конец приватного ключа, значит у нас есть q. Теперь дело за малым - открыть SAGE и найти флаг. Ссылка на докер с SAGE
Поясняю за базовую матешу:
d - секретная экспонента, такая что $$ e * d = 1 \pmod{\phi(N)}$$, значит $$d = e ^{-1} \pmod{\phi(N)}$$, то есть обратный элемент, где $$\phi(N) = lcm(p - 1, q - 1)$$, где lcm - Наименьший общий делитель
c - зашифрованное сообщение. $$c = m^e \pmod{N}$$, где m - изначальное сообщение
Кольцо - множество всех элементов от 0 до n - 1, где n - составное.
Поле - множество всех элементов от 0 до n - 1, где n - простое.
Поясняю за команды в SAGE:
Zmod - генерация кольца.
Возведя c^d, получаем m.
FLAG:gigem{Q_Fr0M_Pr1V473_K3Y_89JD54}
Truncated 2: #
Условие задачи #
- Дан зашифрованный флаг
- Дан открытый ключ шифрования
- Дана часть приватного ключа шифрования
Решение #
Распарсив pem’ки, мы выясним, что в приватном ключе всего три параметра
Нерешаемый, то нерешаемый, но для нас он решаемый!
Разберемся, что за dQ, dP, qInv #
Криптографы достаточно быстро столкнулись с проблемой увеличения мощностей, что за собой влекло увеличения количества бит в p,q, а как следствие и увеличение d. По итогу увеличевалось время дешифровки.
Важно Посмотреть! #
Для тех, кто не хочет смотреть pdf: #
- $$dQ = d \pmod{q - 1}$$
- $$dP = d \pmod{p - 1}$$
- $$qInv = q ^ {-1}\pmod{p}$$
В этой пдфке описан процесс дешифровки, а также атака, которой я воспользуюсь. Так как p > q, по правилам генерации, можно реализовать брутфорс атаку,где мы перебираем k, на dP
$$ p = gcd((e * dP - 1) / k + 1 , N)$$ , где $$k \in [1..e]$$
А дальше делаем все, как в первом решении
FLAG:gigem{DP_DQ_r54_7rUNC473D_SDA79}
Эпилог #
Задонатить автору на баночку безалкоголки: https://clck.ru/39wm3q