MD2 англ Message Digest Algorithm хеш функція розроблена Рональдом Ріверстом RSA Laboratories в 1989 році і описана RFC

MD2 (англ. Message Digest Algorithm) — хеш-функція, розроблена Рональдом Ріверстом (RSA Laboratories) в 1989 році і описана RFC 1319 (оновлено від RFC 1115). Розмір хешу — 128 біт (16 байт). Всі операції алгоритму виконуються з октетами (байтами).

MD2
Загальні
Уперше оприлюднений	2008
Серія	MD2, MD4, MD5, MD6
Деталі
Розмір даджеста	128 біт
Раундів	18

Хоча алгоритм все ще повністю не було зламано, в 2011 IETF змінило його статус на "історичний" і натомість рекомендує використовувати SHA-256 чи інші сильні алгоритми.

Опис алгоритму

Спочатку повідомлення доповнюють так, щоб його довжина в байтах була кратна 16. Для цього додають до кінця повідомлення $i$ (від 1 до 16-ти) байтів кожен з яких містить значення $i$ . Повідомлення матиме довжину $N=n+i$ , таку що $N\equiv 0{\pmod {16}}$ . $M$ позначатиме доповнене повідомлення.

На другому кроці додають чексуму $C$ , використовуючи "випадкову" перестановку з 256 байт, побудовану з цифр числа Пі, $S$ . Для цього робиться наступне:

для і := від 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 байтів чексуми додаються до повідомлення $M$ , нова довжина повідомлення $N'=N+16$

На третьому кроці виділяється і обнуляється буфер для дайджесту повідомлення з 48 байтів.

На четвертому кроці виконується хешування повідомлення блок за блоком. Використовується таке саме значення перестановки $S$ як на кроці 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 = [0] * 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 = [0] * 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 використовуючи варіант ^[en] в якому генератор псевдовипадкових чисел використовує цифри десяткового представлення Пі (див. ^[en]).

Реалізації

В RFC 1319 дається еталонна реалізація на С, крім цього існують реалізації на Python, JavaScript, Java, Goта іншими мовами програмування.

Безпека

Функція демонструє лавиновий ефект, зміна лише одного символа змінює кожен байт в хеші. Наприклад в наступних двох хешах червоним кольором показано половинку байта що не змінилась:

MD2('wikipedia') = 'e01ebd633170ac3210b4c25e941b3417' MD2('wikipedib') = 'b2451ac2a2691e485a30519caf8c0512'

Хеш має розмір 128 біт, тому для того аби знайти повідомлення яке хешується в найгіршому випадку треба перебрати $2^{1}28$ варіантів. Знайдені вразливості, які дозволяють скоротити кількість варіантів до $2^{1}04$

Історія

Після винайдення асиметричної криптографії й алгоритму RSA, постала проблема того що RSA занадто повільний для того аби підписувати довгі повідомлення. Безпечна криптографічна хеш-функція могла б значно підвищити зручність цифрового підпису, тому були створені функції MD та MD2. MD, на відміну від MD2 не була опублікована, і використовувалась в додатках безпечної електронної пошти від RSA Security.

Зноски

Kaufman, Perlman та Speciner, 2002, Hashes and Message Digests.
RFC 6149
RFC Errata Report » RFC Editor.
MD2.py. Github Gist (англ.).
RFC 1319
How is the MD2 hash function S-table constructed from Pi?. Cryptography Stack Exchange. Stack Exchange. 2 серпня 2014. Процитовано 23 травня 2021.
https://urchin.earth.li/~twic/md2.py
MD2 — PyCryptodome 3.190b1 documentation. pycryptodome.readthedocs.io.
js-md2. npm (англ.). 8 лютого 2017.
MD2 (Oracle Fusion Middleware Crypto FIPS Java API Reference). docs.oracle.com.
md2 package - github.com/htruong/go-md2 - Go Packages. pkg.go.dev.
Muller, Frédéric (2004). The MD2 Hash Function Is Not One-Way. Advances in Cryptology - ASIACRYPT 2004: 214—229. doi:https://doi.org/10.1007/978-3-540-30539-2_16. {{}}: Перевірте значення |doi= ()

Література

Kaufman, Charlie; Perlman, Radia; Speciner, Mike (2002). Network security: private communication in a public world (вид. 2.). Upper Saddle River, NJ London: Prentice Hall PTR. ISBN .

Посилання

Це незавершена стаття з криптографії.
Ви можете проєкту, виправивши або дописавши її.

[FOOTNOTEKaufmanPerlmanSpeciner2002Hashes_and_Message_Digests-1] Kaufman, Perlman та Speciner, 2002, Hashes and Message Digests.

[2] RFC 6149

[3] RFC Errata Report » RFC Editor.

[4] MD2.py. Github Gist (англ.).

[5] RFC 1319

[6] How is the MD2 hash function S-table constructed from Pi?. Cryptography Stack Exchange. Stack Exchange. 2 серпня 2014. Процитовано 23 травня 2021.

[7] ttps://urchin.earth.li/~twic/md2.py

[8] MD2 — PyCryptodome 3.190b1 documentation. pycryptodome.readthedocs.io.

[9] s-md2. npm (англ.). 8 лютого 2017.

[10] MD2 (Oracle Fusion Middleware Crypto FIPS Java API Reference). docs.oracle.com.

[11] 2 package - github.com/htruong/go-md2 - Go Packages. pkg.go.dev.

[12] Muller, Frédéric (2004). The MD2 Hash Function Is Not One-Way. Advances in Cryptology - ASIACRYPT 2004: 214—229. doi:https://doi.org/10.1007/978-3-540-30539-2_16. {{}}: Перевірте значення |doi= ()