Envejs kompressionsfunktion

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 1. oktober 2020; verifikation kræver 1 redigering .

En envejskomprimeringsfunktion i kryptografi er en funktion , der producerer en outputværdi af længde givet to inputværdier af længde [1] . En envejstransformation betyder, at det er let at beregne hashværdien ud fra preimage, men det er svært at skabe et preimage, hvis hashværdi er lig med den givne værdi [2] [3] . $n$ $n$

Envejskomprimeringsfunktionen bruges for eksempel i Merkle-Damgor-strukturen inde i kryptografiske hash-funktioner .

Envejskomprimeringsfunktioner er ofte bygget ud fra blokcifre . For at omdanne enhver standard blokchiffer til en envejs komprimeringsfunktion er der Davis-Meyer, Mathis-Meyer-Oseas, Miaguchi-Presnel-skemaer (enkeltbloklængde komprimeringsfunktioner) [4] .

Kompressionsfunktion

Kompressionsfunktioner er funktioner, der tager en streng med variabel længde som input og konverterer den til en streng med fast, normalt mindre længde.

For eksempel, hvis input A er 128 bit langt, er input B 128 bit langt, og de komprimeres sammen til en enkelt 128 bit output. Det er det samme, som hvis en enkelt 256-bit input komprimeres sammen til en enkelt 128-bit output.

Nogle komprimeringsfunktioner har forskellige størrelser af de to indgange, men outputtet har normalt samme størrelse som en af indgangene. For eksempel kan input A være 256 bit, input B 128 bit, og de komprimeres sammen med et output på 128 bit. Det vil sige, at i alt 384 inputbits komprimeres sammen til 128 outputbits. [5]

Blanding sker således ved at opnå en lavineeffekt, det vil sige, at hver outputbit afhænger af hver inputbit. [6]

Envejsfunktion

Envejskomprimeringsfunktionen skal have følgende egenskaber:

Modstand mod søgningen efter det første præbillede - fraværet af en effektiv polynomialalgoritme til beregning af den inverse funktion , det vil sige, at det er umuligt at gendanne teksten fra dens kendte foldning i realtid (irreversibilitet). Denne egenskab svarer til, at en hashfunktion er en envejsfunktion. $m$ $H(m)$
Modstand mod søgningen efter den anden prototype (kollisioner af den første slags). Når man kender inputmeddelelsen og dens foldning , er det beregningsmæssigt umuligt at finde et andet input til . $m_{{1}}$ $H(m_{1})$ $m_{{2}}$ $H(m_{1})=H(m_{2})$
Modstand mod kollisioner (kollisioner af anden art). Det må være beregningsmæssigt umuligt at matche et par beskeder og det . [7] $m_{{1}}$ $m_{{2}}$ $H(m_{1})=H(m_{2})$

Lad os reducere problemet med krypteringsanalyse af hashfunktioner til problemet med at finde en kollision: hvor mange beskeder skal scannes for at finde beskeder med to identiske hashes.

Sandsynligheden for at støde på de samme hashes for beskeder fra to forskellige sæt, der indeholder og tekster, er lig med . Hvis , så sandsynligheden for succes for angrebet og kompleksiteten af angrebsoperationerne . $n_{1}$ ${\displaystyle n_{2))$ $P\thickapprox 1-e^{-{\frac {n_{1}\cdot n_{2}}{2^{l))))$ $n_{1}=n_{2}=2^{l/2}$ $P\thickapprox 1-e^{-1}\thickapprox 0,63$ $2^{l/2+1}$

For at finde en kollision skal du generere to pseudo-tilfældige meddelelsessæt (i hvert meddelelsessæt) og finde hashes for dem. Så ifølge fødselsdagsparadokset (se også fødselsdagsangreb ) er sandsynligheden for, at der blandt dem er et par beskeder med de samme hashes større end 0,5. Angrebet kræver en stor mængde hukommelse til at gemme tekster og effektive sorteringsmetoder. [otte] $2^{{n/2}}$

Merkle-Damgor struktur

Essensen af konstruktionen er en iterativ proces af successive transformationer, når input fra hver iteration modtager en blok af kildeteksten og output fra den foregående iteration [9] .

De mest udbredte hash-funktioner baseret på denne konstruktion er i MD5 , SHA-1 og SHA-2 .

Hash-funktionen skal konvertere en inputmeddelelse af vilkårlig længde til et output med fast længde. Dette kan opnås ved at opdele inputmeddelelsen i et antal lige store blokke og behandle dem sekventielt med en envejskomprimeringsfunktion. Kompressionsfunktionen kan enten være specifikt designet til hashing eller være en blokchifferfunktion.

Det andet preimage-angreb (med en besked finder angriberen en anden besked at tilfredsstille ) kan udføres ifølge Kilsey og Schneier, for en besked på 2 k blokke kan udføres i tiden k × 2 n/2+1 + 2 n- k+1 . Det er vigtigt at bemærke, at hvis meddelelserne er lange, så er kompleksiteten af angrebet mellem 2 n/2 og 2 n , og når meddelelseslængden bliver mindre, nærmer kompleksiteten sig 2 n . [ti] $m_{{1}}$ $m_{{2}}$ $H(m_{1})=H(m_{2})$

Kompressionsfunktionens rolle kan udføres af enhver blokchiffer E. Denne idé dannede grundlaget for udviklingen af Merkle-Damgor-konstruktionen i Davis-Meyer, Mathis-Meyer-Oseas, Miaguchi-Prenel-skemaerne [11] .

Davis-Meyer struktur

I dette skema føres meddelelsesblokken og den tidligere hashværdi som henholdsvis nøglen og klartekstblokken til input af blokchifferet . Den resulterende blok af krypteret tekst tilføjes ( XOR-operation ) med resultatet af den forrige hash-iteration ( ) for at opnå den næste hashværdi ( ). [elleve] $m_{{i}}$ $H_{i-1}$ $E$ $H_{i-1}$ $Hej}}$

I matematisk notation kan Davis-Meier-skemaet skrives som:

H_{i}=E_{m_{i}}{(H_{i-1})}\oplus {H_{i-1}}.

Hvis blokchifferet f.eks. bruger en 256-bit nøgle, er hver meddelelsesblok ( ) et 256-bit meddelelsesfragment. Hvis blokchifferet bruger en blokstørrelse på 128 bit, så er input- og outputværdierne for hash-funktionen i hver runde 128 bit. $m_{{i}}$

En vigtig egenskab ved Davies-Meyer-konstruktionen er, at selvom den underliggende chifferblok er fuldstændig sikker, kan man beregne de fikspunkter, der skal konstrueres: for enhver kan finde en værdi sådan, at : bare skal indstilles . [12] $m$ $h$ $E_{m}(h)\oplus h=h$ $h=E_{m}^{-1}(0)$

Davis-Meyer-strukturens sikkerhed blev først bevist af Winternitz [13] .

Mathis-Meyer-Oseas strukturen

Dette er en version af Davis-Meyer-skemaet: meddelelsesblokke anvendes som nøgler til et kryptosystem . Skemaet kan bruges, hvis datablokkene og krypteringsnøglen har samme størrelse. For eksempel er AES velegnet til dette formål.

I denne konstruktion føres meddelelsesblokken og den tidligere hashværdi som henholdsvis nøglen og klartekstblokken til input af blokchifferet . Men værdien er allerede forbehandlet af funktionen på grund af mulige forskelle i størrelsen af hash-summen og størrelsen af chiffernøglen . Denne funktion knytter en n-bit hash-værdi til en k-bit chiffernøgle . Som et resultat af anvendelsen af krypteringsoperationen opnås en blok med privat tekst, som føjes til den tilsvarende blok med almindelig tekst ( ). [fjorten] $m_{{i}}$ $H_{i-1}$ $E$ $H_{i-1}$ $g$ $E$ $E$ $m_{{i}}$

I matematisk notation kan Mathis-Meyer-Oseas-skemaet skrives som:

H_{i}=E_{g(H_{i-1})}(m_{i})\oplus m_{i}.

Miaguchi-Presnel struktur

Miaguchi-Prenel-ordningen er en udvidet version af Mathis-Meyer-Oseas-ordningen. Forskellen er, at den private tekstblok summeres ikke kun med den tilsvarende almindelige tekstblok ( ), men også med resultatet af den tidligere hashingiteration ( ). For at gøre algoritmen mere modstandsdygtig over for angreb, bliver klarteksten, chiffernøglen og chifferteksten XORed sammen for at skabe en ny digest . Dette skema bruges i Whirlpool til at skabe en hash-funktion. Summeringsresultatet bestemmes af ligningen [15] : $m_{{i}}$ $H_{i-1}$ $Hej}}$

H_{i}=E_{g(H_{i-1})}(m_{i})\oplus H_{i-1}\oplus m_{i}.

Noter

↑ Handbook of Applied Cryptography af Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Femte oplag, august 2001 .
↑ Bruce Schneier, 2006 , s. 37-38.
↑ V.V. Yashchenko, 1999 , s. tredive.
↑ Avezova, 2015 , s. 60.
↑ S. Barichev, R. Serov, 2001 , s. 106-108.
↑ A.V. Antonov, 2012 , s. 106-107.
↑ S.V. Dubrov, 2012 , s. 65.
↑ S.V. Dubrov, 2012 , s. 66-67.
↑ Avezova, 2015 , s. 60-61.
↑ Kelsey og Schneier 2005 , s. 474-490.
↑ 1 2 Avezova, 2015 , s. 61.
↑ Handbook of Applied Cryptography af Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Femte oplag, august 2001 , s. 375.
↑ Winternitz, 1984 , s. 88-90.
↑ Avezova, 2015 , s. 61-62.
↑ Avezova, 2015 , s. 62.

Litteratur

Bøger

Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Kapitel 9 // Hash-funktioner og dataintegritet . - 5. udg. - August 2001. - S. 328.
Bruce Schneier. Anvendt kryptografi. - 2. udg. - 2006. - S. 37-38. - 610 s.
V.V.Yashchenko. Introduktion til kryptografi. - 1999. - S. 30. - 271 s.
S. Barichev, R. Serov. Grundlæggende om moderne kryptografi. - Moskva, 2001. - S. 106-108. — 122 s.
S.V.Dubrov. Grundlæggende om moderne kryptografi . - Novosibirsk, 2012. - S. 65-67. — 260 s.
John Kelsey og Bruce Schneier. Andet preimages på n-bit hash-funktioner til meget mindre end 2n arbejde. - 2005. - S. 474-490.
R. Winternitz. En sikker envejs hash-funktion bygget fra DES. - IEEE Press, 1984. - S. 88-90.

Videnskabelige artikler

Avezova Yana Eduardovna Moderne tilgange til konstruktion af hash-funktioner på eksemplet fra finalisterne i sha-3-konkurrencen . - Moskva, 2015.
A.V. Antonov. [www.hups.mil.gov.ua/periodic-app/article/1988/soivt_2012_2_23.pdf Udvikling af konstruktionsmetoden for hashfunktion]. - Kharkov, 2012.