Hvordan fungerer hashing?

Kryptografiske hashfunktioner er matematiske objekter, der kan beskrives som “en stor blanding og kryptering af nogle bits “. De tager som input en sekvens af bits (muligvis en meget lang) og tilbyder en output af fast størrelse. Groft sagt er de så sammenfiltrede, at selvom der ikke er noget hemmeligt ved dem (det er bare deterministisk kode), kan ingen finde ud af, hvordan man ”inverterer” dem (finde en matchende input til en given output) undtagen ved den grundlæggende metode kaldet “held”: prøv tilfældige input, indtil der findes et match.

Hvordan det videnskabeligt kan ske, at hash-funktioner overhovedet kan findes, er et godt spørgsmål .

Hashing er ikke kryptering . Der er ingen hemmelighed, ingen nøgle til hashing.

Hash-funktioner har mange anvendelser; en af dem er “adgangskodelagring”. En hash-funktion ser ud som en god ting til adgangskodelagring. Vi ønsker ikke at gemme adgangskoder direkte (ellers ville en lejlighedsvis kigge på vores databaser af angriberen give ham for meget information; se dette blogindlæg til en diskussion) ; vi vil gemme adgangskodebekræftelsestokens : noget, der muliggør verifikation af en adgangskode (som brugeren præsenterer), men ikke afslører selve adgangskoden. Så ideen er: lad os gemme hash af adgangskoden. Når en adgangskode skal verificeres, beregner vi bare dens hash og ser, om den matcher den gemte værdi. Men det er svært at gætte adgangskoden fra hash-værdien, da hash-funktionen er modstandsdygtig over for “inversion” (se ovenfor).

Da adgangskoder er en speciel type data (det er data, som mennesker kan huske), for korrekt sikkerhed, har vi brug for en “styrket” hash-funktion:

• Vi vil have en meget langsom hash-funktion.
• Vi vil ikke have en hash-funktion, men mange forskellige hash-funktioner, så hver adgangskode bliver hash med sin egen hash-funktion; dette handler om at afskrække parallelle angreb. Denne proces med at omdanne en enkelt hash-funktion til mange varianter kaldes saltning .

Se dette svar for en grundig behandling af emnet for hashing-adgangskoder.

Kommentarer

• Undskyld, men mens dit svar var ekstremt grundigt og godt sammensat, fandt jeg det andet svar ligner mere det, jeg ledte efter.

Hashing er en funktion fra nogle bitstreng (normalt variabel længde) til en anden bitstreng (normalt mindre og med fast længde).

Hashing bruges i databaser til datahentning og i datastrukturer i hukommelsen kaldet hash-tabeller. Det giver os mulighed for at reducere vilkårlige data, såsom en tegnstreng eller et kompliceret objekt med mange felter, til et binært tal, som derefter kan bruges direkte som et indeks i et sparsomt array til at hente de tilknyttede data (med nogle detaljer til håndtering af hash kollisioner).

De hashfunktioner, der anvendes på ovenstående måde, er “fætre” til kryptografiske hashfunktioner. De er designet til forskellige krav. De skal være hurtige at beregne og opnå en god distribution.

I sikker databehandling bruges kryptografiske hashes til at fordøje data til en eller anden repræsentativ, lille bitstreng. Kryptografiske funktioner har forskellige krav. De er designet til at være vanskelige at vende om (for at være “fældedør” eller “envejs” -funktioner). Ikke kun det, men et vigtigt krav er, at det skal være svært at finde for en given almindelig tekst og hashværdi en anden almindelig tekst, der producerer den samme hash.

Hashing kan ikke kun bruges til adgangskoder, men som kontrolsum til verificering af dataintegritet og som en del af implementeringen af digitale signaturer. For at digitalt underskrive et stort dokument er vi simpelthen nødt til at hash dokumentet for at producere en “fordøjelse” (et navn, der bruges til output af en hashing-funktion, når noget meget langt er hashet). Derefter placeres netop denne fordøjelse gennem det offentlige nøgle-krypto-system for at producere en signatur. Du kan se svagheden der: Hvad hvis en angriber lykkes at producere et dokument, der har samme fordøjelse? Derefter ser det ud til, at den originale signatur, der er produceret over det ægte dokument, faktisk er en signatur af et forfalsket dokument: en signaturtransplantationsforfalskning er effektivt blevet udført. en adgangskode, men giver dem alligevel mulighed for at kontrollere, om brugeren, der prøver at få adgang, kender denne adgangskode. Ikke kun tillader hashing systemer ikke at gemme adgangskoder i almindelig tekst (som skal beskyttes meget omhyggeligt), men det giver mulighed for, at selvom hashene er offentligt eksponeret, er adgangskoderne stadig sikre (på samme måde som offentlig nøglekrypto) systemer er i stand til at afsløre offentlige nøgler). Selvom i praksis er hashes alligevel beskyttet mod offentlig adgang: for eksempel /etc/shadow filer på Unix-lignende systemer, der supplerer verdenslæsbare /etc/passwd filer .

Hash-funktionen er alt andet end tilfældig. Imidlertid anvendes randomisering til at modvirke angribere, der bygger store ordbøger med adgangskoder og hash, der gør det muligt for dem at slå en hash-kode op og hente den tilsvarende adgangskode.

For at hash en adgangskode mere sikkert kan vi blot tilføje nogle tilfældige bits til det kaldes et “salt”. Forskellige salte føjet til den samme adgangskode fører naturligvis til forskellige hashes (forhåbentlig med få eller ingen kollisioner).

Hvis tilfældigt salt er f.eks. 32 bit bredt, betyder det, at teoretisk kan en adgangskode hash på over fire milliarder forskellige måder, hvilket gør det meget upraktisk at have en forudberegnet ordbog over alle mulige hash af et stort antal adgangskoder.

Selvfølgelig, når brugeren bliver godkendt, ved hun ikke noget om dette salt. Det er okay, fordi saltet opbevares sammen med hashen i brugerens profil (ofte kombineret med hashen i en enkelt kompakt bitstreng). Når brugerens adgangskodepost valideres, tilføjes saltet til den adgangskode, som helst gik hun ind, så haschen udføres med det rigtige salt. Hvis adgangskoden er korrekt, vil hashen matche, da det anvendte salt også er det rigtige, efter at være trukket fra brugerens profil.

Så sådan er tilfældighed indarbejdet i adgangskodeshashing, mens man stadig lader det arbejde.

Det, der gør hash svært at knække, er at de er bygget fra “fældedør” eller “envejs” -funktioner. I matematik er der mange eksempler på sådanne ting. For eksempel , enkel tilføjelse er en fældedør. Hvis vi tilføjer nogle heltal for at producere et beløb, er det umuligt at gendanne de oprindelige tal, idet vi kun kender summen.

Adgangskodehash er ikke krypterede adgangskoder. hash og salt af en adgangskode og tilfældigvis gætter adgangskoden, så kan hun let bekræfte dette nøjagtigt på samme måde som login-godkendelsessoftwaren gør det: hun kører adgangskoden plus salt gennem hashing-funktionen og ser, at den korrekte hash dukker op.

Kommentarer

• Fremragende skrivefærdigheder og en virkelig let y for at forstå svar, der i det hele taget er korrekt, men alligevel tackler alle punkter og bevarer en naturlig strøm til det, der gør det så meget mere omfattende. At ‘ ikke er en let bedrift, så meget tak for dit svar!
• meget informativ. Du dækkede alle aspekterne.

En af nøglerne til hashing er, at den smider information. Du kan ikke vende en hash, fordi den nødvendige viden er væk. Her er et par eksempler på brugbare (men ret værdiløse) hashfunktioner. Hvis du giver mig en adgangskode, kunne jeg gøre noget som et af følgende:

• Tæl antallet af vokaler
• Tag ASCII-koden for hvert bogstav og XOR dem alle sammen
• Tag CRC32-kontrolsummen af den binære repræsentation af adgangskoden (denne er faktisk en rigtig hash, bare ikke en kryptografisk)

I hvert af disse tilfælde kan jeg ikke vende processen. I stedet skal jeg køre processen igen, når du giver mig adgangskoden igen senere for at se, om den beregning, jeg kørte, stemmer overens.

For eksempel: Hvis du oprindeligt giver mig adgangskoden “abe”, gemmer jeg muligvis nummer 3 (3 vokaler). Senere, når jeg forsøger at godkende adgangskoden “drage”, kører jeg den samme kontrol igen og kommer med 2, som matcher ikke 3. Så jeg ved, at du gav mig den forkerte adgangskode. Men hvis du giver mig adgangskoden “melissa”, antager jeg forkert, at du har indtastet den rigtige adgangskode. Dette er en hash kollision .

Det regelsæt, du anvender for at komme med det nummer, der repræsenterer en given adgangskode er din hash-funktion . Disse betragtes som “envejs” -funktioner, fordi du ikke skulle være i stand til at vende dem. Højkvalitets hashfunktioner er designet til at begrænse antallet af potentielle kollisioner, så du ikke behøver at bekymre dig om dette problem. Et skridt videre, kryptografiske hashfunktioner er designet til at gøre det vanskeligt at komme med en streng, der kan matche en given output ( og måske med vilje skabe kollisioner). De er også designet til at begrænse mængden af information, du kan hente om et givet input fra kun hash-output.

Så som et resultat er den eneste måde at fortælle, hvilken adgangskode der matcher en given kryptografisk hash, at prøve alle mulighederne, indtil du snubler over en, der fungerer. Yderligere modforanstaltninger (salt, BPKDF2 osv.) Gør denne gætteproces endnu sværere ved at få personen til at gætte adgangskoden til at hoppe gennem flere bøjler for hvert forsøg.

Bemærk, at jeg helt gliste over, hvordan en kryptografisk hash-funktion gør det svært at komme med en fungerende adgangskode (selvom den ikke er den oprindelige). Dette kaldes et “ preimage-angreb “. I det trivielle eksempel ovenfor er det at komme med” melissa “som en kandidatadgangskode indeholdende 3 vokaler et eksempel på et sådant angreb.

Kryptografiske hashfunktioner gør dette typisk ved at køre input selvom flere” runder “af en given proces, hvor output fra hver runde bliver en del af input til den næste.For at finde ud af indgangen til den første runde, skal du finde ud af indgangen til den anden runde, hvilket igen kræver, at du finder ud af indgangen til den tredje runde osv., Hvilket betyder, at hvert gæt af hver komponent skal kontrolleres gennem et langt og komplekst sæt beregninger. Thomas Pornin har en smuk udtømmende forklaring på, hvordan denne modstand fungerer; ret nyttig læsning, hvis du virkelig vil forstå det.

1. Bestem den konstante værdi af z, der tilfredsstiller denne ligning: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. Brug for hjælp? OK, x = 32. Kan du stadig ikke løse det? Derefter skal du ikke kende svaret i første omgang.

   Værdien af y, som reducerer dette til en enkelt variabelligning, hvilket gør løsningen af den enkelt variabel triviel for enhver 6.-klassing (muligvis har brug for en lommeregner), er en hemmelighed, som jeg kun har delt med folk, jeg stoler på. Uden den kunne z være noget; dens værdi afhænger af y, og den kan derfor ikke løses tilfredsstillende uden en konstant, kendt y. Hvis du ikke ” ikke kender y s værdi, det er fordi jeg ikke har tillid til dig nok til at give det til dig privat.

   Dette er det grundlæggende princip for kryptografi; den matematiske formel eller anden deterministisk proces er godt -dokumenteret, og en eller flere af de mulige variabler med formlen tillades også at være offentligt kendte, hvilket gør det muligt for de to parter at blive enige om en måde at oprette deres koder på, så hver kan dekryptere, hvad de andre krypterer. forblive hemmelig; hvis du kender den ene, kan du opdage den anden. Den du burde kende er nøglen og den du kan opdage med nøglen er beskeden.

   For en hash er den lidt anderledes. En hash kræver ikke, at en hemmelighed skal holdes for at holde en anden. I stedet for hashes arbejde baseret på en irreversibel matematisk transformation; for enhver H (x) = y er der ingen kendt H ^-1 (y) = x bortset fra at prøve H (x) for alle mulige x, indtil du får y. Normalt skyldes dette, at flere mellemresultater af ligningen er tvetydige; for eksempel beregner kvadratroden af et positivt tal teknisk begge et positivt og negativt resultat, da begge tal kunne ganges med sig selv for at producere resultatet. Det inverse af et modul er ligeledes tvetydigt; tallet 1, produceret af x mod 3, kunne have været produceret af en hvilken som helst x = 3k + 1. Disse typer af “envejs” -transformationer kombineres på en sådan måde, at forsøg på at beregne den inverse hash-funktion genererer uendelige muligheder; den lettere (nemmeste) måde at løse dem på er derfor simpelthen at prøve alle mulige input, indtil en output matcher. Dette tager stadig lang tid.

2. Hashes er ikke tilfældige. Som jeg tidligere har nævnt, er hashes resultatet af en irreversibel matematisk operation. Denne operation skal stadig være deterministisk; givet en konstant input, er output konstant uanset hvor mange gange du udfører operationen. Der er ingen tilfældig komponent.

   Hvor du måske har været forvirret, er udtrykket for, hvad en hash simulerer, hvilket er et tilfældigt orakel . Forestil dig en sort kasse, inde i hvilken en lille mand har en fotografisk hukommelse og en eller anden mystisk metode til at generere helt tilfældige tal. Du skriver noget ned på et stykke papir og skubber det gennem en åbning, hvor manden får det. Han læser det, og en af to ting sker. Enten har han ikke læst det før, i hvilket tilfælde han vil generere et nyt tilfældigt tal og give det til dig og overdrage både din besked og nummeret til hans hukommelse. Eller, han har læst denne nøjagtige besked før, i hvilket tilfælde han husker det nummer, han genererede første gang, han læste det og giver dig nummeret. Generatoren for tilfældige tal genererer aldrig et nummer, den allerede har genereret, den har uendelig mulig størrelse, og den lille mand ” hukommelse er ubegrænset og ufejlbarlig. Derfor vil den lille mand aldrig tro, at han har læst en besked før, hvis han ikke har, glem aldrig, at han har læst en besked før, og det vil aldrig nogensinde frembringe to forskellige numre til den nøjagtige samme besked eller den samme nummer for to forskellige meddelelser.

   Dette er hvad hash-funktioner prøver at simulere. De kan ikke modellere denne lille mand med fotografisk hukommelse, fordi det ville kræve uendelig lagerplads og ubegrænset, universel tilgængelighed, endda enheder, der ikke er forbundet til nogen anden enhed på nogen anden måde. I stedet stoler de på en deterministisk, men tilfældig udseende beregning, der “fordøjer” meddelelsen til dens hash-værdi. Den samme hash-funktion, givet den samme besked, vil producere den samme fordøjelse, men disse funktioner er begrænset i antallet af hash-værdier, de får lov til at returnere. Dette skaber muligheden for, hvad vi kalder hash-kollisioner; der er flere mulige meddelelser end hash-værdier, så før eller senere (forhåbentlig senere), to forskellige mig ssages producerer den samme hash.

3. Hash kan knækkes af tre grundlæggende grunde.For det første, fordi de er en deterministisk, matematisk afledning af deres budskab, finder matematikere (og dermed angribere) til sidst et matematisk forhold mellem en besked og dens hash eller mellem to meddelelser og deres resulterende hashes. Hvad der engang så tilfældigt ud, er ikke længere det. Det ville give mulighed for et antal angreb baseret på arten af den svaghed, der blev fundet; hvis der er en algoritmisk måde, der gives en besked og dens hash, til at generere en kolliderende besked, er det et problem. Hvis der er en måde at manipulere en besked på og forudsige den resulterende hash, er det et andet problem. Hvis der faktisk er en måde at vende hashen på, producerer en besked fra hashen, der, når den genhashes, producerer den samme hash, det “sa alvorlige problem.

   For det andet, fordi hashes har en begrænset fordøjelsesstørrelse, før eller senere, vil to meddelelser producere den samme hash. Det betyder, at en angriber ikke behøver at finde den besked, som du bruger til at producere en bestemt hash ; alt hvad han skal gøre er at finde en besked, der producerer den samme hash. Oddsene herfor er små, teoretisk en chance ud af hvor mange mulige hashes der er, men stadig bedre end en i uendelighed.

   Endelig, mens der er mange mulige beskeder, er der langt mindre antal sandsynlige beskeder. De meddelelser, vi typisk giver hashfunktioner, har normalt en eller anden struktur (baseret på sprog, emne, elektronisk formatering og formål), hvilket betyder, at vi i betragtning af en del af meddelelsen mere nøjagtigt kan gætte andre dele af meddelelsen. Dette betyder i informationsvidenskabelig henseende, at meddelelser, der konverteres til hashes, ofte har lavere entropi end selve hash-funktionen; klart sagt, en hash-funktion, der producerer 256-bit fordøjelser, kan teoretisk producere enhver permutation af disse bits, 2 ^ 256. Men hvis der f.eks. Kun er 10.000 mulige meddelelser, der nogensinde kunne indtastes i denne hash-funktion af et system, der undersøges for angreb, vil kun 10.000 af de 2 ^ 256 mulige hash-værdier nogensinde blive set, og vigtigere, en angriberen ville i værste fald kun skulle prøve alle 10.000 mulige input for at finde den, der producerer den hash-værdi, han leder efter.

Kommentarer

• Og det er … derfor elsker jeg it-sikkerhed ‘ s stack exchange site-ting.
• Også din forklaring af nr. 1 er præcis, hvad jeg havde brug for. Jeg har dog et spørgsmål. Det ser ud til, at ” hashes ” er som nummerversioner for en given ting (adgangskoder i dette tilfælde). Så hvis jeg har et websted, og 100.000 mennesker tilmelder mig. Derefter bruger 50% adgangskoden ” adgangskode ” Jeg er i stand til at spare masser af plads ved bare at gemme den hashede værdi på ” adgangskode ” i stedet for adgangskode et ton gange?
• Nå hvis du ‘ genbruger en sikker hash (> = 256-bit fordøjelsesstørrelse) og gemmer derefter den hashede værdi af ” adgangskode ” øger din lagerstørrelse. Desuden, hvis en hacker nogensinde skulle se, at 50% af brugerkontiene havde den samme hash med adgangskode, ved han ‘, at alt han ‘ d skal gøre er at knække et kodeord, og han har adgang til 50% af brugerkontiene. Du skal ” saltning ” din adgangskode hashes; der er en række forskellige metoder, men slutresultatet er, at den samme adgangskode, der er hashet af den samme algoritme, producerer en anden fordøjelse på grund af en ekstra unik saltværdi for hver konto.