MD4

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 16. října 2021; ověření vyžaduje 1 úpravu .

MD4
Vytvořeno	1990_ _
zveřejněno	října 1990_ _
Předchůdce	MD2
Nástupce	MD5
Velikost hash	128 bit
Počet kol	3
Typ	hashovací funkce

MD4 ( Message Digest 4 ) je kryptografická hašovací funkce vyvinutá profesorem University of Massachusetts Ronaldem Rivestem v roce 1990 a poprvé popsána v RFC 1186 . Vzhledem k libovolné vstupní zprávě funkce vygeneruje 128bitovou hodnotu hash nazvanou souhrn zprávy . Tento algoritmus se používá v ověřovacím protokolu MS-CHAP vyvinutém společností Microsoft k provádění postupů ověřování na vzdálených pracovních stanicích Windows . Je to předchůdce MD5 .

Algoritmus MD4

Předpokládá se, že vstupem je zpráva složená z bitů, jejichž hash musíme vypočítat. Zde je libovolné nezáporné celé číslo ; může být nula, nemusí být násobkem osmi a může být libovolně velká. Napišme zprávu kousek po kousku ve tvaru: $b$ $b$

m_0 m_1 \ldots m_{b-1}

Následuje 5 kroků používaných k výpočtu hash zprávy.

Krok 1. Přidání chybějících bitů.

Zpráva je rozšířena tak, že její délka v bitech modulo 512 je 448. V důsledku rozšíření je tedy zpráva o 64 bitů kratší než násobek délky 512 bitů. Rozšíření se provede vždy, i když má zpráva původně správnou délku.

Rozšiřování se provádí následovně: ke zprávě se přidá jeden bit rovný 1 a poté se přidávají bity rovné 0, dokud délka zprávy není 448 modulo 512. Celkem se ke zprávě přidá alespoň 1 bit, a maximálně 512.

Krok 2. Přidání délky zprávy.

64bitová reprezentace (délka zprávy před přidáním výplňových bitů) je přidána k výsledku předchozího kroku. V nepravděpodobném případě, že je větší než , se použije pouze nejméně významných 64 bitů. Tyto bity jsou přidány jako dvě 32bitová slova, přičemž slovo obsahující nejméně významné bity se přidává jako první. $b$ $b$ $2^{64}$

V této fázi (po sečtení bitů a délky zprávy) dostaneme zprávu o délce, která je násobkem 512 bitů. To je ekvivalentní této zprávě, která je násobkem 16 32bitových slov. Označme pole slov ve výsledné zprávě (zde násobek 16). $M[0 \ldots N-1]$ $N$

Krok 3. Inicializujte vyrovnávací paměť MD.

K výpočtu hashe zprávy se používá vyrovnávací paměť sestávající ze 4 slov (32bitové registry): . Tyto registry jsou inicializovány následujícími hexadecimálními čísly (nejprve nižšími bajty): $(A,B,C,D)$

slovo : 01 23 45 67

A

slovo : 89 ab cd ef

B

slovo : fe dc ba 98

C

slovo : 76 54 32 10

D

Krok 4. Zpracování zprávy v blocích po 16 slovech.

Nejprve definujeme tři pomocné funkce, z nichž každá přijímá tři 32bitová slova jako vstup a vypočítává z nich jedno 32bitové slovo.

F(X,Y,Z)=XY\nebo \neg XZ

G(X,Y,Z)=XY\nebo XZ\lor YZ

H(X,Y,Z)=X\oplus Y\oplus Z

Funguje jako podmíněný výraz na každé bitové pozici : if , then ; jinak . Funkce by mohla být definována pomocí namísto , protože a nemohou se obě rovnat . působí na každou pozici bitu jako funkce maximální hodnoty: pokud jsou alespoň ve dvou slovech odpovídající bity , pak se vrátí v tomto bitu, jinak vrátí bit rovný . Je zajímavé poznamenat, že pokud jsou bity a jsou statisticky nezávislé, pak budou statisticky nezávislé také bity a . Funkce se implementuje bitově , má stejnou vlastnost jako . $F$ $X$ $Y$ $Z$ $F$ $+$ $\lor$ $XY$ $\neg XZ$ $jeden$ $G$ $X,Y,Z$ $jeden$ $G$ $jeden$ $G$ $0$ $X$ $Y$ $Z$ $F(X,Y,Z)$ $G(X,Y,Z)$ $H$ $xor$ $F$ $G$

Hašovací algoritmus v abstraktním programovacím jazyce :

/* Zpracuj každý blok 16 slov */ pro i = 0 až N / 16-1 do /* Zadejte i-tý blok do proměnné X */ pro j = 0 až 15 do nastavte X [ j ] na M [ i * 16 + j ]. konec /* konec smyčky na j */ /* Uložit A jako AA, B jako BB, C jako CC a D jako DD */ AA = A B.B. = B CC = C DD = D /* 1. kolo */ /* Nechť [abcd ks] znamená následující operaci: a = (a + F(b,c,d) + X[k]) <<< s. */ /* Proveďte následujících 16 operací: */ [ ABCD 0 3 ] [ DABC 1 7 ] [ CDAB 2 11 ] [ BCDA 3 19 ] [ ABCD 4 3 ] [ DABC 5 7 ] [ CDAB 6 11 ] [ BCDA 7 19 ] [ ABCD 8 3 ] [ DABC 9 7 ] [ CDAB 10 11 ] [ BCDA 11 19 ] [ ABCD 12 3 ] [ DABC 13 7 ] [ CDAB 14 11 ] [ BCDA 15 19 ] /* 2. kolo */ /* Nechť [abcd ks] označuje následující operaci: a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. */ /* Proveďte následujících 16 operací: */ [ ABCD 0 3 ] [ DABC 4 5 ] [ CDAB 8 9 ] [ BCDA 12 13 ] [ ABCD 1 3 ] [ DABC 5 5 ] [ CDAB 9 9 ] [ BCDA 13 13 ] [ ABCD 2 3 ] [ DABC 6 5 ] [ CDAB 10 9 ] [ BCDA 14 13 ] [ ABCD 3 3 ] [ DABC 7 5 ] [ CDAB 11 9 ] [ BCDA 15 13 ] /* 3. kolo */ /* Nechť [abcd ks] znamená následující operaci: a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */ /* Proveďte následujících 16 operací: */ [ ABCD 0 3 ] [ DABC 8 9 ] [ CDAB 4 11 ] [ BCDA 12 15 ] [ ABCD 2 3 ] [ DABC 10 9 ] [ CDAB 6 11 ] [ BCDA 14 15 ] [ ABCD 1 3 ] [ DABC 9 9 ] [ CDAB 5 11 ] [ BCDA 13 15 ] [ ABCD 3 3 ] [ DABC 11 9 ] [ CDAB 7 11 ] [ BCDA 15 15 ] /* Poté provedeme následující operace sčítání. (Zvyšte hodnotu v každém registru o hodnotu, kterou měl před iterací přes i */ A = A + AA B = B + BB C = C + CC D = D + DD konec /* konec smyčky na i */

Komentář. Hodnota 5A827999 je 32bitová hexadecimální konstanta, první bajty jsou vysoké. Je to druhá odmocnina ze 2 . Je také v osmičkovém zobrazení: 013240474631. Hodnota 6ED9EBA1 je hexadecimální 32bitová konstanta, první bajty jsou vysoké. Je to druhá odmocnina ze 3. Je také v osmičce: 015666365641. Tato data jsou uvedena v Knuth, The Art of Computer Programming , 1981 Edition, svazek 2, strana 660, tabulka 2.

Krok 5. Vytvoření hashe.

Výsledek (hashovací funkce) se získá jako ABCD. To znamená, že vypíšeme 128 bitů, počínaje nejméně významným bitem A a konče nejvýznamnějším bitem D.

Implementace algoritmu v jazyce C je obsažena v RFC 1320 .

Příklady hashů

128bitové hash MD4 jsou 32místné číslo v hexadecimálním formátu. Následující příklad ukazuje hash 43bajtového řetězce ASCII :

MD4(" Rychlá hnědá liška skáče přes líného psa ") = 1bee69a46ba811185c194762abaeae90

Jakákoli i sebemenší změna v hashované informaci má za následek úplně jiný hash, například změna jednoho písmene z d na c v příkladu :

MD4 ("Rychlá hnědá liška skáče přes líného voza ") = b86e130ce7028da59e672d56ad0113df

Příklad MD4 hash pro "null" řetězec:

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0

Srovnání s MD5

MD4 používá tři smyčky po 16 krocích, zatímco MD5 používá čtyři smyčky po 16 krocích.

V MD4 se extra konstanta v první smyčce nepoužije. Podobná dodatečná konstanta se používá pro každý z kroků ve druhé smyčce. Další přídavná konstanta se používá pro každý z kroků ve třetí smyčce. V MD5 jsou pro každý ze 64 kroků aplikovány různé další konstanty T[i].

MD5 používá čtyři základní logické funkce, jednu na cyklus, ve srovnání s MD4 tři, jednu na cyklus.

V MD5 se v každém kroku aktuální výsledek přičte k výsledku předchozího kroku. Například výsledkem prvního kroku je upravené slovo A. Výsledek druhého kroku je uložen v D a je tvořen přidáním A k výsledku elementární funkce, cyklicky posunutým doleva o určitý počet bitů. . Podobně je výsledek třetího kroku uložen v C a je tvořen přidáním D k cyklickému vlevo posunutému výsledku elementární funkce. MD4 nezahrnuje tento poslední přídavek.

Zabezpečení

Úroveň zabezpečení stanovená v MD4 byla navržena tak, aby vytvořila dostatečně stabilní hybridní systémy digitálního podpisu založené na MD4 a kryptosystému veřejného klíče. Ronald Rivest věřil, že hashovací algoritmus MD4 by mohl být také použit pro systémy, které potřebují silnou kryptografickou sílu . Zároveň ale poznamenal, že MD4 byl vytvořen především jako velmi rychlý hashovací algoritmus, takže může být špatný z hlediska kryptografické síly. Jak ukázaly následné studie, měl pravdu a pro aplikace, kde je především důležitá kryptografická síla, se začal používat algoritmus MD5 .

Zranitelnosti

Zranitelnosti v MD4 byly demonstrovány v článku Berta den Boera a Antona Bosselarse v roce 1991. První kolize byla nalezena Hansem Dobbertinem v roce 1996.

Viz také

Odkazy

Hledání kolizí

Vylepšený Collision Attack na MD4

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA