Новая атака на схему симметричного шифрования в OpenPGP


Эта новость поступила только около часа назад, и я успел ознакомиться с деталями[link1] лишь поверхностно. Однако, и хочу это сразу подчекнуть, атака носит ограниченно-прикладной характер, и неприменима ни к одной существующей реализации стандарта OpenPGP!

Шнайера-Джеллада-Катца[link2]

Мистер и Цуккерато, как Шнайер, Джеллад и Катц, использовали методы адаптивно подобранного шифртекста и дешифрующего оракула. В случае успеха оппонент сможет восстанавливать первые два байта из любого блока шифртекста при 2^15 (в среднем) запросов к оракулу на каждый (два часа в лабораторных условиях на стандартном Pentium M 1.8 ГГц). Это несравнимо меньше, чем при успешной атаке Шнайера-Джеллада-Катца, где одного подобранного шифртекста, переданного оракулу, достаточно (при определённых условиях), чтобы дешифровать весь открытый текст единичного сообщения.

Итак, суть в следующем. Каждый симметрично зашифрованный пакет данных предваряется 64- или 128-битовым вектором инициализации. Когда открытый текст шифруется, в самом начале пакета непосредственно перед "полезной нагрузкой" вставляется так называемый QC-тэг (quick check, быстрая проверка), состоящий из двух последних байт ВИ. Он служит тому, чтобы при расшифровании можно было сразу узнать, используется ли правильный симметричный ключ или неверный и, в случае чего, не прогонять расшифрование по всему сообщению: если расшифрованный QC-тэг совпадает с последними байтами ВИ, программа продолжает расшифрование всего сообщения, иначе выдаёт ошибку. Это особенно полезно, если зашифрованные данные составляют несколько мегабайт или гигабайт — программе не нужно расшифровывать пакет целиком, чтобы в итоге определить, что операция проводится не тем ключом, и сообщить об этом пользователю. Вот за эту-то функцию и зацепились криптологи.

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

Взломщик имеет в своём распоряжении сообщение, симметрично зашифрованное парольной фразой (это важно: сообщение, зашифрованное открытым ключом, не поддаётся такой атаке). Он вносит определённые изменения в пакет шифртекста и отправляет модифицированное сообщение оракулу, чтобы узнать, прошла ли "быстрая проверка". Если оракул возращает взломщику "Ошибка", взломщик снова вносит корректировку и повторяет процесс, пока, наконец, оракул не сообщит, что сообщение расшифровано, т.е., технически, подогнанные взломщиком байты QC-тэга совпали с последними байтами ВИ (оракул в результате расшифрования получит мусор, но это не важно). Теперь взломщик знает последние два байта ВИ. Он "сдвигает" ВИ на эти два байта и повторяет весь процесс, пока не получит полный вектор инициализации.

(В действительности, оракулу не обязательно возвращать "Правильно" или "Ошибка". Даже если при расшифровании мусора он всё равно сообщит взломщику "Ошибка", последний сможет провести тайминг-атаку, замерив время, затраченное на обработку сообщения.)

Это подготовительный этап, на который у исследователей уходило, в среднем, 4 часа. Исходя из полученных данных и при помощи специальных вычислений и дополнительных запросов к оракулу, можно за каждые 2 часа (в среднем) дешифровать по два первых байта из каждого блока шифртекста.

Как можно видеть, такая атака применима только против автоматизированных систем, выдающих избыточную информацию при взаимодействии с пользователем. Живой человек не станет отвечать "Правильно" или "Ошибка" и пытаться расшифровать около 30 тысяч присланных сообщений. Более того, на сегодня нет ни одной реализации OpenPGP, подходящей под необходимые допущения.

В то же время, в стандарт OpenPGP и в крупнейшие реализации — PGP и GnuPG — будут внесены соответствующие корректировки, запрещающие обработку QC-тэга в симметрично зашифрованных сообщениях.


Комментарии
— unknown (12/02/2005 13:32)   
Ну что тут скажешь. Как всегда, создатели протоколов просто "переэкономили". Нет чтобы проверять хотя бы хэш-значения нескольких блоков текста, ограничились несколькими байтами для проверки, "чтобы быстрее было". Хотя где нужна такая быстрота?

Ведь замедляют же специально вычисление ключа из пароля, а здесь ускоряют проверку!

Для коротких сообщений (а их может быть >95% случаев ) можно было бы сделать и медленную, зато более безопасную проверку (например от хэш-функции всего сообщения да еще с отдельным проверочным ВИ – IV-salt).

Для длинных – проверять хэши от первых нескольких блоков и т.д.

Обидно, что уязвимость возникает из-за несложной в устранении проблемы, такую проверку легко можно реализовать и более безопасных (пусть и немного медленных способов) – масса.
— SATtva (12/02/2005 14:02)   
Причина, скорее, — ползучесть стандартов. OpenPGP писался в 97-м — тогда и компьютеры были помедленнее, и авторы понеопытнее. Но, хотя мир не стоит на месте, менять стандарт всегда непросто из-за проблем наследования: как обеспечивать совместимость старых приложений и новых? Так, сейчас, например, рабочая группа обсуждает, отходить ли от 3DES и SHA-1 как обязательных алгоритмов и переключаться ли на AES и SHA-256? Всё равно когда-то надо будет начинать. Зато встраиваемые приложения и аппаратные реализации, как с ними быть? Теряется совместимость. Но это я так, к слову...

Предложения по исправлению данной ошибки уже есть. Судя по всему это будет хэш сеансового ключа, помещённый внутрь блока шифртекста вместа тэга quick check.
Гость (27/02/2005 22:44)   
Я добавил следующий комментарий в документацию[link3] моей реализации OpenPGP:

WARNING: The quick check for symmetric key integrity constitutes a serious vulnerability under certain circumstances, when using ePointPGP in server applications.
In short, by repeated attempts at decrypting a number of carefully chosen fake ciphertext messages purporting to have been encrypted with the same symmetric key as the attacked message, the attacker can gain enough information from the fact whether or not it has passed the quick check to decrypt the first two bytes in the next block (and then those in all subsequent blocks).
For a detailed analysis and explaination, please read "An Attack on CFB Mode Encryption As Used By OpenPGP" by Serge Mister and Robert Zuccherato.
Please note that ePointPGP is intended primarily for client-side applications (applets) and we do not recommend it for any server application. On the client side, the quick check is still useful, and cannot be in practice exploited in the above described way.


Думаю, что это достаточно хорошо описывает опасность связанную с quick-check, от которого я не хочу отказываться в данной реализации. Я уже спросил мнение одного из авторов статьи (S. Mister — я аспирант на той же кафедре, где он получил PhD в свое время), но пока нет ответа. Если будет, с удовольствием поделюсь.
— SATtva (27/02/2005 23:52)   
А нельзя просто самому приложению запретить, когда оно работает в серверном режиме, сообщать пользователю, прошла quick check или не прошла? Проблема ведь именно в этом. Если оппонент не будет знать результатов "быстрой проверки", он не сможет организовать атаку.

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

Либо ошибка выводится, но с задержкой в несколько секунд. Теоретически, от тайминг-атаки это не спасёт, но сделает её совершенно нереальной: оппоненту придётся всякий раз ждать означенное время, и проведение 30 тысяч тестов выйдет за пределы практической применимости. (Понятно, что и вывод результата успешного расшифрования должен производиться не ранее, чем через аналогичный срок, иначе, если производится дешифрование небольшого сообщения, оппонент не станет выжидать весь период задержки, а только время, максимально необходимое на легитимное расшифрование. По истечении этого времени он может повторять запрос, не дожидаясь предыдущего ответа.)
Гость (09/03/2005 09:14)   
Нет, к сожалению это не практично. В случае длинных файлов, то, что ключ не подходит, выясняется только в самом конце процесса расшифрования при использовании пакетов No18 или вообше не выясняется в случае пакетов No9. Quick check предназначен для того, чтобы сразу понять, что ключ не верный. К сожалению, множество неверных ключей quick-check проходят, и это делает атаку возможной. Серверное приложение не может позволить расшифровку длинных сообщений "в пустую", так как это легко можно использовать для атаки DOS — слишком легко перегрузить комп шифрованием.
Решение проблемы может принести только новый вид пакета. Так же, как вместо No9 был придуман No18, нам нужен новый вид пакета который проверяет ключ в самом начале, скажем при помощи его хеширования в начале зашифрованного файла (хеш уже зашифрован).
Кстати, Sarge Mister мне ответил, и он с моими комментариями согласен.
— SATtva (09/03/2005 12:18)   
А что скажете о задержке перед выводом результатов расшифрования (или ошибки) в качестве временной меры?
Гость (10/03/2005 15:54)   
Это значительно лучше. Задержка грузит только память (а ее много), но не процессор. Так что DOS в таком случае не так страшен.
Рандомизированная задержка еще лучше.
Но на самом деле, в большинстве случаев достаточна компрессия перед шифрованием. В этом случае четверть расшифрованного сообщения, которую с трудом может добыть противник ничего полезного для него не содержит. Так как стандарт OpenPGP поддерживает компрессию перед шифровкой, ее просто надо использовать не добавляя ничего в приложение.
Гость (17/03/2005 12:15)   

В то же время, в стандарт OpenPGP и в крупнейшие реализации — PGP и GnuPG — будут внесены соответствующие корректировки, запрещающие обработку QC-тэга в симметрично зашифрованных сообщениях.


Какие еще существуют реализации OpenPGP? Будут ли уже в следующей версии (например 9,1) внесены указанные изменения?
— SATtva (30/06/2005 19:41)   
Да, Гость, контрмеры реализованы в PGP 9.0 и GnuPGP 1.4.1. Что касается реализаций OpenPGP, то среди них такие, как Veridis FileCrypt, Cipherix и ряд других, в том числе встраиваемых и сугубо специализированных приложений, основанных на стандарте.

Ссылки
[link1] http://eprint.iacr.org/2005/033

[link2] http://www.pgpru.com/faq/crypto/#6

[link3] http://epoint.sourceforge.net/java/doc/net/sourceforge/epoint/pgp/ENCRYPTEDPacket.htm