Об аргументации отсутствия свойств случайного оракула у некоторых криптографических хеш-функций | Прикладная дискретная математика. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/30

Об аргументации отсутствия свойств случайного оракула у некоторых криптографических хеш-функций

Представлены новые алгебраические атаки на хеш-функции вида MD4-k, где k - число шагов базового алгоритма MD4, 39 ^ k ^ 48. Для решения алгебраических уравнений используются SAT-решатели. Представленные атаки демонстрируют отсутствие свойств случайного оракула у рассматриваемых хеш-функций. Более точно, мы строим оценки доли легко обратимых выходов этих функций и показываем, что даже для полнораундовой функции MD4 эта доля весьма высока. Для построения оценок с каждой функцией вида MD4-k связывается специальная функция, длина входа которой существенно меньше 512. Показано, что любое значение такой функции является значением MD4-k. Задача обращения специальной функции, как правило, существенно проще, чем задача обращения MD4-k. Оценка доли векторов в {0,1}128, являющихся значениями специальной функции, даёт оценку доли легко обратимых значений исходной функции MD4-k.

On the argument of the absence of properties of a random oracle for some cryptographic hash functions.pdf Случайный оракул - это гипотетический объект, обладающий рядом привлекательных с точки зрения криптографии свойств. Строго (см., например, [1]) случайный оракул определяется как отображение вида O : {0,1}* ^ {0,которое произвольному конечному двоичному слову сопоставляет слово, являющееся бесконечной последовательностью испытаний Бернулли с p = 1/2. Однако такое определение полностью неконструктивно. Для практических приложений необходимы функции вида {0,1}* ^ {0,1}* или даже {0,1}n ^ {0,1}m, которые обладают (гипотетически) свойствами случайного оракула, но могут быть заданы посредством некоторых алгоритмов. Более точно, требуется, чтобы алгоритм, задающий функцию, был детерминированным (то есть выдавал одинаковые выходы для одинаковых входов). Почти все выходы (длины m) функции, выполняющей роль случайного оракула, должны выглядеть как последовательности Бернулли с p = 1/2. Соответственно для случайно сгенерированного входа такой функции сложность задачи обращения соответствующего выхода должна быть сопоставима со сложностью повторения фиксированной последовательности Бернулли в результате m-кратного подбрасывания идеальной монеты. Существование случайных оракулов вида O : {0,1}n ^ {0,1}m было бы чрезвычайно полезно для многих криптографических приложений. Скажем, некто может сгенерировать свой секретный идентификатор a £ {0,1}n, а затем многократно доказывать свою аутентичность, используя a и несекретный алгоритм O. В [1] отмечено, что на роль реальных прототипов случайного оракула подходят стойкие криптографические хеш-функции. Эта идея получила серьезное развитие в [2, 3], после появления которых возникло целое направление, известное как «доказательства в модели случайного оракула». В настоящей работе показано, что некоторые известные криптографические хеш-функции не обладают свойствами случайного оракула. Более точно, будем рассматривать задачу обращения криптографической хеш-функции h : {0,1}* ^ {0,1}C. Такие функции обычно разбивают хешируемое сообщение на блоки фиксированной длины n, соответственно рассматриваются задачи обращения функций вида / : {0,1}n ^ {0,1}C (для функций из семейств MD и SHA n = 512). Основная цель работы - показать для некоторых криптографических хеш-функций, что легко обратимые выходы этих функций составляют значительную долю в {0,1}C. Интуитивно, любая такая функция h не может быть случайным оракулом, поскольку выбор случайного входа a с высокими шансами даст выход Y, обращение которого потребует меньше вычислительных ресурсов, чем простой подбор такого a' £ {0,1}n, что h(a') = 7. Будем исследовать хеш-функции вида MD4-k, где k - число базовых шагов алгоритма MD4 [4]. В основе описываемых далее атак лежат результаты [5, 6]. Основная идея этих атак заключается в использовании «ослабляющих ограничений». Впервые использовать подобные ограничения предложил Г. Доббертин в [7]. Новизна подхода из [5, 6] заключается в том, что ослабляющие ограничения строятся в автоматическом режиме в процессе решения задачи оптимизации специальной псевдобулевой функции [9], оценивающей некоторую эвристическую меру эффективности соответствующих ограничений. Ослабляющие ограничения - это нулевые значения некоторых переменных сцепления (chaining variables). Изначально Г. Доббертин предложил приравнять произвольной константе значения 12 переменных сцепления, используемых в первых двух раундах алгоритма MD4. Для решения получающейся системы булевых уравнений Г. Доббертин предложил алгоритм, позволяющий обращать на персональном компьютере функцию MD4-32. В [8] описан, по сути, вариант атаки Доббертина (т. е. ослабляющие ограничения накладываются на те же переменные сцепления), в котором для решения уравнений используется SAT-решатель, а для построения ослабляющих ограничений - константа 0. При помощи метода, предложенного в [5, 6], удалось построить различные виды ослабляющих ограничений, среди которых оказались такие, которые дали существенно более эффективную атаку на MD4-39, чем в работе [8]. Один из наборов ослабляющих ограничений из [5, 6] позволил обращать менее чем за 1 мин работы SAT-решателя MINISAT2.2 примерно 65% случайных векторов из {0,1}128, рассматривая их как значения функции MD4-39. Анализируя различные ослабляющие ограничения, построенные в [5, 6], можно заметить, что с исходной обращаемой функцией вида /MD4-k : {0,1}512 ^ {0,1}128 естественным образом связываются специальные функции вида gMD4-fc : {0,1}d ^ {0,1}128, обладающие целым рядом интересных свойств (через Л здесь обозначен булев вектор, задающий некоторый набор ослабляющих ограничений). Во-первых, любое значение функции gMD4-fc является значением функции /md4-&. Во-вторых, что очень важно, d может оказаться существенно меньше, чем 512. Так, один из векторов ослабляющих ограничений для задачи обращения /md4-39, обозначаемый Л1, даёт функцию gM1D4-39 : {0,1}128 ^ {0,1}128. Наконец, если y - значение функции вида gMD4-k и а' Е {0,1}d - его прообраз, то от а' можно эффективно перейти к такому а Е {0,1}512, что /MD4-fc (а) - Y. Функции вида gMD4-k могут быть определены не всюду на {0,1}d и далеко не каждый y Е {0,1}128 является образом функции gMD4-k. Однако задача обращения функции gMD4-fc может оказаться существенно проще, чем задача обращения /md4-&. Так, на обращение каждого значения функции gM1D4-39 тратится менее минуты работы обычного последовательного SAT-решателя MINISAT2.2. При этом примерно 65% векторов из {0,1}128 имеют gMD^^-прообразы. Сказанное означает, что примерно 65% выходов функции MD4-39 являются легко обратимыми, поскольку такова доля выходов MD4-39, совпадающих с выходами функции gM1D4-39. Это означает, что MD4-39 не удовлетворяет свойствам случайного оракула, поскольку, выбрав случайный вход а Е {0,1}512, с вероятностью ~ 65% получим y - /MD4-39(a), который имеет gM1D4-39-прообраз. Найдя этот прообраз, мы эффективно построим по нему такой а Е {0,1}512, что /MD4-39 (а) - Y. В таблице представлены ослабляющие ограничения, задающие функции вида gMD4-fc, для которых задачи обращения решаются в среднем за время < t при помощи однопоточного SAT-решателя. Ослабляющие ограничения d k t, с Ai 000000000000011011101110111010000000000000000000 128 39 12 А2 000000000000011011101110111011000000000000000000 96 43 4,5 A3 000000000000111011101110111010000000000000000000 96 44 20 А4 000000000010111111011101110100000000000000000000 64 41 5,7 А5 000000000000111011101110111011000000000000000000 64 47 914 Аб 000000000000111011101110111011100000000000000000 32 48 509 В таблице приведены булевы векторы Л^ Е {0,1}48, i Е {1,..., 6}, задающие ослабляющие ограничения в форме значений «переменных переключения» [5, 6]: единичные компоненты вектора Л^ означают, что переменные сцепления, вычисляемые на шагах с соответствующими номерами, заменяются в системе уравнений, кодирующей криптоанализ функции MD4-k, 32-битной константой K - 0. Каждый такой набор ослабляющих ограничений позволяет построить семейство специальных функций вида gMD4-k : {0,1}d ^ {0,1}128. Так, например, вектор Л3 задаёт набор ослабляющих ограничений, в которых константой K - 0 означиваются переменные сцепления, вычисляемые на шагах с номерами 13, 14, 15, 17, 18, 19, 21, 22, 23, 25, 26, 27, 29. Для Л3 можно построить специальные функции вида gM3D4-k : {0,1}96 ^ {0,1}128. Для k - 44 функция gM3D4-44 определена на ~ 50 % случайных входов, а задача обращения дМ3Б4-44-образа случайного входа из {0,1}96 решается за время ^ 20 с работы SAT-решателя MINISAT2.2. Для соответствующих входов доказывается отсутствие коллизий за относительно небольшое время работы MINISAT2.2 (все эксперименты проводились на вычислительном кластере «Академик В. М. Матросов» ИДСТУ СО РАН [10]). Следовательно, доля значений функции дМм-44 в {0,1}128 составляет приблизительно 2-32. Это означает, что вероятность для случайно выбранного входа из {0,1}512 получить легкообратимое значение функции MD4-44 составляет примерно 2-32 - весьма большая вероятность в сравнении с 2-128. Таким образом, функция MD4-44 не удовлетворяет свойствам случайного оракула. Интересно, что для полнораундовой функции MD4 (т. е. функции MD4-48) доля легко обратимых значений, как следует из шестой строки таблицы, составляет 2-96, что тоже недопустимо много для случайного оракула.

Ключевые слова

криптографические хеш-функции, поиск прообразов хеш-функций, MD4, MD4-39, SAT, cryptographic hash functions, preimage attack on hash functions, MD4, MD4-39, SAT

Авторы

ФИООрганизацияДополнительноE-mail
Грибанова Ирина АлександровнаИнститут динамики систем и теории управления им. В. М. Матросова СО РАНаспиранткаthe42dimension@gmail.com
Семёнов Александр АнатольевичИнститут динамики систем и теории управления им. В. М. Матросова СО РАНандидат технических наук, доцент, заведующий лабораторией 6.2biclop.rambler@yandex.ru
Всего: 2

Ссылки

Bellare M. and Rogaway P. Random oracles are practical: a paradigm for designing efficient protocols // Proc. CCS'93. N.Y.: ACM, 1993. P. 62-73.
Pointcheval D. and Stern J. Security proofs for signature schemes // EUROCRYPT'96. LNCS. 1996. V. 1070. P. 387-398.
Pointcheval D. and Stern J. Security arguments for digital signatures and blind signatures // J. Cryptology. 2000. V. 13. No. 3. P. 361-396.
RivestR.L. The MD4 message digest algorithm // CRYPT0'90. LNCS. 1990. V. 537. P. 303-311.
Gribanova I. and Semenov A. Using automatic generation of relaxation constraints to improve the preimage attack on 39-step MD4 // Proc. MIPR0-2018. IEEE, 2018. P. 1174-1179.
Грибанова И. А. Новый алгоритм порождения ослабляющих ограничений в задаче обращения хеш-функции MD4-39 // Прикладная дискретная математика. Приложение. 2018. №11. С. 139-141.
Dobbertin H. The first two rounds of MD4 are not one-way // Proc. FSE'1998. LNCS. 1998. V. 1372. P. 284-292.
De D., Kumarasubramanian A, and Venkatesan R. Inversion attacks on secure hash functions using SAT solvers // Proc. FSE'2007. LNCS. 2007. V.4501. P. 377-382.
Boros E. and Hammer P. L. Pseudo-boolean optimization // Discr. Appl. Math. 2002. V. 123(1-3), P. 155-225.
Иркутский суперкомпьютерный центр СО РАН. http://hpc.icc.ru.
 Об аргументации отсутствия свойств случайного оракула у некоторых криптографических хеш-функций | Прикладная дискретная математика. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/30

Об аргументации отсутствия свойств случайного оракула у некоторых криптографических хеш-функций | Прикладная дискретная математика. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/30