Построение коллизии для 75-шаговой версии хэш-функции sha-1 с использованием



Pdf просмотр
Дата13.02.2017
Размер2.17 Mb.
Просмотров160
Скачиваний0

Построение коллизии для 75-шаговой версии хэш-функции SHA-1 с использованием
ГПУ-кластеров
Е.А. Гречников
1
, А.В. Адинец
2,3
МГУ им. М. В. Ломоносова, механико-математический факультет
1
,
Научно-исследовательский вычислительный центр МГУ им. М. В. Ломоносова
2
,
Объединённый институт ядерных исследований
3
Криптографические хэш-функции, в частности, SHA-1, в настоящее время ши- роко используются в современных информационных технологиях. Важным свой- ством таких функций является устойчивость к коллизиям, т.е. сложность постро- ения двух различных входных сообщений, значения хэш-функции от которых совпадают. Мы развиваем метод разностных (дифференциальных) атак для по- иска коллизий хеш-функции SHA-1 и её сокращённых вариантов. В данной ста- тье описывается реализация метода характеристик для хэш-функции SHA-1 на кластере из графических процессоров. Использование различных оптимизаций позволило достичь эффективности ГПУ-реализации 50%, и ускорения в 39 раз по сравнению с реализацией на одном ядре ЦПУ. Оптимизации также включали мо- дификацию метода поиска характеристик. На текущий момент наши улучшения метода и использование ГПУ-раздела суперкомпьютера �Ломоносов� позволили найти коллизию для SHA-1, сокращённой до 75 шагов (полная функция состоит из 80), что является мировым рекордом.
1. Введение
В современной криптографии широко используются различные хеш-функции. Хеш- функция есть функция, отображающая сообщения (строки из 0 и 1) произвольной длины в последовательности из 0 и 1 ограниченной длины � значения хеш-функции или хеш- значения. Значение хеш-функции есть как бы отпечаток всего сообщения, а роль его по- добна отпечаткам пальцев в процессе идентификации.
Для любой хеш-функции существуют сообщения, имеющие одинаковые хеш-значения,
ведь множество сообщений бесконечно, а множество хеш-значений конечно. Если удаёт- ся явно построить два различных сообщения, имеющие совпадающее хеш-значение, иначе говоря, построить коллизию, то хеш-функция считается скомпрометированной, что имеет разрушительные последствия для некоторых криптографических приложений.
Хеш-функция, обозначаемая SHA-1 (Secure Hash Algorithm), преобразует сколь угод- но длинные сообщения (в стандарте максимальная длина равна 2 64
− 1 бит) в 160-битные хеш-значения. Эта хеш-функция была опубликована NIST (National Institute of Standards and Technology) в США в 1995 г. и в настоящее время используется как важная составная часть различных государственных и индустриальных стандартов безопасности, таких как электронная цифровая подпись, аутентификация пользователей, обмен ключами и постро- ение псевдослучайных последовательностей. SHA-1 внедрена почти во все коммерческие системы безопасности.
В течение ряда лет в различных странах предпринимаются активные попытки компро- метации функции SHA-1, и, хотя коллизия для этой функции не построена, исследователи продвинулись в этой деятельности достаточно далеко. В настоящее время NIST проводит конкурс на построение новой хеш-функции, которая смогла бы заменить SHA-1. Предпола- гается ввести новую функцию в действие в 2012 году.
Криптоаналитические задачи, как правило, достаточно легко распараллеливаются на любое доступное количество вычислительных ресурсов. Поэтому тем более логично ис-
111
пользовать ГПУ для решения таких задач. И хотя ГПУ активно используются для задачи подбора пароля [1], нам не встречались случаи использования ГПУ для поиска коллизий для хэш-функций.
Наша цель � построить коллизию хеш-функции SHA-1. На настоящий момент с исполь- зованием ГПУ-раздела суперкомпьютера �Ломоносов� мы установили мировой рекорд [3],
построив коллизию для хеш-функции, устроенной аналогично SHA-1, но с меньшим значе- нием одного из параметров схемы: 75 шагов вместо 80 шагов в SHA-1.
Вклад данной статьи можно кратко описать следующим образом:
• Нами впервые предложена реализация поиска коллизий для хэш-функций, использу- ющая графические процессоры
• При помощи нашей реализации построена коллизия для 75-раундовой версии SHA-1,
что на данный момент является мировым рекордом
Данная статья организована следующим образом. В разделе 2 описывается устройство хэш-функции SHA-1. В разделе 3 описывается устройство разностных атак, в том числе применительно к хэш-функции SHA-1, а в разделе 4 описывается используемый алгоритм поиска характеристики. Особенности ГПУ-реализации приводятся в разделе 5, а в разделе
6 описываются проведённые расчёты и приводится полученная коллизия. Наконец, раздел
7 содержит подведение итогов и благодарности.
2. Хэш-функция SHA-1
Используемые в настоящей статье в формулах обозначения приведены в таблице 1
Хеш-функция SHA-1 [2] устроена следующим образом. В конец входного сообщения опре- делённым образом добавляется несколько бит, зависящих от длины сообщения, так, чтобы результат состоял из нескольких 512-битных блоков M
1
, . . . , M
k
. 160-битное хеш-значение представляет из себя набор из 5 32-битных переменных, для вычисления которых к началь- ному набору H
0
последовательно �подмешиваются� блоки M
i следующим образом: для i = 1, . . . , k вычисляется H
i
= H
i
−1
+ g(M
i
, H
i
−1
)
. Константа H
0
является частью стандар- та. Хеш-значением входного сообщения является H
k
Таблица 1
. Обозначения, используемые в данной статье
Обозначение
Описание
X
32-битное число, связанное с первым сообщением
X

32-битное число, связанное со вторым сообщением
X
2
пара 32-битных чисел (X, X

)
X
⊕ Y
побитовое исключающее ИЛИ (XOR)
X + Y
сложение по модулю 2 32
[X]
i i
-й бит числа X (i = 0 � младший бит)
X
≪ i циклический сдвиг влево на i бит
X
≫ i циклический сдвиг вправо на i бит
Для нахождения коллизии достаточно построить два набора (M
1
, . . . , M
k
)
и (M

1
, . . . , M

k
)
одной и той же длины, для которых H
k
= H

k
. Поскольку длины одинаковы, то биты, до- бавляемые в конец сообщений при вычислении SHA-1, также будут одинаковы, так что последующие значения H
i и H

i совпадут.
Сжимающая функция g(M, H) строит новое 160-битное значение по старому 160-битному значению H и 512-битному блоку сообщения M. Входные и выходные данные представля- ются как 32-битные переменные, H = (A
0
, B
0
, C
0
, D
0
, E
0
)
, M = (M
0
, . . . , M
15
)
, g(M, H) =
112

(A
80
, B
80
, C
80
, D
80
, E
80
)
. Вычисление сжимающей функции состоит из двух частей: расши- рения сообщения и обновления состояния.
Расширение сообщения линейно дополняет 16 переменных M
i до 80 переменных W
i
,
которые будут использоваться при обновлении состояния:
W
i
= M
i
,
0
� i < 16;
W
i
= (W
i
−3
⊕ W
i
−8
⊕ W
i
−14
⊕ W
i
−16
)
≪ 1, i � 16.
Обновление состояния состоит из 80 шагов следующего вида, изображённого на рис. 1.
A
i
B
i
C
i
D
i
E
i


≪ 5













≫ 2
























+





+





K
i

+




f i






+





W
i

















A
i+1
B
i+1
C
i+1
D
i+1
E
i+1
Рис. 1
. Вид одного раунда хэш-функции SHA-1
Здесь K
i
� константы, а f i
� следующие функции:
• на первых 20 шагах K
i
=
0x5A827999,
f i
(b, c, d) = f
IF
(b, c, d) = (b
∧ c) ∨ (b ∧ d);
• на вторых 20 шагах K
i
=
0x6ED9EBA1,
f i
(b, c, d) = f
XOR
(b, c, d) = b
⊕ c ⊕ d;
• на третьих 20 шагах K
i
=
0x8F1BBCDC,
f i
(b, c, d) = f
M AJ
(b, c, d) = (b
∧ c) ∨ (b ∧ d) ∨ (c ∧ d);
• на последних 20 шагах K
i
=
0xCA62C1D6,
f i
(b, c, d) = f
XOR
(b, c, d) = b
⊕ c ⊕ d.
Легко видеть, что B
i
= A
i
−1
, C
i
= A
i
−2
≫ 2, D
i
= A
i
−3
≫ 2, E
i
= A
i
−4
≫ 2. Таким образом, достаточно рассматривать только переменные A
i
; начальные значения (A
0
, . . . , E
0
)
задают (A
−4
, . . . , A
0
)
, конечные значения (A
80
, . . . , E
80
)
получаются из (A
76
, . . . , A
80
)
Поскольку вычисления для функции SHA-1 достаточно трудоёмки, для демонстрации новых и оптимизации существующих методов принято использовать так называемые со- кращённые варианты, которые отличаются от �полной� функции меньшим количеством шагов в сжимающей функции, сами шаги при этом остаются теми же.
113

3. Разностные атаки
Если взять в качестве блока сообщения случайный набор бит, то хеш-функция SHA-1
выдаст случайное 160-битное хеш-значение с приблизительно равномерным распределени- ем среди всех возможных 160-битных строк; таким образом, если взять два случайных блока, то вероятность того, что они образуют коллизию, составляет примерно 2
−160
, что,
разумеется, слишком мало для практических целей.
Разностные атаки эволюционировали со временем, различные этапы (в том числе атаки на другие хеш-функции, построенные по той же схеме) отмечены в работах [4] (MD4), [7]
(35 шагов SHA-0), [8] (полный SHA-0), [5] (MD5), [6] (58 шагов SHA-1), [9] (64 шагов SHA-
1), [10] (70 шагов SHA-1). Мы усовершенствуем метод характеристик, описанный в двух последних работах.
Ключевая идея разностных атак заключается в том, чтобы вести перебор не по всем возможным парам сообщений, а только по парам сообщений с фиксированными разностями по модулю 2 δM
i
= M
i
⊕ M

i
, за что атаки и получили такое название. Помимо фиксирова- ния δM
i
, полезным также оказывается фиксировать отдельные биты в M
i
, а также δA
i и
A
i
. Более точно, назовём характеристикой набор из (80 + 85) · 32 элементарных условий на пары бит ([W
i
]
j
, [W

i
]
j
)
и ([A
i
]
j
, [A

i
]
j
)
. Каждое элементарное условие какие-то из 4 возмож- ных вариантов разрешает, остальные запрещает; все 2 4
возможных элементарных условий собраны в следующей таблице вместе с условными обозначениями для них.
Таблица 2
. Обозначения условий на биты, применяемые при записи характеристик

i
(0, 0) (1, 0) (0, 1) (1, 1)
*




-




x




0




u




n




1




#




3




5




7




A




B




C




D




E




Множество пар (X, X

)
, удовлетворяющих всем 32 условиям на соответствующую пе- ременную, будем обозначать ∇X. Пусть известна некоторая характеристика и мы хотим организовать перебор по этой характеристике для нахождения коллизии. Будем последо- вательно подбирать M
2 0
= (M
0
, M

0
)
, затем M
2 1
и так далее. На каждом новом шаге мы выбираем очередной вариант для пары M
2
i с учётом условий из характеристики, вычисля- ем пару A
2
i+1
, проверяем условия из характеристики, пока не исчерпаем все возможности или не найдём нужной пары. Если пара найдена, продвигаемся на шаг вперёд, если возмож- ности исчерпаны, отступаем на шаг назад. После того, как мы подобрали M
2 15
, сообщение становится полностью определено, так что последующие шаги состоят только из проверок условий.
114

Число вариантов пары A
2
i+1
, удовлетворяющих условиям характеристики, может быть меньше, чем у соответствующей пары M
2
i
. В таком случае мы перебираем A
2
i+1
и вычисляем
M
2
i
; при фиксированных предыдущих значениях A
i
, A

i соответствие взаимно-однозначно.
Перебор будем вести до нахождения первой коллизии или до исчерпания простран- ства перебора. Предположим, что перебор завершится успехом, и попробуем оценить его сложность. Для этого введём несколько определений.
Набор (W
2 0
, . . . , W
2
i
)
назовём непротиворечивым, если его можно продолжить до полной пары расширенных сообщений, удовлетворяющих характеристике. Степень свободы сооб- щения на шаге i (обозначается ˜
F
W
(i)
) – это число непротиворечивых наборов (W
0
, . . . , W
i
)
,
продолжающих непротиворечивый набор (W
0
, . . . , W
i
−1
)
. При i
� 16, очевидно, ˜
F
W
(i) = 1
Если в характеристике условия на W
16
, . . . , W
79
тривиальны, то при i < 16 степень сво- боды сообщения на шаге i равна просто |∇W
i
|. В общем случае условия характеристики на W
16
, . . . , W
79
влекут за собой какие-то линейные соотношения на отдельные биты [M
i
]
j
;
если есть m таких независимых соотношений, то ˜
F
W
(i)
равно
|∇W
i
|
2
m
Можно также посчитать ˜
F
A
(i) =
|∇A
2
i+1
|. Если ˜
F
A
(i)
� ˜
F
W
(i)
, то мы перебираем M
2
i и вычисляем A
2
i+1
; иначе мы перебираем A
2
i+1
и вычисляем M
2
i
. В первом случае положим
F
W
(i) = ˜
F
W
(i)
, во втором положим F
W
(i) =
˜
F
A
(i)
2
m
; тогда F
W
(i)
� число потомков вершины дерева перебора на шаге i с поправкой на неявные линейные ограничения.
В определении хеш-функции значение A
i+1
вычисляется на каждом шаге по значениям
A
i
−j
, 0
� j � 4, и W
i
. Для оценок введём величины, которые характеризуют шаг хеш- функции; временно забудем, что A получаются по сообщениям, и рассмотрим вероятностное пространство, в котором A
i
−j
, 0
� j � 4, и W
i
� независимые величины, удовлетворяющие соответствующим ограничениям из характеристики.
Неконтролируемая вероятность на шаге i (обозначается P
u
(i)
) � это вероятность того, что результат шага i будет удовлетворять характеристике при условии, что на всех предыдущих шагах состояния и расширенные сообщения удовлетворяют характеристике.
То есть при ˜
F
A
(i)
� ˜
F
W
(i)
P
u
(i) := P r(A
2
i+1
∈ ∇A
i+1
|A
2
i
−j
∈ ∇A
i
−j
, 0
� j � 4, W
2
i
∈ ∇W
i
),
а при ˜
F
A
(i) < ˜
F
W
(i)
P
u
(i) := P r(W
2
i
∈ ∇W
i
|A
2
i
−j
∈ ∇A
i
−j
, 0
� j � 4, A
2
i+1
∈ ∇A
i+1
).
Контролируемая вероятность на шаге i (обозначается P
c
(i)
) – это вероятность того,
что найдется хотя бы одна пара W
2
i
, удовлетворяющая характеристике, такая что результат шага i будет удовлетворять характеристике при условии, что на всех предыдущих шагах состояния удовлетворяют характеристике. То есть
P
u
(i) := P r(
∃W
2
i
∈ ∇W
i
: A
2
i+1
∈ ∇A
i+1
|A
2
i
−j
∈ ∇A
i
−j
, 0
� j � 4).
(Контролируемая вероятность не меняется при перемене ролей A и W .)
Можно с некоторой погрешностью оценить сложность успешного перебора, считая при- ближённо, что все шаги независимы. А именно, на i-м шаге в среднем придётся обойти N
S
(i)
вершин дерева перебора, где:
• N
S
(80) = 1
(достаточно найти одну коллизию),
• N
S
(i) = max

N
S
(i+1)
F
W
(i)P
u
(i)
,
1
P
c
(i)

(с одной стороны, в среднем у вершины дерева перебора будет F
W
(i)
потомков, среди которых доля P
u
(i)
будет давать вершину следующего уровня; с другой стороны, с вероятностью P
c
(i)
вершина дерева перебора безнадёжна для получения вершин следующего уровня).
115

Величину
80

i=0
N
S
(i),
зависящую только от характеристики, будем называть фактором объёма перебора характе- ристики. Чем меньше фактор объёма перебора, тем характеристика лучше.
4. Подбор характеристики
Подбор характеристики состоит из трёх этапов.На первом этапе выбирается линейная характеристика, состоящая только из условий - и x (что эквивалентно, фиксирует все δW
i
,
δA
i
, но не отдельные биты). Для этого рассматривается линеаризация хеш-функции, при которой структура функции сохраняется, но все нелинейные операции (включая сложение по модулю 2 32
) заменяются на подходящие линейные. Идея заключается в том, чтобы найти характеристику с возможно меньшим количеством условий x; поскольку любая операция на совпадающих входах даёт совпадающие выходы, то хеш-функция может �разойтись� с линеаризацией только из-за отличающихся бит, соответствующих x в линеаризации. Линей- ные операции достаточно просты. Задачу о нахождении линейной характеристики с малым числом условий x можно сформулировать как поиск вектора малого веса в некотором ли- нейном коде, теория кодов даёт решение этой задачи.
Мы строим коллизию, состоящую из двух блоков. Характеристика для каждого блока своя, но строится по одной и той же линейной характеристике. Хеш-значение вычисляется как H
2
= H
1
+ g(M
2
, H
1
) = H
0
+ g(M
1
, H
0
) + g(M
2
, H
1
)
, H

2
= H
0
+ g(M

1
, H
0
) + g(M

2
, H

1
)
Линейная характеристика задаёт g(M
1
, H
0
)
⊕ g(M

1
, H
0
)
и g(M
2
, H
1
)
⊕ g(M

2
, H

1
)
; посколь- ку она одна и та же для обоих блоков, то фиксацией значений различающихся бит можно добиться того, чтобы разность выходов сжимающей функции на первом блоке была проти- воположна по знаку разности выходов сжимающей функции на втором блоке. Тогда будет
H
2
= H

2
Второй этап начинается с отбрасывания всех условий линейной характеристики на пер- вых 12 шагах на A
i и подстановки начальных условий для A
2
−4
, . . . , A
2 0
. Для первого блока начальным условием является константа H
0
, для второго блока � результат вычислений по первому блоку (таким образом, строить характеристику для второго блока можно только после того, как подобран первый блок коллизии). Кроме того, условия вида xx (на две под- ряд идущих пары бит) можно заменить на -x, если различие в старшем из этих бит может быть обусловлено переносом из младшего (это не всегда так из-за циклических сдвигов).
На втором этапе следует найти какой-нибудь �путь� (согласованный набор условий) от начальных условий до линейной характеристики. Для этого будем выбирать случайные по- зиции в A
2
i
, на которых ещё нет ограничений, накладывать ограничение - и вычислять,
какие дополнительные ограничения будут выполнены как следствие всех текущих. Кроме того, при появлении ограничений x в A
2
i
(два соответствующих друг другу битов различа- ются) оказывается полезным дополнительно фиксировать значения различающихся битов
(к примеру, требовать, чтобы бит первого сообщения был нулевым, а соответствующий бит второго сообщения был единичным). При обнаружении противоречивых условий возвраща- емся к последней фиксации условия x и используем вторую возможную фиксацию значения бит. Второй этап заканчивается, когда все условия имеют вид одного из -xun01.
На третьем этапе последовательно улучшается фактор объёма перебора найденной ха- рактеристики. Для этого перебираем все позиции в характеристике, рассматриваем возмож- ные усиления условия на позиции, вычисляем дополнительные ограничения, появляющиеся как следствие усиления, вычисляем фактор объёма перебора для новой характеристики. По- сле окончания перебора фиксируем то из условий, для которого фактор объёма перебора был минимален.
В подборе характеристики отметим только несколько важных моментов:
116

• Величины F
W
, P
u
, P
c вычисляются последовательно от младших битов к старшим при помощи перебора элементарных условий и возможных переносов.
• Следствия от введения нового условия для одного шага вычисляются в два прохо- да, вначале от младших бит к старшим запоминаются возможные переносы, затем с учётом переносов вычисляются возможные следствия ограничений. Эта процедура быстрая, но находит не все возможные дополнительные ограничения. Поэтому для по- иска следствий мы используем цикл по позициям бит, в котором временно фиксируем возможные значения бит и смотрим, не находит ли быстрая процедура противоречий.
На третьем этапе цикл включает все биты, на втором этапе � только биты, �соседние�
с изменёнными.
• Для повышения эффективности перебота по характеристике на ГПУ важна когерент- ность, т.е. одинаковость путей исполнения ядра в соседних потоках. Когерентность оказывается выше, если сильные ограничения сконцентрированы в начале характери- стики. Поэтому на втором этапе мы выбираем позиции в начале с несколько меньшей вероятностью (чтобы условия - в среднем тяготели к шагам с большим номером). По- добная оптимизация даёт повышение производительности поиска на ГПУ более чем на 80%.
5. Реализация поиска на ГПУ
Перейдём к вопросам перебора по готовой характеристике. Именно он является наи- более вычислительно сложной частью задачи. Сначала отметим некоторые особенности,
которые не зависят от выбора платформы реализации:
• Итоговые характеристики всегда состоят только из условий, входящих в список -xun01.
Следовательно, набор условий на каждую пару 32-битных переменных эквивалентен
X
⊕ X

= a
, X ∧ b = c, где a, b, c � некоторые константы. Предвычисление a, b, c позволяет быстро проверять пару переменных.
• Величины A
i на двух последних шагах не участвуют в вычислениях f i
, а потому вместо двух условий из предыдущего пункта достаточно проверять, что X − X

= a
Кроме того, при вычислении первого блока условия на двух последних шагах можно вообще игнорировать, поскольку любую возможную разность можно будет сократить на втором блоке без увеличения количества необходимых условий. Значения N
S
(i)
в приводимых нами таблицах скорректированы с учётом этого.
• Эффективный перебор всех пар X таких, что X ∧ b = c: первый элемент множества есть X = c, следующий после x задаётся формулой (((x ∨ b) + 1) ∧ b) + c, перебор заканчивается, когда формула из-за переполнения даёт c.
• Линейные соотношения на M
i
, возникающие из условий на W
k при больших k, могут либо выражать какой-то бит [M
i
]
j через какие-то биты предыдущих сообщений, либо давать какую-то связь между двумя или более битами [M
i
]
j
. Первый случай меняет только то, что числа a, b, c зависят не только от характеристики, но и от предыдущих сообщений. Соотношений, соответствующих второму случаю, мало, от них можно из- бавиться, просто наложив дополнительные искусственные ограничения, которые не меняют существенно фактор объёма перебора.
Перебор естественным образом разделяется на генерацию, где выполняется собственно перебор и генерация пар сообщений, и проверку, где характеристика проверяется для остав- шихся раундов для построенной пары сообщений. Генерацию можно рассматривать как по- иск с возвратом, и проверка просто добавляется как вызов функции в последний раунд
117
генерации. Генерация разделяется на часть, выполняемую на хосте, и часть, выполняемую на устройстве. На хосте дерево перебора раскрывается до определённой глубины, чтобы сгенерировать достаточное количество стеков поиска для задействования ресурсов ГПУ- параллелизма. Эта глубина сейчас задаётся вручную для каждой характеристики. Слиш- ком маленькая глубина приведёт к недостаточному ресурсу параллелизма, а при слишком большой глубине стеки поиска просто не поместятся в память ГПУ. В результате экспери- ментов мы установили, что примерно 100 тыс. стеков на ГПУ достаточно для эффективного использования его ресурсов.
Во время ГПУ-части поиск по всем стекам идёт параллельно на большом количестве
ГПУ. Если поиск для стека завершён, после завершения ГПУ-ядра стек удаляется. Новые стеки во время ГПУ-части не генерируются. Главное ГПУ-ядро реализует поиск с возвра- том и проверку построенного сообщения. В этом ядре каждый ГПУ-поток обрабатывает свой стек поиска. Во время вызова ядра каждый поток выполняет фиксированное число итераций поиска, после чего завершает свою работу. Главное ядро также собирает статисти- ческие данные по количеству перебранных вершин, общему количеству раундов проверки,
а также максимальной достигнутой при проверке глубине. Между вызовами ядра выпол- няется проверка на достижение необходимой глубины и сжатие стека поиска.
Вычисление на распределённом кластере реализовано при помощи MPI. Каждый MPI- процесс работает только с одним ГПУ. Используется блочно-циклическое распределение стеков поиска между процессами. Во время хост-части каждый процессор генерирует все стеки, после чего оставляет себе только те, что ему принадлежат. В первой реализации после каждого вызова ГПУ-ядра использовался глобальный барьер, в том числе для обмена статистическими данными. Однако эксперименты показали, что ввиду разбалансировки загрузки, возникающей вследствие неравномерности завершения работы над стеками, для некоторых характеристик ГПУ простаивают 50% времени. Поэтому в текущей реализации от глобального барьера мы отказались. Вместо этого мастер-процесс (с рангом 0) порождает
2 дополнительных потока, один для сбора статистики, и один для показа статистики через заданный промежуток времени (обычно 1 минута). Все процессы отсылают собственную статистику потоку сбора статистики в процессе с номером 0.
Для реализации на ГПУ использовался язык Nemerle и система NUDA (Nemerle Unified
Device Architecture) [11], набор расширений этого языка для программирования ГПУ. Си- стема NUDA была выбрана вследствие её свободного распространения и реализации высо- коуровневой поддержки ГПУ. При этом низкоуровневые детали, такие как передача дан- ных и параметров ядра, скрыты от программиста и обрабатываются самой системой. Для генерации ГПУ-кода для циклов и взаимодействия с ГПУ NUDA использует технологию
OpenCL.
В нашей первой реализации поиск с возвратом был реализован как один цикл, в кото- ром этапы, требующие специальной обработки, были реализованы в виде условий. Таких этапа было 2: переключение между раундами поиска, где требуется предвычислить большое количество значений, и проверка сгенерированного сообщения. Тестирование было реали- зовано в отдельной функции, а цикл по раундам тестирования полностью развёрнут при помощи аннотации inline, доступной в NUDA.
Однако производительность первой реализации была хороша только для некоторых ха- рактеристик, и очень плоха для других. Например, на 73-1 была достигнута эффективность
60% (от пиковой производительности ГПУ), в то время как на 72-2 достигнутая эффектив- ность составляла лишь 15%. Низкая эффективность была вызвана низкой когерентностью между потоками одного варпа. Для повышения когерентности мы использовали две опти- мизации.
Первая оптимизация состояла в сортировке стеков после каждого вызова основного яд- ра. Использование устойчивого алгоритма сортировки давало лучшие результаты по срав- нению с неустойчивыми алгоритмами (например, быстрой сортировкой), поскольку она со-
118
храняла порядок значений с одинаковыми ключами, а значит, сохраняла когерентность.
Мы пробовали сортировку по разным ключам, однако в конце концов остановились на значении поиска (состоянии или сообщении) на текущем раунде. На характеристике 72-2,
просто устойчивая сортировка давала 45%-ый прирост производительности по сравнению с изначальной реализацией. Для реализации устойчивой сортировки на ГПУ использовал- ся алгоритм побитовой сортировки [12], и эксперименты показали, что время сортировки стеков достаточно мало по сравнению с временем выполнения основного ядра. Сортировка сочеталась с модификацией цикла поиска сообщения: выход из цикла разрешался только при переключении раунда. Сортировка по значению поиска вместе с модификацией цикла даёт прирост производительности 87%.
Второй оптимизацией была замена одинарного цикла в поиске возвратов на тройной цикл. Самый вложенный цикл выполняет перебор на одном раунде и проверяет соответствие характеристике, пока либо не будет найдена хорошая вершина, либо не будут перебраны все вершины в этой ветке дерева на этом раунде. Второй по вложенности цикл реализует проверку сообщения, и имеет смысл только на последнем раунде перебора. Так как бо- лее 75% времени затрачивается на проверку сообщения, это повышает производительность.
Наконец, внешний цикл выполняет переходы между раундами, и проверяет условие за- вершения ядра. Конструкция с тройным циклом, хотя и может понижать когерентность за счёт разного количества итераций внутреннего цикла у соседних потоков, ещё и препятству- ет расхождению соседних потоков. В целом мы обнаружили, что использование тройного цикла совместно с устойчивой сортировкой по значению поиска даёт более чем 2-кратное увеличение производительности на характеристике 75-1 по сравнению с изначальной реа- лизацией.
Выполнялись и другие оптимизации. Это включало использование константной памяти для хранения данных характеристик, а также использование разделяемой памяти на чи- пе для хранения стеков поиска. К нашему удивлению, использование разделяемой памяти улучшило производительность только на 2.5% по сравнению с хранением стеков в глобаль- ной памяти. Это показывает, что используемый алгоритм работает на каждом мультипро- цессоре с небольшим множеством адресов, которое хорошо помещается в кэш 1-го уровня на
ГПУ NVidia Fermi. Финальная версия, с помощью которой проводился расчёт, использует все описанные оптимизации, включая описанную ранее модификацию алгоритма нахожде- ния характеристики. Эффект от влияния различных оптимизаций на производительность отражён в таблице 3.
Таблица 3
. Влияние различных оптимизаций на произовдительность поиска на ГПУ
Оптимизация
Ускорение
Модификация поиска характеристики
1.8
×
Устойчивая сортировка по значению поиска 1.87×
Тройной цикл
1.25
×
Прочее
1.12
×
Итого
4.2
×
Поскольку по предварительным оценкам поиск второй пары блоков должен был длить- ся очень долго, в приложение была добавлена поддержка контрольных точек. А поскольку ожидалось, что количество доступных узлов будет меняться, реализация контрольных то- чек поддерживала сохранение с одним числом процессов и последующее восстановление в другое число процессов. Поскольку во время ГПУ-части нет глобальной синхронизации,
каждый процесс писал файл контрольной точки независимо от остальных, через фиксиро- ванные промежутки времени, по умолчанию каждый час.
119

6. Результаты вычислений
Первые эксперименты и настройка параметров выполнялись на ГПУ-кластере �Гра- фИТ!�, установленном в НИВЦ МГУ. Эта система состоит из 16 узлов, на каждом из ко- торых стоит по 3 ГПУ NVidia Fermi M2050 с 3 ГБ памяти на каждом. Итого это даёт 48
ГПУ, но мы проводили расчёты не более чем на 30 из них.
Финальные расчёты для 1-го и 2-го блока коллизии выполнялись на ГПУ-разделе кла- стера �Ломоносов�, также установленного в НИВЦ МГУ. На каждом узле ГПУ-раздела установлено 2 ГПУ NVidia Fermi X2070, с 6 ГБ памяти на каждом ГПУ. Поскольку во время расчётов система находилась в режиме бета-тестирования, не все узлы были доступ- ны для вычислений. Использованные для расчётов характеристики в данной статье для краткости опущены, однако они доступны в [3].
Объём перебора для нахождения первого блока оценивался как 2 58
вершин. Ввиду огра- ничения на сообщения, характеристика была разделена на 4 части, и только одна из них выбрана для расчёта. Расчёт выполнялся на 264 ГПУ, и занял 11000 секунд. Количество обработанных вершин дерева перебора было 2 54.06
. Здесь в качестве �вершин� учитываются как собственно вершины дерева, так и раунды проверки сообщения, хотя один раунд про- верки требует в 2.5 раз больше вычислений, чем вершина собственно перебора. Для первого блока раундов проверки было примерно 40% от общего числа �вершин�.
Объём перебора для 2-го блока оценивался как 2 63.01
вершин. Перебор начался на 320
ГПУ, и несколько раз перезапускался с контрольных точек ввиду сбоев на узлах или ввода в строй дополнительных узлов с ГПУ. В конце расчёт проходил на 512 ГПУ, а в среднем число использованных ГПУ составило 455. Весь расчёт длился 1904252 секунды, или примерно
22 дня 45 минут. Было обработано 2 61.92
вершин, примерно 58.8% из которых составили раунды проверки. Эффективность составила 52% от пиковой производительности всех ГПУ.
Если бы нам был доступен весь кластер с 1554 ГПУ, для завершения расчёта всё равно потребовалась бы целая неделя.
Для каджого блока нам в определённом смысле �повезло�, т.к. поиск занял меньше времени, чем ожидалось. Для 1-го блока �повезло� в 16 раз, а для 2-го � в 2 раза. Если бы нам не �повезло�, весь расчёт занял бы полтора месяца.
Если сравнивать ГПУ-реализацию с предыдущей реализацией на кластере из обычных процессоров [13], 1 ГПУ обрабатывает данные в 39 раз быстрее, чем 1 ЦПУ. Если исходить из этого, то эквивалентное количество обычных ядер для нашего расчёта было бы 17745,
что не сильно превышает количество ядер, использовавшихся для получения предыдущего результата. Однако получить столько ядер на такой промежуток времени на �Ломоносове�
было бы достаточно проблематично. Спрос на ГПУ был намного меньше, и их получить в требуемом объёме было сравнительно легко.
В таблице 4 приводятся данные построенной коллизии.
7. Заключение
В данной статье предложена реализация поиска коллизий для хэш-функции SHA-1 при помощи метода характеристик на кластерах из ГПУ. Основываясь на результатах преды- дущей работы, а также с помощью предложенных оптимизаций удалось достигнуть эффек- тивности расчёта 50%. При помощи разработанной реализации удалось построить коллизию для 75-раундовой версии хэш-функции SHA-1, что в настоящее время является мировым рекордом для данной хэш-функции.
Поскольку сложность расчёта с каждым следующим раундом возрастает примерно в
8 раз, дальнейшее увеличение количества используемых раундов потребует хотя бы ча- стичного пересмотра используемого метода. Предварительные работы в этом направлении ведутся, но о результатах говорить пока рано.
Мы выражаем благодарность НИВЦ МГУ им. М.В.Ломоносова за предоставленные
120

Таблица 4
. Пример 75-шаговой коллизии SHA-1
i
Сообщение 1, первый блок
Сообщение 1, второй блок
1–4
F01EE8EE BDDFF313 B2F59EE4 BB37F2BB
F072633F 0D32226A DFF74459 98507743 5–8 2F472A36 1C052F6A 96403EF0 F144298B
EEFE63DD FE10D5C5 AFE33902 EF74984E
9–12
DAF5519C 7A90DD71 2BF3718E A7E3DE6D
350272F7 DB382ABC 155B0414 B800179D
13–16
EFFA975E 9B00AA95 6056E3EE 2BA4483A
18ECD4BC 15497213 1505284C 60C4F869
i
Сообщение 2, первый блок
Сообщение 2, второй блок
1–4 001EE884 3DDFF353 22F59E94 0B37F2E8 00726355 8D32222A 4FF74429 28507710 5–8 1F472A3E 1C052F29 46403E82 4144299B
DEFE63D5 FE10D586 7FE33970 5F74985E
9–12 2AF551FE BA90DD33 2BF371BE 47E3DE2F
C5027295 1B382AFE 155B0424 580017DF
13–16
CFFA973E 7B00AAD4 4056E3BE EBA4487B
38ECD4DC F5497252 3505281C A0C4F828
i
XOR-разности в двух блоках совпадают
1–4
F000006A 80000040 90000070 B0000053
F000006A 80000040 90000070 B0000053 5–8 30000008 00000043 D0000072 B0000010 30000008 00000043 D0000072 B0000010 9–12
F0000062 C0000042 00000030 E0000042
F0000062 C0000042 00000030 E0000042 13–16 20000060 E0000041 20000050 C0000041 20000060 E0000041 20000050 C0000041
i
Совпадающие хеш-значения
1–5 3DF7F21E 130079F3 C2E6EFFF FD9C4141 9AA8723A
вычислительные ресурсы. Кроме того, мы выражаем благодарность группе поддержки су- перкомпьютера �Ломоносов� и лично Антону Коржу за оперативное решение вопросов,
возникающих во время использования кластера.
Литература
1. Teat C., Peltsverger S. The security of cryptographic hashes. // Proceedings of the 49th
Annual Southeast Regional Conference, ACM, 2011, pp. 103–108.
2. National Institute of Standards and Technology (NIST). FIPS-180-2: Secure Hash
Standard, August 2002. Available online at http://www.itl.nist.gov/fipspubs/.
3. Grechnikov E.A., Adinetz A.V. Collision for 75-step SHA-1: Intensive Parallelization with
GPU // Cryptology ePrint Archive: Report 2011/641. Available online at http://eprint.iacr.org/2011/641.
4. Hans Dobbertin, Cryptanalysis of MD4, Fast Software Encryption, LNCS 1039, D.
Gollmann, Ed., Springer-Verlag, 1996, pp. 53–69.
5. Xiaoyun Wang and Hongbo Yu, How to Break MD5 and Other Hash Functions, Eurocrypt
2005.
6. Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu, Finding Collisions in the Full SHA-1, in
Proceedings of CRYPTO, LNCS 3621, Springer, 2005, pp. 17–36.
7. Florent Chabaud, Antoine Joux, Differential Collisions in SHA-0, CRYPTO 1998.
8. Eli Biham, Rafi Chem, Antoine Joux, Patrick Carribault, Christophe Lemuet, William
Jalby, Collisions of SHA-0 and Reduced SHA-1, Eurocrypt 2005.
9. Christophe De Canni`ere, Christian Rechberger, Finding SHA-1 Characteristics: General
Results and Applications, In Proceedings of ASIACRYPT, LNCS 4284, pp. 1–20, Springer,
2006.
10. Christophe De Canni`ere, Florian Mendel, Christian Rechberger, Collisions for 70-Step
SHA-1: On the Full Cost of Collision Search, In Proceedings of Selected Areas in
Cryptography, LNCS 4876, pp. 56–73, Springer, 2007.
11. Andrew V. Adinetz. NUDA Programmer’s Guide. URL: http://nuda.sf.net.
121

12. Nadathur Satish, Changkyu Kim, Jatin Chhugani, Anthony D. Nguyen, Victor W. Lee,
Daehyun Kim, and Pradeep Dubey. Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort. In Proceedings of the 2010 international conference on Management of data (SIGMOD ’10), pages 351-362. ACM, New York, NY, USA, 2010.
13. E. A. Grechnikov. Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics. Cryptology ePrint Archive: Report 2010/413, available at http://eprint.iacr.org/2010/413.
122


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал