MD4

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 16. lokakuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

MD4
Luotu	1990_ _
julkaistu	lokakuuta 1990_ _
Edeltäjä	MD2
Seuraaja	MD5
Hash-koko	128 bittinen
Kierrosten lukumäärä	3
Tyyppi	hash-toiminto

MD4 ( Message Digest 4 ) on Massachusettsin yliopiston professori Ronald Rivestin vuonna 1990 kehittämä kryptografinen hajautusfunktio , joka kuvattiin ensimmäisen kerran RFC 1186 : ssa . Kun annetaan mielivaltainen syöttöviesti , funktio luo 128-bittisen hajautusarvon, jota kutsutaan sanoman tiivisteeksi . Tätä algoritmia käytetään Microsoftin kehittämässä MS-CHAP- todennusprotokollassa suorittamaan todennustoimenpiteitä Windows - etätyöasemissa . Se on MD5 :n edeltäjä .

MD4-algoritmi

Oletetaan, että syöte on biteista koostuva viesti , jonka hash on laskettava. Tässä on mielivaltainen ei-negatiivinen kokonaisluku ; se voi olla nolla, sen ei tarvitse olla kahdeksan kerrannainen ja se voi olla mielivaltaisen suuri. Kirjoitetaan viesti pala kerrallaan, muodossa: $b$ $b$

m_0 m_1 \ldots m_{b-1}

Seuraavassa on viisi vaihetta, joita käytetään viestin hajautusarvon laskemiseen.

Vaihe 1. Puuttuvien bittien lisääminen.

Viestiä laajennetaan siten, että sen pituus bitteinä modulo 512 on 448. Laajennuksen seurauksena viesti jää siis 64 bittiä 512 bitin pituudeltaan monikertaiseksi. Laajennus suoritetaan aina, vaikka viesti olisi alun perin oikean pituinen.

Laajennus tehdään seuraavasti: viestiin lisätään yksi bitti, joka on yhtä suuri kuin 1, ja sitten lisätään bittejä, jotka ovat yhtä suuria kuin 0, kunnes viestin pituus on 448 modulo 512. Yhteensä sanomaan lisätään vähintään 1 bitti, ja enintään 512.

Vaihe 2. Viestin pituuden lisääminen.

64-bittinen esitys (viestin pituus ennen täytebittien lisäämistä) lisätään edellisen vaiheen tulokseen. Siinä epätodennäköisessä tapauksessa, joka on suurempi kuin , käytetään vain vähiten merkitseviä 64 bittiä. Nämä bitit lisätään kahtena 32-bittisenä sanana, jolloin vähiten merkitseviä bittejä sisältävä sana lisätään ensin. $b$ $b$ $2^{64}$

Tässä vaiheessa (bittien ja viestin pituuden lisäämisen jälkeen) saadaan sanoma, jonka pituus on 512 bitin kerrannainen. Tämä vastaa sitä, että tämä viesti on 16 32-bittisen sanan monikerta. Merkitään sanajoukkoa tuloksena olevassa viestissä (tässä 16:n kerrannainen). $M[0 \ldots N-1]$ $N$

Vaihe 3. Alusta MD-puskuri.

Viestin hashin laskemiseen käytetään puskuria, joka koostuu 4 sanasta (32-bittiset rekisterit): . Nämä rekisterit alustetaan seuraavilla heksadesimaaliluvuilla (alemmat tavut ensin): ${\näyttötyyli (A,B,C,D)}$

sana : 01 23 45 67

A

sana : 89 ab cd ef

B

sana : fe dc ba 98

C

sana : 76 54 32 10

D

Vaihe 4. Viestin käsittely 16 sanan lohkoina.

Aluksi määritämme kolme apufunktiota, joista jokainen vastaanottaa kolme 32-bittistä sanaa syötteenä ja laskee niistä yhden 32-bittisen sanan.

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

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

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

Se toimii ehdollisena lausekkeena jokaisessa bittipaikassa : if , then ; muuten . Funktio voidaan määrittää käyttämällä , asemesta , koska ja molemmat eivät voi olla yhtä suuria . vaikuttaa jokaiseen bittipaikkaan maksimiarvon funktiona: jos vähintään kahdessa sanassa vastaavista bitteistä on , niin se palaa kyseisessä bitissä, muuten se palauttaa bitin, joka on yhtä suuri kuin . On mielenkiintoista huomata, että jos bitit ja ovat tilastollisesti riippumattomia, niin bitit ja ovat myös tilastollisesti riippumattomia. Funktio toteuttaa bittikohtaisesti , sillä on sama ominaisuus kuin . $F$ $X$ $Y$ $Z$ $F$ $+$ $\lor$ $XY$ $\neg XZ$ $yksi$ $G$ ${\näyttötyyli X,Y,Z}$ $yksi$ $G$ $yksi$ $G$ $0$ $X$ $Y$ $Z$ $F(X,Y,Z)$ ${\näyttötyyli G(X,Y,Z)}$ $H$ $xor$ $F$ $G$

Tiivistysalgoritmi abstraktilla ohjelmointikielellä :

/* Käsittele jokainen 16 sanan lohko */ i = 0 - N / 16-1 do _ /* Syötä i:s lohko muuttujaan X */ j = 0 - 15 do _ aseta X [ j ] arvoksi M [ i * 16 + j ]. loppu /* j:n silmukan loppu */ /* Tallenna A AA:na, B BB:nä, C CC:nä ja D DD:nä */ AA = A B.B. = B CC = C DD = D /* Erä 1 */ /* Tarkoittaa [abcd ks] seuraavaa operaatiota: a = (a + F(b,c,d) + X[k]) <<< s. */ /* Suorita seuraavat 16 toimintoa: */ [ 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 ] /* Kierros 2 */ /* Merkitään [abcd ks] seuraavaa operaatiota: a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. */ /* Suorita seuraavat 16 toimintoa: */ [ 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 ] /* Kierros 3 */ /* Tarkoittaa [abcd ks] seuraavaa operaatiota: a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */ /* Suorita seuraavat 16 toimintoa: */ [ 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 ] /* Sitten suoritamme seuraavat summaustoiminnot. (Kasvata arvoa jokaisessa rekisterissä sillä määrällä, joka sillä oli ennen iterointia i:n yli */ A = A + AA B = B + BB C = C + CC D = D + DD loppu /* silmukan loppu i:ssä */

Kommentti. Arvo 5A827999 on 32-bittinen heksadesimaalivakio, ensimmäiset tavut ovat korkeita. Se on luvun 2 neliöjuuri . Se on myös oktaalimuodossa: 013240474631. Arvo 6ED9EBA1 on heksadesimaalinen 32-bittinen vakio, ensimmäiset tavut ovat korkeita. Se on luvun 3 neliöjuuri. Se on myös oktaalista: 015666365641. Nämä tiedot on annettu julkaisussa Knuth, The Art of Computer Programming , 1981, painos, osa 2, sivu 660, taulukko 2.

Vaihe 5. Hajautuksen muodostaminen.

Tulos (hash-funktio) saadaan ABCD:nä. Eli kirjoitetaan 128 bittiä alkaen vähiten merkitsevästä A:n bitistä ja päättyen D:n merkittävimpään bittiin.

Algoritmin C -toteutus sisältyy RFC 1320 :een .

Esimerkkejä tiivisteistä

128-bittiset MD4-tiivisteet ovat 32-numeroinen luku heksadesimaalimuodossa. Seuraava esimerkki näyttää 43-tavuisen ASCII -merkkijonon hajautusarvon :

MD4(" Nopea ruskea kettu hyppää laiskan koiran yli ") = 1bee69a46ba811185c194762abaeae90

Pieninkin muutos tiivistetyssä tiedossa johtaa täysin erilaiseen tiivisteeseen, esimerkiksi muuttamalla yksi kirjain d :stä c :ksi esimerkissä :

MD4("Nopea ruskea kettu hyppää laiskan yli " ) = b86e130ce7028da59e672d56ad0113df

Esimerkki MD4-tiivisteestä "nolla"-merkkijonolle:

MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0

Vertailu MD5:een

MD4 käyttää kolmea 16-vaiheista silmukkaa, kun taas MD5 käyttää neljää 16-vaiheista silmukkaa.

MD4:ssä ensimmäisen silmukan ylimääräistä vakiota ei käytetä. Samanlaista lisävakiota käytetään jokaiselle toisen silmukan vaiheelle. Toista lisävakiota käytetään jokaiselle kolmannen silmukan vaiheelle. MD5:ssä erilaisia lisävakioita, T[i], sovelletaan jokaiseen 64 vaiheeseen.

MD5 käyttää neljää peruslogiikkafunktiota, yhtä per sykli, verrattuna MD4:n kolmeen, yksi sykliä kohti.

MD5:ssä jokaisessa vaiheessa nykyinen tulos lisätään edellisen vaiheen tulokseen. Esimerkiksi ensimmäisen vaiheen tulos on muunnettu sana A. Toisen vaiheen tulos tallennetaan D:hen ja muodostetaan lisäämällä A perusfunktion tulokseen, siirrettynä syklisesti vasemmalle tietyllä määrällä bittejä. . Samoin kolmannen vaiheen tulos tallennetaan C:hen ja muodostetaan lisäämällä D perusfunktion sykliseen vasemmalle siirrettyyn tulokseen. MD4 ei sisällä tätä viimeistä lisäystä.

Turvallisuus

MD4:ssä asetettu turvallisuustaso on suunniteltu luomaan riittävän vakaat MD4:ään ja julkisen avaimen salausjärjestelmään perustuvat hybrididigitaaliallekirjoitusjärjestelmät. Ronald Rivest uskoi, että MD4-hajautusalgoritmia voitaisiin käyttää myös järjestelmissä, jotka tarvitsevat vahvaa kryptografista vahvuutta . Mutta samalla hän totesi, että MD4 luotiin ensisijaisesti erittäin nopeaksi hajautusalgoritmiksi, joten se voi olla huono kryptografisen vahvuuden kannalta. Kuten myöhemmät tutkimukset osoittivat, hän oli oikeassa, ja sovelluksissa, joissa kryptografinen vahvuus on ensisijaisesti tärkeä, alettiin käyttää MD5 -algoritmia .

Haavoittuvuudet

MD4:n haavoittuvuudet esitettiin Bert den Boerin ja Anton Bosselarsin artikkelissa vuonna 1991. Ensimmäisen törmäyksen löysi Hans Dobbertin vuonna 1996.

Katso myös

Linkit

Törmäysten etsiminen

Parannettu törmäyshyökkäys MD4:lle

Hash-funktiot
yleinen tarkoitus	Adler-32 CRC Fletcherin tarkistussumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash summa
Kryptografinen	Stribog GOST R 34.11-94 Vyö BLAKE BMW CubeHash KAIKU edonkey2k FSB Fuuga 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 Iho Snefru Tiikeri Whirlpool
Avainten luontitoiminnot	bcrypt PBKDF2 scrypt Argon 2 Lyra 2
Tarkista numero ( vertailu )	Tarkista summa Verhouffin algoritmi Kuun algoritmi Damm-algoritmi Viivakoodi pankkitilit pankkikortit ISIN SNILS OKPO TINA OKATO ISBN OGRN ja OGRNIP VIN
Hashes	Sekkinumeroiden vertailu Todennusprotokollat Viivakoodin vertailu Kryptografia Magneettilinkki Merklen allekirjoitus ed2k UURNA