MD2

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

MD2

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

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

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

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

На другому кроці додають чексуму ${\displaystyle C}$, використовуючи "випадкову" перестановку з 256 байт, побудовану з цифр числа Пі, ${\displaystyle 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^[3]), замість L = C[j] = C[j] xor S[c xor L] там роблять присвоєння L = C[j] = S[c xor L], тому якщо реалізовувати точно як в RFC, вивід хеш-функції не буде відповідати деяким тестовим прикладам з RFC (`abcdefghijklmnopqrstuvwxyz` і довшим)^[4].

16 байтів чексуми додаються до повідомлення ${\displaystyle M}$, нова довжина повідомлення ${\displaystyle N'=N+16}$

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

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

Реалізації

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

Безпека

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

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

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

Історія

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