Применение инверсных лазеек для построения атак из класса &quot;угадывай и определяй&quot; на хеш-функции семейства MD4

Грибанова, Ирина Александровна; Семенов, Александр Анатольевич

Применение инверсных лазеек для построения атак из класса "угадывай и определяй" на хеш-функции семейства MD4

Грибанова, Ирина Александровна, Семенов, Александр Анатольевич

Дата публикации: 2020

Дата публикации в реестре: 2020-10-01T12:54:44Z

Аннотация:

Приведены новые атаки из класса «угадывай и определяй» для хеш-функций вида MD4-k, k > 39. Описываемые атаки основаны на концепции инверсной лазейки. Для решения задач криптоанализа, ослабленных подстановками угадываемых бит, используются SAT-решатели. Задача поиска инверсной лазейки, обеспечивающей атаку с относительно малой трудоёмкостью, ставится в форме задачи минимизации специальной псевдобулевой функции. Для её решения используются три метаэвристических алгоритма: алгоритм поиска с запретами, (1+1)-FEAe и специальный вариант генетического алгоритма. Перечисленные алгоритмы дают атаки на рассматриваемые функции с близкими оценками трудоемкости. Для функции сжатия полнораундового MD4 лучшие атаки строит генетический алгоритм.

Ключевые слова:
задача поиска прообразов криптографической хеш-функции, атаки из класса "угадывай и определяй", инверсные лазейки

Тип: статьи в сборниках

Источник: Прикладная дискретная математика. Приложение. 2020. № 13. С. 124-129