CryptoHack. Решение ECB Oracle

В этой статье я расскажу о режиме шифрования ECB и покажу каким образом можно расшифровывать произвольный текст, при наличии возможности добавлять известный открытый текст к данным. Данная статья является расширением ранее опубликованной мной статьи на Medium.

Задача

Для начала посмотрим на саму задачу, а после я попробую разобрать составляющие части и подробно описать решение. Итак, в задаче нам предоставляют ссылку на страницу https://aes.cryptohack.org/ecb_oracle/

Здесь есть исходный код сервера

И возможность взаимодействия с ним

Также мы можем взаимодействовать с сервером программно через GET запросы.

Суть задачи — найти значение FLAG.

Курим код

from Crypto.Cipher import AES from Crypto.Util.Padding import pad, unpad   KEY = ? FLAG = ?   @chal.route('/ecb_oracle/encrypt/<plaintext>/') def encrypt(plaintext):     plaintext = bytes.fromhex(plaintext)      padded = pad(plaintext + FLAG.encode(), 16)     cipher = AES.new(KEY, AES.MODE_ECB)     try:         encrypted = cipher.encrypt(padded)     except ValueError as e:         return {"error": str(e)}      return {"ciphertext": encrypted.hex()}

Сервер поддерживает только одну функцию — encrypt, в которую мы можем передать произвольный plaintext. При получении текста сервер пытается преобразовать его из хекс-строки в байты. Дальше важно — к переданному нами тексту присоединяется флаг, и к этому всему применяют pad(то есть по сути дополняют в конце так, чтобы результат делился нацело на блоки по 16 байт).

Почему 16? Потому что это размер блока алгоритма шифрования AES, с помощью которого значение padded шифруется в режиме ECB. Результат шифрования в формате хекс-строки возвращается к нам.

Разбираемся с понятиями

Как работает AES я здесь рассказывать не стану. Во-первых, это большая тема и требует отдельной статьи. Во-вторых, в данной задаче нам совершенно всё равно как он работает. Уязвимость, которую мы будем использовать, применима к любому блочному шифру. Или, если говорить строже, то к любому шифру, который можно считать функцией

(где — шифрование текста , с помощью ключа , — зашифрованное сообщение), такой, что $\forall k_1 = k_2, T_1 = T_2 \implies C_1 = C_2$ . Использовать мы будем как раз это свойство.

А вот что стоит разобрать подробно, так это режим шифрования ECB.

ECB в деталях

Блочные шифры (AES, DES и прочие) по своему устройству способны шифровать только блоки определённой длины, и надёжность таких шифров определяется исходя из надёжности шифрования одного блока. Конечно, существуют методы криптоанализа, основанные на анализе шифрования большого количества блоков. Однако в них каждый блок шифруется своим ключом.

Короче говоря, блочные шифры задуманы так, что вы берёте один блок текста и шифруете его. Если нужно зашифровать ещё блок, то вы берёте другой ключ, независимый от первого, и шифруете опять, и так далее. Вообще всякий раз, когда нужно что-то зашифровать, вам нужен новый ключ. Только в такой ситуации авторы шифров гарантируют надёжность (ну или хотя бы пытаются гарантировать).

Конечно, на практике мы хотим шифровать произвольные объёмы данных, к тому же используя один ключ, или менять ключи, но не для каждого блока — создание и передача надёжных ключей по сети это отдельная головная боль. Для решения этой проблемы придумали режимы шифрования, их существует много и у каждого есть свои достоинства и недостатки (и уязвимости). В данной статье поговорим про ECB.

ECB (Electronic codebook) — самый простой режим шифрования. В этом режиме сообщение просто разбивается на блоки, каждый из которых шифруется независимо от остальных.

Всё делается одним ключем и в этом большая проблема, потому что в таком случае одинаковые блоки открытого текста превращаются в одинаковые зашифрованные блоки. Крупные паттерны открытого текста при этом просачиваются в зашифрованные данные, что сильно упрощает криптоанализ. В статье на Википедии есть чудесный пример этого эффекта:

Изображение зашифрованное AES в режиме ECB

Этим мы и воспользуемся во время решения задачи.

Решение

Сначала узнаем длину флага, для этого отправляем на сервер 0. Получаем в ответ значение3f45e266104a0af716e403ee251aa94e7a55b6b6959613d98c9b0976d44818a6 длиной 32 байта.

Мы отправили всего один байт, значит длина флага должна быть в пределах 16-31 байт: если бы флаг был короче 16 байт, то добавление одного байта не потребовало бы шифрования двух блоков текста, а если бы длина была больше 31, то добавление одного байта потребовало бы шифрования уже трёх блоков, т.е. мы бы получили не 32, а 48 байт.

С этим справились, а теперь обратим внимание на первый блок текста. Из зашифрованного в первом блоке текста мы знаем один байт — остальные 15 нам неизвестны. А что если мы поступим наоборот — отправим 15 известных байт? Тогда только один байт будет нам неизвестен. Вот как это будет выглядеть:

А теперь вспоминаем, что одинаковые открытые тексты дают одинаковые шифротексты. Это значит, что мы можем просто перебирать все 256 вариантов для этого последнего байта, каждый из вариантов отправить на сервер и сравнить с тем шифротекстом, который получили когда отправляли только 15 байт. Как только шифротексты совпадут это будет значить, что мы угадали значение для этого байта.

То есть что мы делаем:

Отправляем 15 любых байтов на сервер (важно только чтобы они были для нас известны)
Получаем от сервера зашифрованный текст, пусть это будет . В этом шифротексте первый блок состоит из 15 известных нам байтов + один байт , который мы не знаем.
Теперь отправляем на сервер 16 байтов, где первые 15 байтов равны байтам из п. 1, а 16й перебираем (0, 1, 2, …, 255), получая при этом $C_0, C_1, C_2,...,C_{255}$
Когда какой-то из ответов от сервера совпадёт с , это будет значить, что , то есть мы расшифровали первый байт флага.
Теперь давайте расшифровывать второй байт. Для этого отправляем на сервер уже 14 байтов текста. таким образом в первый блок шифротекста попадут уже 2 байта из флага.
Но ведь первый байт мы уже знаем! Значит можем проделывать пункт 3, но теперь отправляем 14 байт нулей, на 15й байт ставим первый байт флага, который мы узнали в пункте 4, а 16й байт так же перебираем.
Снова, когда ответ сервера совпадёт с тем, что мы получили в пункте 5, мы расшифровали уже второй байт флага.
Последовательно повторяя эту процедуру мы можем найти весь флаг.

Но флаг может быть и больше 16 байт, так что одного блока текста нам не хватит, но это не проблема — просто добавляем ещё 16 байт, но делаем всё то же самое — всегда отправляем такой текст, чтобы в конце блока оставался только один неизвестный нам байт:

Сколько нам будет стоить эта атака? Так как флаг может быть длиной до 31 байта, то в худшем случае нам придётся перебрать значений. Вручную отправлять все эти запросы я, конечно, не хочу, поэтому я написал скрипт для решения.

import requests import json import curses   def main(stdscr):      curses.resize_term(100, 300)     stdscr.refresh()     curses.start_color()     curses.curs_set(0)      curses.init_pair(1, curses.COLOR_RED, curses.COLOR_BLACK)     curses.init_pair(2, curses.COLOR_GREEN, curses.COLOR_BLACK)     curses.init_pair(3, curses.COLOR_CYAN, curses.COLOR_BLACK)      stdscr.clear()      stdscr.addstr(0, 0, "***********************{ AES ECB CHOSEN PLAINTEXT ATTACK }***********************", curses.color_pair(2))      # Базовый адрес для отправки запросов     base = "http://aes.cryptohack.org/ecb_oracle/encrypt/"      stdscr.addstr(1, 0, "Address to attack: " + base, curses.color_pair(3))     stdscr.addstr(3, 0, "[*] Getting ciphertexts...", curses.color_pair(1))     stdscr.refresh()      # Собираем шифротексты до начала перебора     block1 = []     block2 = []      for i in range(16, 32):         pad = "00" * i         response = requests.get(base + pad)         ciphertext = json.loads(response.content)["ciphertext"]         block1.append(ciphertext[32:64])         block2.append(ciphertext[64:96])      samples = block1 + block2      stdscr.addstr(4, 0, "[!] Retrieved ciphertexts:", curses.color_pair(2))     stdscr.addstr(5, 5, "Block 1:")      for i in range(16):         stdscr.addstr(6 + i, 10, samples[i])      stdscr.addstr(7 + i, 5, "Block 2:")     for i in range(16, 32):         stdscr.addstr(7 + i, 10, samples[i])      stdscr.addstr(40, 0, "[-] Attacking...", curses.color_pair(1))     stdscr.refresh()      # Изначально известный текст пустой     known = ""     t = ["-", "\\", "|", "/", "-", "\\", "|", "/"]     for i in range(1, 33):         stdscr.addstr(41, 0, "Known text -> " + bytes.fromhex(known).decode(), curses.color_pair(3))          if i <= 16:             rm = samples[-16 - i]  # Берём шифротекст из первого блока             stdscr.addstr(6 + 16 - i, 10, rm + "<- attack", curses.color_pair(1))         else:             rm = samples[16 - i]  # Берём шифротекст из второго блока             stdscr.addstr(7 + 48 - i, 10, rm + "<- attack", curses.color_pair(1))          # Перебираем не все 256 значений, а только печатные символы, таким образом снижая количество возможных запросов с 8192 до 3040.         for j in range(32, 127):             stdscr.addstr(40, 0, f"[{t[j % len(t)]}] Attacking...", curses.color_pair(1))              # Подготавливаем payload             pad = "00" * (31 - len(known) // 2)              # Формируем запрос             request = base + pad + known + format(j, "02x")              # Получаем ответ             response = requests.get(request)             ciphertext = json.loads(response.content)["ciphertext"][32:64]              stdscr.addstr(42, 0, "Payload: 0x" + pad, curses.color_pair(3))             stdscr.addstr(42, 11 + len(pad), known, curses.color_pair(2))             stdscr.addstr(42, 11 + len(pad) + len(known), format(j, "02x"), curses.color_pair(1))             stdscr.addstr(43, 0, "Current ciphertext: " + ciphertext, curses.color_pair(3))             stdscr.refresh()              # Если шифротексты совпали, то переходим к следующему шагу             if ciphertext == rm:                 known += hex(j)[2:]                  if i <= 16:                     stdscr.addstr(6 + 16 - i, 10, rm + "<- processed", curses.color_pair(2))                 else:                     stdscr.addstr(7 + 48 - i, 10, rm + "<- processed", curses.color_pair(2))                  # Когда нашли закрывающую скобку, останавливаем перебор, потому что нам уже известен флаг                 if chr(j) == "}":                     stdscr.addstr(44, 0, "[2] Attack successful!", curses.color_pair(1))                     stdscr.addstr(45, 0, "[2] Flag retrieved: " + bytes.fromhex(known).decode(), curses.color_pair(2))                     stdscr.getkey()                     return                 break     stdscr.getkey()   curses.wrapper(main)

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

Заключение

Вот и всё, такой вот он ECB. Спасибо всем, кто дочитал до конца, приходите в комментарии с вопросами и замечаниями и stay tuned for more 😉

ссылка на оригинал статьи https://habr.com/ru/articles/855906/