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

Криптографическая хеш-функция MD5 предложена в 1992 г. Ключевым компонентом MD5 является 64-шаговая функция сжатия. До сих пор не представляется возможным обратить функцию сжатия MD5 за реальное время, поэтому зачастую в данном контексте анализируются версии с сокращённым количеством шагов. В 2007 г. с помощью алгоритмов решения проблемы булевой выполнимости (SAT) была обращена 26-шаговая функции сжатия MD5. В 2012 г. с помощью SAT были обращены 27- и 28-шаговые версии. В настоящем исследовании предлагается подход к формированию 32 промежуточных задач обращения между парой последовательных шагов функции сжатия MD5. С помощью этого подхода построены промежуточные задачи обращения между 28 и 29 шагами. Несколько простых задач использованы для параметризации современного SAT-решателя, в результате чего впервые обращена 29-шаговая функция сжатия MD5.