Преглед на кода на MD5

{{експерт}}
{{машинен превод}}
'''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 2fcab5<span style="color:red">8</span>712467eab 4004583eb8fb7f89
 55ad340609f4b302 83e4888325 <span style="color:red">7</span> 1415a 085125e8f7cdc99f d91dbd<span style="color:red">f</span>280373c5b
 d8823e3156348f5b ae6dacd436c919c6 dd53e2<span style="color:red">b</span>487da03fd 02396306d248cda0
 e99f33420f577ee8 ce54b67080<span style="color:red">a</span>80d1e c69821bcb6a88393 96f965<span style="color:red">2</span>b6ff72a70

 d131dd02c5e6eec4 693d9a0698aff95c 2fcab5<span style="color:red">0</span>712467eab 4004583eb8fb7f89
 55ad340609f4b302 83e4888325<span style="color:red">f</span>1415a 085125e8f7cdc99f d91dbd<span style="color:red">7</span>280373c5b
 d8823e3156348f5b ae6dacd436c919c6 dd53e2<span style="color:red">3</span>487da03fd 02396306d248cda0
 e99f33420f577ee8 ce54b67080<span style="color:red">2</span>80d1e c69821bcb6a88393 96f965<span style="color:red">a</span>b6ff72a70

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

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

== Алгоритъм ==
[[Картинка:MD5 algorithm.svg|мини|300п|Фигура 1. Една операция по MD5 хеширане. Кодирането се състои от 64 такива операции, разделени на 4 етапа от 16 операции.
''F'' е нелинейна функция, за всеки етап от кодирането се ползва различна функция.

С ''M<sub>i</sub>'' са означени 32-битови блокове от входните данни, а с ''K<sub>i</sub>'' се означават 32-битови константи, различни за всяка операция. Със [[Файл:lll.png|left shift]]<sub>''s''</sub> е обозначено логическо изместване наляво със ''s'' позиции, като ''s'' варира за всяка операция. Със [[Файл:Boxplus.png|Addition]] е означена операцията по получаване остатъка от целочисленото делене с 2<sup>32</sup>.]]

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

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

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

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

:<math>F(B,C,D) = (B\wedge{C}) \vee (\neg{B} \wedge{D})</math>
:<math>G(B,C,D) = (B\wedge{D}) \vee (C \wedge \neg{D})</math>
:<math>H(B,C,D) = B \oplus C \oplus D</math>
:<math>I(B,C,D) = C \oplus (B \vee \neg{D})</math>

<math>\oplus, \wedge, \vee, \neg</math> означават логическите операции [[XOR]], [[Logical conjunction|AND]], [[Logical disjunction|OR]] и [[Negation|NOT]].

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

<span style="color:green;">//''Note: All variables are unsigned 32 bit and wrap modulo 2^32 when calculating''</span>
'''var''' ''int''[64] s, K

<span style="color:green;">//''s specifies the per-round shift amounts''</span>
: 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}

<span style="color:green;">//''Use binary integer part of the sines of integers (Radians) as constants:''</span>
 '''for''' i '''from''' 0 '''to''' 63
     K[i] := floor(abs(sin(i + 1)) × (2 '''pow''' 32))
 '''end for'''
<span style="color:green;">//''(Or just use the following table):''</span>
 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 }

 <span style="color:green;">//''Initialize variables:''</span>
 '''var''' ''int'' a0 := 0x67452301 <span style="color:green;">//A</span>
 '''var''' ''int'' b0 := 0xefcdab89 <span style="color:green;">//B</span>
 '''var''' ''int'' c0 := 0x98badcfe <span style="color:green;">//C</span>
 '''var''' ''int'' d0 := 0x10325476 <span style="color:green;">//D</span>

 <span style="color:green;">//''Pre-processing: adding a single 1 bit''</span>
 '''append''' „1“ bit '''to''' message<span style="color:green;">
 /* Notice: the input bytes are considered as bits strings,
   where the first bit is the most significant bit of the byte.<ref>RFC 1321, section 2, „Terminology and Notation“, Page 2.</ref>
   </span>

 <span style="color:green;">//''Pre-processing: padding with zeros''</span>
 '''append''' „0“ bit '''until''' message length in bit ≡ 448 (mod 512)
 '''append''' length '''mod''' (2 '''pow''' 64) '''to''' message

 <span style="color:green;">//''Process the message in successive 512-bit chunks:''</span>
 '''for each''' ''512-bit'' chunk '''of''' message
     break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
 <span style="color:green;">//''Initialize hash value for this chunk:''</span>
     '''var''' ''int'' A := a0
     '''var''' ''int'' B := b0
     '''var''' ''int'' C := c0
     '''var''' ''int'' D := d0
 <span style="color:green;">//''Main loop:''</span>
     '''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'''
 <span style="color:green;">//''Add this chunk's hash to result so far:''</span>
     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 <span style="color:green;">//''(Output is in little-endian)''</span>

 <span style="color:green;">//''leftrotate function definition''</span>
 '''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++.

<syntaxhighlight lang="cpp">
/*
 * 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;
}
</syntaxhighlight>

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

== Източници ==
<references />

== Вижте също ==
* [[Криптография]]
* [[Хеш-функция]]

== Външни препратки ==
* [http://md5-hash-online.waraxe.us/ Безплатен онлайн MD5 калкулатор]
* [http://www.ietf.org/rfc/rfc1321.txt Официално описание на MD5 алгоритъма]

[[Категория:Компютърна сигурност]]
[[Категория:Криптография]]