1 of 25

Padding Oracle

Автор Сценария:

Кирилл Шипулин

MUCH WOW

SUCH CRYPTO

VERY EXCITED

SO PADDING

TOO CBC

VERY PKCS

VERY ORACLE

MANY CLEARTEXT

2 of 25

Padding Oracle - Chosen ciphertext attack

1

SEND CIPHERTEXT #1

2

ERROR / SUCCESS

3

MODIFY CIPHERTEXT #1

SEND CIPHERTEXT #2

3 of 25

Padding дополняет данные до размера блока

В режиме блочного шифрования (ECB, CBC) данные дополняются до размера блока

8 bytes

PKCS #7

Атака в первую очередь связана с тем, как именно данные подготавливаются для блочного шифра, например AES или DES. Блочные шифры работают с множеством небольших блоков данных, обычно 8 или 16 байт. Перед тем, как открытый текст будет подвергнуть шифрованию, его дополняют с конца пустыми данными, именуемыми пэддингом, чтобы итоговый размер данных стал кратен размеру блока.

В данном случае, слово HELLO дополняется тремя байтами справа, чтобы размер данных стал кратен 8и байтам. Каждый байт имеет значение равное длинне педдинга, то есть 3. Такая схема называется PKCS7.

4 of 25

Неправильный Padding приводит к ошибке

PKCS7 padding is incorrect

500 Internal Server Error

etc...

5 of 25

Последнее условие - режим CBC

6 of 25

Режим ECB не всегда вам подходит

7 of 25

В CBC можем изменять байты паддинга

Поэтому существуют разные режимы для смешивания блоков. В режиме CBC шифротекст предыдущего блока ксорится с блоком открытого текста следующего. Ксор это ассоциативная операция сложения по модулю два, то есть ксор самого себя дает ноль.

То есть последний байт из 2го блока на картинке напрямую влияет на последний байт открытого текста 3го блока.

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

8 of 25

CORRECT PADDING

DECRYPTION

D ⊕ 0xD1	0x03

9 of 25

STILL CORRECT

DECRYPTION

D ⊕ 0xD1	0x03
D ⊕ 0xD2	0x01

10 of 25

Мы не знаем, какой Padding имеет шифротекст

Перебираем байт предыдущего блока

Y = 0x00..0xFF

Correct Padding

Z = 0x01

А в чем же атака? Дело в том, что на примерах с предыдущих слайдов мы имели информацию об открытом текста и могли предугадать его поведение. Но на практике, мы не имеем о нем никакого знания - ни его точную длину, ни одного его байта. Что нам в таком случае делать? - Перебирать последний байт предыдущего блока, ведь существует только одно значение из 256 вариантов, при котором байт педдинга Z окажется равным 0x01, то есть валидным пэддингом. Во всех иных случаях мы получим ошибку при проверке педдинга.

11 of 25

Мы не знаем, какой Padding имеет шифротекст

Перебираем байт предыдущего блока

Y1, Z1 = 0x01

Z = (Y1 ⊕ Z1) ⊕ Y

Z = (Y1 ⊕ 1) ⊕ Y

12 of 25

Пример

Перебираем красный байт, пока не исчезнет ошибка паддинга

13 of 25

Пример

Перебираем красный байт, пока не исчезнет ошибка паддинга

14 of 25

Пример

X = (Y1 ⊕ 1) ⊕ Y = 0x3B ⊕ 1 ⊕ 0x3D = 0x07

15 of 25

Далее так же перебираем следующий байт

XX = Y1 ⊕ Z1 ⊕ 0x02

Y2, Z2 = 0x02

16 of 25

Раскрываем весь текст последнего блока

17 of 25

Затем двигаемся на блок влево

18 of 25

Пример: Apache Axis2 XML Encryption

IV C1 C2 ...

Байты с конца “съедаются” без проверки

Берем IV, C1

Перебираем правый байт IV

Получаем 16 без ошибки

В 2011 году было найдено, что т.н. стандарт XML Encryption был уязвим к атаке Padding Oracle. Несмотря на то, что байты педдинга не проверялись, а просто съедались, атаку эксплуатировали интересным способом с учетом того, что внутри зашифрованных данных хранился ещё один XML.

Атакуем сперва первый первый блок шифротекста C1. Вектор инициализации будет ксориться с ним после дешифрования и перебирая последний байт IV мы перебираем байт педдинга. Т.к. байты просто съедаются, правильных с точки зрения педдинга комбинаций будет 16. И одна определенная из этих комбинаций дает педдинг 0x10.

19 of 25

Пример: Apache Axis2 XML Encryption

Затем идем на блок вправо

IV = C1

C1 = C2

Перебираем байты в IV чтобы найти ошибки

xxxx < xxxxxxxxxxx - Error

Как раскрыть остальные байты, если педдинг просто съедается?

Воспользуемся тем, что ошибка вернется в ответ не только когда у нас длина педдинга > 16 или < 1, но и когда XML внутри неправильный. Например есть открывающийся тег, но нет закрывающегося.

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

Как только раскрыли первый блок C1, идем дальше. Тогда IV становится блок C1, а работаем мы уже с C2.

20 of 25

Другой формат Padding тоже уязвим?

ISO 10126

ANSI X.923

ISO/IEC 7816-4

21 of 25

Другой формат Padding тоже уязвим?

ANSI X.923

Как и в PKCS7,5 - все байты паддинга проверяются.

Атакуем также

22 of 25

Другой формат Padding тоже уязвим?

ISO/IEC 7816-4

Как и в PKCS7,5 - все байты паддинга проверяются.

Атакуем также

23 of 25

Другой формат Padding тоже уязвим?

ISO 10126

Воспользоваться знанием о формате сообщения после дешифрования

(XML Encryption)

Двигать байты вправо, если можем шифровать “свои” данные

Самый интересный это конечно верхний ISO формат. Тут байты не проверяются а просто съедаются по значению крайнего правого. Атаковать его сложнее.

Во первых, можно перебрать этот самый крайний байт и мы получим 16 из 256 итераций без ошибки педдинга. Вычислить потом длинну педдинга не составит труда, потому что 1 из этих 16 итераций будет отличаться от остальных старшим 4м битом и педдинг при нем будет равен длине блока 16.

Что потом делать с остальными байтами? Вообще говоря, ничего мы не можем с ними сделать без дополнительных условий. Например, как с атакой на XML Encryption, мы можем воспользоваться форматом данных который ожидается после дешифровки сообщения. Напомню, что с XML мы играли на символе <, который также давал нам ошибку.

И ещё один способ я применил, играя в CTF. Там у меня была возможность подставлять данные в одно из полей, которое потом шифровалось вместе с остальными. Я подавал строки все длиннее и длиннее пока не добавился один блок, второй и так далее. Байты там тоже съедались, как и с этим педдингом. Я просто придумал двигать байты вправо по одному и отгадывать всегда крайний правый байт блока.

24 of 25

Encrypt-then-MAC поможет защититься

MAC-then-Encrypt - Так делает TLS
Encrypt-and-MAC - Так делает SSH
Encrypt-then-MAC - Так советуют делать

Холиварный достаточно вопрос

Атаку разобрали, примеры посмотрели, а как защищаться то?

Всего навсего давайте подписывать наши шифротексты сигнатурами. Например брать от шифротекста и ключа хеш и добавлять в конец шифротекста. Сначала шифруем, потом считаем хеш. А при дешифровке проверяем пришедший шифротекст на целостность. Message Authentication Code поможет нам заметить подмену шифротекста и исключить атакую Padding Oracle. Вообще говоря, какой именно механизм из трех на слайде использовать - это достаточно холиварный вопрос, но большинство исследователей склоняются к схеме Encrypt-then-MAC. Главное теперь - правильно её реализовать.

25 of 25

Вопросы

kirill_wow

MUCH WOW

SUCH CRYPTO

VERY EXCITED

SO PADDING

TOO CBC

VERY PKCS

VERY ORACLE

MANY CLEARTEXT