06 февраля 2012
Алгоритм хэширования MD2
Часть 1
Данная статья начинает цикл статей, посвященных алгоритмам хэширования семейства MD (Message Digest). Алгоритмы MD2, MD4, MD5 и MD6 широко известны; первые три из них широко использовались и продолжают широко использоваться, несмотря на то, что существуют известные криптоаналитические атаки против каждого из них.
Алгоритмы MD обладают различными характеристиками; они разработаны в разные годы известным криптологом Рональдом Ривестом (Ronald Rivest) с участием некоторых других специалистов RSA Laboratories – научного подразделения компании RSA Data Security Inc.
Первая из статей данного цикла посвящена алгоритму MD2 и описывает его структуру. MD2 (который изначально назывался RSA-MD2) является первым из широко известных алгоритмов семейства MD. Существует и алгоритм MD1 (он же RSA-MD1), который, однако, является закрытым, его спецификация не опубликована. Алгоритм MD1 упоминается, в частности, в известной работе [1], а в [2] сказано, что RSA-MD1 – «закрытый алгоритм, практически идентичный алгоритму RSA-MD2».
Алгоритм хэширования MD2 был разработан в 1988 г. для использования в качестве одного из криптографических алгоритмов, входящих в стандарт защищенной электронной почты PEM (Privacy-Enhanced Mail); его реализация на языке Си была приведена в RFC 1115 [3]. Впоследствии спецификация и обновленная реализация MD2 были опубликованы в RFC 1319 [4].
MD2 хэширует данные переменного размера с получением 128-битного выходного значения. Прежде всего, выполняется дополнение входных данных до размера, кратного 16 байтам (дополнение выполняется и в том случае, когда исходный размер сообщения кратен 16 байтам), следующим образом: в конец сообщения добавляется определенное количество (n) байтов (от 1 до 16); значение каждого дополняемого байта равно n (например, дополнение 27-байтного сообщения состоит из 5 байтов, каждый из которых содержит значение 5).
Затем вычисляется 16-байтная контрольная сумма сообщения, которая также дополняет сообщение перед его дальнейшей обработкой. Контрольная сумма вычисляется следующим образом: для каждого 16-байтного блока дополненного сообщения 16 раз выполняются следующие действия:
c = M[i * 16 + j],
C[j] = S[c  L]  C[j], |
L = C[j],
где:
i – номер 16-байтного блока данных;
j – номер текущего шага цикла;
M[x] – x-й байт сообщения, т. е. M[i * 16 + j] – это j-й байт текущего блока данных;
с и L – временные переменные, L изначально содержит значение 0;
C[j] – j-й байт массива контрольной суммы; перед вычислением контрольной суммы массив содержит нулевые байты;
S – табличная замена, определенная следующим образом:
41 |
46 |
67 |
201 |
162 |
216 |
124 |
1 |
61 |
54 |
84 |
161 |
236 |
240 |
6 |
19 |
98 |
167 |
5 |
243 |
192 |
199 |
115 |
140 |
152 |
147 |
43 |
217 |
188 |
76 |
130 |
202 |
30 |
155 |
87 |
60 |
253 |
212 |
224 |
22 |
103 |
66 |
111 |
24 |
138 |
23 |
229 |
18 |
190 |
78 |
196 |
214 |
218 |
158 |
222 |
73 |
160 |
251 |
245 |
142 |
187 |
47 |
238 |
122 |
169 |
104 |
121 |
145 |
21 |
178 |
7 |
63 |
148 |
194 |
16 |
137 |
11 |
34 |
95 |
33 |
128 |
127 |
93 |
154 |
90 |
144 |
50 |
39 |
53 |
62 |
204 |
231 |
191 |
247 |
151 |
3 |
255 |
25 |
48 |
179 |
72 |
165 |
181 |
209 |
215 |
94 |
146 |
42 |
172 |
86 |
170 |
198 |
79 |
184 |
56 |
210 |
150 |
164 |
125 |
182 |
118 |
252 |
107 |
226 |
156 |
116 |
4 |
241 |
69 |
157 |
112 |
89 |
100 |
113 |
135 |
32 |
134 |
91 |
207 |
101 |
230 |
45 |
168 |
2 |
27 |
96 |
37 |
173 |
174 |
176 |
185 |
246 |
28 |
70 |
97 |
105 |
52 |
64 |
126 |
15 |
85 |
71 |
163 |
35 |
221 |
81 |
175 |
58 |
195 |
92 |
249 |
206 |
186 |
197 |
234 |
38 |
44 |
83 |
13 |
110 |
133 |
40 |
132 |
9 |
211 |
223 |
205 |
244 |
65 |
129 |
77 |
82 |
106 |
220 |
55 |
200 |
108 |
193 |
171 |
250 |
36 |
225 |
123 |
8 |
12 |
189 |
177 |
74 |
120 |
136 |
149 |
139 |
227 |
99 |
232 |
109 |
233 |
203 |
213 |
254 |
59 |
0 |
29 |
57 |
242 |
239 |
183 |
14 |
102 |
88 |
208 |
228 |
166 |
119 |
114 |
248 |
235 |
117 |
75 |
10 |
49 |
68 |
80 |
180 |
143 |
237 |
31 |
26 |
219 |
153 |
141 |
51 |
159 |
17 |
131 |
20 |
Псевдослучайное заполнение таблицы сформировано значениями дробной части числа ?. Каждая n-я ячейка таблицы содержит значение S[n], 0 ? n ? 255. Данная таблица используется и в функции сжатия алгоритма MD2.
Функция сжатия использует 48-байтное внутреннее состояние X[0]…X[47], которое обнуляется перед началом вычислений. Каждый 16-байтный i-й блок дополненного сообщения, включая блок контрольной суммы, накладывается на внутреннее состояние следующим образом:
- Блок данных копируется в состояние следующим образом:
X[16 + j] = M[i * 16 + j], j = 0…15,
X[32 + j] = (X[16 + j]  X[j]), j = 0…15. |
Таким образом, если представить внутреннее состояние как 3 фрагмента по 16 байт, то после копирования блока данных второй из фрагментов состояния содержит обрабатываемый блок данных, а третий – результат применения побитовой операции «исключающее или» (XOR) к текущему содержимому первого фрагмента и блока данных (см. рис. 1). 
Рис. 1 Копирование блока данных в состояние
- Выполняется обработка состояния, которая состоит из 18 раундов преобразований, в рамках каждого из которых выполняется обновление каждого байта состояния следующим образом:
X[k] = (X[k]  S[t]), k = 0…47, |
t = X[k],
где t – временная переменная, которая изначально имеет нулевое значение, а после выполнения каждого j-го раунда (j = 0…17) t модифицируется:
t = t + j mod 256.
После обработки всех блоков сообщения в первом 16-байтном фрагменте состояния X[0]…X[15] находится результирующее хэш-значение алгоритма.
Отметим, что алгоритм MD2 является крайне простым в реализации.
В следующей статье перечислим основные протоколы и приложения, в которых используется алгоритм MD2, а также обсудим быстродействие алгоритма и известные на данный момент результаты его криптоанализа.
Литература
- Preneel B. Analysis and Design of Cryptographic Hash Functions. // http://homes.esat.kuleuven.be – February 2003.
- Dusse S. R., Kaliski B. S. Jr. A Cryptographic Library for the Motorola DSP56000. // http://ftp.zedz.net – 1998 – RSA Data Security Inc.
- Linn J. RFC 1115. Privacy Enhancement for Internet Electronic Mail: Part III -- Algorithms, Modes, and Identifiers. // http://tools.ietf.org – August 1989 – DEC.
- Kaliski B. RFC 1319. The MD2 Message-Digest Algorithm. // http://tools.ietf.org – April 1992 – RSA Laboratories.
Мнения экспертов
Статья полезная и технически грамотная. Написано немного суховато и требует базовых знаний по данному предмету. Тем не менее недостатков, по большому счету нет.
Сам цикл статей по задумке интересный, но мне кажется, детальное описание алгоритма можно найти во многих источниках, поэтому приводить его в статье необходимости нет, интереснее было бы больше внимания уделить основным протоколам и приложениям, в которых используется алгоритм MD2, а также известные на данный момент результаты его криптоанализа.
В предложенной статье рассматривается криптографический алгоритм МD2, который продолжает использоваться в различных приложениях, несмотря на то, что на данный момент признан уязвимым. К алгоритмам хэширования предъявляется целый ряд требований, помимо криптографической стойкости(необратимость, стойкость к коллизиям первого и второго рода), важную роль играет простота реализации и оптимизация по быстродействию. Рассмотрение данного алгоритма имеет дидактическую ценность, ведь именно благодаря простоте, можно досконально разобраться в основах, чтобы в дальнейшем иметь глубокое понимание различных инструментов, применяемых в сфере информационной безопасности. Также хочется отметить соответствующие иллюстрации, помогающие понять излагаемый материал. Данная статья, безусловно, имеет высокую практическую ценность. Будем ожидать продолжения, тем более, что можно надеяться на выход целого цикла публикаций в дальнейшем.
Довольно компактное, но весьма подробное описание алгоритма хэширования MD2. Статья будет интересна не только программистам, желающим реализовать данный алгоритм получения хэшей в своем коде, но и все, кто несколько глубже желает познакомиться с существующими алгоритмами хэширования семейства MD. Однако, статью можно было расширить, описав в конце статьи «основные протоколы и приложения, в которых используется алгоритм MD2», так, чтобы все читалось на одном дыхании.
Правильнее эту статью, как зачинающую перспективный цикл статей, назвать «Алгоритмы хэширования MD2», а не «Алгоритм..». И хорошо бы в качестве предисловия обозначить перспективы практического применения этих алгоритмов, их реализацию. - Поближе к практике!
Ваши комментарии:
Для того, чтобы оставлять коментарии, Вам нужно авторизоваться на Sec.Ru. Если У Вас еще нет аккаунта, пройдите процедуру регистрации.
|
|
