Привет, %username%!
Недавно мы вернулись с конференции EuroCrypt 2019, где познакомились с чрезвычайно умными людьми и заодно узнали новые, чрезвычайно обидные факты о ГОСТовском SBox.
Так что, это второй подход к снаряду. Исправленный и дополненный.
В этот раз не будет непонятных красно-синих слайдов, зато будут оригинальные документы из комитета ISO c объяснениями авторов Кузнечика.
И даже челлендж в конце!
Поехали.
Вначале ликбез. В предыдущей статье его не было, в этот раз исправляюсь.
Chosen Plaintext Attack (CPA)
Начнем мы с базовой модели атаки на блочные шифры.
В этой модели атакующий знает о криптосистеме всё кроме ключа шифрования. Он может создавать любые открытые тексты, получать соответствующие им шифротексты и его задачей является вычислить ключ, т.к. это единственная переменная.
Блочный шифр в данной ситуации можно рассматривать как псевдослучайную перестановку. Функцию, которая блоку открытого текста сопоставляет блок шифротекста таким образом, что связь между ними определить невозможно.
Идеальный блочный шифр можно представить себе как большую таблицу, где по горизонтали будут все возможные ключи от 000...000 до 111...111, по вертикали — все возможные открытые тексты тоже от 000...000 до 111...111, а на месте их пересечения — случайным образом сгенерированные шифротексты, которые однозначно связывали бы пару «ключ — открытый текст». Создать такую таблицу в реальной жизни не представляется возможным из-за её размеров, поэтому её эмулируют с помощью различных алгоритмов блочного шифрования.
Атаку на блочный шифр можно назвать успешной если мы можем определить «неслучайность», с которой алгоритм выбирает шифротексты, соответствующие открытым текстам. Эта неслучайность и позволяет в самых худших случаях вычислить ключ шифрования.
(Не)линейность
Процесс шифрования в блочном шифре можно представить простой формулой
C = M х K
где C — шифротекст, M — открытый текст, K — ключ шифрования, а x — блочный шифр.
Эта формула визуально похожа на школьную формулу линейного уравнения y = kx+b, графиком которой является прямая линия.
Любую прямую линию можно восстановить всего по двум точкам. И в то же время мы очень не хотим, чтобы по двум парам открытый текст — шифротекст можно было восстановить ключ шифрования. Для этого в алгоритмы шифрования добавляют специальные прослойки, отвечающие за нелинейность. Эти прослойки призваны не допустить возможность вычисления связи между открытым текстом, шифротекстом и ключом.
Их качество критически важно для безопасности алгоритма.
Что такое SBox?
Это та самая нелинейная прослойка. Функция, которая в случае Кузнечика и некоторых других шифров однозначно сопоставляет одному байту другой байт.
Очень часто она задаётся простой таблицей соответствия, например такой
Потому что иначе её не описать. На первый взгляд.
Почему SBox важен?
Потому что это единственная нелинейная функция во всём шифре. Без неё взломать шифр будет не просто, а очень просто, представив его в виде системы линейных уравнений. Поэтому к функции перестановки так много внимания. Есть даже практические задания по взлому AES с линейным SBox.
Почему нельзя создать один безопасный SBox на всех?
Проблема в том, что криптография не является точной наукой. Единственным доказуемо стойким алгоритмом шифрования является одноразовый блокнот. Всё остальное — робкие попытки уместиться в диапазон доступных нам знаний, набор которых не так уж велик.
Мы точно не знаем, стоек ли RSA или AES или эллиптические кривые, но мы знаем, что такие-то и такие-то вещи делать точно нельзя. Всё что между — творчество.
Отсюда и постоянная паранойя по поводу различных «магических констант» и прочих моментов, которые авторы алгоритмов преподносят как безопасные, но не могут это доказать.
Как создают SBox?
Различных вариантов SBox — 256!, это примерно 21684. Выбор большой и за годы криптоанализа были выработаны метрики и характеристики, которыми должен обладать SBox, устойчивый к известным на сегодня атакам. Конечно, создатели таблиц думают на годы вперед и пытаются создать перестановки, которые были бы устойчивы даже к атакам, придуманными через 5-10 лет. Но это уже больше из разряда магии и шаманства.
Есть два принципиально разных подхода к созданию SBox.
Первый — случайный поиск. Разработчики генерируют случайные таблицы, смотрят на их характеристики и отсеивают те, которые не подходят. Так продолжается до тех пор, пока разработчики не удовлетворятся найденным.
В цивилизованном мире это происходит, например, следующим образом:
- Берется некоторое начальное значение, например цитата из книги или первые несколько цифр числа Pi
- Прогоняется через хэш
- Результат хэширования используется как данные для формирования SBox
- Если SBox не подошел — берем текущий хэш и возвращаемся к п.2
Так любой может воспроизвести этот процесс и убедиться, что были соблюдены хотя бы минимальные требования к псевдослучайному поиску.
Знаете, куда делись сиды от главного симметричного алгоритма страны? Потерялись! Я думал их специально не выдают, секрет там или что, но российские коллеги на EuroCrypt рассказали, что во время разработки алгоритма в 2007м году никто почему-то не думал, что придётся обосновывать дизайн таблицы подстановок, и значения из которых она получилась, были навсегда утеряны. История красивая, вот только не стоит забывать, что алгоритм создавался не в школе на перемене, а в недрах ФСБ.
Второй способ — создать SBox самим, руководствуясь доступным математическим аппаратом. Так поступили авторы AES и у них неплохо получилось. Если сравнить нелинейность SBox AES, SM4(китайский стандарт) и Кузнечика (он использует тот же SBox, что и хэш Стрибог), то результат будет не в пользу последнего
AES non-linearity (min, max) = (112.0, 112.0)
SM4 non-linearity (min, max) = (112.0, 112.0)
Streebog non-linearity (min, max) = (102.0, 110.0)
Код вычисления нелинейности использует Walsh Transform и доступен здесь
Документы
В моё распоряжение попали два документа из ISO. В первом дизайнеры Кузнечика объясняют как создавали SBox, в другом комитет обсуждает их доводы
из первого документа нам интересны две цитаты:
и
Надеюсь, тема с «Лео Перрин сам придумал, что авторы искали SBox случайным образом» теперь закрыта.
Из объяснений дизайнеров следует, что
- Они действительно искали SBox псевдослучайным образом (учитывая критерии безопасности)
- Никакой скрытой структуры в нём якобы заложено не было.
И вот в этом месте они капитально облажались.
Что такое структура?
Структура, применительно к таблице перестановки — некий алгоритм, который эту таблицу описывает.
В документе был упомянут AES. Но таблица перестановки для AES была изначально создана не случайным поиском, а с помощью нескольких математических приёмов, позволивших описать нелинейный слой несколькими формулами. В этом, кстати, уникальность AES.
Напротив, если вы ищите SBox случайным образом, то таких структур в нём быть не должно и проблема с SBox Кузнечика в том, что слова дизайнеров алгоритма очень сильно расходятся с фактами. Про саму структуру кузнечика под названием TKLog я писал в предыдущей статье, в этот раз поговорим о структурах вообще.
Колмогоровская сложность
Это результат исследований из последней статьи Лео Перрина на тему Кузнечика.
Основной контраргумент к статьям про структуры в SBox Кузнечика в том, что «практически в любом SBox можно найти какую-то структуру, если захотеть». И «хоть вероятность нахождения структуры, которую нашел Лео, ничтожна мала, если бы был другой SBox, то нашлась бы другая, тоже с ничтожной вероятностью».
Допустим, это так. Но. Как оказалось, можно вывести некую «степень заструктурированности» SBox, которая не зависит от вероятности попадания в ту или иную структуру.
Зато она зависит от размера алгоритма, который нужен для генерации данного SBox!
Это и называется Колмогоровской сложностью.
Если представить SBox как строку байт, то в случае случайной строки не должно быть алгоритма, который генерирует эту строку и при этом сам меньше этой строки.
Применительно к кузнечику
Итак, размер SBox — 256 байт. Перед вами читабельная версия кода авторства Лео Перрина, которая реализует таблицу Кузнечика. На входе — исходный байт, на выходе — соответствующий ему байт из SBox Кузнечика. Главным условием для такого алгоритма является запрет на использование языковых или платформенных структур, читерски сокращающих размер программы. К примеру, если где-то внутри стандартной библиотеки есть константа, содержащая половину SBox, то использовать её нельзя.
Челлендж — написать программу, размер которой будет меньше, чем SBox.
unsigned char p(unsigned char x){
unsigned char
s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};
if(x) {
unsigned char l=1, a=2;
while(a!=x) {
a=(a<<1)^(a>>7)*29;
l++;
}
if (l%17) return 252^k[l%17]^s[l/17];
else return 252^k[l/17];
}
else return 252;
}
Наша задача показать, что в SBox Кузнечика заложена «сильная» структура, такая, что её размер сильно меньше размера самого SBox. Код выше занимает 416 символов, что пока многовато.
Если упаковать константы в символы юникода и избавиться от некоторой красоты, то получится следующий код:
p(x){
unsigned char
*t="@`rFTDVbpPBvdtfR@xacp?xe2>4xa6xe9{zxe3q5xa7xe8",
a=2,l=0,b=17;
while(x && (l++,a^x)) a=2*a^a/128*29;
return l%b ? t[l%b]^t[b+l/b]^b : t[l/b]^188;
}
Этот исходник занимает уже 196 байт, что уже на 23% меньше чем сам SBox. Но мы идём дальше. Если убрать лишние пробелы и переносы строк, то лучшая на сегодняшний день рабочая версия С кода выглядит так:
p(x){char*k="@`rFTDVbpPBvdtfR@xacp?xe2>4xa6xe9{zxe3q5xa7xe8";int l=256,b=17;while(--l*x^l)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}
Чтобы вывести на экран SBox можно воспользоваться следующим простым кодом:
int main() {
for(int i = 0; i < 256; i++){
if (i % 16 == 0){
printf("n");
}
printf("%d, ", (unsigned char)p(i));
}
}
Можете запустить и убедиться, что код действительно работает и соответствует SBox Кузнечика.
Эта версия С кода занимает 153 символа. Поскольку все символы кода — валидные ANSI, то можно считать каждый символ равным 7 битам, а не 8. Таким образом имеем 1071 бит или ~134 байта. А это уже почти половина от размера таблицы, хоть и всё еще текстовый исходник.
Что касается скомпилированного кода, то для архитектуры Cortex-M4 Лео удалось скомпилировать код размером всего 80 байт (ассемблерный код есть в статье)
Это тоже не предел, уже есть рабочие имплементации размером меньше чем 64 байта.
И что, это означает бекдор?
Нет, мы не можем говорить о наличие бекдора в Кузнечике, пока он не будет стопроцентно найден.
Но и структура, в 4 раза меньшая чем Sbox, не может попасть в SBox случайно, что бы там ни говорили авторы и защитники Кузнечика.
Только вдумайтесь. Реальный размер таблицы подстановки Кузнечика, найденной «псевдослучайным поиском» сравним с размером таблицы AES (60 символов, GolfScript), у которого структура была известна с самого начала.
Есть или нет бекдор в Кузнечике — мы не знаем. Но в том, что авторы соврали — сомнений не осталось.
Выводы
Дизайнеры Кузнечика неоднократно декларировали отсутствие скрытых структур в важнейшем элементе алгоритма — SBox. Но исследования показали, что процесс создания таблицы подстановки был далёк от случайного поиска. Даже с теми критериями, которые описали авторы в своём объяснении.
Если авторам верить (а по эту сторону границы им безоговорочно верят), то они случайно наткнулись на структуру, размер которой в 4 раза меньше, чем сам SBox. Повторюсь, криптография — не точная наука и достаточно малейшего повода для сомнения, чтобы разбудить в людях паранойю. В данной ситуации размер повода в 4 раза более чем достаточный, чтобы считать алгоритм, разработанный в недрах наших прославленных силовых структур, очень подозрительным. Нет, ну правда, смешно когда наши доблестные ФСБшники включают школьников и говорят, что 11 лет назад этот алгоритм начинал разрабатываться чуть ли не в свободное время, поэтому они в итоге потеряли и сиды и скорее всего программу, которая генерировала таблицу подстановок. Просто так получилось, что side project стал национальным стандартом ¯_(ツ)_/¯.
Послесловие
Сейчас в ISO идёт полугодовой период исследования Кузнечика на наличие бекдора. По его результатам будет принято решение о дальнейшей судьбе алгоритма как международного стандарта. Либо процесс будет продлён еще на пол года.
Со слов людей, лично знакомых с дизайнерами Кузнечика, алгоритм был разработан в то время, когда никто не требовал объяснять почему SBox имеет именно заданный ими вид. Поэтому никто не сохранил стартовые значения для перебора. Аргумент, как по мне, слабоват.
На конференции я поговорил с автором Curve25519 Daniel J. Bernstein и Tanja Lange, которые являются членами комитета ISO по стандартизации новых алгоритмов. Они сказали, что предоставлять сиды не обязательно, достаточно показать саму программу, которая генерировала этот злосчастный SBox. Этого сделано до сих не было и вероятность этого события не слишком большая. Ибо секрет.
Вообще в протоколе обсуждения можно найти много интересных деталей и реплик, позволяющих понять ход мыслей членов комитета.
Что касается дальнейшей судьбы алгоритма, вероятность принять его как международный стандарт довольно низкая. Это признают как члены ISO, так и сотрудники российских компаний, с которыми я познакомился на EuroCrypt.
Более того, по последним данным есть ненулевая вероятность выпиливания уже принятого в стандарт хэша Стрибог (с тем же SBox), а так же RFC 7801, в котором описан Кузнечик.
Можно было бы создать новый, правильный по всем канонам SBox, этим даже ради интереса занялись в одной из российских компаний (кстати, обещали результаты показать). Но проблема в том, что в России Кузнечик уже стандартизирован, реализован в железе и внедрён везде, где только можно. Замена Кузнечика на Кузнечик V2 обойдется в очень круглую сумму.
Девяностые и нулевые давно позади. Пора перестать создавать алгоритмы шифрования в подвальных шарашках и говорить, что «а кроме ФСБ никто ничего подобного создать в России не может, у нас выбора нет».
Может хотя бы попробовать конкурс провести перед тем, как бросаться такими словами? И не забывать, что AES вообще-то не в США был придуман.
Может тогда у нас отпадёт необходимость бить по рукам совковых раздолбаев, которые находят место детским отмазкам в алгоритмах, защищающих, помимо прочего, гос. тайну.
Challenge!
Нужно написать реализацию функции SBox Кузнечика, которая была бы по возможности еще меньше, чем найденная Лео и его коллегами. Но пойдут и те, что просто меньше 256 байт. Технические детали тут. Там же несколько примеров на разных языках. Самым успешным — слава, респект и уважуха за вклад в честную криптографию.
Пока рекорд — 58 байт на языке Stax. Это меньше чем четверть от размера «случайно найденного» SBox.
Спасибо за внимание.
Автор: Алексей
