Hvordan fungerer hashing? (Norsk)

Kryptografiske hashfunksjoner er matematiske objekter som kan beskrives som «en stor blanding og kryptering av noen biter «. De tar som inngang en sekvens av biter (muligens en veldig lang) og tilbyr en utgang av fast størrelse. Grovt sett er de så sammenfiltrede at selv om det ikke er noe hemmelig om dem (det er bare deterministisk kode), kan ingen finne ut hvordan man kan «invertere» dem (finne en matchende inngang for en gitt utdata) bortsett fra ved den grunnleggende metoden som kalles «flaks»: prøv tilfeldige innganger til en kamp er funnet.

Hvordan det kan skje vitenskapelig at hashfunksjoner i det hele tatt kan eksistere er et godt spørsmål .

Hashing er ikke kryptering . Det er ingen hemmelighet, ingen nøkkel i hashing.

Hash-funksjoner har mange bruksområder; en av dem er «passordlagring». En hash-funksjon ser ut som en god ting for passordlagring. Vi ønsker ikke å lagre passord direkte (ellers vil en sporadisk titt på databasene våre av angriperen gi ham for mye informasjon. Se dette blogginnlegget for en diskusjon) ; vi vil lagre passordbekreftelsestokener : noe som tillater verifisering av et passord (som brukeren presenterer), men ikke avslører selve passordet. Så ideen er: la oss lagre hash av passordet. Når et passord skal bekreftes, beregner vi bare hash og ser om det samsvarer med den lagrede verdien. Men å gjette passordet fra hashverdien er vanskelig, siden hash-funksjonen er motstandsdyktig mot «inversjon» (se ovenfor).

Siden passord er en spesiell type data (det er data som mennesker kan huske), for riktig sikkerhet, trenger vi en «styrket» hash-funksjon:

• Vi vil ha en veldig treg hash-funksjon.
• Vi vil ikke ha en hash-funksjon, men mange distinkte hash-funksjoner, slik at hvert passord blir hash med sin egen hash-funksjon; dette handler om å avskrekke parallelle angrep. Denne prosessen med å gjøre en enkelt hashfunksjon om til mange varianter kalles salting .

Se dette svaret for en grundig behandling av emnet hashing-passord.

Kommentarer

• Beklager, men mens svaret ditt var ekstremt grundig og godt sammensatt, fant jeg det andre svaret var mer som det jeg lette etter.

Hashing er en funksjon fra noen bitstreng (vanligvis variabel lengde) til en annen bitstreng (vanligvis mindre og med fast lengde).

Hashing brukes i databaser for datainhenting, og i datastrukturer i minnet som kalles hash-tabeller. Det lar oss redusere vilkårlige data, for eksempel en tegnstreng eller et komplisert objekt med mange felt, til et binært tall som deretter kan brukes direkte som en indeks i et sparsomt utvalg for å hente de tilknyttede dataene (med noen detaljer for håndtering av hash kollisjoner).

Hashfunksjonene som brukes på ovennevnte måte er «fettere» til kryptografiske hashingfunksjoner. De er designet etter forskjellige krav. De må være raske å beregne, og oppnå en god distribusjon.

I sikker databehandling brukes kryptografiske hashes for å fordøye data til en eller annen representativ, liten bitstreng. Kryptografiske funksjoner har forskjellige krav. De er designet for å være vanskelige å reversere (for å være «felle dør» eller «enveis» funksjoner). Ikke bare det, men et viktig krav er at det må være vanskelig å finne, for en gitt klartekst og hash-verdi, en annen ren tekst som produserer den samme hash.

Hashing kan ikke bare brukes til passord, men som et kontrollsum for verifisering av dataintegritet og som en del av implementeringen av digitale signaturer. For å signere et stort dokument digitalt, må vi bare hasjlegge dokumentet for å produsere en «fordøye» (et navn som brukes til utdata fra en hashfunksjon, når noe veldig langt er hash). Så blir akkurat denne fordøyelsen satt gjennom det offentlige nøkkelkrypto-systemet for å produsere en signatur. Du kan se svakheten der: Hva om en angriper lykkes med å produsere et dokument som har samme sammendrag? Da ser det ut som den originale signaturen som er produsert over det ekte dokumentet, faktisk er en signatur av et forfalsket dokument: en forfalskning av signaturtransplantasjon har blitt effektivt utført. et passord, men lar dem likevel verifisere om brukeren som prøver å få oppføring, kjenner passordet. Ikke bare tillater hashing at systemene ikke lagrer passord for ren tekst (som må beskyttes veldig nøye), men det gir mulighet for at selv om hasjene er offentlig eksponert, er passordene fremdeles sikre (på samme måte som kryptering av offentlig nøkkel systemer er i stand til å avsløre offentlige nøkler). I praksis er hashes likevel beskyttet mot offentlig tilgang: for eksempel /etc/shadow filer på Unix-lignende systemer, og supplerer verdilesbare /etc/passwd filer .

Hash-funksjonen er alt annet enn tilfeldig. Imidlertid brukes randomisering for å hindre angripere som bygger store ordbøker med passord og hash, som gjør det mulig for dem å slå opp en hash-kode og hente det tilsvarende passordet. noen tilfeldige biter til den kalt et «salt». Ulike salter som er lagt til det samme passordet, fører selvfølgelig til forskjellige hashes (forhåpentligvis med få eller ingen kollisjoner).

Hvis det tilfeldige saltet er, si 32 bits bredt, betyr det at, i teorien, kan ett passord hasj på over fire milliarder forskjellige måter, noe som gjør det veldig upraktisk å ha en forhåndsberegnet ordbok med alle mulige hashes av et stort antall passord.

Når brukeren autentiseres, vet hun selvfølgelig ikke noe om dette saltet. Det er greit fordi saltet lagres sammen med hasjen i brukerens profil (ofte kombinert med hashen i en enkelt kompakt bitstreng). Når brukerens passordoppføring valideres, blir saltet lagt til uansett passord hun kom inn, slik at hasjen blir utført med riktig salt. Hvis passordet er riktig, vil hasjen matche, siden saltet som brukes er også det rette, etter å ha blitt trukket fra brukerens profil.

Så det er slik tilfeldighet er innlemmet i passordhashing, mens du fremdeles lar den fungere.

Det som gjør hashes vanskelig å knekke, er at de er bygd fra «felle dør» eller «enveis» funksjoner. I matematikk er det mange eksempler på slike ting. , enkelt tillegg er en felle dør. Hvis vi legger til noen heltall for å produsere en sum, er det umulig å gjenopprette de opprinnelige tallene, bare å vite summen.

Passordhash er ikke krypterte passord. Hvis en angriper har hash og salt av et passord, og tilfeldigvis gjetter passordet, så kan hun enkelt bekrefte dette, akkurat på samme måte som påloggingsautentiseringsprogramvaren gjør det: hun kjører passordet pluss salt gjennom hashfunksjonen og ser at det riktige hash dukker opp.

Kommentarer

• Utmerkede skriveferdigheter og veldig lett y for å forstå svaret som faktisk er riktig, men takler alle punkter og beholder en naturlig flyt til det som gjør det så mye mer omfattende. At ‘ ikke er noen enkel prestasjon, takk så mye for svaret ditt!
• veldig informativ. Du dekket alle aspektene.

En av nøklene til hashing er at den kaster informasjon. Du kan ikke snu en hash fordi den nødvendige kunnskapen er borte. Her er noen eksempler på brukbare (men ganske verdiløse) hashfunksjoner. Hvis du gir meg et passord, kan jeg gjøre noe av det følgende:

• Tell antall vokaler
• Ta ASCII-koden for hver bokstav og XOR dem alle sammen
• Ta CRC32-kontrollsummen av den binære representasjonen av passordet (dette er faktisk en ekte hash, bare ikke en kryptografisk)

I hvert av disse tilfellene kan jeg ikke reversere prosessen. I stedet må jeg kjøre prosessen på nytt når du gir meg passordet igjen senere for å se om beregningen jeg kjørte samsvarer.

For eksempel: Hvis du først gir meg passordet «monkey», kan jeg lagre nummer 3 (3 vokaler). Senere, når jeg prøver å godkjenne passordet «dragon», kjører jeg den samme sjekken igjen og kommer opp med 2, som stemmer ikke med 3. Så jeg vet at du ga meg feil passord. Men hvis du gir meg passordet «melissa», antar jeg feil at du skrev inn riktig passord. Dette er en hash kollisjon .

Regelsettet du bruker for å komme opp med nummeret som representerer et gitt passord er hash-funksjonen . Disse betraktes som «enveis» -funksjoner fordi du ikke skal kunne reversere dem. Hash-funksjoner av høy kvalitet er designet for å begrense antall potensielle kollisjoner, slik at du ikke trenger å bekymre deg for det problemet. Et skritt videre, kryptografiske hashfunksjoner er designet for å gjøre det vanskelig å komme opp med en streng som kan matche en gitt utgang ( og kanskje med vilje skape kollisjoner). De er også designet for å begrense mengden informasjon du kan hente om en gitt inngang fra bare hasjutgangen.

Så som et resultat er den eneste måten å fortelle hvilket passord som samsvarer med en gitt kryptografisk hash, å prøve alle mulighetene til du snubler over et som fungerer. Ytterligere mottiltak (salt, BPKDF2 osv.) Gjør denne gjetningsprosessen enda vanskeligere ved å få personen til å gjette passordet til å hoppe gjennom flere bøyler for hvert forsøk. vanskelig å komme med et fungerende passord (selv om det ikke er det originale). Dette kalles et « preimage-angrep «. I det trivielle eksemplet ovenfor er det å komme opp med» melissa «som et kandidatpassord som inneholder tre vokaler, et eksempel på et slikt angrep.

Kryptografiske hashfunksjoner gjør dette vanligvis ved å kjøre inngangen gjennom flere» runder «av en gitt prosess, der utgangen fra hver runde blir en del av inngangen til den neste.For å finne ut inngangen til den første runden, må du finne ut inngangen til den andre runden, som igjen krever at du regner ut inngangen til den tredje runden osv., Noe som betyr at hver gjetning av hver komponent må kontrolleres gjennom et langt og komplekst sett med beregninger. Thomas Pornin har en ganske uttømmende forklaring på hvordan denne motstanden fungerer; ganske nyttig lesing hvis du virkelig vil forstå det.

1. Bestem den konstante verdien av z som tilfredsstiller denne ligningen: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. Trenger du hjelp? OK, x = 32. Kan du fortsatt ikke løse det? Da burde du ikke vite svaret i utgangspunktet.

   Verdien av y, som vil redusere dette til en enkelt variabelligning, noe som gjør løsningen på den ene variabelen triviell for enhver 6.-klassing (muligens trenger en kalkulator), er en hemmelighet som jeg bare har delt med folk jeg stoler på. Uten den kan z være hva som helst; verdien er avhengig av y og så kan den ikke løses tilfredsstillende uten en konstant, kjent y. Hvis du ikke » ikke kjenner verdien din, den er fordi jeg ikke har stolt på deg nok til å gi den til deg privat.

   Dette er det grunnleggende prinsippet for kryptografi; den matematiske formelen eller annen deterministisk prosess er vel -dokumentert, og en eller flere av de mulige variablene med formelen har også lov til å være offentlig kjent, slik at de to partene kan bli enige om en måte å sette opp kodene sine slik at hver kan dekryptere hva de andre krypterer. forbli hemmelig; hvis du kjenner den ene, kan du oppdage den andre. Den du bør vite er nøkkelen, og den du kan oppdage med nøkkelen er meldingen.

   For en hash er den litt annerledes. En hash krever ikke at en hemmelighet skal oppbevares for å beholde en annen. I stedet for hasharbeid basert på en irreversibel matematisk transformasjon; for enhver H (x) = y er det ingen kjent H ^-1 (y) = x bortsett fra å prøve H (x) for alle mulige x til du får y. Vanligvis er dette fordi flere mellomresultater av ligningen er tvetydige; for eksempel produserer teknisk beregning av kvadratroten av et positivt tall begge et positivt og negativt resultat, siden begge tallene kan multipliseres med seg selv for å produsere resultatet. Det inverse av en modul er tilsvarende tvetydig; tallet 1, produsert av x mod 3, kunne ha blitt produsert av hvilken som helst x = 3k + 1. Disse typer «enveis» transformasjoner er kombinert på en slik måte at det å prøve å beregne den inverse hash-funksjonen genererer uendelige muligheter. Den enkleste (enkleste) måten å løse dem på er derfor å prøve alle mulige innganger til en utgang samsvarer. tar fortsatt lang tid.

2. Hash er ikke tilfeldig. Som jeg tidligere har uttalt, er hashes resultatet av en irreversibel matematisk operasjon. Den operasjonen må fremdeles være deterministisk; gitt en konstant inngang, er utgangen konstant uavhengig av hvor mange ganger du utfører operasjonen. Det er ingen tilfeldig komponent.

   Hvor du kanskje har vært forvirret, er begrepet for hva en hash simulerer, som er et tilfeldig orakel . Se for deg en svart boks, der det er en liten mann med et fotografisk minne og en eller annen mystisk metode for å generere helt tilfeldige tall. Du skriver noe ned på et papir, og skyver det gjennom en spalte der mannen får det. Han leser det, og en av to ting skjer. Enten har han ikke lest det før, i så fall vil han generere et nytt tilfeldig nummer og gi det til deg, forplikte både meldingen din og nummeret til hans minne. Eller, han har lest nøyaktig meldingen før, i hvilket tilfelle han husker nummeret han genererte første gang han leste det og ga deg nummeret. Tilfeldige tallgeneratoren vil aldri generere et nummer den allerede har generert, den har uendelig mulig størrelse, og den lille mannen «s minne er ubegrenset og ufeilbarlig. Derfor vil den lille mannen aldri tro at han har lest en melding før hvis han ikke har, glem aldri at han har lest en melding før, og vil aldri aldri produsere to forskjellige tall for nøyaktig samme melding eller den samme nummer for to forskjellige meldinger.

   Dette er hva hashfunksjoner prøver å simulere. De kan ikke modellere denne lille mannen med fotografisk minne, fordi det ville kreve uendelig lagringsplass og ubegrenset, universell tilgjengelighet, til og med til enheter som ikke er koblet til andre enheter på noen annen måte. I stedet stoler de på en deterministisk, men tilfeldig- ser beregning som «fordøyer» meldingen til hash-verdien. Den samme hash-funksjonen, gitt den samme meldingen, vil produsere den samme fordøyelsen, men disse funksjonene er begrenset i antall hash-verdier de får returnere. Dette skaper muligheten for det vi kaller hash-kollisjoner; det er flere mulige meldinger enn hash-verdier, så før eller senere (forhåpentligvis senere), to forskjellige meg ssages vil produsere samme hash.

3. Hashes kan bli sprukket av tre grunnleggende grunner.For det første fordi matematikere (og dermed angripere) til slutt finner en matematisk sammenheng mellom en melding og dens hash, eller mellom to meldinger og deres resulterende hashes. Det som en gang så tilfeldig ut, er ikke lenger det. Det ville tillate en rekke angrep basert på arten av svakheten som ble funnet; hvis det er en algoritmisk måte, gitt en melding og dens hash, for å generere en kolliderende melding, er det et problem. Hvis det er en måte å manipulere en melding på og forutsi den resulterende hash, er det et annet problem. Hvis det faktisk er en måte å reversere hasjen på, produserer en melding fra hashen som når den blir hash, produserer den samme hasjen, det «sa alvorlige problemet.

   For det andre, fordi hashes har en begrenset fordøyelsesstørrelse, før eller senere, vil to meldinger gi samme hash. Det betyr at en angriper ikke trenger å finne den meldingen du bruker for å produsere en viss hash ; alt han trenger å gjøre er å finne en melding som gir samme hash. Oddsen for dette er liten, teoretisk en sjanse ut av hvor mange mulige hashes det er, men likevel bedre enn en i uendelig.

   Til slutt, mens det er mange mulige meldinger, er det langt mindre antall sannsynlige meldinger. Meldingene vi vanligvis gir til hashfunksjoner har vanligvis en eller annen struktur (basert på språk, emne, elektronisk formatering og formål), noe som betyr at vi, gitt en del av meldingen, kan gjette andre deler av meldingen mer nøyaktig. Dette betyr, i informasjonsvitenskapelig henseende, at meldinger som konverteres til hashes ofte har lavere entropi enn hash-funksjonen selv; klart sagt, en hash-funksjon som produserer 256-bit fordøyelser kan teoretisk produsere en hvilken som helst permutasjon av disse bitene, 2 ^ 256. Imidlertid, hvis det, si, bare 10 000 mulige meldinger som noen gang kan legges inn i denne hashfunksjonen av et system som blir studert for angrep, vil bare 10 000 av de 2 ^ 256 mulige hashverdiene noen gang bli sett, og enda viktigere, en angriperen, i verste fall, bare måtte prøve alle 10.000 mulige innganger for å finne den som produserer hashverdien han leter etter.

Kommentarer

• Og dette …. er derfor jeg elsker IT-sikkerhet ‘ s stack exchange site thing.
• Også forklaringen din av # 1 er akkurat det jeg trengte. Imidlertid har jeg et spørsmål. Det ser ut til at » hashes » er som nummerversjoner for en gitt ting (passord i dette tilfellet). Så hvis jeg har en nettside og 100000 mennesker registrerer seg. Da bruker 50% passordet » passord » Jeg er i stand til å spare massevis av plass ved å bare lagre den hashverdien til » passord » i stedet for passord mange ganger?
• Vel hvis du ‘ bruker en sikker hash (> = 256-bit fordøyelsesstørrelse) og lagrer deretter hashverdien til » passord » vil øke lagringsstørrelsen. I tillegg, hvis en angriper noen gang skulle se at 50% av brukerkontiene hadde samme passordhash, ville han ‘ d vite at alt han ‘ d må gjøre er å knekke ett passord, og han har tilgang til 50% av brukerkontiene. Du bør » salting » passordet ditt hasher; Det finnes en rekke metoder, men sluttresultatet er at det samme passordet som er hash av den samme algoritmen, gir en annen fordøyelse på grunn av en ekstra unik saltverdi for hver konto.