Все мы знаем, что не следует самостоятельно реализовывать криптографические примитивы. Мы также в курсе, что даже если мы хитрым образом развернем порядок букв во всех словах сообщения, сдвинем каждую букву по алфавиту на 5 позиций и разбавим текст случайными фразами, чтобы сбить атакующих с пути, наш замечательный шифр скорее всего вскроет любой мало-мальски знакомый с криптографией человек (а в данном случае с задачей справится и в меру умный 12-летний подросток).
Однако, и внедрение известных и стойких алгоритмов не является панацеей. Даже если вы возьмете готовую реализацию данного алгоритма, сгенерируете секретные ключи согласно всем требованиям и тому подобное, все-равно вы останетесь потенциально подвержены некоторым весьма эффективным атакам. Опытному злоумышленнику достаточно крошечной, казалось бы, совершенно несвязанной с криптосистемой толики информации, чтобы обойти шифрование.
Мой посыл не в том, что убедить вас отказаться от самостоятельного использования криптографических средств или пойти и нанять консультанта с зарплатой от $1000 в час всякий раз когда вы задумываетесь о шифровании.
Частично я веду к тому, что вам никогда не следует расслабляться, всегда нужно быть начеку, изыскивая пути, которые злоумышленник может использовать для получения дополнительной информации о вашей системе, а частично к тому, что Padding Oracle Attack является крутой демонстрацией всего этого. Итак, начнем.
CBC, или режим сцепления блоков шифротекста, это один из режимов симметричного блочного шифрования с использованием механизма обратной связи. Это означает, что при шифровании очередной блок открытого текста проходит через блочный алгортим шифрования, а также дополнительно изменяется с использованием результата шифрования предыдущего блока.
Так что, если мы шифруем предложение:
мы получим результат шифрования для каждого блока из 16 байт, причем последний блок открытого текста будет специальным образом дополнен (но об этом далее).
В CBC каждый блок открытого текста складывается побитово по модулю два (xor) с предыдущим блоком шифротекста перед тем как поступить на вход алгоритму шифрования. Данная взаимозависимость блоков означает, что каждый блок шифротекста зависит от каждого блока открытого текста, который был обработан к данному моменту. Причем изменение любого байта открытого текста приведет к изменению всех последующих байт шифротекста (лавинный эффект, ага). Согласно Википедии — CBC является «одним из двух режимов симметричного блочного шифрования, рекомендованных Нилом Фергюсоном и Брюсом Шнайером».
Предпочтительным методом дополнения блоков шифротекста, является PKCS7. В нем значение каждого дополняемого байта устанавливается равным количеству дополняемых байт. Так если мы имеем блок из 12 символов, он будет дополнен четырьмя байтами [04, 04, 04, 04] до стандартного размера блока в 16 байт. Если блок имеет размер в 15 байт, он будет дополнен одним байтом [01]. Если блок имеет размер ровно в 16 байт, мы добавляем новый блок состоящий из [16]*16. (подробнее — https://en.wikipedia.org/wiki/Padding_(cryptography)#PKCS7)
Солгасно данному методу, последний блок расшифрованного открытого текста не может заканчиваться, например, на [..., 13, 06, 05]. А значит, что и оригинальный шифротекст является неверным, потому как не существует допустимых открытых текстов, которые могли бы быть преобразованы в такой шифротекст.
Оказывается, что знания факта, получается ли при расшифровке шифротекста открытый текст с корректным дополнением, достаточно атакующему для проведения успешной атаки на шифрование в режиме CBC. Если мы можем подавать какому-то сервису шифротексты, а он будет возвращать нам информацию, корректно ли дополнение — мы сможем вскрыть ЛЮБОЙ шифротекст.
Так что ошибкой, которой достаточно, чтобы обрушить ваше шифрование, может являться некоторый API, который будет возвращать код 200, если поданный нами шифротекст расшифровывается во что-то с корректным дополнением, и код 500, если нет.
Это не маловероятная ситуация. Например, Ruby OpenSSL подвержен данной проблеме. Достаточно использовать пример кода из официальной документации (http://www.ruby-doc.org/stdlib-1.9.3/libdoc/openssl/rdoc/OpenSSL/Cipher.html#documentation):
Данный код выдает OpenSSL::Cipher::CipherError: bad decrypt, который, если его не перехватить, вернет ответ с ошибкой 500.
Положим, что мы украли шифротекст. Если мы можем посылать шифротексты и определять расшифровываются ли они в сообщения с корректным дополнением, как же нам использовать это для того, чтобы полностью расшифровать украденный шифротекст?
Повторим еще раз — в CBC режиме каждый блок открытого текста побитово складывается по модулю два (XOR) с предыдущим блоком шифротекста перед тем как пойти на вход шифру. При расшифровании каждый шифротекст проходит через дешифратор и затем XOR'ится с предыдущим блоком шифротекста, чтобы произвести открытый текст.
Атака работает через вычисление «промежуточного состояния» процедуры расшифрования (смотри схему) для каждого блока шифротекста. Это состояние блока шифротекста после расшифрования блочным алгоритмом, но ДО процедуры XOR с предыдущим блоком шифротекста. Мы будем находить это состояние, поднимаясь снизу от открытого текста, вместо того, чтобы спускаться вниз через блочный шифр. Также мы вообще не будем волноваться на счет ключа шифрования или алгоритма блочного шифрования.
Почему же данное промежуточное состояние так важно? Заметим:
Мы уже знаем C1 т.к. это часть шифротекста, который мы имеем. Так что если мы найдем I2, мы можем легко найти P2 и расшифровать сообщение.
Вспомним, что мы можем подавать на вход системе любой шифротекст, и сервер ответит нам корректное ли дополнение получается после расшифрования. Мы используем данный факт, подавая на вход C1' + C2, где C1' — специальным образом сформированный нами блок шифротекста, а C2 — это блок, который мы хотим расшифровать. Под обозначением C1' + C2 мы понимаем простую конкатенацию (то-есть, «склеивание» блоков). Обозначим результат расшифрования как P'2.
Начнем с того, что мы заполним C1'[1..15] случайными байтами, а C1'[16] заполним нулем (0x00). Теперь подадим C1' + C2 серверу. Если сервер ответит, что дополнение получилось корректное, то мы можем быть уверены (с большой вероятностью), что P2'[16] равно 0x01 (т.к. дополнение корректно). Если сервер отвечает ошибкой — посылаем сообщение с C1'[16], установленным в 0x01, затем в 0x02 и.т.д. пока не получим нужный нам ответ.
Теперь положим, что сервер вернул ответ 200 при C1'[16] = 94.
Ура! Мы получили финальный байт промежуточного состояния. Т.к. C2 взят из реального шифротекста, то I2 тоже идентичен реальному. Поэтому, мы можем расшифровать последний байт настоящего открытого текста:
Мы подаем на вход C1'[16] = C1[16] и получаем последний байт реального открытого текста. На этом этапе, мы нашли всего-лишь заполнитель, так что придется проделать еще несколько итераций данного процесса, пока мы не обнаружим что-нибудь интересное.
Мы нашли последний байт прокручиванием C1' до получения корректного дополнения. При этом мы можем сделать заключение, что последний байт P'2 равен 0x01. Затем используя P2'[16] и C1'[16], находим I2[16]. Продолжая этот процесс, находим оставшиеся байты I2 и расшифровываем весь блок шифротекста.
Заполняем C1'[1..14] случайными байтами, C1'[15] устанавливаем в 0x00, а C1'[16] таким, чтобы получить P2'[16] == 0x02:
Теперь мы можем быть уверены, что P2' будет заканчиваться на 0x02, и поэтому единственный вариант, при котором P2' будет иметь корректное дополнение — если P2[16] == 0x02. Мы будем прокручивать C1'[15], пока сервер не выдаст нам код 200. Предположим, что это случилось при C1'[15] == 106. Проделываем опять то, что мы уже умеем:
И вуаля! Мы знаем предпоследний байт I2. Поэтому можем найти предпоследний байт P2, как мы это уже проделывали ранее:
И так далее для всех 16 байтов C2.
Форма блоков шифротекста зависит только от них самих и предшествующих блоков. Так что мы можем применить вышеприведенный алгоритм к каждому блоку шифротекста (отдельно от первого). Первый блок будет зашифрован с использованием вектора инициализации (IV), а сам IV выбран случайно при процедуре зашифрования. До тех пор, пока мы не узнаем IV, мы не сможем расшифровать первый блок, и нет ничего, что тут можно придумать, кроме глупого перебора очевидных значений [0,0,0,...] для IV и просмотра, получается ли какой-нибудь разумный открытый текст. И делать так в надежде, что первые 16 байт будут чем-нибудь вроде "Дорогой Евгений!".
Это все и есть Padding Oracle Attack.
Вот почему все, что связано с криптографией пугает.
Мы знаем, что не следует самостоятельно реализовывать криптографические примитивы, и что мы строим систему на чем-то уже изобретенном. Легко почувствовать себя расслабленно, когда мы прячемся за стойким шифром, разработанным специалистами. И пока мы держим наши ключи в секрете и не храним нигде открытые тексты, мы чувствуем себя неуязвимыми.
Но, как вы только что видели, достаточно малейшего стороннего канала, капельки информации, чтобы система стала полностью уязвимой. Наш воображаемый разработчик использовал стойкий алгоритм из существующей библиотеки, сгенерировал ключи требуемой длины и не сделал никаких глупостей, вроде повторного использования временных значений (nonce). Его единственной ошибкой было не перехватить неочевидное исключение, что привело нас к возможности понять расшифровывается ли наш шифротекст во что-то корректное.
Конечно, конкретно данная атака может быть предотвращена путем перехвата исключений, ограничения числа запросов с одного IP адреса и мониторингом подозрительных запросов, но не в этом суть. Злоумышленники всегда изощренные и будут использовать даже малейшее несовершенство реализации. Будьте осторожны со своей криптографией, даже если она взята из надежного источника.
Спасибо.
The Matasano Crypto Challenges (http://matasano.com/articles/crypto-challenges/), благодаря которым я заинтересовался криптографией. Очень рекомендую!
_____
Перевод сделан с разрешения автора статьи Robert Heaton.
Источник: http://robertheaton.com/2013/07/29/padding-oracle-attack/
Еще интересные ссылки по теме:
https://class.coursera.org/crypto-preview/lecture/38
Однако, и внедрение известных и стойких алгоритмов не является панацеей. Даже если вы возьмете готовую реализацию данного алгоритма, сгенерируете секретные ключи согласно всем требованиям и тому подобное, все-равно вы останетесь потенциально подвержены некоторым весьма эффективным атакам. Опытному злоумышленнику достаточно крошечной, казалось бы, совершенно несвязанной с криптосистемой толики информации, чтобы обойти шифрование.
Мой посыл не в том, что убедить вас отказаться от самостоятельного использования криптографических средств или пойти и нанять консультанта с зарплатой от $1000 в час всякий раз когда вы задумываетесь о шифровании.
Частично я веду к тому, что вам никогда не следует расслабляться, всегда нужно быть начеку, изыскивая пути, которые злоумышленник может использовать для получения дополнительной информации о вашей системе, а частично к тому, что Padding Oracle Attack является крутой демонстрацией всего этого. Итак, начнем.
Режим CBC
CBC, или режим сцепления блоков шифротекста, это один из режимов симметричного блочного шифрования с использованием механизма обратной связи. Это означает, что при шифровании очередной блок открытого текста проходит через блочный алгортим шифрования, а также дополнительно изменяется с использованием результата шифрования предыдущего блока.
Так что, если мы шифруем предложение:
This is a sentence of a carefully chosen length.
мы получим результат шифрования для каждого блока из 16 байт, причем последний блок открытого текста будет специальным образом дополнен (но об этом далее).
В CBC каждый блок открытого текста складывается побитово по модулю два (xor) с предыдущим блоком шифротекста перед тем как поступить на вход алгоритму шифрования. Данная взаимозависимость блоков означает, что каждый блок шифротекста зависит от каждого блока открытого текста, который был обработан к данному моменту. Причем изменение любого байта открытого текста приведет к изменению всех последующих байт шифротекста (лавинный эффект, ага). Согласно Википедии — CBC является «одним из двух режимов симметричного блочного шифрования, рекомендованных Нилом Фергюсоном и Брюсом Шнайером».
Как работает дополнение блоков (важно!)
Предпочтительным методом дополнения блоков шифротекста, является PKCS7. В нем значение каждого дополняемого байта устанавливается равным количеству дополняемых байт. Так если мы имеем блок из 12 символов, он будет дополнен четырьмя байтами [04, 04, 04, 04] до стандартного размера блока в 16 байт. Если блок имеет размер в 15 байт, он будет дополнен одним байтом [01]. Если блок имеет размер ровно в 16 байт, мы добавляем новый блок состоящий из [16]*16. (подробнее — https://en.wikipedia.org/wiki/Padding_(cryptography)#PKCS7)
Солгасно данному методу, последний блок расшифрованного открытого текста не может заканчиваться, например, на [..., 13, 06, 05]. А значит, что и оригинальный шифротекст является неверным, потому как не существует допустимых открытых текстов, которые могли бы быть преобразованы в такой шифротекст.
The Padding Oracle Attack
Оказывается, что знания факта, получается ли при расшифровке шифротекста открытый текст с корректным дополнением, достаточно атакующему для проведения успешной атаки на шифрование в режиме CBC. Если мы можем подавать какому-то сервису шифротексты, а он будет возвращать нам информацию, корректно ли дополнение — мы сможем вскрыть ЛЮБОЙ шифротекст.
Так что ошибкой, которой достаточно, чтобы обрушить ваше шифрование, может являться некоторый API, который будет возвращать код 200, если поданный нами шифротекст расшифровывается во что-то с корректным дополнением, и код 500, если нет.
Это не маловероятная ситуация. Например, Ruby OpenSSL подвержен данной проблеме. Достаточно использовать пример кода из официальной документации (http://www.ruby-doc.org/stdlib-1.9.3/libdoc/openssl/rdoc/OpenSSL/Cipher.html#documentation):
decipher = OpenSSL::Cipher::AES.new(128, :CBC)
decipher.decrypt
decipher.key = "the most secret!"
decipher.iv = "also very secret"
plain = decipher.update("thewrongpadding!") + decipher.final
Данный код выдает OpenSSL::Cipher::CipherError: bad decrypt, который, если его не перехватить, вернет ответ с ошибкой 500.
Положим, что мы украли шифротекст. Если мы можем посылать шифротексты и определять расшифровываются ли они в сообщения с корректным дополнением, как же нам использовать это для того, чтобы полностью расшифровать украденный шифротекст?
Промежуточное состояние (The intermediate state)
Повторим еще раз — в CBC режиме каждый блок открытого текста побитово складывается по модулю два (XOR) с предыдущим блоком шифротекста перед тем как пойти на вход шифру. При расшифровании каждый шифротекст проходит через дешифратор и затем XOR'ится с предыдущим блоком шифротекста, чтобы произвести открытый текст.
Атака работает через вычисление «промежуточного состояния» процедуры расшифрования (смотри схему) для каждого блока шифротекста. Это состояние блока шифротекста после расшифрования блочным алгоритмом, но ДО процедуры XOR с предыдущим блоком шифротекста. Мы будем находить это состояние, поднимаясь снизу от открытого текста, вместо того, чтобы спускаться вниз через блочный шифр. Также мы вообще не будем волноваться на счет ключа шифрования или алгоритма блочного шифрования.
Почему же данное промежуточное состояние так важно? Заметим:
I2 = C1 ^ P2
и
P2 = C1 ^ I2
Мы уже знаем C1 т.к. это часть шифротекста, который мы имеем. Так что если мы найдем I2, мы можем легко найти P2 и расшифровать сообщение.
Манипулирование шифротекстами
Вспомним, что мы можем подавать на вход системе любой шифротекст, и сервер ответит нам корректное ли дополнение получается после расшифрования. Мы используем данный факт, подавая на вход C1' + C2, где C1' — специальным образом сформированный нами блок шифротекста, а C2 — это блок, который мы хотим расшифровать. Под обозначением C1' + C2 мы понимаем простую конкатенацию (то-есть, «склеивание» блоков). Обозначим результат расшифрования как P'2.
Начнем с того, что мы заполним C1'[1..15] случайными байтами, а C1'[16] заполним нулем (0x00). Теперь подадим C1' + C2 серверу. Если сервер ответит, что дополнение получилось корректное, то мы можем быть уверены (с большой вероятностью), что P2'[16] равно 0x01 (т.к. дополнение корректно). Если сервер отвечает ошибкой — посылаем сообщение с C1'[16], установленным в 0x01, затем в 0x02 и.т.д. пока не получим нужный нам ответ.
(примечание переводчика. Конечно же возможна ситуация, когда мы получим два верных ответа:
1) для дополнения 01
2) для дополнения 02,02 или 03,03,03…
Если произошла такая ситуация — просто меняем предпоследний байт C1' и повторяем операцию заново.
В самом крайнем случае, нам понадобится три попытки, но это маловероятно.
)
Теперь положим, что сервер вернул ответ 200 при C1'[16] = 94.
I2 = C1' ^ P2'
I2[16] = C1'[16] ^ P2'[16]
= 94 ^ 01
= 95
Ура! Мы получили финальный байт промежуточного состояния. Т.к. C2 взят из реального шифротекста, то I2 тоже идентичен реальному. Поэтому, мы можем расшифровать последний байт настоящего открытого текста:
P2[16] = C1[16] ^ I2[16]
= C1[16] ^ 95
Мы подаем на вход C1'[16] = C1[16] и получаем последний байт реального открытого текста. На этом этапе, мы нашли всего-лишь заполнитель, так что придется проделать еще несколько итераций данного процесса, пока мы не обнаружим что-нибудь интересное.
Продолжаем
Мы нашли последний байт прокручиванием C1' до получения корректного дополнения. При этом мы можем сделать заключение, что последний байт P'2 равен 0x01. Затем используя P2'[16] и C1'[16], находим I2[16]. Продолжая этот процесс, находим оставшиеся байты I2 и расшифровываем весь блок шифротекста.
Заполняем C1'[1..14] случайными байтами, C1'[15] устанавливаем в 0x00, а C1'[16] таким, чтобы получить P2'[16] == 0x02:
C'1[16] = P'2[16] ^ I2[16]
= 02 ^ 95
= 93
Теперь мы можем быть уверены, что P2' будет заканчиваться на 0x02, и поэтому единственный вариант, при котором P2' будет иметь корректное дополнение — если P2[16] == 0x02. Мы будем прокручивать C1'[15], пока сервер не выдаст нам код 200. Предположим, что это случилось при C1'[15] == 106. Проделываем опять то, что мы уже умеем:
I2 = C1' ^ P2'
I2[15] = C1'[15] ^ P2'[15]
= 106 ^ 02
= 104
И вуаля! Мы знаем предпоследний байт I2. Поэтому можем найти предпоследний байт P2, как мы это уже проделывали ранее:
P2[15] = C1[15] ^ I2[15]
= C1[15] ^ 104
И так далее для всех 16 байтов C2.
Остальные блоки
Форма блоков шифротекста зависит только от них самих и предшествующих блоков. Так что мы можем применить вышеприведенный алгоритм к каждому блоку шифротекста (отдельно от первого). Первый блок будет зашифрован с использованием вектора инициализации (IV), а сам IV выбран случайно при процедуре зашифрования. До тех пор, пока мы не узнаем IV, мы не сможем расшифровать первый блок, и нет ничего, что тут можно придумать, кроме глупого перебора очевидных значений [0,0,0,...] для IV и просмотра, получается ли какой-нибудь разумный открытый текст. И делать так в надежде, что первые 16 байт будут чем-нибудь вроде "Дорогой Евгений!".
Это все и есть Padding Oracle Attack.
Вот почему все, что связано с криптографией пугает.
Мы знаем, что не следует самостоятельно реализовывать криптографические примитивы, и что мы строим систему на чем-то уже изобретенном. Легко почувствовать себя расслабленно, когда мы прячемся за стойким шифром, разработанным специалистами. И пока мы держим наши ключи в секрете и не храним нигде открытые тексты, мы чувствуем себя неуязвимыми.
Но, как вы только что видели, достаточно малейшего стороннего канала, капельки информации, чтобы система стала полностью уязвимой. Наш воображаемый разработчик использовал стойкий алгоритм из существующей библиотеки, сгенерировал ключи требуемой длины и не сделал никаких глупостей, вроде повторного использования временных значений (nonce). Его единственной ошибкой было не перехватить неочевидное исключение, что привело нас к возможности понять расшифровывается ли наш шифротекст во что-то корректное.
Конечно, конкретно данная атака может быть предотвращена путем перехвата исключений, ограничения числа запросов с одного IP адреса и мониторингом подозрительных запросов, но не в этом суть. Злоумышленники всегда изощренные и будут использовать даже малейшее несовершенство реализации. Будьте осторожны со своей криптографией, даже если она взята из надежного источника.
Спасибо.
The Matasano Crypto Challenges (http://matasano.com/articles/crypto-challenges/), благодаря которым я заинтересовался криптографией. Очень рекомендую!
_____
Перевод сделан с разрешения автора статьи Robert Heaton.
Источник: http://robertheaton.com/2013/07/29/padding-oracle-attack/
Еще интересные ссылки по теме:
https://class.coursera.org/crypto-preview/lecture/38
