Wednesday, July 27, 2011

ГОСТ 28147-89 НЕ взломан, пока...

Не писал бы, но, видимо, надо. После ряда публикаций в весьма авторитетных источниках даже среди своего небольшого отдела стал наблюдать какую-то истерию, хотя, на мой взгляд ничего не изменилось. Попробую изложить факты
1. Я не видел в открытом доступе ни одного нормального доказательства утверждений Куртуа. Исследование Таканори Исоби, доступно только в виде презентации на FSE 2011 из которой мало что понятно. Попытки найти что-нибудь об "Algebraic Complexity Reduction" (ссылка [12] в статье Куртуа) закончились неуспешно (если у кого есть что, пожалуйста, комментарьте!), за исключением вот этого (собственно, из самой статьи):
"The main idea is as follows: In order to reduce the attack complexity, we
exploit the self-similarity of the cipher and add some well-chosen assumptions
which produce interesting and sometimes quite non-trivial consequences due to
the high-level structural properties of the cipher, which makes cryptanalysis
problems smaller, simpler and easier to solve." В целом, стандартный подход для любого криптоанализа, только, как следствие, подобный метод будет работать только при строго определенных условиях (на ключах с определенными зависимостями, или на специальных открытых текстах или и то и другое, или "специальные" S-блоки и т.п.), что крайне ограниченно может применяться на практике (но, тем не менее, полезно для академической науки).
2. Сама статья Куртуа больше похожа на научно-популярный труд типа Прикладная криптография, (не упущу заметить, что книжка Шнаера - очень хорошая и я всем рекомендую ее почитать), где излагается общая структура ГОСТа, его история и прочее на уровне Википидии. SecLab предложил практически дословный ее перевод. Из нее ничего не следует, кроме голословных утверждений.
3. Размер блока ГОСТа - 64 бита. Если мы знаем 2^64 пар открытый текст - шифртекст - это и есть все, что нам нужно знать :-) Это - полный перебор, нам ключ не нужен, так как у нас есть все возможные открытые тексты и соответствующие (биективно!) им шифртексты.
4. На практике атаку KPA, накопив 2^64 (да и 2^32, как требует Исоби) пар открытый текст - шифртекст, невозможно, так как сессионный ключ меняется ЗНАЧИТЕЛЬНО чаще.
5. Все показанные успешные компрометации ГОСТа крутятся около 8-раундной "модификации", тогда как в оригинальной реализации из 32 (!). То, что ГОСТ обладает плохими диффузионными свойствами и это компенсируется количество раундов - давно известно, здесь как раз это и эксплуатируется.
6. Отдельно про презентацию Исоби хочется отметить, что даже когда вы-таки сподобились и как-то насобирали 2^32 пар шифртекстов и открытых текстов (C/P), сложность атаки остается 2^225 (См. слайд "Result" его презентации). У меня проблема, я не могу с ходу понять что мне, как взломщику, проще: выполнить обычный перебор из 1 пары C/P и сложностью 2^256 или наловить 2^32 C/P, провести с этим какие-то шаманства "Reflection Meet-In-The-Middle" (R-MITM) и отбрутофорсить выделенные этим шаманством "Surviving Key Space", причем общая сложность будет 2^225, что, в общем-то не сильно отличается от 2^256.... Думайте сами.

Итого: Тяжело оценить вклад Куртуа/Исоби в практику компрометации ГОСТа (в основном, очень мало информации - может, в этом и секрет, что секрета просто нет :-)) => не стоит делать поспешных выводов и, тем более, тратить нервную систему.

1 comment:

Виктор Штонда said...

Будет переиздана культовая книга Брюса Шнайера «Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке C(Си)» - 2-е исправленное и юбилейное издание 2015 года