Регистрация25.10 // Н.Куртуа пытается доказать невозможность создания стойких S-блоков для ГОСТ-28147-89
ГОСТ 28147-89 — широко известный блочный шифр, являющийся стандартом Российской Федерации. Он претендует на альтернативу для AES-256 и 3-DES и с 2010 года его пытаются провести через процедуру прохождения международной стандартизации в комитете международной организации по стандартизации для стандарта ISO 18033.
До 2010 года большинство исследователей считали ГОСТ стойким, а 20-летние попытки криптоанализа — безуспешными. В 2011 было неожиданно открыто множество разных типов атак на ГОСТ: атаки на рефлективных свойствах, атаки с двойным отражением, угадывание с подтверждением без использования рефлективных свойств, улучшенные дифференциальные атаки. Последним шагом большинства атак для восстановления ключа было использование различных классов программно-алгебраических атак, атак встречи посредине и дифференциальных атак угадывания с подтверждением битов ключа.
Если отбросить крайнюю сложность этих атак по количеству требуемых данных и учитывать только время исполнения, то до октября 2011 самой быстрой была атака Куртуа за 2216 шагов. Затем Шамир и др. улучшили эту атаку до значения 2192, что было представлено на конференции FSE 2012. Новая улучшенная дифференциальная атака Куртуа, представленная в его последней работе, многократно снижает стойкость ГОСТ (до уровня 2178) и требует всего одного ключа для полнораундовой версии шифра.
Следует отметить, что на сегодняшний момент для AES в таких условиях известны лишь атаки, снижающие его стойкость по сравнению с полным перебором лишь на несколько битов. Однако, следует отметить и то, что Куртуа снова прибегает к своему излюбленному приёму — исчерпанию полной кодовой книги шифра, исходя из размеров блока. Атака требует 264 известных открытых текстов и 270 затрат памяти. Получение такого объёма открытых текстов при таких размерах блока позволит противнику читать сообщения даже зашифрованные идеальным шифром, хотя и без восстановления ключа. Однако, для доказательства быстрого прогресса в криптоанализе с восстановлением ключа эта атака подходит.
В работе также указывается на опасность многоключевых атак: редко когда шифр используется для шифрования огромного числа данных на одном ключе, а использование многих ключей снижает количество требуемых данных до обозримого 232 и 2148 вычислений на ключ, но работает не против всех ключей.
Наиболее интересно предположение Н. Куртуа о бесполезности попыток создания стойких S-блоков для ГОСТ:
Ключевой момент, который мы хотим здесь донести, это то, что класс этих дифференциалов НЕ зависит от S-блоков сколько-нибудь значительно, они больше зависят от структуры шифра и точных связей внутри него. Это особенно важно для множеств, включающих множество дифференциалов, такие как изученные в данной работе, когда отдельные очень сильные дифференциалы становятся слабее.
Обычное заблуждение состоит в том, что безопасность такого шифра как GOST против дифференциального криптоанализа (DC) существенно зависит от S-блоков и какие-то "оптимальные" S-блоки могут сделать его более безопасным, см. [18, 20]. Исследователи в научном сообществе изучают S-блоки по отдельности [18] и предлагают новые шифры [18, 20], но когда S-блоки объединяются вместе, всё становится по другому. Мы не уверены, возможно ли вообще сделать такой шифр как ГОСТ устойчивым к дифференциальному криптоанализу за счёт замены только S-блоков [18, 20], идея чего обсуждалась в ходе процесса стандартизации ГОСТа в ISO. Вопрос, как далеко мы можем продвинуться в улучшенных дифференциальных атаках, таких, как изученных в данной работе, остаётся широко открытым.
Мы полагаем, что безопасность ГОСТ против улучшенных форм DC зависит "по существу" от связей в шифре и хотя некоторые S-блоки могут его сделать более слабым против DC, никакие из них не сделают его по настоящему более сильным.
P.S. Данная новость приведена на основе текущих дополнений и уточнений в ревизии работы, ранее рассмотренной в марте 2012.
Источник: Cryptology ePrint Archive
комментариев: 9796 документов: 488 редакций: 5664
Во-первых, для случайных S-блоков, с более-менее равномерным распределением, а то так таблицу результатов операций XOR или ADD тоже можно назвать S-блоком, хотя там сплошная линейность.
Во-вторых, начиная с размера S-блока 8x8, а не 4x4, как в ГОСТ.
В-третьих, в четвёртых, в n-ых есть ещё куча факторов, которые и стараются подбирать оптимально, с соответствующими доказательствами, а не тупо наращивать по всем параметрам.
Вот в AES доказано, что вероятность нахождения дифференциальной раундовой характеристики должна быть менее такого-то числа. Опубликование одной храктеристики, которая при подстановке даёт другое (большее) число — это взлом. Само предъявление такой характеристики — факт, не требующий доказательств, а опровергающий доказательства стойкости. Доказательство взлома при возможности проверки не самого взлома, а параметров прохождения характеристики через раунды не требуется.
Почему врут. Это тривиальный факт, от которого ГОСТу никак не легче.
Наверно, некоторые под доказательством понимают техническую проверку в лоб.* Математические расчёты их не удовлетворяют. По такой логике расстояние до Марса вообще неизмеримо, потому что никто с линейкой-рулеткой до туда не добирался, а все косвенные способы измерения — вами критикуемые "факты". Вот эту задачу тоже никто не проверял. Может, врут, что понадобится куб с пшеницей размером 10км×10км×15км?
*Наука как раз создавалась для того, чтобы такую проверку проводить лишь в исключительных случаях, а то бы вы до сих пор объём любого тела вёдрами с водой мерили.
Врут. Ибо 10кмх10кмх15км — это никак не куб.
Для взлома одного ключа это вполне практический факт. Можно ввести характерное основание числа операций: 2^30=миллиард. Частота современного процессора это доли наносекунды, секунда дает миллиард элементарных операций процессора – это первый миллиард. В году примерно 30 миллионов секунд, значит 30 лет (вполне достижимой срок работы) это миллиард секунд – это второй миллиард. Объемы современного производства процессоров исчисляются миллардами штук – это третий миллиард. Миллиард современных процессоров за 30 лет вычислений дадут искомые 2^90 операций.
Потом, а какого спрашивается х.. процессор с миллиаром, а то и триллионом, транзисторов должен использовать в каждый момент времени только малую их часть? Вполне можно заставить работать все эти миллиарды транзисторов процессора одновременно – это четвертый миллиард. Так что человечеству вполне по плечу выполнить 2^120 операций.
Если не изобретать велосипед, то всё уже сказано и посчитано.
комментариев: 9796 документов: 488 редакций: 5664
Не спорю, но у Куртуа нет доказательств – нечего проверять, а китайцы хоть и пишут не очень понятно, но хотя бы пишут – есть что проверять! Куртуа же просто утверждает: "факт: мы можем ...". Какие-то наши исследователи докладывались на РусКрипто: они проверили некоторые "факты" Куртуа и кое-какие ключевые не подтвердились! Он утверждал, что проверил это с помощью компьютерного моделирования, поэтому проверить это можно ТОЛЬКО с помощью такого же моделирования. Причем один из фактов, судя по простым оценкам, он "моделировал" несколько месяцев. Если, конечно, у него не было под боком маленького суперкомпьютера.
комментариев: 9796 документов: 488 редакций: 5664
Открываете его работу с так раздражающим словом факт. Подставляете дифференциал, который дан как факт без доказательств. Прогоняете по всем шагам одной из его атак (вроде расписано подробно). Если получается различитель за определённое число шагов, сравниваете с его результатом. Большинство атак вроде должны обходиться без особо навороченных вычислений. Не верю, что из работы вообще ничего нельзя проверить.
Скрещивание этих атак с алгебраическим криптоанализом — это действительно мутная тема, он публиковал (или рассылал) свои эксклюзивные программные наработки. Работали на простом компе, но выжирали много памяти. Можно попросить выслать. Ну не верится, что вся работа — липа. Он мог самые пробивные атаки нераскрыть, а основа для нахождения различителя — проверяема, тем более уже несколько групп исследователей подтвердили.
Опять же, местечковое РусКрипто — это хорошо, но никак не влияет на его репутацию. Могли бы опубликовать развёрнутую критику в IACR или хотя бы в ArXiV для обсуждения. Даже пустая работа привлекла бы внимание: "смотрите, Куртуа врёт".
Вы что, этот IACR и arXiv — американские сервера, а с чего это Великая Империя будет преклоняться перед американцами? Ну, arXiv — точно американский, причём он Лос Аламосовский был изначально, т.е. от института, который работал на оборонку и против СССР. Так что пусть вся мировая общественность переводит свои результаты на русский и посылает их на престижную конференцию РусКрипто, проводящуюся под пристальным вниманием и присутствием лучшей шифровальной спецслужбы мира — ФСБ.
Гость (12/08/2013 12:39), я всё правильно сказал?
комментариев: 9796 документов: 488 редакций: 5664
Алексеев Евгений К. жжот: сначала на pgpru, потом на родном криптопро.
Нет, их только на блог криптопро хватило, и то только на русском. У людей серьёзный бизнес™, а вы им про IACR какой-то говорите...