AES-CBC - Padding Oracle Attack

2024-11-14 2024-11-18 2782 слов 13 минут

Содержание

1 AES-CBC - Padding Oracle Attack

Padding Oracle Attack — это криптографическая атака, которая эксплуатирует механизм паддинга в некоторых схемах шифрования, таких как CBC (Cipher Block Chaining), использующий симметричное шифрование, например AES. Она позволяет злоумышленнику расшифровывать или изменять данные, не зная ключа шифрования.

С помощью этой атаки можно:

Расшифровать зашифрованное сообщение
Зашифровать произвольное сообщение

2 Что нужно чтобы воспользоваться Padding Oracle Attack?

Атакующий должен иметь возможность:
- Вносить изменения в шифротекст.
- Отправлять изменённый шифротекст серверу.
- Получать ответы на запросы многократно.
Уязвимая система должна:
- Применять блочный шифр в режиме AES-CBC (Cipher Block Chaining) или аналогичный режим, где требуется дополнение данных.
- Дополнять данные с PKCS#7.
- Явно или неявно указывать корректен ли паддинг (это можно определить по явному сообщению об ощибке, по разным кодам ошибок, по разному времени вополнения запроса, сбою в обслуживанию или инному поведению)

3 Как работает паддинг и для чего он нужен

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

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

Обзщая схема применения падинга при шифровании:

pad

plaintext = get_plaintext()     // Получили сообщение размера,
                                // которое хотим зашифровать.
plaintext = pad(plaintext)      // Добавили в конец сообщения паддинг,
                                // чтобы размер сообщения был кратен размеру блока.
ciphertext = encrypt(plaintext) // После шифрования получили шифротекст,
                                // размер которого кратен размеру блока.

Обзщая схема применения падинга при расшифровании:

unpad

ciphertext = get_ciphertext()   // Получили сообщение, которое хотим расшифровать.
                                // Размер ciphertext кратен размеру блока.
plaintext = encrypt(ciphertext) // После расшифрования получили текст,
                                // размер которого кратен размеру блока
                                // (и совпадает в размером ciphertext)
plaintext = unpad(plaintext)    // Убрали из конец сообщения паддинг,
                                // чтобы размер сообщения совпал с изначальным размером
                                // (до применения шифрования)

3.1 Как работает PKCS#7

В конец сообщения добавляется необходимое число байт, чтобы размер сообщения стал кратен размеру блока.
Если размер сообщения уже кратен размеру блока, то добавляется целый блок.
Значние добавленных байт совпадает с количеством добавленных байт.

Примеры

PKCS#7 example

"Hello World!1" -> "Hello World!12\x03\x03\x03"
"Hello World!12" -> "Hello World!123\x02\x02"
"Hello World!123" -> "Hello World!123\x01"
"Hello World!1234" -> "Hello World!1234\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10"
"Hello World!12345" -> "Hello World!12345\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f"

Возможная реализация на python:

pkcs7.py

def pkcs7_pad(data: bytes, block_size: int) -> bytes:
    if block_size <= 0 or block_size > 255:
        raise ValueError("The block size must be in the range of 1 to 255")

    pad_len = block_size - (len(data) % block_size)
    padding = bytes([pad_len] * pad_len)
    return data + padding

def pkcs7_unpad(data: bytes, block_size: int) -> bytes:
    if not data or len(data) % block_size != 0:
        raise ValueError("The data has an incorrect length")

    pad_len = data[-1]
    if pad_len <= 0 or pad_len > block_size:
        raise ValueError("Incorrect padding value")

    if data[-pad_len:] != bytes([pad_len] * pad_len):
        raise ValueError("Incorrect PKCS#7 padding")

    return data[:-pad_len]

4 Padding Oracle Attack - Decrypt

Атакующий знает все значения блоков Ciphertext (IV, ct1, ct2, …, ctN).
Атакующий хочет восстановить все значения блоков Plaintext (pt1, pt2, …, ptN).

Рассмотрим алгоритм расшифровывания на примере двух последних блоков ct1, ct2.

is2 = decrypt(key, ct2) // Вычисляется внутреннее состояние is2
pt2 = is2 xor ct1       // Вычисляется pt2
pt2 = unpad(pt2)        // Удаляется падинг

Так как размер падинга не превышает размера блока, то unpad влияет только на последний блок.

В каких ситуачаях сервер может сообщить об некорректном падинге?

Корректные форматы блока

correct format

 X  X  X  X  X  X  X  X  X  X  X  X  X  X  X  1
 X  X  X  X  X  X  X  X  X  X  X  X  X  X  2  2
 X  X  X  X  X  X  X  X  X  X  X  X  X  3  3  3
 X  X  X  X  X  X  X  X  X  X  X  X  4  4  4  4
 X  X  X  X  X  X  X  X  X  X  X  5  5  5  5  5
.....
 X  X 14 14 14 14 14 14 14 14 14 14 14 14 14 14
 X 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16

где

X - любое значение байта.
цифра - значение байта в десятеричной системе.

Все остальные форматы приводят к некорректному падингу.

4.1 Алгоритм

Обозначения: ct2 - последний блок, ct1 предпоследний блок.

Алгоритм нахождения Intermediate state последнего блока:

Проверяем, что паддинг соответствует формату X X X X X X X X X X X X X X X 1:
- Перебираем все значения ct1[15]
- Если сервер ответил, что паддинг кооректный, то
  - is2[15] = ct1[15] xor 1
  - Переходим к слеующему шагу
Проверяем, что паддинг соответствует формату X X X X X X X X X X X X X X 2 2:
- Выставляем ct1[15] в значение 2
- Перебираем все значения ct1[14]
- Если сервер ответил, что паддинг кооректный, то
  - is2[14] = ct1[14] xor 2
  - Переходим к слеующему шагу
Проверяем, что паддинг соответствует формату X X X X X X X X X X X X X 3 3 3:
- Выставляем ct1[14], ct[15] в значение 3
- Перебираем все значения ct1[13]
- Если пока сервер ответил, что паддинг кооректный, то
  - is2[13] = ct1[13] xor 3
  - Переходим к слеующему шагу
Проверяем, что паддинг соответствует формату X X X X X X X X X X X X 4 4 4 4:
- Выставляем ct1[13], ct1[14], ct[15] в значение 4
- Перебираем все значения ct1[12]
- Если сервер ответил, что паддинг кооректный, то
  - is2[12] = ct1[12] xor 4
  - Переходим к слеующему шагу
Аналогичными действиями находим все значения is2[0], is2[1], ..., is2[16]

Алгоритм расшифровки всех блоков:

Пока ciphertext не пустой
- Находим is2 последнего блока
- Вычисляем pt2 = ct1 xor is2
- Сохраняем результат plaintext = pt2 + plaintext
- Отбрасываем последний блок
К plaintext применить unpad, чтобы убрать паддинг
В plaintext будет сохранен расшифрованное сообщение

4.2 Пример

Реализуем алгоритм и проверим его работу, решив задачу AES-CBC-POA.
https://pwn.college/intro-to-cybersecurity/cryptography/

Есть dispatcher, который зашифровывает сообщение

dispatcher.py

#!/run/workspace/bin/python3

from base64 import b64encode
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

import sys

key = open("/home/hacker/challenge/.key", "rb").read()
cipher = AES.new(key=key, mode=AES.MODE_CBC)

if len(sys.argv) > 1 and sys.argv[1] == "flag":
    plaintext = open("/home/hacker/challenge/flag", "rb").read().strip()
else:
    plaintext = b"sleep"

ciphertext = cipher.iv + cipher.encrypt(pad(plaintext, cipher.block_size))
print(f"TASK: {b64encode(ciphertext).decode()}")

Есть worker, который расшифровывает сообщение

worker.py

#!/run/workspace/bin/python3

from base64 import b64decode
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Random import get_random_bytes

import time
import sys

key = open("/home/hacker/challenge/.key", "rb").read()

while line := sys.stdin.readline():
    if not line.startswith("TASK: "):
        continue
    data = b64decode(line.split()[1])
    iv, ciphertext = data[:16], data[16:]

    cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
    plaintext = unpad(cipher.decrypt(ciphertext), cipher.block_size).decode('latin1')

    if plaintext == "sleep":
        print("Sleeping!")
        time.sleep(1)
    elif plaintext == "flag":
        print("Not so easy...")
    else:
        print("Unknown command!")

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

Получать зашифрованное сообщение будем через вызов внешней программы с захватом вывода:

dispatcher.py

def dispatcher(args):
    result = subprocess.run(dispatcher_cmd + args, capture_output=True, text=True)
    return base64.b64decode(result.stdout.split()[1])

Проверять валидность паддинга будем через проверку кода возврата:

check_pad.py

def check_pad(ct, isprint=False):
    text = f"TASK: {base64.b64encode(ct).decode()}\n"
    result = subprocess.run(worker_cmd, input=text, capture_output=True, text=True)
    if isprint and result.returncode == 0:
        print(result.stdout)
    return result.returncode == 0

Функция aes_pao_dfs работает с последними двумя блоками ct1, ct2.
Возвращает внутреннее состояние Intermediate state для блока ct2.
Параметры idx, is2 нужны для передачи состояния через рекурсивные вызовы.
В функции происходит перебор всех значений на позиции idx. В случае успеха происходит переход к следующей позиции.

aes_pao_dfs.py

def aes_pao_dfs(ct_prefix, ct1, ct2, idx, is2, check):
    if idx == -1:
        return is2

    if idx < 0 or idx > 15:
        return None

    ct1_new = ct1[:]
    for i in range(idx+1, 16):
        ct1_new[i] = is2[i] ^ (16 - idx)

    for i in range(256):
        ct1_new[idx] = i

        if not check(ct_prefix + ct1_new + ct2):
            continue

        is2 = is2[:]
        is2[idx] = ct1_new[idx] ^ (16 - idx)

        print(f"idx={idx:03}   i={i:03}   is2={is2.hex()}   pt2={xor(ct1, is2)}", flush=True)

        res = aes_pao_dfs(ct_prefix, ct1, ct2, idx - 1, is2, check)
        if res != None:
            return res

    return None

Разбиваем исходное зашифрованное сообщение на блоки.
Для каждой пары блоков возвращает внутреннее состояние Intermediate state для последнего блока и удаляем этот блок.
По завершению работы остается только применить flag = ct1 xor is2.

blocks.py

for i in range(len(ct) - 16 - 16, -1, -16):
    ct_prefix, ct1, ct2, ct_suffix = ct[:i], ct[i:i+16], ct[i+16:i+16+16], ct[i+16+16:]
    is2 = bytearray(b"\x00" * 16)

    is2 = aes_pao_dfs(ct_prefix, ct1, ct2, 16-1, is2, check_pad)
    if is2 == None:
        print("NOT FOUND")
        break

    flag = xor(ct1, is2).decode() + flag
    print(f"flag: {flag}   {flag.encode()}")
    check_pad(ct, True)

Полное решение:

main.py

#!/usr/bin/python3

import subprocess
import base64
import os
from datetime import datetime


dispatcher_cmd = ["/home/hacker/challenge/dispatcher"]
worker_cmd = ["/home/hacker/challenge/worker"]


def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))


def dispatcher(args):
    result = subprocess.run(dispatcher_cmd + args, capture_output=True, text=True)
    return base64.b64decode(result.stdout.split()[1])


def check_pad(ct, isprint=False):
    text = f"TASK: {base64.b64encode(ct).decode()}\n"
    result = subprocess.run(worker_cmd, input=text, capture_output=True, text=True)
    if isprint and result.returncode == 0:
        print(result.stdout)
    return result.returncode == 0


def aes_pao_dfs(ct_prefix, ct1, ct2, idx, is2, check):
    if idx == -1:
        return is2

    if idx < 0 or idx > 15:
        return None

    ct1_new = ct1[:]
    for i in range(idx+1, 16):
        ct1_new[i] = is2[i] ^ (16 - idx)

    for i in range(256):
        ct1_new[idx] = i

        if not check(ct_prefix + ct1_new + ct2):
            continue

        is2 = is2[:]
        is2[idx] = ct1_new[idx] ^ (16 - idx)

        print(f"idx={idx:03}   i={i:03}   is2={is2.hex()}   pt2={xor(ct1, is2)}", flush=True)

        res = aes_pao_dfs(ct_prefix, ct1, ct2, idx - 1, is2, check)
        if res != None:
            return res
    
    return None



ct = dispatcher(["flag"])
ct = bytearray(ct)
print(f"ct: {ct.hex()}")

flag = ""

for i in range(len(ct) - 16 - 16, -1, -16):
    ct_prefix, ct1, ct2, ct_suffix = ct[:i], ct[i:i+16], ct[i+16:i+16+16], ct[i+16+16:]
    is2 = bytearray(b"\x00" * 16)

    is2 = aes_pao_dfs(ct_prefix, ct1, ct2, 16-1, is2, check_pad)
    if is2 == None:
        print("NOT FOUND")
        break

    flag = xor(ct1, is2).decode() + flag
    print(f"flag: {flag}   {flag.encode()}")
    check_pad(ct, True)

Запускаем программу и ждем пока не будет расшифрованно сообщение полностью:

output.txt

[amyasnikov@ubuntu:~]$ python3 ./main.py
ct: fdcd63a14bb2531530c19bb6cb9ac6e2d8e3ea7b83e8dae1bdeff3a42aefba4a837e42dc0f654b3516c7a136cc0c69b5414267dda54386231b58b5bed61fb201468ed73a20e435dec7afb1ac46364603
idx=015   i=001   is2=00000000000000000000000000000000   pt2=b'ABg\xdd\xa5C\x86#\x1bX\xb5\xbe\xd6\x1f\xb2\x01'
idx=015   i=006   is2=00000000000000000000000000000007   pt2=b'ABg\xdd\xa5C\x86#\x1bX\xb5\xbe\xd6\x1f\xb2\x06'
idx=014   i=182   is2=0000000000000000000000000000b407   pt2=b'ABg\xdd\xa5C\x86#\x1bX\xb5\xbe\xd6\x1f\x06\x06'
idx=013   i=026   is2=0000000000000000000000000019b407   pt2=b'ABg\xdd\xa5C\x86#\x1bX\xb5\xbe\xd6\x06\x06\x06'
idx=012   i=212   is2=000000000000000000000000d019b407   pt2=b'ABg\xdd\xa5C\x86#\x1bX\xb5\xbe\x06\x06\x06\x06'
idx=011   i=189   is2=0000000000000000000000b8d019b407   pt2=b'ABg\xdd\xa5C\x86#\x1bX\xb5\x06\x06\x06\x06\x06'
idx=010   i=181   is2=00000000000000000000b3b8d019b407   pt2=b'ABg\xdd\xa5C\x86#\x1bX\x06\x06\x06\x06\x06\x06'
idx=009   i=034   is2=00000000000000000025b3b8d019b407   pt2=b'ABg\xdd\xa5C\x86#\x1b}\x06\x06\x06\x06\x06\x06'
idx=008   i=096   is2=00000000000000006825b3b8d019b407   pt2=b'ABg\xdd\xa5C\x86#s}\x06\x06\x06\x06\x06\x06'
idx=007   i=025   is2=00000000000000106825b3b8d019b407   pt2=b'ABg\xdd\xa5C\x863s}\x06\x06\x06\x06\x06\x06'
idx=006   i=248   is2=000000000000f2106825b3b8d019b407   pt2=b'ABg\xdd\xa5Ct3s}\x06\x06\x06\x06\x06\x06'
idx=005   i=049   is2=00000000003af2106825b3b8d019b407   pt2=b'ABg\xdd\xa5yt3s}\x06\x06\x06\x06\x06\x06'
idx=004   i=203   is2=00000000c73af2106825b3b8d019b407   pt2=b'ABg\xddbyt3s}\x06\x06\x06\x06\x06\x06'
idx=003   i=230   is2=000000ebc73af2106825b3b8d019b407   pt2=b'ABg6byt3s}\x06\x06\x06\x06\x06\x06'
idx=002   i=088   is2=000056ebc73af2106825b3b8d019b407   pt2=b'AB16byt3s}\x06\x06\x06\x06\x06\x06'
idx=001   i=018   is2=001d56ebc73af2106825b3b8d019b407   pt2=b'A_16byt3s}\x06\x06\x06\x06\x06\x06'
idx=000   i=018   is2=021d56ebc73af2106825b3b8d019b407   pt2=b'C_16byt3s}\x06\x06\x06\x06\x06\x06'
flag: C_16byt3s}   b'C_16byt3s}\x06\x06\x06\x06\x06\x06'

idx=015   i=246   is2=000000000000000000000000000000f7   pt2=b'\x83~B\xdc\x0feK5\x16\xc7\xa16\xcc\x0ciB'
idx=014   i=040   is2=00000000000000000000000000002af7   pt2=b'\x83~B\xdc\x0feK5\x16\xc7\xa16\xcc\x0cCB'
idx=013   i=080   is2=00000000000000000000000000532af7   pt2=b'\x83~B\xdc\x0feK5\x16\xc7\xa16\xcc_CB'
idx=012   i=155   is2=0000000000000000000000009f532af7   pt2=b'\x83~B\xdc\x0feK5\x16\xc7\xa16S_CB'
idx=011   i=118   is2=0000000000000000000000739f532af7   pt2=b'\x83~B\xdc\x0feK5\x16\xc7\xa1ES_CB'
idx=010   i=230   is2=00000000000000000000e0739f532af7   pt2=b'\x83~B\xdc\x0feK5\x16\xc7AES_CB'
idx=009   i=159   is2=00000000000000000098e0739f532af7   pt2=b'\x83~B\xdc\x0feK5\x16_AES_CB'
idx=008   i=117   is2=00000000000000007d98e0739f532af7   pt2=b'\x83~B\xdc\x0feK5k_AES_CB'
idx=007   i=095   is2=00000000000000567d98e0739f532af7   pt2=b'\x83~B\xdc\x0feKck_AES_CB'
idx=006   i=117   is2=0000000000007f567d98e0739f532af7   pt2=b'\x83~B\xdc\x0fe4ck_AES_CB'
idx=005   i=026   is2=0000000000117f567d98e0739f532af7   pt2=b'\x83~B\xdc\x0ft4ck_AES_CB'
idx=004   i=119   is2=000000007b117f567d98e0739f532af7   pt2=b'\x83~B\xdctt4ck_AES_CB'
idx=003   i=229   is2=000000e87b117f567d98e0739f532af7   pt2=b'\x83~B4tt4ck_AES_CB'
idx=002   i=019   is2=00001de87b117f567d98e0739f532af7   pt2=b'\x83~_4tt4ck_AES_CB'
idx=001   i=066   is2=004d1de87b117f567d98e0739f532af7   pt2=b'\x833_4tt4ck_AES_CB'
idx=000   i=255   is2=ef4d1de87b117f567d98e0739f532af7   pt2=b'l3_4tt4ck_AES_CB'
flag: l3_4tt4ck_AES_CBC_16byt3s}   b'l3_4tt4ck_AES_CBC_16byt3s}\x06\x06\x06\x06\x06\x06'

idx=015   i=040   is2=00000000000000000000000000000029   pt2=b'\xd8\xe3\xea{\x83\xe8\xda\xe1\xbd\xef\xf3\xa4*\xef\xbac'
idx=014   i=140   is2=00000000000000000000000000008e29   pt2=b'\xd8\xe3\xea{\x83\xe8\xda\xe1\xbd\xef\xf3\xa4*\xef4c'
idx=013   i=158   is2=000000000000000000000000009d8e29   pt2=b'\xd8\xe3\xea{\x83\xe8\xda\xe1\xbd\xef\xf3\xa4*r4c'
idx=012   i=030   is2=0000000000000000000000001a9d8e29   pt2=b'\xd8\xe3\xea{\x83\xe8\xda\xe1\xbd\xef\xf3\xa40r4c'
idx=011   i=254   is2=0000000000000000000000fb1a9d8e29   pt2=b'\xd8\xe3\xea{\x83\xe8\xda\xe1\xbd\xef\xf3_0r4c'
idx=010   i=146   is2=0000000000000000000094fb1a9d8e29   pt2=b'\xd8\xe3\xea{\x83\xe8\xda\xe1\xbd\xefg_0r4c'
idx=009   i=134   is2=0000000000000000008194fb1a9d8e29   pt2=b'\xd8\xe3\xea{\x83\xe8\xda\xe1\xbdng_0r4c'
idx=008   i=132   is2=00000000000000008c8194fb1a9d8e29   pt2=b'\xd8\xe3\xea{\x83\xe8\xda\xe11ng_0r4c'
idx=007   i=140   is2=00000000000000858c8194fb1a9d8e29   pt2=b'\xd8\xe3\xea{\x83\xe8\xdad1ng_0r4c'
idx=006   i=180   is2=000000000000be858c8194fb1a9d8e29   pt2=b'\xd8\xe3\xea{\x83\xe8dd1ng_0r4c'
idx=005   i=215   is2=0000000000dcbe858c8194fb1a9d8e29   pt2=b'\xd8\xe3\xea{\x834dd1ng_0r4c'
idx=004   i=223   is2=00000000d3dcbe858c8194fb1a9d8e29   pt2=b'\xd8\xe3\xea{P4dd1ng_0r4c'
idx=003   i=041   is2=00000024d3dcbe858c8194fb1a9d8e29   pt2=b'\xd8\xe3\xea_P4dd1ng_0r4c'
idx=002   i=157   is2=00009324d3dcbe858c8194fb1a9d8e29   pt2=b'\xd8\xe3y_P4dd1ng_0r4c'
idx=001   i=139   is2=00849324d3dcbe858c8194fb1a9d8e29   pt2=b'\xd8gy_P4dd1ng_0r4c'
idx=000   i=173   is2=bd849324d3dcbe858c8194fb1a9d8e29   pt2=b'egy_P4dd1ng_0r4c'
flag: egy_P4dd1ng_0r4cl3_4tt4ck_AES_CBC_16byt3s}   b'egy_P4dd1ng_0r4cl3_4tt4ck_AES_CBC_16byt3s}\x06\x06\x06\x06\x06\x06'

idx=015   i=151   is2=00000000000000000000000000000096   pt2=b'\xfd\xcdc\xa1K\xb2S\x150\xc1\x9b\xb6\xcb\x9a\xc6t'
idx=014   i=165   is2=0000000000000000000000000000a796   pt2=b'\xfd\xcdc\xa1K\xb2S\x150\xc1\x9b\xb6\xcb\x9aat'
idx=013   i=235   is2=00000000000000000000000000e8a796   pt2=b'\xfd\xcdc\xa1K\xb2S\x150\xc1\x9b\xb6\xcbrat'
idx=012   i=187   is2=000000000000000000000000bfe8a796   pt2=b'\xfd\xcdc\xa1K\xb2S\x150\xc1\x9b\xb6trat'
idx=011   i=224   is2=0000000000000000000000e5bfe8a796   pt2=b'\xfd\xcdc\xa1K\xb2S\x150\xc1\x9bStrat'
idx=010   i=248   is2=00000000000000000000fee5bfe8a796   pt2=b'\xfd\xcdc\xa1K\xb2S\x150\xc1eStrat'
idx=009   i=179   is2=000000000000000000b4fee5bfe8a796   pt2=b'\xfd\xcdc\xa1K\xb2S\x150ueStrat'
idx=008   i=084   is2=00000000000000005cb4fee5bfe8a796   pt2=b'\xfd\xcdc\xa1K\xb2S\x15lueStrat'
idx=007   i=094   is2=00000000000000575cb4fee5bfe8a796   pt2=b'\xfd\xcdc\xa1K\xb2SBlueStrat'
idx=006   i=061   is2=00000000000037575cb4fee5bfe8a796   pt2=b'\xfd\xcdc\xa1K\xb2dBlueStrat'
idx=005   i=220   is2=0000000000d737575cb4fee5bfe8a796   pt2=b'\xfd\xcdc\xa1KedBlueStrat'
idx=004   i=021   is2=0000000019d737575cb4fee5bfe8a796   pt2=b'\xfd\xcdc\xa1RedBlueStrat'
idx=003   i=215   is2=000000da19d737575cb4fee5bfe8a796   pt2=b'\xfd\xcdc{RedBlueStrat'
idx=002   i=043   is2=000025da19d737575cb4fee5bfe8a796   pt2=b'\xfd\xcdF{RedBlueStrat'
idx=001   i=150   is2=009925da19d737575cb4fee5bfe8a796   pt2=b'\xfdTF{RedBlueStrat'
idx=000   i=174   is2=be9925da19d737575cb4fee5bfe8a796   pt2=b'CTF{RedBlueStrat'
flag: CTF{RedBlueStrategy_P4dd1ng_0r4cl3_4tt4ck_AES_CBC_16byt3s}   b'CTF{RedBlueStrategy_P4dd1ng_0r4cl3_4tt4ck_AES_CBC_16byt3s}\x06\x06\x06\x06\x06\x06'

Было известно зашифрованное сообщение fdcd63a14bb2531530c19bb6cb9ac6e2d8e3ea7b83e8dae1bdeff3a42aefba4a837e42dc0f654b3516c7a136cc0c69b5414267dda54386231b58b5bed61fb201468ed73a20e435dec7afb1ac46364603

После применения Padding Oracle Attack смогли его расшифровать и получить флаг CTF{RedBlueStrategy_P4dd1ng_0r4cl3_4tt4ck_AES_CBC_16byt3s}.

Задача решена!

5 Padding Oracle Attack - Encrypt

Почти все рассужения при поиске pt и поиске ct совпадают, так как базовая задача - найти is.
А pt и ct симметричны относительно is:

pt = ct xor is
ct = pt xor is

Алгоритм генерации всех блоков ct:

Создаем случайный ciphertext размером, равным plaintext (без учета iv)
Для каждой смежной пары блоков ct, начиная с последнего
- Находим is2 последнего блока
- Вычисляем ct1 = pt2 xor is2
- Обновляем блок ct1 в исходном ciphertext
- Отбрасываем последний блок
ciphertext содержит искомый шифр, при расшифровании которого получится нужный plaintext

5.1 Пример

Реализуем алгоритм и проверим его работу, решив задачу AES-CBC-POA-Encrypt.
https://pwn.college/intro-to-cybersecurity/cryptography/

Есть dispatcher, который зашифровывает сообщение

dispatcher.py

#!/run/workspace/bin/python3

import os

from base64 import b64encode
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Random import get_random_bytes

key = open("/home/hacker/challenge/.key", "rb").read()
cipher = AES.new(key=key, mode=AES.MODE_CBC)
ciphertext = cipher.iv + cipher.encrypt(pad(b"sleep", cipher.block_size))

print(f"TASK: {b64encode(ciphertext).decode()}")

Есть worker, который расшифровывает сообщение

worker.py

#!/run/workspace/bin/python3

from base64 import b64decode
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Random import get_random_bytes

import time
import sys

key = open("/home/hacker/challenge/.key", "rb").read()

while line := sys.stdin.readline():
    if not line.startswith("TASK: "):
        continue
    data = b64decode(line.split()[1])
    iv, ciphertext = data[:16], data[16:]

    cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
    plaintext = unpad(cipher.decrypt(ciphertext), cipher.block_size).decode('latin1')

    if plaintext == "sleep":
        print("Sleeping!")
        time.sleep(1)
    elif plaintext == "please give me the flag, kind worker process!":
        print("Victory! Your flag:")
        print(open("/home/hacker/challenge/flag").read())
    else:
        print("Unknown command!")

dispatcher.py и worker.py незначительно отличаются от предыдущей задачи.

Основное отличие, что нам не нужен dispatcher. Так как вы будет сами генерировать ciphertext в зависимости от Intermediate state каждого блока и сообшения, которое хотим получить после расшифровывания.

Разбиваем исходное зашифрованное сообщение на блоки.
Последовательно генерируем ciphertext блоки по порядку от последнего к первому.

blocks.py

plaintext = b"please give me the flag, kind worker process!"
plaintext = pad(plaintext, 16)

ct = bytearray(bytearray(os.urandom(16+len(plaintext))))
print(f"ct: {ct.hex()}")

for i in range(len(ct) - 16 - 16, -1, -16):
    ct_prefix, ct1, ct2, ct_suffix = ct[:i], ct[i:i+16], ct[i+16:i+16+16], ct[i+16+16:]
    is2 = bytearray(b"\x00" * 16)

    is2 = aes_pao_dfs(ct_prefix, ct1, ct2, 16-1, is2, check_pad)
    if is2 == None:
        print("NOT FOUND")
        break

    ct = ct_prefix + xor(plaintext[i:i+16], is2) + ct2 + ct_suffix
    print(f"ct: {ct.hex()}")
    check_pad(ct, True)

Полное решение:

main.py

#!/usr/bin/python3

import subprocess
import base64
import os
from datetime import datetime
from Crypto.Util.Padding import pad, unpad


worker_cmd = ["/home/hacker/challenge/worker"]


def xor(a, b):
    return bytes(x ^ y for x, y in zip(a, b))


def check_pad(ct, isprint=False):
    text = f"TASK: {base64.b64encode(ct).decode()}\n"
    result = subprocess.run(worker_cmd, input=text, capture_output=True, text=True)
    if isprint and result.returncode == 0:
        print(result.stdout)
    return result.returncode == 0


def aes_pao_dfs(ct_prefix, ct1, ct2, idx, is2, check):
    if idx == -1:
        return is2

    if idx < 0 or idx > 15:
        return None

    ct1_new = ct1[:]
    for i in range(idx+1, 16):
        ct1_new[i] = is2[i] ^ (16 - idx)

    for i in range(256):
        ct1_new[idx] = i

        if not check(ct_prefix + ct1_new + ct2):
            continue

        is2 = is2[:]
        is2[idx] = ct1_new[idx] ^ (16 - idx)

        print(f"idx={idx:03}   i={i:03}   is2={is2.hex()}   pt2={xor(ct1, is2).hex()}", flush=True)

        res = aes_pao_dfs(ct_prefix, ct1, ct2, idx - 1, is2, check)
        if res != None:
            return res
    
    return None



plaintext = b"please give me the flag, kind worker process!"
plaintext = pad(plaintext, 16)

ct = bytearray(bytearray(os.urandom(16+len(plaintext))))
print(f"ct: {ct.hex()}")

for i in range(len(ct) - 16 - 16, -1, -16):
    ct_prefix, ct1, ct2, ct_suffix = ct[:i], ct[i:i+16], ct[i+16:i+16+16], ct[i+16+16:]
    is2 = bytearray(b"\x00" * 16)

    is2 = aes_pao_dfs(ct_prefix, ct1, ct2, 16-1, is2, check_pad)
    if is2 == None:
        print("NOT FOUND")
        break

    ct = ct_prefix + xor(plaintext[i:i+16], is2) + ct2 + ct_suffix
    print(f"ct: {ct.hex()}")
    check_pad(ct, True)

Запускаем программу и ждем пока не будет расшифрованно сообщение полностью:

output.txt

[amyasnikov@ubuntu:~]$ python3 ./main.py
ct: 7f23a74329096543f82e02e91fb2e94b2915ff85cd908857803cbc5b7e501f5b16c3358b69f2e0487ce66d1f9252a670ca2f0dca4810b08704e27c32fe4ffbcb
idx=015   i=009   is2=00000000000000000000000000000008   pt2=16c3358b69f2e0487ce66d1f9252a678
idx=014   i=157   is2=00000000000000000000000000009f08   pt2=16c3358b69f2e0487ce66d1f92523978
idx=013   i=079   is2=000000000000000000000000004c9f08   pt2=16c3358b69f2e0487ce66d1f921e3978
idx=012   i=040   is2=0000000000000000000000002c4c9f08   pt2=16c3358b69f2e0487ce66d1fbe1e3978
idx=011   i=078   is2=00000000000000000000004b2c4c9f08   pt2=16c3358b69f2e0487ce66d54be1e3978
idx=010   i=164   is2=00000000000000000000a24b2c4c9f08   pt2=16c3358b69f2e0487ce6cf54be1e3978
idx=009   i=207   is2=000000000000000000c8a24b2c4c9f08   pt2=16c3358b69f2e0487c2ecf54be1e3978
idx=008   i=039   is2=00000000000000002fc8a24b2c4c9f08   pt2=16c3358b69f2e048532ecf54be1e3978
idx=007   i=099   is2=000000000000006a2fc8a24b2c4c9f08   pt2=16c3358b69f2e022532ecf54be1e3978
idx=006   i=075   is2=000000000000416a2fc8a24b2c4c9f08   pt2=16c3358b69f2a122532ecf54be1e3978
idx=005   i=049   is2=00000000003a416a2fc8a24b2c4c9f08   pt2=16c3358b69c8a122532ecf54be1e3978
idx=004   i=222   is2=00000000d23a416a2fc8a24b2c4c9f08   pt2=16c3358bbbc8a122532ecf54be1e3978
idx=003   i=117   is2=00000078d23a416a2fc8a24b2c4c9f08   pt2=16c335f3bbc8a122532ecf54be1e3978
idx=002   i=241   is2=0000ff78d23a416a2fc8a24b2c4c9f08   pt2=16c3caf3bbc8a122532ecf54be1e3978
idx=001   i=162   is2=00adff78d23a416a2fc8a24b2c4c9f08   pt2=166ecaf3bbc8a122532ecf54be1e3978
idx=000   i=110   is2=7eadff78d23a416a2fc8a24b2c4c9f08   pt2=686ecaf3bbc8a122532ecf54be1e3978
ct: 7f23a74329096543f82e02e91fb2e94b2915ff85cd908857803cbc5b7e501f5b0cc69a0af24a33054cadd1380d4f9c0bca2f0dca4810b08704e27c32fe4ffbcb
Unknown command!

idx=015   i=005   is2=00000000000000000000000000000004   pt2=2915ff85cd908857803cbc5b7e501f5f
idx=014   i=174   is2=0000000000000000000000000000ac04   pt2=2915ff85cd908857803cbc5b7e50b35f
idx=013   i=152   is2=000000000000000000000000009bac04   pt2=2915ff85cd908857803cbc5b7ecbb35f
idx=012   i=052   is2=000000000000000000000000309bac04   pt2=2915ff85cd908857803cbc5b4ecbb35f
idx=011   i=166   is2=0000000000000000000000a3309bac04   pt2=2915ff85cd908857803cbcf84ecbb35f
idx=010   i=137   is2=000000000000000000008fa3309bac04   pt2=2915ff85cd908857803c33f84ecbb35f
idx=009   i=016   is2=000000000000000000178fa3309bac04   pt2=2915ff85cd908857802b33f84ecbb35f
idx=008   i=188   is2=0000000000000000b4178fa3309bac04   pt2=2915ff85cd908857342b33f84ecbb35f
idx=007   i=185   is2=00000000000000b0b4178fa3309bac04   pt2=2915ff85cd9088e7342b33f84ecbb35f
idx=006   i=016   is2=0000000000001ab0b4178fa3309bac04   pt2=2915ff85cd9092e7342b33f84ecbb35f
idx=005   i=006   is2=00000000000d1ab0b4178fa3309bac04   pt2=2915ff85cd9d92e7342b33f84ecbb35f
idx=004   i=116   is2=00000000780d1ab0b4178fa3309bac04   pt2=2915ff85b59d92e7342b33f84ecbb35f
idx=003   i=204   is2=000000c1780d1ab0b4178fa3309bac04   pt2=2915ff44b59d92e7342b33f84ecbb35f
idx=002   i=049   is2=00003fc1780d1ab0b4178fa3309bac04   pt2=2915c044b59d92e7342b33f84ecbb35f
idx=001   i=121   is2=00763fc1780d1ab0b4178fa3309bac04   pt2=2963c044b59d92e7342b33f84ecbb35f
idx=000   i=033   is2=31763fc1780d1ab0b4178fa3309bac04   pt2=1863c044b59d92e7342b33f84ecbb35f
ct: 7f23a74329096543f82e02e91fb2e94b59131fa7146c7d9c947ce6cd54bbdb6b0cc69a0af24a33054cadd1380d4f9c0bca2f0dca4810b08704e27c32fe4ffbcb
Unknown command!

idx=015   i=089   is2=00000000000000000000000000000058   pt2=7f23a74329096543f82e02e91fb2e913
idx=014   i=073   is2=00000000000000000000000000004b58   pt2=7f23a74329096543f82e02e91fb2a213
idx=013   i=102   is2=00000000000000000000000000654b58   pt2=7f23a74329096543f82e02e91fd7a213
idx=012   i=193   is2=000000000000000000000000c5654b58   pt2=7f23a74329096543f82e02e9dad7a213
idx=011   i=107   is2=00000000000000000000006ec5654b58   pt2=7f23a74329096543f82e0287dad7a213
idx=010   i=181   is2=00000000000000000000b36ec5654b58   pt2=7f23a74329096543f82eb187dad7a213
idx=009   i=210   is2=000000000000000000d5b36ec5654b58   pt2=7f23a74329096543f8fbb187dad7a213
idx=008   i=033   is2=000000000000000029d5b36ec5654b58   pt2=7f23a74329096543d1fbb187dad7a213
idx=007   i=021   is2=000000000000001c29d5b36ec5654b58   pt2=7f23a7432909655fd1fbb187dad7a213
idx=006   i=034   is2=000000000000281c29d5b36ec5654b58   pt2=7f23a74329094d5fd1fbb187dad7a213
idx=005   i=052   is2=00000000003f281c29d5b36ec5654b58   pt2=7f23a74329364d5fd1fbb187dad7a213
idx=004   i=019   is2=000000001f3f281c29d5b36ec5654b58   pt2=7f23a74336364d5fd1fbb187dad7a213
idx=003   i=152   is2=000000951f3f281c29d5b36ec5654b58   pt2=7f23a7d636364d5fd1fbb187dad7a213
idx=002   i=191   is2=0000b1951f3f281c29d5b36ec5654b58   pt2=7f2316d636364d5fd1fbb187dad7a213
idx=001   i=005   is2=000ab1951f3f281c29d5b36ec5654b58   pt2=7f2916d636364d5fd1fbb187dad7a213
idx=000   i=145   is2=810ab1951f3f281c29d5b36ec5654b58   pt2=fe2916d636364d5fd1fbb187dad7a213
ct: f166d4f46c5a087b40a3d64ea8006b2c59131fa7146c7d9c947ce6cd54bbdb6b0cc69a0af24a33054cadd1380d4f9c0bca2f0dca4810b08704e27c32fe4ffbcb
Victory! Your flag:
CTF{RedBlueStrategy_P4dd1ng_0r4cl3_4tt4ck_AES_CBC_16byt3s}

Для сообщения "please give me the flag, kind worker process!" сгенерировали зашифрованное сообщение
f166d4f46c5a087b40a3d64ea8006b2c59131fa7146c7d9c947ce6cd54bbdb6b0cc69a0af24a33054cadd1380d4f9c0bca2f0dca4810b08704e27c32fe4ffbcb без знания ключа.

После применения Padding Oracle Attack смогли зашифровать сообщение и получить флаг CTF{RedBlueStrategy_P4dd1ng_0r4cl3_4tt4ck_AES_CBC_16byt3s}.

Задача решена!

6 Выводы

Очень интересная атака.
По сути использование pad, unpad делают еспользование AES-CBC полностью незащищенным

Содержание

AES-CBC - Padding Oracle Attack

1 AES-CBC - Padding Oracle Attack

2 Что нужно чтобы воспользоваться Padding Oracle Attack?

3 Как работает паддинг и для чего он нужен

3.1 Как работает PKCS#7

4 Padding Oracle Attack - Decrypt

AES - CBC

4.1 Алгоритм

4.2 Пример

5 Padding Oracle Attack - Encrypt

5.1 Пример

6 Выводы

Похожее