MD5 – извлечение на съобщение – (англ. Message Digest 5) е хеш функция разработена от Райвест (MIT) през 1991 г. като замяна на MD4. Резултатът на функцията е 128-битови извлечения. Една степен по-бърза от шифриращите блокове алгоритми. Специфициран в RFC 1321, MD5 се използва в многобройни приложения за сигурност, като често се използва и за проверка на целостта на данните. MD5 хеш стойност обикновено се изразява като шестнадесетично число, 32 цифри.

Въпреки това, тъй като е доказано, че MD5 не е устойчив на атаки (анг. collision resistant) той не е подходящ за приложения като SSL сертификати или цифрови подписи.

Дефекти започват да бъдат намирани от 1996 г., криптографите започнали да препоръчват използването на други алгоритми, като SHA-1-който впоследствие е установено, че също е уязвим. През 2007 г. е показана и лесна атака за съвпадения. През декември 2008 г. е показано и фалшифициране на SSL сертификати и SEI (Software Engineering Institute) посочва „MD5 трябва да се разглежда като криптографско „счупен и негоден за по-нататъшна употреба“. Повечето американски правителствени приложения сега изискват SHA-2 хеш функции.

История и криптоанализ редактиране

MD5 е един от поредицата алгоритми – message digest – проектирани от проф. Роналд Ривест от Масачузетския технологичен институт Когато аналитична дейност показват, че предшественикът на MD5, MD4 е вероятно несигурен, MD5 е призван да го замести. Слабости в MD4 бяха намерени по-късно от Ханс Доббертин.

Сигурност редактиране

Сигурността на MD5 хеш функция е тежко компрометирана. Съществуват атаки, (collision attack) които могат да намерят съвпадения за секунди на компютър с 2.6 GHz Pentium 4 процесор. Има други атаки, при които се получава сблъсък на два различни произволно избрани входа в рамките на часове, и то използвайки компютърна техника, която е морално остаряла. Могат да бъдат изчислени на NVIDIA GeForce 8400GS графичен процесор, 16 – 18 милиона хешове в секунда. На NVIDIA GeForce 8800 Ultra могат да бъдат обработени повече от 200 милиона хешове за секунда. Тези хеш сблъсък атаки са демонстрирани в обществото в различни ситуации, включително файлове на документи и цифрови сертификати.

Устойчивост на колизии (анг. collisions) редактиране

Да се намерят колизии (анг. collisions) това означава да има различни съобщения с еднаква хеш стойност. Възможно е потребител, да използва тази възможност, за да подмени първоначалното съобщение.

През 1996, колизия е била намерена в компресирана функция на MD5. Ханс Доббертин я описва в RSA Laboratoties – вестник за специализирана техническа литература – „Представената атака все още не заплашва приложенията на MD5, но се доближава до това... в бъдеще MD5 не би следвало да се прилага, когато се изисква устойчивост на колизии.“

През месец август 2004 г. на конференцията Cripto2004 китайските изследователи Weng, Feng, Lai и Yu, обявяват, че са намерили начин да „счупят“ редица алгоритми в това число и MD5. Според материалите им те могат да създадат два файла с една и съща хеш стойност, което е известно като колизия. Тяхната теория е известна като birhday attack 1.

През 2005 г. учените са били в състояние да създадат двойки на PostScript документи и X.509 сертификати със същия хеш. По-късно същата година, дизайнерът на MD5 Ron Rivest пише: „md5 и sha1 са явно разбити от гледна точка на резистентност към колизии)“.

MD5 използва Merkle–Damgård конструкция, така че ако два кода могат да имат еднакъв хеш, то може да се добави парче код към тях, за да направи колизията по=вероятно да бъде приета като валидна от използващата я програма. Освен това съществуващите техники за работа с колизии позволяват да се определят произволни префикси. Така един хакер може да създаде два файла които започват с едно и също съдържание. Това което трябва да направи нападателя е да създаде два 128 битови файла групирани по 64 бита, съществуващ алгоритъм може свободно да променя битове като запазва един и същи хеш. Пример MD5 сблъсък, с две съобщения, различаващи се по 6 бита, е:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325 7 1415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70
d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

И двата примера произвеждат MD5 хеш 79054025255fb1a26e4bc422aef54eb4. Разликата между тях е че водещия бит във всяка четворка битове (анг. nibble) e преобърнат.

Приложения редактиране

Предвид изложените недостатъци в сигурността, за сега MD5 единствено намира приложение в използването на чек суми за достоверността на данни във файлове и при предаване на данни.

Алгоритъм редактиране

 
Фигура 1. Една операция по MD5 хеширане. Кодирането се състои от 64 такива операции, разделени на 4 етапа от 16 операции. F е нелинейна функция, за всеки етап от кодирането се ползва различна функция. С Mi са означени 32-битови блокове от входните данни, а с Ki се означават 32-битови константи, различни за всяка операция. Със  s е обозначено логическо изместване наляво със s позиции, като s варира за всяка операция. Със   е означена операцията по получаване остатъка от целочисленото делене с 232.

Алгоритъмът на MD5 образува код с фиксирана големина от 128 бита при входни данни с променлива големина.

Входното съобщение се разделя на блокове от 512 бита (или 16 32-битови сектора), като при нужда дължината му се удължава до стойност, която позволява точно делене на 512.

Процедурата по удължаването на съобщението е следната:

  1. Добавя се единичен бит със стойност 1 към края на входното съобщение.
  2. Следва добавяне на нулеви битове до достигане на стойност на дължината, по-малка с 64 от най-близката кратна на 512 стойност.
  3. Оставащите 64 бита се използват за запис на остатъка от целочисленото деление на дължината на първоначалното входно съобщение и числото 264.

Главния кодиращ алгоритъм на MD5 създава като резултат един 128 битов ключ, разделен на четири части (A,B,C,D), всяка от които с големина от 32 бита (виж фигура 1). След първоначалната обработка на входните данни (виж по-горе), се задават начални стойности на блоковете A,B,C,D от списък с константи. Следват четири етапа на кодиране, при всеки един от който се извършват 16 сходни операции с блоковете, базиращите се на нелинейната функция F. Всъщност зад F се крият четирите функции, изброени по-долу, като се ползва различна функция за всеки един от четирите етапа.

 
 
 
 

  означават логическите операции XOR, AND, OR и NOT.

Псевдокод редактиране

По-долу е даден един примерен алгоритъм за изчисляване на MD5 хешове.

//Note: All variables are unsigned 32 bit and wrap modulo 2^32 when calculating var int[64] s, K

//s specifies the per-round shift amounts

s[ 0..15] := { 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22}
s[16..31] := { 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20}
s[32..47] := { 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23}
s[48..63] := { 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21}

//Use binary integer part of the sines of integers (Radians) as constants:

for i from 0 to 63
    K[i] := floor(abs(sin(i + 1)) × (2 pow 32))
end for

//(Or just use the following table):

K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 }
K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be }
K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 }
K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa }
K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 }
K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed }
K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a }
K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c }
K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 }
K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 }
K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 }
K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 }
K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 }
K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 }
K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }
//Initialize variables:
var int a0 := 0x67452301 //A
var int b0 := 0xefcdab89 //B
var int c0 := 0x98badcfe //C
var int d0 := 0x10325476 //D
//Pre-processing: adding a single 1 bit
append „1“ bit to message
/* Notice: the input bytes are considered as bits strings,
  where the first bit is the most significant bit of the byte.[1]
//Pre-processing: padding with zeros
append „0“ bit until message length in bit ≡ 448 (mod 512)
append length mod (2 pow 64) to message
//Process the message in successive 512-bit chunks:
for each 512-bit chunk of message
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
//Initialize hash value for this chunk:
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
//Main loop:
    for i from 0 to 63
        if 0 ≤ i ≤ 15 then
            F := (B and C) or ((not B) and D)
            g := i
        else if 16 ≤ i ≤ 31
            F := (D and B) or ((not D) and C)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47
            F := B xor C xor D
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63
            F := C xor (B or (not D))
            g := (7×i) mod 16
        dTemp := D
        D := C
        C := B
        B := B + leftrotate((A + F + K[i] + M[g]), s[i])
        A := dTemp
    end for
//Add this chunk's hash to result so far:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for
var char digest[16] := a0 append b0 append c0 append d0 //(Output is in little-endian)
//leftrotate function definition
leftrotate (x, c)
    return (x << c) binary or (x >> (32-c));

MD5 хешове редактиране

128-битовите MD5 хешове обикновено се представят като низ от 32 шестнайсететични цифри. Следващия приемр демонстрира 43-байтово входно съобщение в ASCII кодировка и съответния MD5 хеш:

MD5(„Жълтата дюля беше щастлива, че пухът, който цъфна, замръзна като гьон“)
= 77b60f1c4fb8bb5aa2895c7ad9e994d9

Дори една малка промяна в горното изречение ще доведе доведе до почти изцяло различен хеш, явление дължащо се на т.н ефект на лавината. Например, ако бъде добавена точка в края на изречението резултатът ще е следния:

MD5("Жълтата дюля беше щастлива, че пухът, който цъфна, замръзна като гьон.")
= cfa6723e71621f633f3d162ef5cd7c9b

Резултатът от MD5 хеширането на празен символен низ е:

MD5("")
= d41d8cd98f00b204e9800998ecf8427e

Алгоритъмът за кодиране на MD5 може да работи с входни данни състоящи се от произволен брой битове, като не е необходимо броя да е кратен на 8 бита (октети, байтове) както е в примерите дадени по-горе. При някои имплементации като md5sum може да има ограничение до октети, или да няма поддръжка на „стрийминг“ за съобщения, чиято дължина не е предварително известна.

Реализация редактиране

По-долу е представена една реализация на псевдокода на MD5 алгоритъма, написана на езика C++.

/*
 * Simple MD5 implementation
 *
 * Compile with: gcc -o md5 md5.c
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

// Constants are the integer part of the sines of integers (in radians) * 2^32.
const uint32_t k[64] = {
0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 };

// r specifies the per-round shift amounts
const uint32_t r[] = {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
                      5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20,
                      4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
                      6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21};

// leftrotate function definition
#define LEFTROTATE(x, c) (((x) << (c)) | ((x) >> (32 – (c))))

void to_bytes(uint32_t val, uint8_t *bytes)
{
    bytes[0] = (uint8_t) val;
    bytes[1] = (uint8_t) (val >> 8);
    bytes[2] = (uint8_t) (val >> 16);
    bytes[3] = (uint8_t) (val >> 24);
}

uint32_t to_int32(const uint8_t *bytes)
{
    return (uint32_t) bytes[0]
| ((uint32_t) bytes[1] << 8)
| ((uint32_t) bytes[2] << 16)
| ((uint32_t) bytes[3] << 24);
}

void md5(const uint8_t *initial_msg, size_t initial_len, uint8_t *digest) {

    // These vars will contain the hash
    uint32_t h0, h1, h2, h3;

    // Message (to prepare)
    uint8_t *msg = NULL;

    size_t new_len, offset;
    uint32_t w[16];
    uint32_t a, b, c, d, i, f, g, temp;

    // Initialize variables – simple count in nibbles:
    h0 = 0x67452301;
    h1 = 0xefcdab89;
    h2 = 0x98badcfe;
    h3 = 0x10325476;

    //Pre-processing:
    //append "1" bit to message
    //append "0" bits until message length in bits ≡ 448 (mod 512)
    //append length mod (2^64) to message

    for (new_len = initial_len + 1; new_len % (512/8) != 448/8; new_len++)
        ;

    msg = (uint8_t*)malloc(new_len + 8);
    memcpy(msg, initial_msg, initial_len);
    msg[initial_len] = 0x80; // append the "1" bit; most significant bit is "first"
    for (offset = initial_len + 1; offset < new_len; offset++)
        msg[offset] = 0; // append "0" bits

    // append the len in bits at the end of the buffer.
    to_bytes(initial_len*8, msg + new_len);
    // initial_len>>29 == initial_len*8>>32, but avoids overflow.
    to_bytes(initial_len>>29, msg + new_len + 4);

    // Process the message in successive 512-bit chunks:
    //for each 512-bit chunk of message:
    for(offset=0; offset<new_len; offset += (512/8)) {

        // break chunk into sixteen 32-bit words w[j], 0 ≤ j ≤ 15
        for (i = 0; i < 16; i++)
            w[i] = to_int32(msg + offset + i*4);

        // Initialize hash value for this chunk:
        a = h0;
        b = h1;
        c = h2;
        d = h3;

        // Main loop:
        for(i = 0; i<64; i++) {

            if (i < 16) {
                f = (b & c) | ((~b) & d);
                g = i;
            } else if (i < 32) {
                f = (d & b) | ((~d) & c);
                g = (5*i + 1) % 16;
            } else if (i < 48) {
                f = b ^ c ^ d;
                g = (3*i + 5) % 16;
            } else {
                f = c ^ (b | (~d));
                g = (7*i) % 16;
            }

            temp = d;
            d = c;
            c = b;
            b = b + LEFTROTATE((a + f + k[i] + w[g]), r[i]);
            a = temp;

        }

        // Add this chunk's hash to result so far:
        h0 += a;
        h1 += b;
        h2 += c;
        h3 += d;

    }

    // cleanup
    free(msg);

    //var char digest[16] := h0 append h1 append h2 append h3 //(Output is in little-endian)
    to_bytes(h0, digest);
    to_bytes(h1, digest + 4);
    to_bytes(h2, digest + 8);
    to_bytes(h3, digest + 12);
}

int main(int argc, char **argv) {
    char *msg = argv[1];
    size_t len;
    int i;
    uint8_t result[16];

    if (argc < 2) {
        printf("usage: %s 'string'\n", argv[0]);
        return 1;
    }

    len = strlen(msg);

    // benchmark
    for (i = 0; i < 1000000; i++) {
        md5((uint8_t*)msg, len, result);
    }

    // display result
    for (i = 0; i < 16; i++)
        printf("%2.2x", result[i]);
    puts("");

    return 0;
}

Входното съобщение, което трябва да се хешира, се подава като първи параметър при стартиране на командата (виж main(...,...) функцията).

Източници редактиране

  1. RFC 1321, section 2, „Terminology and Notation“, Page 2.

Вижте също редактиране

Външни препратки редактиране