N-hash

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 14. januar 2015; verifikation kræver 21 redigeringer .

N-hash
Oprettet	1990
offentliggjort	1990
Hash størrelse	128 bit
Antal runder	12 eller 15
Type	hash funktion

N-Hash er en kryptografisk hash-funktion baseret på den cykliske FEAL- funktion . Anses i øjeblikket for usikker [1] .

Den blev udviklet i 1990 af Nippon Telegraph and Telephone (som også udviklede FEAL).

Oprindeligt havde N-Hash-funktionen til formål at løse problemet med informationssubstitution på vejen mellem to telefonbrugere (Nippon Telegraph og Telephone - et teleselskab) og fremskynde datahentning. For eksempel, hvis en person sender en SMS- besked, vil den før levering blive tjekket for ægthed ved hjælp af en hash-funktion. Og hvis brugeren af Nippon Telegraph and Telephone-produkter hurtigt skal finde en persons kontaktperson på telefonen, så kan brugen af N-Hash forenkle processen med at finde et navn på listen. Dette skyldes, at det første bogstav i kontakten er erklæret som en hash-kode (en lille definerende del af kontakten) af navnet.

Oprindelse

N-Hash- algoritmen er baseret på FEAL -blokkrypteringsalgoritmen . Det største teleselskab Nippon Telegraph and Telephone skabte FEAL baseret på DES . Men selvom denne algoritme overgår DES i hastighed, er den meget upålidelig og let sårbar: en kryptoanalytiker havde brug for meget lidt information for at bryde algoritmen. Det var hackingen af FEAL-algoritmen, der førte til fremkomsten af N-Hash-hash-funktionen i 1990. N-Hash er også hurtigere end DES: sammenlignet med DES's 9Kbps kører N-Hash med 24Kbps for et 15-runders skema og 29Kbps for et 12-runders skema. Samtidig opnåede Nippon Telegraph and Telephone en stigning i pålideligheden sammenlignet med FEAL [1] .

I nogen tid blev N-Hash-algoritmen brugt af Nippon Telegraph og Telefon i overensstemmelse med målene for denne funktion, men efter et stykke tid blev fødselsdagsmetoden udviklet , som nemt knækkede denne algoritme. I forbindelse med hacket blev ikke kun N-Hash opgivet, men næsten alle funktioner baseret på blokcifre, da de alle har samme problem: De er let sårbare over for fødselsdagsmetoden. I stedet bruger de nu mere pålidelige funktioner baseret på MD-teknologier: MD5 , SHA-1 og andre opført på listen over funktioner, der i øjeblikket anses for pålidelige (i henhold til ISO / IEC 10118-standarden).

Brug

N-Hash-funktionen blev brugt i kort tid i begyndelsen af 1990'erne, indtil den blev knækket af fødselsdagsmetoden.

N-Hash var beregnet til at løse problemet med data-spoofing:
- For en moderne person kan dette problem let beskrives ved hjælp af eksemplet på interaktion mellem en person og en onlinebutik . Når en bruger bestiller et produkt i en netbutik, sender butikken ham ordrenummer, betalingsbeløb osv. Yderligere, når brugeren forsøger at betale for ordren ved hjælp af f.eks. Webmoney , beregner Webmoney hashkoden for den modtagne besked og sammenligner den med hashkoden modtaget fra netbutikken. Hvis disse hash-koder matcher, er oplysningerne sendt af brugeren sande. Hvis de ikke stemmer overens, er oplysningerne bestemt til at være falske, og betalingen går ikke igennem.
En anden use case er enkel: alfabetiser dine kontakter på din mobiltelefon og søg efter en kontakt med det første bogstav. Det første bogstav i dette navn er valgt som hash-koden for navnet, derfor, når en person trykker på et bestemt bogstav i sin telefon, søges der efter en hash-kode, der matcher dette bogstav, og kontakter, der starter med det, vises på skærmen.

Funktioner i N-Hash

Ensrettet

Definition: Lad være en besked af en vis længde. $M$

En funktion kaldes envejs hvis fra lighed $H$ $h=H(M)$

let:

find hash-koden ved at kende beskeden $h$ $M$

meget arbejdskrævende:

finde en besked ved hjælp af en kendt hash-kode (dvs. hvis hashkoden for adgangskoden er blevet kendt af hackeren , så vil han ikke finde adgangskoden ved hjælp af den); $M$ $h$
finde en meddelelse, der er forskellig fra , sådan at deres hash-koder matcher. $M$ $M'$ $H(M')=H(M)$

En lettere definition kan skrives sådan:

Ensrettethed er et " fingeraftryk ":

Hvis en bestemt person er givet, så kan du tage hans fingeraftryk;
Det er umuligt at finde en person ved hans fingeraftryk (hvis der ikke er nogen database med fingeraftryk af alle mennesker, men der er ingen);
Det er umuligt at finde en anden person med samme fingeraftryk som den anden.

Ensrettethed løser et meget vigtigt problem. Lad os overveje det med et eksempel.

Alice og Bob udpeger traditionelt emnerne for informationsoverførsel. Eksempler

Lad os sige, at Alice underskrev en kontrakt med en hashkode, som Alice og Bob kender . Hvis det var ikke ensrettet, så kunne Bob finde en så anderledes kontrakt , at og derfor kunne hævde, at Alice underskrev . $M$ $h=H(M)$ $H$ $M'$ $H(M')=H(M)$ $M'$
Antag, at Alice har det samme fingeraftryk h som en forbryder, så kunne Bob hævde, at denne forbryder er Alice.

Kollisionsmodstand

For at forhindre Alice i at bruge "fødselsdage"-metoden til at narre Bob, er det meget praktisk at indføre en endnu stærkere tilstand end envejstilstanden. H er sådan, at det er svært at finde beskeder og , sådan at deres hash-koder matcher. Det vil sige, at det er umuligt at finde to personer med samme fingeraftryk. $M$ $M'$ $H(M)=H(M')$

Denne tilstand kaldes kollisionsmodstand, og den gælder ikke for N-Hash-hash-funktionen.

På grund af kollisionsustabiliteten kan Alice narre Bob på denne måde ("fødselsdage"-metoden):

Alice skriver to versioner af kontrakten: den ene er til gavn for Bob, og den anden er ikke;
Ved at lave små ændringer i hver kontrakt (for eksempel erstattes et mellemrum med to mellemrum), vil hun sikre, at der er nok versioner af kontrakter at vælge , og for hvilke hash-koderne matcher (versionen er til gavn for Bob, men ikke) (hvis kontrakten har 34 linjer, så er det nemt at få versioner af kontrakterne ved at foretage eller ikke foretage ændringer på hver af linjerne); $M$ $M'$ $M$ $M'$ $2^{{34}}$
Nu kan Alice bevise, at Bob skrev under . $M'$

For at undgå et sådant problem er det nok at foretage kosmetiske ændringer i den underskrevne kontrakt. Og selvom denne handling ikke ændrer hash-funktionen H på nogen måde, og derfor ikke påvirker dens modstand mod kollisioner på nogen måde, men ved denne handling vil personen modtage en ny version af kontrakten, hvis hash-kode matcher ikke hashkoden for hackerens kontraktversion. Det vil sige, at hvis Bob i 5. linje sætter et komma et sted, eller sætter to prikker i stedet for én, så vil Alice ikke kunne bevise, at han har underskrevet en anden kontrakt (da hans hashkode ikke længere matcher hashkoden Alices kontrakt).

Du kan overveje et eksempel fra det virkelige liv: Når en notar stempler en underskrevet kontrakt, foretager han kosmetiske ændringer der.

Mål for N-Hash

For at forstå, hvordan N-Hash-funktionen fungerer, skal du skifte til mere videnskabelig tale. Nedenfor er målene for denne funktion, ikke ved eksempler, men i henhold til hvordan de er implementeret og med den passende terminologi .

Sikring af informations integritet [1] :

Denne egenskab er nødvendig for at udelukke muligheden for, at en angriber kan injicere nogle falske oplysninger i den originale meddelelse. For at sikre integriteten skal det være muligt at registrere eventuelle ændringer i meddelelsens tekst (erstatning, indsættelse, sletning). Integriteten sikres ved at indføre redundant information i den originale besked, som vil være en testkombination. Denne kombination kaldes en kontrolsum og kan beregnes ved hjælp af en speciel algoritme. Da denne algoritme afhænger af den hemmelige nøgle , er det usandsynligt , at falsk information vil blive introduceret i beskeden .

$M_{new}=M+''salt''$ , hvor salt er redundant information, M er en besked - checksum; $H(salt)=S$

Det følger af formlen, at hvis salt ændres, så ændres S (checksum) også, hvilket betyder, at både og ændret . $M_{ny}$ $M$

Det vil sige, at vi kan konkludere, at der er tilføjet falsk information.

Dokumentkomprimering : _

N-hash-funktionen fungerer med M beskeder af vilkårlig længde. I dette tilfælde er outputtet en hash-kode med en fast længde på 128 bit. Dette opnås på grund af det faktum, at meddelelsen er opdelt i blokke , 128 bit i størrelse, og algoritmen arbejder sekventielt med hver af blokkene. $M_{i}$

Sikring af pålideligheden af elektroniske data [1] :

Denne egenskab gælder for envejsfunktioner, hvilket er, hvad N-Hash er. Pålideligheden af beskeden M kontrolleres ved at finde den endelige hash-kode (meddelelsessammenfatning) to gange (afsendende og modtagende parter). Resultaterne sammenlignes, og hvis de matcher, så er oplysningerne pålidelige. Integritet garanterer ikke gyldighed .

Sikring af privatlivets fred :

på websteder, hvor du skal indtaste et login og en adgangskode , bliver adgangskoden efter indtastning oversat til en hash-kode. Det vil sige, at brugeren i første omgang indtaster adgangskoden M, men en hash-kode bruges til at komme ind i det beskyttede område . Ved at bruge den kendte hash-kode h og funktionen H er det meget svært at beregne M, hvilket sikrer adgangskodens fortrolighed. $h=H(M)$

Brugergodkendelse : _

Autentificering er proceduren til godkendelse af en bruger eller data ved hjælp af nogle kriterier.

Spørgsmålet opstår om, hvordan hash-funktionen sikrer rigtigheden af autentificering. Dette er let at vise med et eksempel.

Når en bruger indtaster et brugernavn og en adgangskode på ethvert websted , konverteres hans adgangskode til en hash-kode og sendes over netværket til godkendelse. For at logge ind under en andens konto er det naturligvis nok at finde ud af kodeordets hash-kode og derefter bruge formlen (h-hash-kode, M - adgangskode) til at finde adgangskoden. Men N-Hash, som er en envejsfunktion, sikrer adgangskodens sikkerhed, da denne ligning for envejsfunktioner er meget besværlig at løse (ikke ved brug af en personlig computer). $h=H(M)$

Algoritme

N-Hash-algoritmen er baseret på en cyklisk gentagelse (12 eller 15 gange - antallet af runder) af operationer. Der er en hashkode ved indgangen og den kan være vilkårlig, outputtet er en hashkode h for beskeden M , som skal hash. Størrelsen af den udgående hash-kode er fast og lig med 128 bit, mens størrelsen M er vilkårlig [2] . ${\displaystyle h_{0))$

Grundlæggende betegnelser

$M$ — meddelelsen, der skal hash;
$M_{i}$ — en meddelelsesblok med en længde på 128 bit. For at hash en besked er det nødvendigt at opdele den i blokke ; $M$ $M_{i}$
$Hej}}$ — hash -kode for det i-te trin;
$\nu=1010...1010$ — konstant, 128 bit lang;
$||$ - sammenkædning ;
${\displaystyle V_{j}=\delta ||A_{j1}||\delta ||A_{j2}||\delta ||A_{j3}||\delta ||A_{j4))$ hvor k=1, 2, 3, 4; , 24 bit lang; $A_{jk}=4*(j-1)+k$ $\delta =00..00$
EXG - en funktion, der bytter høje og lave bits (64 lav og 64 høj);
PS - transformerende funktion;

Beskrivelse af algoritmen

Diagrammet til højre viser de skematiske betegnelser for de operationer, der er til stede i de følgende diagrammer.

Koordinat (parvis) summering betyder addition modulo 2 ;
Hvis x er input til en funktion f , så er output f(x) .

Én N-hash-cyklus

Nedenfor er en cyklus af N-Hash-algoritmen.

Indgangen til funktionen g er hash-koden for (i-1)-te trin og den i-te beskedblok . I dette tilfælde er det valgt vilkårligt: for eksempel kan det være nul. Og det føres også til outputtet for modulo 2 additionsoperationen, det vil sige, resultatet (hashkoden for det næste trin) vil se sådan ud: ( noget ukendt endnu ). $h_{{i-1}}$ $M_{i}$ ${\displaystyle h_{0))$ $h_{{i-1}}$ $h_{i-1}\oplus$
Det kan ses fra diagrammet, at det ikke kun føres til XOR , men også til outputtet af operationen af additionsmodulo 2. Det vil sige, at nu, i overensstemmelse med første afsnit, ser resultatet således ud: ( noget der forbliver ukendt indtil videre ). $M_{i}$ ${\displaystyle h_{i-1}\oplus M_{i))$

Det resterende ukendte noget findes efter at have passeret gennem en kaskade af otte transformerende funktioner. At få det kan beskrives sådan:

EXG-funktionen bytter de høje og lave cifre og tilføjer resultatet , hvorefter resultatet tilføjes modulo 2 s . $h_{{i-1}}$ $\nu$ $M_{i}$
Som det kan ses af diagrammet, føres resultatet sekventielt til input af j transformerende funktioner, hvis andet argument er summen , hvor j=1, ..., 8. ${\displaystyle h_{i-1}\oplus V_{j))$
Resultatet er en hash-kode for det i-te trin : $Hej}}$

${\displaystyle h_{i}=M_{i}\oplus g(M_{i},h_{i-1})\oplus h_{i-1))$ .

Transformationsfunktion

Spørgsmålet opstår, hvordan transformationsfunktionen fungerer . $PS(X,P)$

Overvej den øverste del af kredsløbet til trådkorset.

Den originale besked er opdelt i blokke af bits. $x$ $128/4=32$

Vi vil betragte mellemudgange som input til den nederste del af kredsløbet. og føres til mellemudgange , mens operationer og føres til de to andre udgange . Nu er det muligt at omdesigne resultaterne ved mellemudgange og gennem dem, på samme måde som den øvre del, finde resultaterne ved udgangen af den nederste del, det vil sige hele kredsløbet som helhed. $X_{1}$ $X_{2}$ ${\displaystyle f(X_{1},P_{1})\oplus X_{2}\oplus X_{4))$ ${\displaystyle f[f(X_{1},P_{1})\oplus X_{2},P_{2}]\oplus X_{1}\oplus X_{3))$

Efter at have udført alle de nødvendige beregninger, får vi, at når den anvendes på input , kan outputmeddelelsen repræsenteres som en sammenkædning af meddelelser ${X=X_{1}\parallel X_{2}\parallel X_{3}\parallel X_{4}}$ ${Y=Y_{1}\parallel Y_{2}\parallel Y_{3}\parallel Y_{4}}$

${\displaystyle {Y_{4}=X_{2}\oplus X_{4}\oplus f(X_{1},P_{1)))))$ ;
${Y_{3}=f[f(X_{1},P_{1})\oplus X_{2},P_{2}]\oplus X_{1}\oplus X_{3))$ ;
${\displaystyle {Y_{2}=X_{2}\oplus Y_{4}\oplus f(Y_{3},P_{3)))))$ ;
${Y_{1}=f[f(Y_{3},P_{3})\oplus Y_{4},P_{4}]\oplus X_{1}\oplus Y_{3))$ .

Find funktionen f(x, P)

Da funktionen f arbejder med argumenter, hvis længde er 32 bit, så har vi fra søgeskemaet for funktionen f(x, P):

Værdien er opdelt i dele af 8 bit. $x\oplus P$
Lad os skrive disse dele som , i=1,...,4 og introducere ny notation: $x_{i}\oplus P_{i}$
- ${Z_{1}=x_{1}\oplus P_{1))$ ;
- ${Z_{2}=x_{2}\oplus P_{2))$ ;
- ${Z_{3}=x_{3}\oplus P_{3))$ ;
- ${Z_{4}=x_{4}\oplus P_{4))$ ;

Funktionsargumenterne (første pil fra venstre) er og . ${S_{0))$ $Z_{1}$ ${S_{1}[Z_{1}\oplus Z_{2},Z_{3}\oplus Z_{4}]}$

Funktionsargumenterne (anden pil fra venstre) er og . ${S_{1))$ ${Z_{1}\oplus Z_{2}}$ ${Z_{3}\oplus Z_{4}}$

Det vil sige, at de to komponenter i outputmeddelelsen allerede er kendte og ens

- ${A_{1}=S_{0}(Z_{1},S_{1}[Z_{1}\oplus Z_{2},Z_{3}\oplus Z_{4}])}$ ;
- ${A_{2}=S_{1}[Z_{1}\oplus Z_{2},Z_{3}\oplus Z_{4}]}$ ;

Yderligere vil vi bruge de allerede modtagne dele af meddelelsen ved udgangen for at gøre notationen nemmere:

- ${A_{3}=S_{0}[Z_{3}\oplus Z_{4},A_{2}]}$ ;
- ${~A_{4}=S_{1}[Z_{4},A_{3}]}$ ;

Så kan outputmeddelelsen repræsenteres som . ${A=A_{1}||A_{2}||A_{3}||A_{4))$

Og det er kendt
- ${S_{0))$ =( venstre 2-bit rotation )(a+b) mod 256
- ${S_{1))$ =( 2-bit venstre rotation )(a+b+1) mod 256

Sikkerhed for hash-funktioner

En hash-funktion er sikker , når en kryptoanalytiker har brug for en masse information for at knække hashen (hvilket gør det usandsynligt, at den bliver cracket), og hvis hashen ikke er blevet knækket nu [3] .

For at en hash-funktion skal være sikker, skal følgende betingelser være opfyldt:

Med ændringer i meddelelsens tekst (indsættelser, permutationer osv.), bør meddelelsens hash-kode også ændre sig; $M$

Ellers kan en person, der indtaster sit brugernavn og password for at komme ind på Wikipedia , komme til en anden deltagers side.

Umuligheden af at finde en besked med en kendt hash-kode fra ; $M$ $h$ $h=H(M)$

Hvis denne betingelse ikke er opfyldt, gør det det muligt at finde Wikipedia-brugeres adgangskoder.

Opgaven med at finde beskeder og sådan, at deres hash-koder er ens , må være meget tidskrævende. $M_{{1}}$ $M_{{2}}$ ${\displaystyle h_{1}=h_{2))$

Ellers ville det være muligt at finde to adgangskoder med de samme hash-koder.

N-Hash er ikke en sikker funktion, fordi den sidste betingelse ikke er opfyldt for det.

Krypteringsanalyse af N-Hash

N-Hash betragtes i øjeblikket som en usikker funktion. Denne figur viser alle sikre envejsfunktioner i øjeblikket i henhold til ISO/IEC 10118 [1] :

Af de algoritmer, der er bygget som N-Hash baseret på blokcifre, anses kun MDC-2 og MDC-4 for at være sikre .

N-Hash er karakteriseret ved følgende problem:

Da længden af hashkoden er lig med længden af blokken af krypteringsalgoritmen, er algoritmen ustabil mod fødselsdagsangrebet .

Angreb på hash-funktioner

Denne figur viser en klassificering af angreb på alle hashing-algoritmer generelt.

Algoritmeafhængige angreb er angreb baseret på egenskaberne af en bestemt algoritme.

For eksempel er N-Hash blevet angrebet med succes ved hjælp af differentialmetode , fastpunktsangreb og møde i midten .

Algoritme-uafhængige angreb kan anvendes på enhver hashfunktion, men det udelukker ikke, at de for nogle algoritmer er meget tidskrævende på grund af den store mængde information eller kodens hastighed.

Effektive angreb på N-Hash

Algoritmebaserede angreb Differentiel metode

Den Boer foreslog en metode til at konstruere en kollision til et en-runde N-Hash-skema.

Biham og Shamir brugte med succes differentiel kryptoanalyse til at kompromittere 6-runders N-Hash-skemaet. Metoden, de foreslog til at konstruere en kollision , fungerer for enhver værdi N, der er et multiplum af tre, og samtidig viser den sig for N ≤ 12 at være mere effektiv end tilgangen baseret på fødselsdagsparadokset .

For et 12-runders skema estimeres kompleksiteten af at konstruere kollisioner ved den foreslåede metode til 256 operationer (kompleksiteten af metoden baseret på fødselsdagsparadokset er 264 operationer).

Algoritme uafhængige angreb

At øge længden af hashkoden og den hemmelige nøgle vil komplicere kryptanalytikerens arbejde. Du kan prøve at gøre beregningerne for tidskrævende for en personlig computer og kræve store ressourcer. Så skal kryptanalytikeren enten lede efter en supercomputer eller skrive en virus, der baseret på paralleliseringen af processen med at knække hash-funktionen vil bruge flere personlige computere på én gang til at løse problemet [3] .

Følgende metoder til at beskytte hash-funktionen [4] er også effektive :

brug af kontrolsummer på forskellige stadier af hashing;
verifikation af oplysningernes nøjagtighed;
indlejr information af typen salt i meddelelsen .

Resultater

I øjeblikket er N-Hash ikke meget brugt, da det ikke er sikkert og blev hacket for mere end 10 år siden.
Nu er der et særligt navn for hash-funktioner som N-Hash - key , det vil sige envejs, men ikke kollisionsbestandig:
- Hvis parterne har tillid til hinanden (det vil sige, at hver af parterne er sikre på, at den anden ikke vil erstatte kontrakten, som i tilfældet med Alice og Bob), så kan N-Hash bruges.

Sammenligning af N-Hash med andre hash-funktioner

Algoritme	Hash værdi længde	Krypteringshastighed (KB/sek.)
Samtidig Davies-Meyer-kredsløb (med IDEA )	128	22
Davies-Meyer (med DES)	64	9
GOST hash funktion	256	elleve
HAVAL (3 sæt)	variabel	168
HAVAL (4 sæt)	variabel	118
HAVAL (5 sæt)	variabel	98
MD2	128	23
MD4	128	236
MD5	128	174
N-hash (12 trin)	128	29
N-hash (15 trin)	128	24
RIPE-MD	128	182
SHA-1	160	75
Snefru (4 pas)	128	48
Snefru (8 sæt)	128	23

Noter

↑ 1 2 3 4 5 Hash-funktioner (utilgængelig link- historik ) . Cryptomash. Hentet: 27. november 2008. (ubestemt) (utilgængeligt link)
↑ Bruce Schneier. Kapitel 18. Envejs-hash-funktioner // Anvendt kryptografi . - 2. udg. Arkiveret 28. februar 2014 på Wayback Machine
↑ 1 2 Hovedudgaven af kryptografi // CIO: tidsskrift. - 17. maj 2005. - Nr. 5 . Arkiveret fra originalen den 29. maj 2008.
↑ Krypteringsanalyse af hash-funktioner (utilgængelig link- historie ) . Cryptomash. Hentet: 27. november 2008. (ubestemt) (utilgængeligt link)

Se også

Litteratur

A. Shcherbakov, A. Domashev. Anvendt kryptografi. - M . : Russisk udgave, 2003. - 404 s. — ISBN 5-7502-0215-1 .
Bruce Schneier. Anvendt kryptografi. - 2. udg. - M . : Triumph, 2002. - 816 s.

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge 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 Hud Snefru Tiger Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE