Недавно мы вернулись с конференции 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)Код вычисления нелинейности использует Walsh Transform и доступен здесь
SM4 non-linearity (min, max) = (112.0, 112.0)
Streebog non-linearity (min, max) = (102.0, 110.0)
Документы
В моё распоряжение попали два документа из 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>4\xa6\xe9{z\xe3q5\xa7\xe8",
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>4\xa6\xe9{z\xe3q5\xa7\xe8";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.
Спасибо за внимание.
Комментарии (76)
SergeySib
13.06.2019 11:48+1А что если авторы алгоритма не врут и действительно использовали первый подход со случайной генерацией таблиц? Но по какой-то причине вместо случайных чисел взяли слабый, предсказуемый ГПСЧ.
«Миром правит не тайная ложа, а явная лажа» (с).Yaris
13.06.2019 13:04В таком случае авторам надо посыпать голову пеплом, сдать все регалии на склад и пойти заново учиться, перед этим явно указав, какой именно ГСПЧ они брали и что это за "какая-то причина". А не отмахиваться со словами "идите
нахуйпрочь, я фея"
saipr
13.06.2019 12:43Что касается дальнейшей судьбы алгоритма, вероятность принять его как международный стандарт довольно низкая. Это признают как члены ISO, так и сотрудники российских компаний
Похоже так и не дождаться шифрсьютов для TCL/HTTPS с российскими криптоалгоритмами, и не увидим мы этой поддержки в браузерах от Google, Mozilla и других.
yleo
13.06.2019 17:18Это будет означать наличие двойных стандартов и дискриминации.
keydet
13.06.2019 17:44Это будет означать, что он им не нужен — не более.
yleo
13.06.2019 18:07Не согласен с формулировкой.
Подобное противопоставление (они — мы) просто еще один шаг к "чебурнету".
В итоге просто будут функциональные форки/клоны OpenSSL (и других библиотек), отдельные версии браузеров и т.д.
Хотя такой сценарий нельзя назвать совсем плохим — будет создан спрос на соответствующие компетенции и их локальную наработку.
shifttstas
13.06.2019 19:29+1Жалко то как!
(На самом деле — нет)
Loggus66
13.06.2019 23:25+1Помните про предложение обязать гос. сайты использовать российскую криптографию? Если зарубежные УЦ, в т. ч. Let's Encrypt, не будут её поддерживать, то многие из этих сайтов перейдут обратно на нешифрованный HTTP, потому что необходимость HTTPS/TLS зачастую не указывается в ТЗ. Будут перс. данные россиян нешифрованные ходить по сетям, как десять лет назад.
shifttstas
14.06.2019 07:48На зло маме отморозить уши? Ну и что в этом плохого? В чем проблема использовать не зарубежного УЦ а местного, но сертификаты с нормальным шифрованием?
yleo
13.06.2019 15:16Scratch, мне кажется стоит аккуратно обозначить в статье возможные причины "мухлежа со структурой".
Уместно вспомнить об истории с таблицей замен в Магме, где таблица замен была загружаемым параметром.
IMHO для Стрибог авторы взяли уже готовый S-BOX, либо он был им предоставлен в какой-то момент. Соответственно, я допускаю, что авторы не знали об алгоритме генерации, т.е. не являются авторами S-BOX. Поэтому и решились давать объяснения в виде "поиска от случайного" и затем "потеряли сиды".
В принципе это соответствует практическим традициям применения крипто-схем с таблицами замен. Причем как с отечественными традициями (явная выдача разных таблиц), так и с зарубежными (тоже самое, только "не столь публично" как у нас).
То что алгоритм генерации решили не раскрывать (или не решились раскрывать) — точно не является плюсом для публичного национального стандарта.
Думаю, стало неожиданным, что алгоритм генерации был восстановлен так быстро. Предполагаю был с умом запущен подбор набора уравнений в GPU-кластере и т.п., но и утечки нельзя исключать. Ну а для авторов Стриборга и Кузненича это стало facepalm-ом.
Крики "бэкдор" и "мы все умрем" IMHO только от "около диванных" аналитиков. Тут у меня несколько тезисов:
- Наличие структуры не говорит о бэкдоре или слабости. В массе S-BOX-ов есть структура. Нужен глубокий анализ с выводами/доказательствами и никак иначе. Мягко говоря, крайне маловероятно, что в S-BOX умышленно внесли слабость (ибо 275 УК). IMHO структура как-раз от обратного, т.е. для стойкости (но безусловно хотелось-бы увидеть доказательства).
- Факт замалчивания структуры неприятен и по-хорошему заставляет ждать публичных результатов криптоанализа "еще три года" после раскрытия алгоритма генерации S-BOX. Т.е. если вы НЕ попадаете под требования регулятора и вольны не использовать Стрибог/Кузненик, то еще года три (видимо) будете относится к ним как к молодым (не проверенными временем) крипто-схемам.
- К заявлениям "в наших SBOX не структуры" стоит относится очень осторожно. Это примерно невозможно доказать. Соответственно, утверждение "в SBOX не структуры" никогда не означает что структуры действительно нет, и нас ждет еще несколько каминг-аутов.
Гипотетическая смена таблицы замен не должна стать проблемой, поскольку AFAIK чуть менее чем во всех отечественных "железных" реализациях предусматривается такая возможность (закладывается в требования).
kunix
17.06.2019 20:52Основная проблема в том, что «структура» S-box Кузнечика коррелирует со «структурами» других шагов алгоритма.
Это повышает вероятность того, что существует достаточно простое алгебраическое описание работы шифра.
Тот, кому известно просто алгебраическое описание, может взламывать шифр.
Направление мысли понятно?yleo
17.06.2019 21:07+1Не-не, там ещё хуже — только два возможных значения у каждого бита и только две базовые операции с ними (причем одна вообще унарная!).
;)
kunix
18.06.2019 00:03К вашему сведению, алгебра не ограничивается бинарной логикой.
Начнем с простых примеров.
Какая система уравнений проще, на ваш взгляд?
Вот эта: S = A+B mod 16
Или вот эта:
S0 = (A0 XOR B0)
S1 = (A1 XOR B1) XOR ((A0 AND B0) OR (A0 XOR B0))
S2 = (A2 XOR B2) XOR (((A1 XOR B1) AND ((A0 AND B0) OR (A0 XOR B0))) OR (A1 AND B1))
S3 = (A3 XOR B3) XOR ((((A2 XOR B2) AND (A1 XOR B1)) AND ((A0 AND B0) OR (A0 XOR B0))) OR (((A2 XOR B2) AND (A1 AND B1)) OR (A2 AND B2)))yleo
18.06.2019 01:13Тут вы немного путаете "божий дар с яичницей".
Очевидно, что для анализа удобнее иметь "алгебраическое описание" компактно отражающее ход мыслей авторов (т.е. дизайн), а не реверсить его из таблицы чисел.
И как уже писал, сокрытие факта наличия структуры (это в первую очередь) и самой структуры (это во вторую очередь) не является плюсом для публичного стандарта.
Однако, мыслимое вами "алгебраическое описание" не будет доказательством наличия/отсутствия тех или иных свойств, хотя (возможно!) позволит легче выполнить такое доказательство (публичный аудит).
kunix
18.06.2019 01:18Я ничего не путаю.
Алгебраическое описание — это также инструмент оптимизации системы уравнений в целях взлома.
Вам накидать статей, как шифры семейства ARX пытаются ломать через алгебраические атаки?
Там как раз основная проблема, что после некоторого числа итераций алгебраическое описание плохо работает, поэтому ломают алгоритмы с урезанным числом итераций.
Наличие простого (и согласованного!) алгебраического описания для двух последовательных шагов алгоритма (к тому же, скрытого авторами) — это очень подозрительно, я бы сказал.
В случае Стрибог так и есть. Читаем Leo Perrin.
Два последовательных шага алгоритма описываются операциями по модулю одного и того же полинома, представляете?
Просто нет слов.
Наверняка, кто-то в недрах секретных НИИ получил медаль за это… ну или пулю в затылок.yleo
18.06.2019 02:43+1Я ничего не путаю.
Алгебраическое описание — это также инструмент оптимизации системы уравнений в целях взлома.Нет, вы всё-таки путаете "описание алгебраической структуры" с чем-то из списка: "описание алгебраической атаки", "доказательство стойкости против таких-то видов атак", "системой уравнений или её выводом".
Вам накидать статей, как шифры семейства ARX пытаются ломать через алгебраические атаки?
Не надо, у меня своё есть )
Там как раз основная проблема, что после некоторого числа итераций алгебраическое описание плохо работает, поэтому ломают алгоритмы с урезанным числом итераций.
При меньшем числе итераций более простая система уравнений. Соответственно её можно немножко по-SAT-ить, по-коррелировать, по-rainbow-ить и т.п.
… Читаем Leo Perrin ...
Вот цитата из его текста:
First of all, I would like to emphasize that I have not found an attack leveraging these properties. Still, I don't know the answer to the question above...
Perrin нашел структуру.
Но из наличия структуры не следует, что какая-то атака становится проще.
Термин "подозрительно" тут не совсем уместен, это FUD.
Утверждение что "атака возможна" — это "не понял / не понял, но осуждаю", тоже FUD.
Тем не менее, изначально FUD конечно пошел от авторов Стрибог/Кузнечик.
И теперь, после работы Perrin, стало очень интересно.
Ведь кроме упомянутой ранее 275 УК могут быть еще два варианта: продвинутые авторы S-box и/или продвинутая контрразведка.
Разбираетесь в дифференциальном криптоанализе — тогда welcome.
yleo
17.06.2019 21:11Если без шуток, то ваше "направлением мысли" НЕ в сторону логики, алгебры и метематики.
kunix
17.06.2019 23:57Будьте добры пояснить, куда же по-вашему идет мое направление мысли.
А то я теряюсь в догадках.yleo
18.06.2019 01:34Основная проблема в том, что «структура» S-box Кузнечика коррелирует со «структурами» других шагов алгоритма.
Для точности: Этот многострадальный S-box был сделан для Стрибога, а потом использован в Кузнечике.
Не могли бы мы чуть более подробнее пояснить, какие именно, на ваш взгляд, преобразования, структуры или шаги в Стрибог или Кузнечике "коррелируют" с процедурой генерации S-Box?
Это повышает вероятность того, что существует достаточно простое алгебраическое описание работы шифра.
Как уже писал "про лотерею" — наличие структуры можно считать доказанным фактом. Поэтому "достаточно простое алгебраическое описание" существует с такой достоверностью, что её вероятность крайне сложно повысить.
Тот, кому известно просто алгебраическое описание, может взламывать шифр.
Нет, это неверный вывод. Пока нет доказательств (наличия/отсутствия тех или иных свойств), никакое знание "просто формулы" не позволяет сделать подобных выводов (как и обратных).
Т.е. видя формулу модульной экспоненты, но не зная всего что "стоит за" RSA и самой проблемы факторизации (и её отсутствия в некоторых случаях), вы не сможете ничего сказать о стойкости.
Направление мысли понятно?
Нет (
SergeyMax
13.06.2019 17:43Непонятно, почему нельзя просто взять шумящий диод, и нагенерировать с его помощью этот злосчастный S-Box.
vvzvlad
13.06.2019 18:44Потому что сгенерированный случайно не обязательно будет равен хорошему. Случайность она на то и случайность, что там может попасться что-нибудь вроде «1,2,3,4,50», и это снизит стойкость. Поэтому случайно сгенерированные данные надо еще проверять.
Sergey_Cheban
14.06.2019 02:13Это-то как раз можно. Но при этом нужно что-то ответить на вопрос «А чем докажете, что вы туда бекдор не вставили?». Наши на этот вопрос отвечают что-то вроде «мамой клянёмся». Ок, такой ответ в принципе тоже возможен, хоть и не слишком убедителен. Но как тогда объяснить нашедшуюся структуру? Шумящий диод такого не генерирует.
По сути, если раньше просто не было оснований верить в отсутствие закладок в этом s-box, то сейчас появились серьёзные основания считать, что закладки таки есть.
mihmig
16.06.2019 10:57Государство — гражданам:
У суда нет оснований не доверять сотруднику полиции…
Технически подкованные граждане — государству:
У нас нет оснований доверять любым «алгоритмам» от государственных структур, не прошедшим независимый аудит.
safari2012
13.06.2019 17:45Кто бы мне популярно объяснил, что такое массивы s[] и k[] и какова их роль в алгоритме генерации и случайность происхождения?
Scratch Автор
13.06.2019 18:27Если совсем в двух словах — эти два массива параметризуют структуру под названием TKLog, о которой я писал в предыдущей статье. Разные значения в массивах дадут нам разные варианты структуры TKLog
safari2012
17.06.2019 17:17Ну, в прошлой статье, вы толком ничего не объяснили, сослались на «оригинал», причем не авторов стрибога, а того самого реверсера. Та статья совсем для узкого круга понятна, из неё я только понял, что алгоритм TKLOG как-то связан с Пи. Возможно, эти два массива констант вынуты оттуда же?
Не то, чтобы я придираюсь и занудствую. Но, эти два массива вынуты вами непонятно откуда, в оригинальной статье я таких последовательностей не нашел. Возможно, там был простенький их рассчет, но тогда не понятно, почему бы именно такой расчет не включить в программу?yleo
18.06.2019 03:15+1Рискну пока идут тесты ;)
Leo Perrin нашел "структуру", из чего следует что у Стрибог/Кузнечик есть определенные "свойства".
Эти свойства изложены в разделе 2.2 его статьи.
Что в этом "плохого" описано в разделе 2.3.
Если из предыдущего раздела и заключительного 2.4 попытаться сделать выводы, то:
- Основная проблема в том, что "структура есть", а авторы Стрибог/Кузнечник утверждали обратное.
- Условия для бэкдора (по методу из диссертации Арно Банье) в Кузненике не найдены.
- Взаимодействия s-box c линейныйм слоем (всем остальным) в Стрибог не понято.
- Векторы атак не найдены, но "подозрительно, ибо не понятно".
- Ай-я-яй, так нельзя...
koldyr
13.06.2019 18:53А ничего, что колмогоровская сложность определяется с точностью до константы и невычислима?
Похоже на передергивание фактов наукообразным способом.Scratch Автор
13.06.2019 19:07Можете пояснить?
koldyr
13.06.2019 19:12-1Для любой конечной последовательности существует интерпретатор, на котором программа, выводящая эту последовательность, занимает 1 бит.
Scratch Автор
13.06.2019 20:44Мы разве использовали такие интерпретаторы?
koldyr
13.06.2019 20:54Дело не в том, какой интерпретатор вы использовали, а в том, что колмогоровская сложность здесь не в тему.
Scratch Автор
13.06.2019 20:56Так себе у вас аргумент
koldyr
13.06.2019 21:08Согласен, не одноходовочка. Желающим разобраться придётся напрячься.
Scratch Автор
13.06.2019 21:12Как видите, уже разобрались и написали научную работу, и не одну. Куда им всем до гениев с хабра
koldyr
13.06.2019 21:28За всю работу не отвечу. Но в тот момент, когда зафиксировали интерпретатор (какой и как написано в статье), с колмогоровской сложности они перешли к чему-то другому. Причём они сами пишут, что язык играет критическую роль.
osmanpasha
13.06.2019 21:46Полагаю, такой вариант программы попадает под упомянутый в статье запрет использовать встроенные в язык и стандартную библиотеку константы, функции и прочее.
koldyr
13.06.2019 21:59Библиотеки под рукой нет, поэтому придётся сослаться на Википедию. В статье про колмогоровскую сложность написано: "С помощью принципа Дирихле легко показать, что для любой универсальной машины существуют алгоритмически случайные строки любой длины, однако свойство строки быть алгоритмически случайной зависит от выбора универсальной машины. "
osmanpasha
13.06.2019 20:42+1А почему, собственно, так важен объем программы, генерирующей блок? Какую ценность для криптографической науки несёт выкидывание пробелов из программы?
И ещё вопрос по сути статьи — правильно ли я понимаю, что если бы авторы честно сказали, что использовали такой вот алгоритм генерации, то никаких претензий из тех, что к ним сейчас предъявляют, к ним бы сейчас не было?
bolk
13.06.2019 20:48+1По всей видимости это подтверждает неслучайных характер выбранных чисел. Вроде достаточно очевидно, что для полностью случайной последовательности минимальная программа должна внутри себя просто содержать всю эту последовательность (так как закономерности нет). То есть для случайной последовательности генерирующая программа не может быть меньше последовательности (с оговоркой на читерство). А тут получается сделать меньше, да ещё в несколько раз.
osmanpasha
13.06.2019 21:40Ну просто в статье еще сказано, что блок Aes тоже алгоритмом сгенерирован, и ничего, норм вышло. (не имею никакого представления о том, какого размера там была программа)
bolk
13.06.2019 21:54+1Так авторы AES этого не скрывают. Штука в том, что в случае ГОСТа утверждается, что это не так.
Scratch Автор
13.06.2019 20:48+1Для криптографической науки несёт ценность тот факт, что таблица подстановок не была сгенерирована случайно. Чем меньше размер программы, тем более «неслучайно» она была сгенерирована
Sergey_Cheban
14.06.2019 02:24-1Тогда к ним были бы другие вопросы:
1. А почему вы использовали именно это, а не что-то более простое? Откуда вы взяли магическую строку "@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8"? Это ФИО разработчиков, или что?
2. Почему вы считаете, что этот s-box достаточно нелинеен? Из текста генератора это, мягко говоря, не очевидно.
AlexSbb
13.06.2019 20:45Для расчета S-Box Кузнечика удалось написть алгоритм который в 4 раза меньше самого S-Box. А что насчет AES и SM4, какие у них результаты?
mmMike
14.06.2019 07:35+1смешно когда наши доблестные ФСБшники включают школьников и говорят, что 11 лет назад этот алгоритм начинал разрабатываться чуть ли не в свободное время, поэтому они в итоге потеряли и сиды и скорее всего программу, которая генерировала таблицу подстановок.
А я в принципе верю. Это конечно не в плюс им.
Верю, глядя на некоторые сертифицированные (ФСБ) криптографические продукты рекомендованные для .....
Как вам например:
- Cпецификация с примерами на "C" с выражениями типа "int len = sizeof(str)", где "str" — указатель на строку!? (len дальше используется как размер строки для подписи!!)
- Или "аутентфикация" запроса (не шифрованного!) в протоколе (стандарта прошлого столения) внутри TCP/IP путем "секретного" константного пароля как одного из полей запроса. А что бы это секретный пароль вдруг не увидели в канале, то он XOR константной. И не строкой, а одним и тем же константным байтом каждого байта "секретного" б.ля пароля?
- А спецификация на протокол в внутри PDF. Которую 2 часа после copy|paste пришлось очищать от артефактов PDF?
И да… формуляры по документации все в лучших традициях. 90% воды и бюрократическ-военного стиля языка.
Честно… "За державу обидно".
Распилы сплошные.
vagran
14.06.2019 07:57Довольно странным выглядит подход с представлением алгоритма генерации на произвольном языке. Гораздо логичнее было бы для этой цели придумать некую специальную виртуальную машину с максимально компактным байт-кодом, и всем использовать её для подобных оценок.
saipr
14.06.2019 11:09Пока основные решения по криптографии принимаются в недрах закрытых
организаций, инсинуации на эту тему будут продолжаться, независимо от их
реальной достоверности.
mihmig
16.06.2019 10:59Процесс шифрования в блочном шифре можно представить простой формулой
C = M х K
где C — шифротекст, M — открытый текст, K — ключ шифрования, а x — блочный шифр.
Эта формула визуально похожа на школьную формулу линейного уравнения y = kx+b, графиком которой является прямая линия.
Вот, блджад мне ни разу не понятно, как от одной «формулы», «визуально» похожей (на самом деле совсем нет) перескочили к другой. Тут либо ТС не обладает компетенциями, либо «не гоже вам знать лишку».Scratch Автор
16.06.2019 15:26Можете объяснить нелинейность на пальцах проще и понятнее? Задача была передать смысл
mihmig
17.06.2019 09:37Я — не могу.
Претензия моего комментария в том, что правильное написание формулы
C=x(M,K)
грубо максируется под операцию умножения и притягивается «за уши» формула прямой на плоскости. Подозреваю, здесь идёт расчёт на то, что читатель запутается и бросит прослеживать ход рассуждений.
Но нет, въедливый читатель не бросит.Scratch Автор
17.06.2019 13:16-1Так что в итоге, я обманул кого-то? Это не научная статья, а её вольный пересказ для неподкованных читателей.
Критикуя — предлагай. Дайте мне лучшее объяснение и я заменю им своё, в чем проблема?
shifttstas
Я же верно понимаю, что это таблица подстановок генерируется каждый раз снова при установке защищённого канала? (По типу приватных ключей) или же она единая на всю систему/страну? И при определении (подборе) данной таблицы можно говорить о компрометации вообще любой криптографии основанной на кузнечике?
Scratch Автор
Эта таблица — константа. Она зафиксирована и общеизвестна. Но вот её характеристики вызывают много вопросов, т.к. это самый важный элемент всего алгоритма
shifttstas
Понятно, т.е она константа вычисляемая кодом
на основе алгоритма, который (предположительно) выдаёт прогнозируемый результат?
Scratch Автор
Таблица была встроена в Кузнечик просто как магический набор чисел. То, что внутри неё есть структура или «алгоритм» выяснилось позже благодаря реверс инжинирингу. Мы не знаем зачем он там, в этом вся загвоздка
shifttstas
А, понятно, т.е там даже не кодом вшита а прямо массивом чисел, это удивительно.
Scratch Автор
Это распространенная практика, но от неё потихоньку уходят
CryptoPirate
Я бы так не сказал, Sbox'ы как раз обычно (в софте) большой таблицей вбивают, а не вычисляют. Или вы про «от неё потихоньку уходят» имеете в виду «как была сгенерирована таблица»?
Scratch Автор
именно
shifttstas
А каким образом если будет установлено, что sbox не случайный — это поможет взлому или докажет Бэкдор? Мне кажется этого не хватает в посте.
yleo
Собственно уже установлено что sbox не случайный, ибо вероятность подобных совпадений — примерно как выиграть во все лотереи по одному билету (набору цифр).
Говорить о бекдоре и "поможет взлому" — нельзя без доказательств, т.е. будет крайней желтизной. Надо отдать должное Scratch за то что не перешел эту грань (хотя рядом) и в статье всё есть, включая основной вопрос — Зачем отрицалось наличие структуры.
Тем не менее, всё таки стоит явно отметить, что наличие структуры в sbox — это не плохо и не хорошо само по себе, а не-идеальные mix/max нелинейности не облегчают атаки.
JohnDoe_71Rus
Если таблица «не секрет», зафиксирована и общеизвестна. В чем опасность что ее можно сгенерить алгоритмом в четверть самой SBox?
Для задачи дешифрования/поиска ключа эта часть уже известна. Только экономия кода для программы.
Scratch Автор
Где гарантия, что этот алгоритм при определенных условиях не превратит SBox в линейный?
Yaris
Если я правильно понимаю ситуацию, опасность в том, что авторы соврали насчёт алгоритма получения таблицы. Из этого запросто может следовать, что реально использованный алгоритм реализует ещё какие-то ограничения на таблицу. В качестве одного такого ограничения — и вот тут опасность переходит в практическую плоскость — может быть существование «линеаризации» S-Box с помощью того же или иного известного (тому, кому надо) алгоритма.
Sheti
Проблема в том, что неслучайность SBox может оказаться намеренной и остаблять сам алгоритм шифрования например создавая целый класс слабых ключей.
yleo
Осмелюсь повторить, что умеренное ослабление — крайне маловероятно, мягко говоря, ибо 275 УК как "Деятельность, направленной против безопасности Российской Федерации").
Т.е. вижу примерно один сценарий (авторы Стриборг/Кузненик получили готовый или исправленный SBOX и были не в курсе его структуры). Как вариант, возможно повторение истории.
Whuthering
Безопасность страны и безопасность отдельных ее граждан — мягко говоря, немного разные вещи.
usdglander
Когда разработчики DES (Да, того самого 1977 года) отправили алгоритм в АНБ, то АНБ полностью переработало все SBox (коих, к слову, 8 штук). Лет через 10, после того как был открыт дифференциальный криптоанализ (ну или стал общеизвестен) выяснилось что переработанные SBox устойчивы и к нему, а вот изначальные снижали стойкость шифра к этому методу. Так что структура всё таки важна. Кроме того есть целая система оценки нелинейности SBox и там требований и матана чуть больше чем… очень много.
Deosis
Проблема в том, что специально подобранный SBox превращается в маленький "асимметричный" шифр. Который снижает стойкость всего алгоритма шифрования.
Если это так, то тот, у кого находится "закрытый" ключ от SBox, может проводить эффективную атаку на криптоалгоритм.
Если SBox можно сгенерировать с помощью 58 байт, то, возможно, придется перебирать только 2^58 вариантов для поиска ключа вместо 2^256 вариантов.