MD6

MD6
Oprettet 2008
offentliggjort 2008
Hash størrelse variabel, 0<d≤512
Antal runder variabel. Standard, Uden nøgle=40+[d/4], med nøgle=max(80,40+(d/4))
Type hash funktion

MD6 ( Message Digest 6 ) er en  hashingalgoritme med variabel længde udviklet af professor Ronald Rivest fra Massachusetts Institute of Technology i 2008 [1] . Designet til at skabe "fingeraftryk" eller beskedsammendrag af vilkårlig længde. Foreslået at erstatte den mindre avancerede MD5 . Ifølge forfatterne er algoritmen modstandsdygtig over for differentiel kryptoanalyse. Bruges til at kontrollere integriteten og i en vis forstand ægtheden af ​​offentliggjorte meddelelser ved at sammenligne meddelelsesoversigten med den offentliggjorte meddelelse. Denne operation kaldes hashcheck. Hash-funktioner er også meget brugt til at generere nøgler med fast længde til krypteringsalgoritmer baseret på en given nøglestreng.

Historie

MD6 er en af ​​en række algoritmer for meddelelsesfordøjelse udviklet af professor Ronald L. Rivest fra Massachusetts Institute of Technology. MD6 blev først introduceret på Crypto 2008-konferencen som en kandidat til SHA-3- standarden . Men senere i 2009 på samme konference udtalte Rivest, at MD6 endnu ikke var klar til at blive en standard. På den officielle MD6 hjemmeside udtalte han, at selvom ansøgningen ikke formelt er trukket tilbage, har algoritmen stadig problemer med hastighed og manglende evne til at levere sikkerhed i versionen med et reduceret antal runder [2] . Som følge heraf kvalificerede MD6 sig ikke til anden runde af konkurrencen. Tidligere, i december 2008, opdagede en forsker hos Fortify Software en bufferoverløbsfejl i den originale MD6-implementering. Den 19. februar 2009 offentliggjorde professor Rivest detaljerne om denne fejl og leverede også en implementeringsrettelse [3] .

Algoritme

Hash-funktionsalgoritmen bruger nogle meget originale ideer. I én omgang behandles 512 bytes, hvilket gør det vanskeligt at udføre en række angreb og letter parallelisering, som også bruges til træstrukturer.

Indtast data og procedurer

M original besked med længden m , 1 ≤ m ≤ (2 64 - 1) bit
d længden af ​​den resulterende hash i bit, 1 ≤ d ≤ 512
K vilkårlig nøgleværdi af længde keylen bytes (0 ≤ keylen ≤ 64), polstret med nuller til højre med et tal på 64 - keylen
L ikke-negativ 1-byte parameter, 0 ≤ L ≤ 64 (standard L = 64), der angiver antallet af parallelle beregninger og trædybden
r 12-bit ikke-negativ parameter: antal runder (standard r = 40 + [ d /4])
Q en matrix af 15 elementer af 8 bytes, dens værdi er angivet nedenfor
ƒ MD6-komprimeringsfunktion, der konverterer 712 bytes inputdata (inklusive blok B på 512 bytes) til resultat C på 128 bytes ved hjælp af r runder af evaluering
PAR parallel krympeoperation for hvert træniveau, kaldes aldrig, når L = 0
SEQ seriel kompressionsoperation, kaldet aldrig, når L = 64
Q = {0x7311c2812425cfa0, 0x6432286434aac8e7, 0xb60450e9ef68b7c1, 0xe8fb23908d9f06f1, 0xdd2e76cba691e5bf, 0x0cd0d63b2c30bc41, 0x1f8ccf6823058f8a, 0x54e5ed5b88e3775d, 0x4ad12aae0a6d6031, 0x3e7f16bb88222e0d, 0x8af8671d3fb50c2c, 0x995ad1178bd25c31, 0xc878c1dd04c4b633, 0x3b72066c7a1552ac, 0x0d6f3522631effcb}

Q-array

Grundlæggende procedure

Initialisering

Betegn l = 0, M 0 = M , m 0 = m .

Hovedsløjfe
  • l = l + 1.
  • Hvis l = L + 1, returner SEQ( M l-1 , d , K , L , r ) som resultat.
  • Ml = PAR ( M1-1 , d , K , L , r , 1 ) . Angiv m l som længden af ​​M l i bits.
  • Hvis m l = 8 * c (dvs. M l er 8 * c bytes lang), returnerer de sidste d bits af M l . Ellers vender vi tilbage til begyndelsen af ​​cyklussen.

Operation PAR

PAR returnerer en meddelelse med længden m l = 1024 * max(1, [ m l-1 / 4096])

Proceduretekst
  • Hvis det er nødvendigt, så udvid Ml -1 , og tilføje nul bit til højre, indtil dens længde bliver et multiplum af 512 bytes. Lad os nu opdele M l-1 i blokke B 0 , B 1 , …, B j-1 , hvor j = max(1, [ m l-1 / 512]);
  • For hver blok B i , i = 0, 1, …, j - 1, beregner vi C i parallelt i henhold til følgende algoritme:
  • Lad p angive antallet af polstrede bit B i , 0 ≤ p ≤ 4096. ( p er altid større end nul for i = j - 1.);
  • Betegn z = 1, hvis j = 1, ellers er z = 0;
  • Angiv V som en 8-byte værdi r ǁ L ǁ z ǁ p ǁ keylen ǁ d således:
  • 4 bit nuller;
  • 12 bit r ;
  • 8 bit L ;
  • 4 bit z ;
  • 16 bit p ;
  • 8 bit nøglen .
  • 12 bit d .
  • Lad os betegne U = l * 2 56 + i – unik 8-byte identifikator for den aktuelle blok;
  • C i = ƒ( Q ǁ K ǁ U ǁ V ǁ B i ).
  • Vi returnerer M l = C 0 ǁ C 1 ǁ … ǁ C j-1 .

Operation SEQ

SEQ returnerer en hash af længden d bits. Denne operation kaldes aldrig, hvis L = 64.

Proceduretekst
  • Lad C -1 betegne en nulvektor med en længde på 128 bytes.
  • Hvis det er nødvendigt, udvider vi M L , og tilføjer nul bits til højre, indtil længden bliver et multiplum af 384 bytes. Lad os nu opdele M L i blokke B 0 , B 1 , …, B j-1 , hvor j = max(1, [ m L / 384]).
  • For hver blok B i , i = 0, 1, …, j - 1, beregner vi C i parallelt i henhold til følgende algoritme:
  • Lad p angive antallet af polstrede bit B i , 0 ≤ p ≤ 3072. ( p er altid større end nul for i = j - 1.);
  • Betegn z = 1, hvis i = j - 1, ellers er z = 0;
  • Betegn V som en 8-byte værdi r ǁ L ǁ z ǁ p ǁ keylen ǁ d på samme måde som i den forrige operation;
  • Angiv U = ( L + 1) * 2 56 + i – entydig 8-byte identifikator for den aktuelle blok;
  • C i = ƒ( Q ǁ K ǁ U ǁ V ǁ C i-1 ǁ B i ).
  • Vi returnerer de sidste d bit af værdien C j-1 som den endelige hash.

MD6 komprimeringsfunktion

Input og output data

Funktionen tager som input et array N , bestående af n = 89 8-byte ord (712 bytes) og antallet af runder r .
Funktionen returnerer et array C med 16 elementer på 8 bytes.

Konstanter
t0 _ t1 _ t2 _ t3 _ t4 _
17 atten 21 31 67
( i - n ) mod 16 0 en 2 3 fire 5 6 7 otte 9 ti elleve 12 13 fjorten femten
r i-n ti 5 13 ti elleve 12 2 7 fjorten femten 7 13 elleve 7 6 12
l i-n elleve 24 9 16 femten 9 27 femten 6 2 29 otte femten 5 31 9

Si -n = S | (in)/
16S | 0 = 0x0123456789abcde
S* = 0x7311c2812425cfa0
S | j+1 = ( S | j <<< 1) ⊕ ( S | j ^ S*)

Funktionstekst

Angiv t = 16 r . (Der vil være 16 trin i hver runde)
Lad A [0.. t + n - 1] være en matrix af t + n 8-byte elementer. De første n elementer skal kopieres fra input-arrayet N .

Hovedfunktionsløkken ser sådan ud:
for i = n til t + n - 1: /* t trin */

x = S i-n ⊕ A i-n ⊕ A i-t 0 x = x ⊕ (A i-t 1 ^ A i-t 2 ) ⊕ (A i-t 3 ^ A i-t 4 ) x = x ⊕ (x >> r i-n ) Ai = x ⊕ (x << l i-n )

Returner A [ t + n - 16 .. t + n - 1].

Noter

  1. ↑ Ronald L. Rivest, MD6 hash-funktionen Et forslag til NIST for SHA-3 Arkiveret 9. november 2020 på Wayback Machine
  2. ↑ Schneier, Bruce MD6 trukket tilbage fra SHA-3-konkurrencen (linket er ikke tilgængeligt) (1. juli 2009). Hentet 9. juli 2009. Arkiveret fra originalen 21. marts 2012. 
  3. ↑ Arkiveret kopi (link ikke tilgængeligt) . Dato for adgang: 28. november 2010. Arkiveret fra originalen 22. februar 2012. 

Links

 Hash funktioner
generelle formål
Kryptografisk
Nøglegenereringsfunktioner
Tjek nummer ( sammenligning )
Hashes