On probability characteristics of random graphs generated by algorithms for finding hash function collisions.pdf В алгоритмах поиска коллизий некоторых хэш-функций семейства MDx (см., например, SHA-1 [1] и RIPEMD [2, 3]), встречается процедура A, которую можно смоделировать случайным процессом Г^. Данный случайный процесс строит корневое дерево G максимальной глубины N. При этом некоторые из вершин дерева G оказываются помеченными как плодоносящие, и только плодоносящие вершины могут иметь потомков. Процесс Г^ считается успешным, если он построит дерево G глубины ровно N и последняя вершина на глубине N, которую сформирует процесс, окажется помеченной как плодоносящая. У процесса rN имеется два набора параметров {pk}k=N и {nk}j1=N, где 0 ^ pk ^ 1 и nk Е N. Формально процесс rN({pk}k=N; {nk}k=N) описывается с помощью следующей рекурсивной процедуры. На вход процессу подается корневая вершина R. Сначала процесс с вероятностью pn помечает её как плодоносящую. Если R оказалась непомеченной, то процесс завершает неуспешно свою работу и в качестве построенного графа возвращает лишь непомеченный корень R. Если же R оказалась помеченной как плодоносящая, то процесс строит её первого потомка R1 и передает его в качестве корневой вершины производному процессу rN-1({pk}k=N_ 1; {nk}k=N_ 1). Если производный процесс завершился успешно, то и процесс rN({pk}k=N; {nk}k=N) также завершается успешно, иначе он строит второго потомка R2 и для него снова запускает производный процесс rN-1({pk}k=N-1; {nk}k=N- 1). Всего может быть построено максимум nN потомков R1,... , RnN. Если для каждого из них производный процесс завершился неуспешно, то и процесс rN({pk}k=N; {nk}k=N) также завершается неуспешно. Пограничный процесс Г0 (p0; 0) никаких потомков не строит, он просто помечает с вероятностью p0 корневую вершину как плодоносящую. Обозначим через Pi вероятность успешного завершения процесса ri({pk}k=i; {nk}k=i). Несложно показать, что для вероятностей Pi выполняется следующее рекуррентное соотношение: (1) Pi = pi(1 - (1 - Pi-1)ni), при этом из определения очевидно, что P0 = p0. C помощью формулы (1) можно вычислить вероятность успеха Pn процедуры A. На практике [1-3] алгоритмы поиска коллизий запускают процедуру A несколько раз до первого успеха и в качестве меры эффективности всего алгоритма берётся его средняя трудоёмкость, которая равна величине ET(A)/PN, где T(A) — трудоёмкость процедуры A. В качестве меры трудоёмкости процедуры A, в свою очередь, служит мощность множества вершин V(G) построенного графа G. Таким образом, практически важной величиной является отношение EV(G)/Pn , для вычисления и оценки которого доказана теорема 1. Теорема 1. Имеют место следующие соотношения: EV(G) _ N 1 PN i N 1 N 1 N 1 Из теоремы 1 следует, что для минимизации средней трудоёмкости алгоритмов поиска коллизий, использующих процедуру A, параметры nk необходимо выбирать как можно больше, если на них нет других ограничений.

Скачать электронную версию публикации