MD2 () — хеш-функція, розроблена Рональдом Ріверстом (RSA Laboratories) в 1989 році і описана RFC 1319 (оновлено від RFC 1115). Розмір хешу — 128 біт (16 байт). Всі операції алгоритму виконуються з октетами (байтами).
Хоча алгоритм все ще повністю не було зламано, в 2011 IETF змінило його статус на "історичний" і натомість рекомендує використовувати SHA-256 чи інші сильні алгоритмиRFC 6149.
Опис алгоритму Спочатку повідомлення доповнюють так, щоб його довжина в байтах була кратна 16. Для цього додають до кінця повідомлення (від 1 до 16-ти) байтів кожен з яких містить значення . Повідомлення матиме довжину , таку що . позначатиме доповнене повідомлення.
На другому кроці додають чексуму , використовуючи "випадкову" перестановку з 256 байт, побудовану з цифр числа Пі, . Для цього робиться наступне:
для і := від 0 до 15: C[i] := 0
L := 0
для і := від 0 до N/16-1: // для кожного блоку по 16 байт для j від 0 до 15: c := M[i*16+j] // символ в блоці L := C[j] := C[j] xor S[c xor L] // оновлюємо чексуму
В описі цього кроку RFC містить помилку (виправлену в Errata 555), замість L = C[j] = C[j] xor S[c xor L] там роблять присвоєння L = C[j] = S[c xor L], тому якщо реалізовувати точно як в RFC, вивід хеш-функції не буде відповідати деяким тестовим прикладам з RFC (`abcdefghijklmnopqrstuvwxyz` і довшим).
16 байтів чексуми додаються до повідомлення , нова довжина повідомлення
На третьому кроці виділяється і обнуляється буфер для дайджесту повідомлення з 48 байтів.
На четвертому кроці виконується хешування повідомлення блок за блоком. Використовується таке саме значення перестановки як на кроці 2.
для і := від 0 до N'/16-1: // для кожного блоку по 16 байт для j від 0 до 15: X[16+j] := M[i*16+j] X[32+j] := X[16+j] xor X[j]
t := 0
для j := від 0 до 17: // 18 раундів хешування для k := від 0 до 47: t := X[k] := X[k] xor S[t] t := t + j mod 256
На останньому кроці повертають перших 16 байтів вмісту буфера X.
Приклад реалізації на Python
def MD2(data): ''' >>> MD2(b'') '8350e5a3e24c153df2275c9f80692773' >>> MD2(b'a') '32ec01ec4a6dac72c0ab96fb34c0b5d1' >>> MD2(b'abc') 'da853b0d3f88d99b30283a69e6ded6bb' >>> MD2(b'message digest') 'ab4f496bfb2a530b219ff33031fe06b0' >>> MD2(b'abcdefghijklmnopqrstuvwxyz') '4e8ddff3650292ab5a4108c3aa47940b' >>> MD2(b'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789') 'da33def2a42df13975352846c30338cd' >>> MD2(b'12345678901234567890123456789012345678901234567890123456789012345678901234567890') 'd5976f79d83d3a0dc9806c3c66f3efd8' '''
M = list(data)
# Крок 1. Доповнення i = 16 - (len(M) % 16) M = M + [i] * i N = len(M)
# Крок 2. Додавання чексуми C = * 16 L = 0 for i in range(N//16): for j in range(16): c = M[i*16 + j] L = C[j] = C[j]^S[c ^ L]
M = M + C N = len(M)
# Крок 3. Ініціалізація буфера MD X = * 48
# Крок 4. обробка повідомлення 16-байтовими блоками for i in range(N//16): for j in range(16): X[16+j] = M[i*16+j] X[32+j] = X[16+j]^X[j]
t = 0 for j in range(18): for k in range(48): t = X[k]^S[t] X[k] = t t = (t + j) % 256
# Крок 5. Вивід return ''.join(f'{x:02x}' for x in X[:16])
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 ]
Перестановка S Масив з 256 байтів S - це S-таблиця. Її побудовано перемішуванням цілих чисел від 0 до 255 використовуючи варіант алгоритму Дарстенфельда в якому генератор псевдовипадкових чисел використовує цифри десяткового представлення ПіRFC 1319 (див. ).
Реалізації В RFC 1319 дається еталонна реалізація на С, крім цього існують реалізації на Pythonhttps://urchin.earth.li/~twic/md2.py, JavaScript, Java, Go та іншими мовами програмування.
Безпека Функція демонструє лавиновий ефект, зміна лише одного символа змінює кожен байт в хеші. Наприклад в наступних двох хешах червоним кольором показано половинку байта що не змінилась:
MD2('wikipedi') = 'e01ebd633170ac3210b4c25e941b417' MD2('wikipedi') = 'b2451ac2a2691e485a30519caf8c512'
Хеш має розмір 128 біт, тому для того аби знайти повідомлення яке хешується в найгіршому випадку треба перебрати варіантів. Знайдені вразливості, які дозволяють скоротити кількість варіантів до
Історія Після винайдення асиметричної криптографії й алгоритму RSA, постала проблема того що RSA занадто повільний для того аби підписувати довгі повідомлення. Безпечна криптографічна хеш-функція могла б значно підвищити зручність цифрового підпису, тому були створені функції MD та MD2. MD, на відміну від MD2 не була опублікована, і використовувалась в додатках безпечної електронної пошти від RSA Security.
Зноски
Література
Посилання RFC 1319 RFC 1115 RFC 6149