Algoritmus souhrnu zpráv 5

Message-Digest Algorithm 5 ( MD5 ) je široce používaná kryptografická hashovací funkce, která generuje 128bitovou hash hodnotu z jakékoli zprávy. To umožňuje například jednoduchou kontrolu správnosti stahování. Je to jedna z řady kryptografických hašovacích funkcí vyvinutých Ronaldem L. Rivestem na Massachusetts Institute of Technology v roce 1991 , kdy analýza ukázala, že její předchůdce, MD4, bude pravděpodobně nejistý. Mezitím se MD5 také již nepovažuje za zabezpečený, protože je možné s přiměřeným úsilím generovat různé zprávy, které mají stejnou hodnotu hash MD5.

MD5 hash

128bitový hash MD5 (také známý jako „přehledy zpráv“) se obvykle označuje jako 32místná hexadecimální čísla. Následující příklad ukazuje 59 bajtový vstup ASCII a přidružený hash MD5:

md5("Franz jagt im komplett verwahrlosten Taxi quer durch Bayern") =
a3cca2b2aa1e3b5b3b5aad99a8529074

Malá změna v textu vytvoří úplně jiný hash. Například u Franka místo Franze (změněno pouze jedno písmeno):

md5("Frank jagt im komplett verwahrlosten Taxi quer durch Bayern") =
7e716d0e702df0505fc72e2b89467910

Hash řetězce nulové délky je:

md5("") = d41d8cd98f00b204e9800998ecf8427e

Použití a dostupnost

Většina linuxových distribucí ve výchozím nastavení instaluje program md5sum jako součást coreutils .

Příkaz md5 je k dispozici v operačních systémech odvozených od BSD , jako je macOS .

Na mnoha dalších unixových derivátech si vystačíte s většinou nainstalovaným programem OpenSSL .

Operační systémy Microsoft Windows od verze Windows 8.1 nebo Windows Server 2012 R2 mají ve výchozím nastavení rutinu PowerShell Get-Filehash.

Kontrola hodnoty hash MD5

Po úspěšném stažení souboru nebo složky se soubory se přidružená hodnota hash MD5 často zpřístupní v jiném souboru. Hodnotu hash lze poté vypočítat ze staženého souboru pomocí testovacího programu, který se poté porovná s hodnotou hash zpřístupněnou. Pokud jsou obě hodnoty hash identické, je potvrzena integrita staženého souboru. Při stahování souboru tedy nedošlo k žádným chybám. To neposkytuje žádné zabezpečení, pokud jde o cílenou manipulaci s daty útočníkem (útok typu man-in-the-middle ), protože útočník může manipulovat také s přenosem hash hodnoty MD5.

Situace je poněkud odlišná při stahování souborů pomocí zrcadlového serveru. Možným útočníkem je zde operátor zrcadlového serveru. Aby se tím vyloučila manipulace, nemusí být přidružená hodnota hash MD5 načtena ze zrcadlového serveru, ale z původního zdroje.

algoritmus

Operace MD5. MD5 se skládá z 64 operací tohoto typu, seskupených do 4 běhů, z nichž každý má 16 operací. F je nelineární funkce, která se používá v příslušném běhu. M _i znamená 32-bitový blok vstupního proudu a K _i jiné 32-bitové konstantní pro každou operaci; _s označuje rotaci vlevo po bitu o místa s , kde s se liší pro každou operaci. označuje přídavek modulo 2 ³² .

MD5 je založen na konstrukci Merkle-Damgård pro generování výstupu pevné délky (128 bitů) ze zprávy proměnné délky. Nejprve je k výstupní zprávě připojen jeden. Výstupní zpráva je poté vyplněna nulami, takže její délka je 64 bitů od dělení 512. Nyní je připojeno 64bitové číslo kódující délku výstupní zprávy. Délka zprávy je nyní dělitelná 512.

Hlavní algoritmus MD5 používá 128bitovou vyrovnávací paměť ve čtyřech 32bitových slovech A , B , C a D jsou rozděleny. Ty jsou inicializovány určitými konstantami. Funkce komprese je nyní volána na této vyrovnávací paměti s prvním 512bitovým blokem jako klíčovým parametrem. Blok zpráv je zpracován ve čtyřech podobných fázích, které kryptografové nazývají „kola“. Každé kolo se skládá ze 16 operací založených na nelineární funkci „F“, modulárním přidáváním a otáčení doleva. Existují čtyři možné funkce „F“, v každém kole se používá jiná:

${\ displaystyle F (X, Y, Z) = (X \ klín {Y}) \ vee (\ neg {X} \ klín {Z})}$

${\ displaystyle G (X, Y, Z) = (X \ klín {Z}) \ vee (Y \ klín \ neg {Z})}$

${\ displaystyle H (X, Y, Z) = X \ oplus Y \ oplus Z}$

${\ displaystyle I (X, Y, Z) = Y \ oplus (X \ vee \ neg {Z})}$

${\ displaystyle \ oplus, \ klín, \ vee, \ neg}$ každý znamená operace XOR, AND, OR a NOT.

Stejná funkce je volána na výsledku s druhým blokem zpráv jako parametrem a tak dále, až do posledního 512bitového bloku. Výsledkem je opět 128bitová hodnota - součet MD5.

Referenční implementace

RFC1321 také obsahuje implementaci algoritmu v jazyce C pod názvem „Dodatek A Reference Implementation“. Tato implementace z roku 1992 společností RSA Data Security, Inc. běží nesprávně na mnoha 64bitových systémech a vypočítává nesprávné hodnoty hash. Je to proto, že v souboru global.h jsou řádky

/* UINT4 defines a four byte word */
typedef unsigned long int UINT4;

nejsou nutně uvedeny. Chyba může být opravena prohlédnutím těchto řádků

#include <inttypes.h>
...
/* UINT4 defines a four byte word */
typedef uint32_t UINT4;

vyměnit. Další spustitelnou implementaci od L Petera Deutsche najdete na Sourceforge.net. Tato implementace je odvozena od specifikace RFC1321 a nikoli od výše zmíněné referenční implementace v RFC1321. Při použití této implementace proto nejsou nutné žádné odkazy na RSA Data Security, Inc.

Pseudo kód

Následuje pseudokód pro algoritmus MD5 .

// Beachte: Alle Variablen sind vorzeichenlose (unsigned) 32-Bit-Werte und
// verhalten sich bei Berechnungen kongruent (≡) modulo 2^32

 // Definition der linksrotation Funktion, c ist der übergebene Wert von s[i] - siehe Hauptschleife
linksrotation(x, c)
    return (x << c)binär or (x >> (32-c));

// s definiert die Anzahl der Bits, die pro Runde rotiert werden:
var uint[64] s, K
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}

// Verwende den binären Vorkommateil vom 2^32-fachen Betrag des Sinus
// von Integerwerten als Konstanten:
für alle i von 0 bis 63
(
    K[i] := floor(abs(sin(i + 1)) × 2^32)
)

// Alternativ kann man auch folgende Tabelle nutzen:
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 }

// Initialisiere die Variablen: (lt. RFC 1321)
var uint a0 := 0x67452301
var uint b0 := 0xEFCDAB89
var uint c0 := 0x98BADCFE
var uint d0 := 0x10325476

// Vorbereitung der Nachricht 'message':
var uint message_laenge := bit_length(message)
erweitere message um bit "1"
erweitere message um bits "0" bis Länge von message in bits ≡ 448 (mod 512)
erweitere message um message_laenge als 64-Bit little-endian Integer

// Verarbeite die Nachricht in aufeinander folgenden 512-Bit-Blöcken:
für alle 512-Bit Block von message
(
    unterteile Block in 16 32-bit little-endian Worte M[i], 0 ≤ i ≤ 15

    // Initialisiere den Hash-Wert für diesen Block:
    var uint A := a0
    var uint B := b0
    var uint C := c0
    var uint D := d0

    // Hauptschleife:
    // not Operator entspricht dem Einerkomplement
    für alle i von 0 bis 63
    (
        wenn 0 ≤ i ≤ 15 dann
            F := (B and C) or ((not B) and D)
            g := i
        sonst wenn 16 ≤ i ≤ 31 dann
            F := (B and D) or (C and (not D))
            g := (5×i + 1) mod 16
        sonst wenn 32 ≤ i ≤ 47 dann
            F := B xor C xor D
            g := (3×i + 5) mod 16
        sonst wenn 48 ≤ i ≤ 63 dann
            F := C xor (B or (not D))
            g := (7×i) mod 16
        wenn_ende

        temp := D
        D := C
        C := B
        B := B + linksrotation((A + F + K[i] + M[g]), s[i])
        A := temp
    )

    // Addiere den Hash-Wert des Blocks zur Summe der vorherigen Hashes:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
)

var uint digest := a0 anfügen b0 anfügen c0 anfügen d0 // Darstellung als little-endian

Místo původní formulace z RFC 1321 lze ke zvýšení účinnosti použít následující:

( 0 ≤ i ≤ 15): F := D xor (B and (C xor D))
(16 ≤ i ≤ 31): F := C xor (D and (B xor C))

Útoky

Již v roce 1993 publikovali Bert de Boer a Antoon Bosselaers algoritmus pro generování pseudokolizí na kompresní funkci MD5: dvě různé inicializační konstanty vedou ke stejné hash hodnotě pro stejnou zprávu.

V roce 1996, Hans Dobbertin našel na kolizi pro dva různé zprávy. Jedná se o skutečnou kolizi, tj. Dvě speciálně připravené zprávy, které se liší, ale přesto vedou ke stejné hash hodnotě. Dobbertin však použil upravenou variantu MD5, ve které jsou použity další inicializační konstanty (pro A, B, C, D). Rovněž nebylo možné určit obsah konfliktních zpráv. Praktické útoky na MD5 nebyly možné, ale vyjasnily se slabiny MD5, takže kryptologové doporučili přejít na jiné hashovací funkce.

V roce 2004 se čínské výzkumné skupině vedené Xiaoyunem Wangem podařilo systematicky generovat kolize, pokud lze podle potřeby zvolit začátek zprávy, ale obě zprávy jsou identické (kolize se společnou předponou) . Na tomto začátku zprávy lze s přiměřeným úsilím vypočítat dvě různá pokračování zprávy, která vedou ke stejné hodnotě hash. Tato kolize se zachová, i když je k oběma zprávám připojena stejná přípona (každá se skládá ze stejného začátku a jednoho nebo druhého pokračování). Tento útok vylepšil Wang a další výzkumné skupiny, takže počítač nyní může během několika sekund vypočítat kolizi MD5.

Snaha najít kolizi je větší, pokud je začátek dvou zpráv odlišný (kolize s vybranou předponou) . V roce 2008 se týmu vedenému Marcem Stevensem a Alexandrem Sotirovem podařilo provést takový kolizní útok s cílem vytvořit padělaný certifikát CA uznaný jako důvěryhodný. Díky tomu byli v zásadě schopni vytvořit certifikát SSL pro libovolnou adresu URL a obejít tak bezpečnostní mechanismy HTTPS na webu. Práce byla poprvé představena v prosinci 2008 na 25. komunikačním kongresu chaosu a o několik měsíců později publikována ve vědeckém článku. K výpočtu srážky použili shluk 200 her Sony PlayStation 3 .

Plamen škodlivého softwaru pro Windows , objevený v roce 2012, používá falešný certifikát pro podepisování kódu založený na nové a dříve neznámé variantě vybrané kolize předpony pro MD5.

I při zmíněných metodách nelze útoky před obrazem provést v rozumném čase. Ve výsledku je stále nemožné následně vytvořit padělaný dokument, který odpovídá konkrétnímu certifikátu vygenerovanému pomocí MD5 . V mnoha případech je však možné pomocí kolizních útoků vytvořit dva dokumenty, jejichž výsledkem je stejná hodnota hash MD5, poté mít podepsaný první legitimní dokument a poté jej nahradit druhým, padělaným dokumentem. Na tomto pozadí není vhodné pokračovat v používání MD5.

bezpečnostní

MD5 je široce používán a původně byl považován za kryptograficky bezpečný. Již v roce 1994 objevili Bert den Boer a Antoon Bosselaers v MD5 pseudokolizice. Zásadní práci při hledání skutečných kolizí provedl také Hans Dobbertin (v té době na BSI ), který již vyvinul úspěšný útok na MD4 a přenesl použité techniky na MD5.

Odolnost proti kolizi

V srpnu 2004 čínský tým vědců zjistil první kolizi v plné funkci MD5. Na klastru IBM P690 trval jejich první útok hodinu a na základě toho bylo možné zjistit další kolize během maximálně pěti minut. Krátce po zveřejnění čínské práce byl MD5CRK přerušen a pokusil se najít kolize pomocí metod hrubou silou .

Stručný popis: Vstupní blok (512 bitů) je upraven, přičemž je proveden pokus o vytvoření určitého rozdílu oproti originálu ve výstupu. Složitá analýza algoritmu může snížit počet neznámých bitů do takové míry, že je to matematicky úspěšné. Stejné metody se používají v dalším 512bitovém bloku k pokusu o zrušení rozdílu. Falzifikát proto vyžaduje koherentní blok dat 1024 bitů = 128 bajtů, což výrazně omezuje jeho použití.

Mezitím kolizní útoky pokročily tak daleko, že další použití MD5, zejména ve scénářích, kdy uživatel plně nekontroluje soubory, které mají být podepsány, musí být odmítnuto. Zkouška provedena v roce 2009 počítačový časopis c't pomocí GPGPU umožňuje high-end herní PC, asi rok starý, se dvěma Nvidia GeForce 9800 GX2 (čtyři grafické procesory celkem ) najít kolizi v necelých 35 minut .

Jednosměrná funkce

Další metodu útoku představují duhové tabulky, které obsahují řetězce znaků s přidruženými hodnotami hash MD5. Útočník vyhledá v těchto tabulkách zadanou hodnotu hash a poté může načíst vhodné řetězce znaků. Tento útok lze použít hlavně k odhalení hesel, která jsou uložena jako hash MD5. Duhové tabulky, které jsou k tomu potřebné, jsou však velmi velké a jejich vytvoření vyžaduje velké výpočetní úsilí. Proto je tento útok obecně možný pouze s krátkými hesly. V tomto případě existují předpočítané duhové tabulky, ve kterých je vynecháno alespoň výpočetní úsilí o vytvoření seznamu. Použití soli , tj. Náhodné, nepředvídatelné hodnoty, která je přidána do prostého textu, však ničí účinnost předpočítaných duhových tabulek.

souhrn

Hledání kolizí znamená hledání dvou různých textů Ma M's hash(M) = hash(M'). V případě pre-image útoku, jeden hledá daný Mnebo hash(M)jeden M'tak, že hash(M) = hash(M'). Jelikož v útoku před obrazem M'ovládáte pouze vy , ne také M, je to mnohem obtížnější.

V současné době je MD5 rozbit pouze v případě kolizních útoků.

Pro bezpečné ukládání hesel je však třeba vzít v úvahu i jiné algoritmy, které byly speciálně vyvinuty pro tento účel, např. B. bcrypt nebo PBKDF2 .

Protože není znám žádný první útok před obrazem , jsou hash MD5 podepsané v minulosti v současnosti (2013) stále v bezpečí.

Viz také

• Kryptologická hashovací funkce

literatura

• Hans Dobbertin: Kryptoanalýza komprese MD5 . Oznámení na internetu, květen 1996 (anglicky, online )
• Hans Dobbertin: Stav MD5 po nedávném útoku . In: CryptoBytes 2 (2), 1996 (anglicky)
• Philip Hawkes, Michael Paddon, Gregory G. Rose: Musings on the Wang et al. Kolize MD5 . Podrobná analýza rozdílového útoku na MD5
• Vlastimil Klima: Hledání kolizí MD5 na notebooku pomocí modifikací více zpráv . Opět vylepšená technika útoku

webové odkazy

• RFC 1321 - MD5 Message-Digest Algorithm; R. Rivest, duben 1992 (anglicky)
• MD5 Collision Demo Dva různé programy se stejným hash MD5 a knihovnou pro generování dalších takových programů
• papíry a ukázky ke kolizím MD5 (anglicky)
• Jürgen Schmidt: Hash me, druhý
• Online generátor pro generování hashů MD5
• Sourceforge.net : knihovna MD5 založená na RFC1321 (bez RSA)

Individuální důkazy

1. ↑ Popis rutiny Powershell Get-Filehash
2. ^ Bert de Boer, Antoon Bosselaers: Srážky pro kompresní funkci MD5 . In: Proceedings of EUROCRYPT '93 Workshop on the theory and application of cryptographic techniques on Advances in cryptology . Springer-Verlag, New York 1994, ISBN 3-540-57600-2
3. ↑ Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger: MD5 je dnes považován za škodlivý. 30. prosince 2008, zpřístupněno 30. prosince 2008 . 
4. ↑ Marc Stevens: TECHNICKÉ ZÁKLADY ÚTOKU FLAME COLLISION. CWI, 7. června 2012, zpřístupněno 8. června 2012 : „výsledky ukázaly, že nebyl použit náš kolizní útok s vybranou předponou, ale zcela nová a neznámá varianta.“ 
5. ↑ Analýza kolizí (PDF; 57 kB)
6. ↑ Vysvětlení problému s kolizí při manipulaci s hash hodnotami md5
7. ↑ Stefan Arbeiter, Matthias Deeg: Bunte Rechenknechte - grafické karty urychlují crackery hesel . In: c't, vydání 06/2009, s. 204. ( poplatek ke stažení )