Перейти к основному содержимому

Молодой человек, у вас приватный ключ выпал!

·4 минут· loading · loading ·
Zer0bp
Crypto
Автор
Zer0bp
4Ray / Делаю что хочу(могу)
Оглавление
Crypto basics - This article is part of a series.

Введение
#

Сегодня на повестке дня: Умеет ли Габен считать до трех?, разбор криптографической базы, а именно парсинг .pem файлов, а также решение простой задачи на RSA с TamuCTF.

Что такое крипта и почему это важно?
#

За крипто может следовать: аналитик, граф и инвестор.

  • Криптоаналитик - специалист, который ищет уязвимости в шифровании, то есть своего рода рыв йор сер. Именно его навыки всегда проверяются на жопарди.
  • Криптограф - специалист, который создает шифры, которые позволят людям безопасно обмениваться информацией.
  • Криптоинвестор - Макс Максбетов.

Первые два заботятся о том, чтобы ваши персональные данные оставались в безопасности, даже если они попадут злоумышленнику в руки.

Тасоки и решения
#

Разберемся зачем нужен .pem файл. PEM - это де-факто формат файла для хранения и отправки криптографических ключей, сертификатов и других данных, основанный на наборе стандартов IETF 1993 года, определяющих “почту с улучшенной конфиденциальностью” ( Ссылка ).

Truncated 1:
#

Условие задачи
#

  1. Дан зашифрованный флаг
  2. Дан открытый ключ шифрования
  3. Дана часть приватного ключа шифрования

Решение
#

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:
#

Условие задачи
#

  1. Дан зашифрованный флаг
  2. Дан открытый ключ шифрования
  3. Дана часть приватного ключа шифрования

Решение
#

Распарсив pem’ки, мы выясним, что в приватном ключе всего три параметра

NO q? It’s unsolveable

Нерешаемый, то нерешаемый, но для нас он решаемый!

Разберемся, что за 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}

Эпилог
#

За нас, за вас - и за КБ-4 (с)Zer0bp

Задонатить автору на баночку безалкоголки: https://clck.ru/39wm3q

Crypto basics - This article is part of a series.