Cryptohack. Решение Pad Thai04.12.2024 11:00

Приветствую, Хабр! В сегодняшней статье я расскажу про работу режима шифрования CBC (Cipher block chaining), паддинг PKCS7, а также атаку на их совместное использование на примере решения задачи Pad Thai с сервиса Cryptohack.

Режим шифрования CBC

Про режимы шифрования в блочных шифрах я уже говорил в своей предыдущей статье, поэтому не буду на этом останавливаться здесь. Тем, кто впервые слышит про режимы шифрования, я очень рекомендую сначала прочесть ту статью, там я рассказываю о них подробнее, а также показываю значительно более простую атаку на режим ECB (electronic codebook). Разобравшись с ней, вам будет легче понять магию происходящего здесь.

Итак, что такое CBC? CBC (Cipher block chaining) — режим шифрования, суть которого состоит в связке блоков шифротекста между собой таким образом, что каждый последующий блок текста зависит от всех предыдущих. Это позволяет избавиться от проблемы, которую мы видели у ECB — одинаковые блоки открытого текста не шифруются в одинаковые блоки шифротекста (при правильном применении режима, о чём я ещё расскажу).

Теперь давайте поподробнее про работу CBC. Схема такая:

f9c23ec11cc62b7c805dc6898d7f4fcc.png

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

А теперь самое интересное. Расшифровка производится по следующей схеме:

938d7bb7ddabab0a92a81e01c03916f2.png

Обратите внимание, на то, что на выходной текст каждого блока напрямую влияет предыдущий блок шифротекста (или IV). И изменения в блоке зашифрованного текста вполне предсказуемо влияют на выходящий текст. Это открывает массу возможностей для атак типа «человек посередине». Суть таких атак в том, что между источником и приёмником зашифрованного текста находится третья сущность, намеревающаяся совершить шалость, которая получает зашифрованное сообщение от источника, но не может его расшифровать. Зато может слегка поменять этот текст и отправить его дальше приёмнику. Вот такую шалость мы и будем сегодня осуществлять для решения задачи Pad Thai.

Паддинг PKCS#7

Но прежде чем мы перейдём к задаче необходимо поговорить о ещё одной составляющей режимов шифрования — паддинге. Говоря о режимах шифрования мы упоминаем блоки, на которые делится открытый текст в соответствии с возможностями алгоритма шифрования в центре этой всей схемы. Однако что делать, если длина текста не делится поровну на размер блока (такое в шифр не отдать)? Ну убрать мы из текста ничего не можем, а значит надо что-то добавить! Вот это добавление и называют паддингом. А вот в зависимости от того, чем дополнять текст, паддинги различаются между собой. Самое простое — добавить просто нули — это Zero padding, но существует множество других схем.

Одна из них таких — схема PKCS#7 (или PKCS7). Она очень простая, но в то же время хитрая. Если до заполнения блока не хватает N байт, то по PKCS7 мы должны дополнить текст байтами N. Например, нам не хватает 4 байт, тогда дополнять надо повторяющимся значением 4, то есть 4 байта в конце блока все будут иметь значение 4. Если 10, то 10 байт в конце блока будут иметь значение 10.

  • А что делать если текст поровну делится на блоки?

  • Очевидный, но не правильный ответ — ничего. Если, используя схему PKCS7, мы сталкиваемся с такой ситуацией, то нам нужно добавлять целый блок текста, заполненный значениями, равными длине блока. Например, у AES длина блока 16, значит нужно добавлять 16 байт со значением 16.

  • Но почему так?

  • А потому что после расшифровки, принимающей стороне нужно как-то понять, какие значения являются паддингом и их можно выбросить, а какие — реальный текст. Если текст делится на блоки поровну, то в конце может быть байт с любым значением. Допустим там 1 — ну тогда принимающая сторона сотрёт этот 1 байт, считая его паддингом. А ведь это был реальный текст. Этого допустить нельзя, значит приходится добавлять целый блок.

Ну и приведу пару примеров для наглядности:

  1. Имеем 6 байтов текста 11 22 33 44 55 66. Пусть длина блока будет 8, значит нам не хватает 2 байтов. Тогда по PKCS7 дополненный текст будет выглядеть так:

    11 22 33 44 55 66 02 02

  2. Теперь пусть у нас будет 8 байтов 11 22 33 44 55 66 77 88, длина блока так же 8. В таком случае дополненный текст будет (чертой разделены блоки):

    11 22 33 44 55 66 77 88 | 08 08 08 08 08 08 08 08

Надеюсь, что с этим всё понятно, теперь можем переходить непосредственно к задаче.

Задача

Задача сформулирована в виде исходного кода сервера, а также адреса, по которому до этого сервера можно достучаться. Давайте изучать код.

#!/usr/bin/env python3

from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from os import urandom

from utils import listener

FLAG = 'crypto{?????????????????????????????????????????????????????}'

class Challenge:
    def __init__(self):
        self.before_input = "Let's practice padding oracle attacks! Recover my message and I'll send you a flag.\n"
        self.message = urandom(16).hex()
        self.key = urandom(16)

    def get_ct(self):
        iv = urandom(16)
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        ct = cipher.encrypt(self.message.encode("ascii"))
        return {"ct": (iv+ct).hex()}

    def check_padding(self, ct):
        ct = bytes.fromhex(ct)
        iv, ct = ct[:16], ct[16:]
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        pt = cipher.decrypt(ct)  # does not remove padding
        try:
            unpad(pt, 16)
        except ValueError:
            good = False
        else:
            good = True
        return {"result": good}

    def check_message(self, message):
        if message != self.message:
            self.exit = True
            return {"error": "incorrect message"}
        return {"flag": FLAG}

    #
    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, msg):
        if "option" not in msg or msg["option"] not in ("encrypt", "unpad", "check"):
            return {"error": "Option must be one of: encrypt, unpad, check"}

        if msg["option"] == "encrypt": return self.get_ct()
        elif msg["option"] == "unpad": return self.check_padding(msg["ct"])
        elif msg["option"] == "check": return self.check_message(msg["message"])

import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13421)

Исходя из кода, сервер умеет выполнять три команды, разберём их по порядку.

Команда encrypt. Эта команда шифрует сообщение с помощьюу AES в режиме CBC и возвращает нам. Обратите внимание на то, что сообщение представляет из себя случайные 16 байт, закодированные в шестнадцатеричную запись. То есть суммарно это 32 байта и все они принадлежат множеству 0123456789abcdef. Этот факт нам очень пригодится, когда мы будем проводить атаку на сервер.

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

Команда check_padding. Эта команда расшифровывает переданное сообщение и пытается применить функцию unpad к расшифрованному тексту. Если функция применяется успешно, то мы получаем ответ True, а если возникает исключение, то False. В этой команде находится уязвимость системы и на неё будет направлена наша атака, поэтому подробности рассмотрим позже.

Команда check_message. Наконец эта команда принимает сообщение. Если оно равно message, то есть тому что было зашифровано в encrypt, то мы получаем флаг.

Уязвимость

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

Первые четыре строчки особого интереса для нас не представляют — это просто расшифровка сообщения: 

ct = bytes.fromhex(ct)
iv, ct = ct[:16], ct[16:]
cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
pt = cipher.decrypt(ct)  # does not remove padding

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

Дальше идёт функция unpad, по названию которой можно догадаться, что она удаляет паддинг из расшифрованного текста. Это тот самый паддинг, про который я говорил в разделе про PKCS7. И именно с PKCS7 она и работает по-умолчанию. Если функция успешно детектирует паддинг и удаляет его, то она вернёт текст без паддинга. А если паддинг неправильный, то функция бросит исключение.

try:
  unpad(pt, 16)
except ValueError:
  good = False
else:
  good = True

Как паддинг может быть неправильным?

Посмотрите на PKCS7 паддинги: у них есть строгая структура. Например, если в тексте не хватает 6 байт до длины блока, то к нему должно прикрепиться 6 байт: 06 06 06 06 06 06. Они обязаны быть именно такими, а малейшее отклонение считается неправильным паддингом. То есть, если паддинг будет 06 06 05 06 06 06, то вот эта пятёрка испортит всё сообщение и функция unpad бросит исключение.

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

Внимательный читатель наверняка заметил, что в функции get_ct, нет кода для добавления паддинга к сообщению. И это не потому что он добавляется где-то в процессе шифрования. Паддинг там действительно не добавляется и если передать полученный шифротекст в check_padding, то функция вернёт False.

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

Так как мы можем передавать в check_padding произвольные значения, мы можем менять полученный от сервера шифротекст специальным образом, затем проверять паддинг, и в соответствии с результатом проверки делать выводы относительно оригинального сообщения.

Атака

Схема атаки во многом схожа с атакой на ECB из предыдущей статьи. Мы также будем перебирать байты в одной позиции, расшифровывая текст по одному байту начиная с конца. Разница в том, что в атаке на ECB мы определяли что подставили правильный байт, когда зашифрованные тексты совпадали, а в этой задаче индикатором правильно подобранного байта будет получение True из функции check_padding.

Идея в том, что если мы отправили какой-то текст в check_padding и получили в ответ True, то это значит, что отправленный нами текст расшифровывается в открытый текст, у которого в конце находится структура PKCS7 паддинга, а именно 01, либо 02 02, либо 03 03 03, и т. д. Если получаем False, то ничего подобного в расшифрованном тексте нет.

Если взять зашифрованное сообщение из функции encrypt, и не изменяя, передать его в check_padding, то мы скорее всего получим False, потому что при шифровании паддинга нет, а вероятностью того, что случайно сгенерированное сообщение будет иметь в конце структуру PKCS7 мы можем пренебречь.

А теперь я утверждаю, что, изменяя полученный от сервера шифротекст, мы можем добиться того, что расшифрованное сообщение будет иметь в конце PKCS7 паддинг. И действительно, посмотрите на схему расшифровки. Если мы поменяем в шифротексте последний байт первого блока, то сам первый блок, конечно, расшифруется во что-то невнятное из-за лавинного эффекта. А вот второй блок изменится ровно в одном последнем байте.

80d7b62a877905c97cbf483667a17cbb.png

Причём величина изменения нам известна. Пусть с_1^{16} — последний байт первого блока шифротекста, x_2^{16} — последний байт расшифрованного сообщения до суммирования с c_1^{16}, а p_2^{16} — результат суммирования c_1^{16} и x_2^{16}, то есть реальный последний байт расшифрованного сообщения.

Тогда, можно записать уравнение

c_1^{16} \oplus x_2^{16} = p_2^{16}36b97c9fb4dc12081c55969e7cb574ec.png

Теперь изменим c_1^{16} на величину \Delta, тогда

c_1^{16} \oplus \Delta \oplus x_2^{16} = p_2^{16} \oplus \Delta

Суть этих махинаций в том, чтобы показать, что сейчас у нас есть уравнение с двумя неизвестными x_2^{16} и p_2^{16}, но перебирая значения \Delta, мы рано или поздно найдём такое, что p_2^{16} \oplus \Delta = 01. Как только такое произойдёт, функция check_padding вернёт True. И тогда мы с лёгкостью можем вычислить значение p_2^{16} = \Delta \oplus 01. А ведь это последний байт сообщения. Отсюда мы можем вычислить и x_2^{16} = c_1^{16} \oplus p_2^{16}, но он нам понадобится позже.

Стоит также отметить, что проверка паддинга может пройти успешно не только когда p_2^{16} \oplus \Delta = 01, но и когда p_2^{16} \oplus \Delta = 02, если p_2^{15} = 02. А также если p_2^{16} \oplus \Delta = 03, и p_2^{15} = p_2^{14} = 03. И так далее. Но я буду пренебрегать такими ситуациями, т. к. вероятность их возникновения невелика.

abc6895af14ca52e2fb0c98c5da1c912.png

Итак, надеюсь что вы поняли как расшифровать последний байт сообщения — менять последний байт в первом блоке до тех пор, пока check_padding не ответит True. Перебирать на самом деле не много, всего существует 256 вариантов. Но если учесть, что сообщением является шестнадцатеричная строка, то существует всего 16 подходящих значений для p_2^{16} и любого другого байта сообщения: 0 1 2 3 4 5 6 7 8 9 a b c d e f. Значит мы можем оптимизировать запросы, и проверять только такие \Delta, что \Delta \oplus 01является одним из подходящих значений. В итоге вместо 256 запросов в худшем случае мы сделаем всего 16.

Хорошо, а как теперь расшифровать следующий байт p_2^{15}? Да также, только меняем теперь c_1^{15} и теперь мы целимся получить значение \Delta такое, что p_2^{15} \oplus \Delta = 02 и хотим получить паддинг 02 02. Конечно, и с_1^{16} нужно будет подставлять такое, чтобы получать p_2^{16} = 02, но это уже не проблема, ведь мы знаем значение p_2^{16}. Значит, в c_1^{16} надо подставлять значение p_2^{16} \oplus 02.

deb608a2fde4c90fb8967854db8b696b.png

Чтобы расшифровать третий байт мы формируем паддинг 03 03 03, для четвёртого 04 04 04 04 и так далее.

Когда мы расшифруем весь второй блок текста, мы возвращаемся к паддингу 01, но теперь меняем байт инициализирующего вектора iv^{16}, чтобы найти p_1^{16}. А второй блок текста отбрасываем вовсе.

37fa7726a971794f135d8cf7948bce99.png

Вот и вся суть атаки. А краткий порядок такой:

  1. Получаем от сервера зашифрованное сообщение.

  2. Меняем в первом блоке сообщения последний байт (c_1^{16}) пока функция check_padding не выдаст True

  3. Расшифровываем последний байт сообщения p_2^{16} = c_1^{16} \oplus 01

  4. Меняем c_1^{16} первого блока так, чтобы p_2^{16} стал равен 02 по формуле c_1^{16} = p_2^{16} \oplus 02 и перебираем предпоследний байт первого блока (c_1^{15}) пока функция check_padding не выдаст True

  5. Расшифровываем предпоследний байт сообщения p_2^{15} = c_1^{15} \oplus 02

  6. И так далее.

Код

Код моего решения на Python выглядит так

import pwn
import json
import curses

address = ("socket.cryptohack.org", 13421)
connection = pwn.connect(address[0], address[1])
connection.recvline()

def createEncryptCommand() -> str:
    return "{\"option\":\"encrypt\"}"

def createUnpadCommand(ct: str) -> str:
    return "{\"option\":\"unpad\",\"ct\":\"" + ct + "\"}"

def createCheckCommand(message: str) -> str:
    return "{\"option\":\"check\",\"message\":\"" + message + "\"}"

def splitBlocks(value: str, size: int):
    blocks = []
    for i in range(0, len(value), size):
        blocks.append(value[i: min(i + size, len(value))])
    return blocks

def joinToHex(array):
    result = ""
    for value in array:
        result += "{0:02x}".format(value)
    return result

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 CBC PKCS7 PADDING ORACLE ATTACK }***************************************************", curses.color_pair(2))

    stdscr.addstr(3, 0, "[*] Getting ciphertext", curses.color_pair(1))
    stdscr.refresh()

    # Получаем зашифрованное сообщение
    command = createEncryptCommand()
    connection.sendline(command.encode())
    ciphertext = json.loads(connection.recvline().decode())["ct"]
    stdscr.addstr(4, 4, "Received ciphertext: " + ciphertext, curses.color_pair(2))
    stdscr.refresh()

    stdscr.addstr(6, 0, "[*] Preparing attack", curses.color_pair(1))
    stdscr.refresh()
    blocks = splitBlocks(ciphertext, 32)
    ivHex = blocks[0]
    ct1Hex = blocks[1]
    ct2Hex = blocks[2]

    ivBytes = bytes.fromhex(ivHex)
    ct1Bytes = bytes.fromhex(ct1Hex)
    ct2Bytes = bytes.fromhex(ct2Hex)

    ivArr = []
    ct1Arr = []
    ct2Arr = []
    for idx in range(0, 16):
        ivArr.append(ivBytes[idx])
        ct1Arr.append(ct1Bytes[idx])
        ct2Arr.append(ct2Bytes[idx])

    stdscr.addstr(7, 4, f"IV hex: {ivHex}, IV bytes: {ivArr}", curses.color_pair(2))
    stdscr.addstr(8, 4, f"Block 1 hex: {ct1Hex}, Block 1 bytes: {ct1Arr}", curses.color_pair(2))
    stdscr.addstr(9, 4, f"Block 2 hex: {ct2Hex}, Block 2 bytes: {ct2Arr}", curses.color_pair(2))

    stdscr.addstr(11, 0, "[*] Attacking", curses.color_pair(1))
    stdscr.refresh()

    knownPlaintext = ""
    decryptedArr = []

    while len(decryptedArr) < 32:
        knownLength = len(decryptedArr)
        attackingIndex = knownLength
        isFirstBlock = knownLength < 16

        paddingSize = knownLength % 16 + 1
        targetValue = paddingSize

        knownPlaintextString = f"Knwon plaintext: {knownPlaintext}, "
        stdscr.addstr(12, 4, knownPlaintextString, curses.color_pair(2))
        stdscr.addstr(12, 4 + len(knownPlaintextString), f"Target padding: {targetValue}", curses.color_pair(2))
        stdscr.refresh()

        replacingValues = []
        for idx in range(knownLength):
            replacingValues.append(decryptedArr[idx] ^ targetValue)
        
        replacedIvArr = ivArr.copy()
        replacedCt1Arr = ct1Arr.copy()
        for idx in range(knownLength):
            if idx < 16:
                if isFirstBlock:
                    replacedCt1Arr[len(replacedCt1Arr) - idx - 1] = replacingValues[idx]
            else:
                replacedIvArr[len(replacedIvArr) - (idx - 16) - 1] = replacingValues[idx]

        stdscr.addstr(13, 4, "Sending values: ", curses.color_pair(2))
        stdscr.refresh()
        for attackingValue in range(256):
            foundX = attackingValue ^ targetValue
            if isFirstBlock:
                plaintextChar = chr(foundX ^ ct1Arr[len(ct1Arr) - knownLength - 1])
            else:
                plaintextChar = chr(foundX ^ ivArr[len(ivArr) - (knownLength - 16) - 1])
            if plaintextChar not in "0123456789abcdef": continue

            stdscr.addstr(14, 0, " " * 1000)
            if isFirstBlock:
                replaceIndex = len(replacedCt1Arr) - attackingIndex - 1
                replacedCt1Arr[replaceIndex] = attackingValue

                lineOffest = 8
                stringBeforeReplacedIdx = f"IV: {joinToHex(replacedIvArr)} Block 1: {joinToHex(replacedCt1Arr[:replaceIndex])}"
                stdscr.addstr(14, lineOffest, stringBeforeReplacedIdx, curses.color_pair(2))
                lineOffest += len(stringBeforeReplacedIdx)

                replacedCt1ValueString = "{0:02x}".format(replacedCt1Arr[replaceIndex])
                stdscr.addstr(14, lineOffest, replacedCt1ValueString, curses.color_pair(1))
                lineOffest += len(replacedCt1ValueString)

                stringAfterReplacedIdx = f"{joinToHex(replacedCt1Arr[replaceIndex + 1:])} Block 2: {joinToHex(ct2Arr)}"
                stdscr.addstr(14, lineOffest, stringAfterReplacedIdx, curses.color_pair(2))
            else:
                replaceIndex = len(replacedIvArr) - (attackingIndex - 16) - 1
                replacedIvArr[replaceIndex] = attackingValue

                lineOffest = 8
                stringBeforeReplacedIdx = f"IV: {joinToHex(replacedIvArr[:replaceIndex])}"
                stdscr.addstr(14, lineOffest, stringBeforeReplacedIdx, curses.color_pair(2))
                lineOffest += len(stringBeforeReplacedIdx)

                replacedIvArrValueString = "{0:02x}".format(replacedIvArr[replaceIndex])
                stdscr.addstr(14, lineOffest, replacedIvArrValueString, curses.color_pair(1))
                lineOffest += len(replacedIvArrValueString)

                stringAfterReplacedIdx = f"{joinToHex(replacedIvArr[replaceIndex + 1:])} Block 1: {joinToHex(ct1Arr)}"
                stdscr.addstr(14, lineOffest, stringAfterReplacedIdx, curses.color_pair(2))

            combinedValue = replacedIvArr + replacedCt1Arr
            if isFirstBlock:
                combinedValue += ct2Arr

            combinedHex = joinToHex(combinedValue)
            command = createUnpadCommand(combinedHex)
            stdscr.addstr(15, 8, f"Command: {command}", curses.color_pair(2))

            connection.sendline(command.encode())
            answer = connection.recvline().decode()
            result = json.loads(answer)["result"]
            if result == True:
                foundX = attackingValue ^ targetValue
                if isFirstBlock:
                    knownPlaintext = chr(foundX ^ ct1Arr[len(ct1Arr) - knownLength - 1]) + knownPlaintext
                else:
                    knownPlaintext = chr(foundX ^ ivArr[len(ivArr) - (knownLength - 16) - 1]) + knownPlaintext
                
                decryptedArr.append(foundX)
                break

            stdscr.refresh()
    
    command = createCheckCommand(knownPlaintext)
    connection.sendline(command.encode())

    answer = connection.recvline().decode()
    flag = json.loads(answer)["flag"]

    stdscr.addstr(16, 0, f"Flag: {flag}", curses.color_pair(3))
    stdscr.refresh()

    while True:
        pass

curses.wrapper(main)

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

Результат работы кода:

2d50f27529145e77b684c3338ee8c338.png

Дополнения The Good, The Pad, The Ugly и Oracular Spectacular

На Cryptohack также есть пара заданий, в основе которых лежит та же атака, но с некоторым усложнением. Первое из них это задача The Good, The Pad, The Ugly с вот таким кодом: 

#!/usr/bin/env python3

from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from os import urandom
from random import SystemRandom

from utils import listener

FLAG = 'crypto{??????????????????????????????????????????}'
rng = SystemRandom()


class Challenge:
    def __init__(self):
        self.before_input = "That last challenge was pretty easy, but I'm positive that this one will be harder!\n"
        self.message = urandom(16).hex()
        self.key = urandom(16)
        self.query_count = 0
        self.max_queries = 12_000

    def update_query_count(self):
        self.query_count += 1
        if self.query_count >= self.max_queries:
            self.exit = True

    def get_ct(self):
        iv = urandom(16)
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        ct = cipher.encrypt(self.message.encode("ascii"))
        return {"ct": (iv+ct).hex()}

    def check_padding(self, ct):
        ct = bytes.fromhex(ct)
        iv, ct = ct[:16], ct[16:]
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        pt = cipher.decrypt(ct)  # does not remove padding
        try:
            unpad(pt, 16)
        except ValueError:
            good = False
        else:
            good = True
        self.update_query_count()
        return {"result": good | (rng.random() > 0.4)}

    def check_message(self, message):
        if message != self.message:
            self.exit = True
            return {"error": "incorrect message"}
        return {"flag": FLAG}

    #
    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, msg):
        if "option" not in msg or msg["option"] not in ("encrypt", "unpad", "check"):
            return {"error": "Option must be one of: encrypt, unpad, check"}

        if msg["option"] == "encrypt": return self.get_ct()
        elif msg["option"] == "unpad": return self.check_padding(msg["ct"])
        elif msg["option"] == "check": return self.check_message(msg["message"])


import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13422)

По сути это тот же Pad Thai, но с двумя различиями:

  1. Появился счётчик на количество запросов в check_padding с ограничением в 12000. По достижении этого лимита сервер нас отключит.

  2. В check_padding поменялась выдача результата с {"result": good} на {"result": good | (rng.random() > 0.4)}.

То есть появился элемент случайности ответа. Если случайное число в пределах от 0 до 1 выданное функцией rng.random() будет больше 0.4, то функция вернёт True, даже если проверка паддинга не удалась.

Случайные числа из rng.random() имеют равномерное распределение. Это значит, что в среднем 60% вызовов rng.random() выдадут значение больше 0.4. То есть у функции check_padding существует шанс ложного срабатывания в 60%.

Эта проблема легко обходится с помощью нескольких проверок. Если функция вернула True, то давайте проверим ещё раз, а потом ещё, и ещё, до тех пор пока наша уверенность в том, что мы нашли правильное число не будет достаточной. Так как вероятность ошибки составляет 0.6, две проверки дадут вероятность ошибки 0.6^2 = 0.36,три проверки 0.216, и т.д. Сколько проверок надо сделать?

Ну, мы могли бы сделать 100 проверок, чтобы получить вероятность ошибки в районе 10^{-23}, но давайте не забывать, что у нас всего 12000 попыток. А расшифровать необходимо 32 символа. Для каждого символа существует 16 вариантов. Суммарно 32 * 16 = 512 вариантов, которые надо проверить. Значит мы можем проверить каждое значение 12000 / 512 = 23.4375 \approx 23 раза с вероятностью ошибки для каждого символа равной 0.6^{23} \approx 0.8 \cdot 10^{-6}. Думаю, что такой уверенности в результате нам должно хватить.

Таким образом, чтобы решить The Good, The Pad, The Ugly, достаточно проверять каждое значение, для которого check_padding выдало True 23 раза. Если все 23 раза мы получили True, то считаем что оно правильное.

Oracular Spectacular

Ещё одна задача, которая строится на Pad Thai — Oracular Spectacular. Сразу признаюсь, что для это задачи я пока флаг получить не смог, поэтому ниже будут мои мысли, не подкреплённые реальным решением. Код у задачи такой: 

#!/usr/bin/env python3

from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from os import urandom
from random import SystemRandom

from utils import listener

FLAG = 'crypto{????????????????????????????????????????????????????}'
rng = SystemRandom()


class Challenge:
    def __init__(self):
        self.before_input = "That last challenge was pretty easy, but I'm positive that this one will be harder!\n"
        self.message = urandom(16).hex()
        self.key = urandom(16)
        self.query_count = 0
        self.max_queries = 12_000

    def update_query_count(self):
        self.query_count += 1
        if self.query_count >= self.max_queries:
            self.exit = True

    def get_ct(self):
        iv = urandom(16)
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        ct = cipher.encrypt(self.message.encode("ascii"))
        return {"ct": (iv+ct).hex()}

    def check_padding(self, ct):
        ct = bytes.fromhex(ct)
        iv, ct = ct[:16], ct[16:]
        cipher = AES.new(self.key, AES.MODE_CBC, iv=iv)
        pt = cipher.decrypt(ct)  # does not remove padding
        try:
            unpad(pt, 16)
        except ValueError:
            good = False
        else:
            good = True
        self.update_query_count()
        return {"result": good ^ (rng.random() > 0.4)}

    def check_message(self, message):
        if message != self.message:
            self.exit = True
            return {"error": "incorrect message"}
        return {"flag": FLAG}

    #
    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, msg):
        if "option" not in msg or msg["option"] not in ("encrypt", "unpad", "check"):
            return {"error": "Option must be one of: encrypt, unpad, check"}

        if msg["option"] == "encrypt": return self.get_ct()
        elif msg["option"] == "unpad": return self.check_padding(msg["ct"])
        elif msg["option"] == "check": return self.check_message(msg["message"])


import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
listener.start_server(port=13423)

От The Good, The Pad, The Ugly он отличается только строчкой

{"result": good ^ (rng.random() > 0.4)}

Получается, что раньше check_padding могла выдать ложный True, но мы хотя бы были уверенны в знаении False. А теперь мы можем получать как ложный True, так и ложный False. Посмотрите на таблицу

good

rng.random () > 0.4

result

False

False

False

False

True

True

True

False

True

True

True

False

То есть просто проверить значение True несколько раз уже не вариант.

А рабочий (опять же, теоретически) подход — это проверять несколько раз любое значение и считать количество True и False, потому что их распределение будет смещено. Я имею в виду тот факт, что rng.random() > 0.4 будет равно True с вероятностью 0.6. Тогда, если значение good равно False (то есть паддинг на самом деле неправильный), то check_padding должен выдавать True с вероятностью 0.6. И наоборот, если паддинг правильный, то check_padding будет выдавать True c вероятностью 0.4. Распределение вероятностей такое:

good

rng.random () > 0.4

result

False

False, P = 0.4

False, P = 0.4

False

True, P = 0.6

True, P = 0.6

True

False, P = 0.4

True, P = 0.4

True

True, P = 0.6

False, P = 0.6

Это означает, что чем ближе распределение True/False в ответах check_padding к 0.4 / 0.6, тем больше вероятность того, что паддинг на самом деле правильный.

Таким образом, потенциально рабочее решение: проверять абсолютно все значения по несколько раз, считать количество True и False и выбирать то значение, которое ближе к распределению 0.4/0.6 (или у которого меньше значений True). Проблема в том, что мы можем сделать не больше 23 запросов на символ и на такой выборке проявляется плохо, поэтому накапливается слишком много.

Заключение

На этом всё. Вот такая достаточно длинная у меня получилась статья в этот раз. Надеюсь что кто-то честно дочитал до конца и не умер со скуки да ещё и всё понял. В любом случае спасибо всем, кто прочёл, оставляйте обратную связь и вопросы в комментариях, и stay tuned for more.

Источники

  1. https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation

  2. https://en.wikipedia.org/wiki/Padding_(cryptography)

© Habrahabr.ru