Hur fungerar hashing?

Kryptografiska hashfunktioner är matematiska objekt som kan beskrivas som ”en stor blandning och kryptering av några bitar ”. De tar som ingång en sekvens av bitar (möjligen en mycket lång) och erbjuder en utdata av fast storlek. Grovt sagt är de så trassliga att även om det inte finns något hemligt om dem (det är bara deterministisk kod), kan ingen räkna ut hur man ”inverterar” dem (hitta en matchande ingång för en given utdata) utom med den grundläggande metoden som kallas ”tur”: prova slumpmässiga ingångar tills en matchning hittas.

Hur det vetenskapligt kan hända att hashfunktioner kan existera alls är en bra fråga .

Hashing är inte kryptering . Det finns ingen hemlighet, ingen nyckel i hashing.

Hash-funktioner har många användningsområden; en av dem är ”lösenordsförvaring”. En hash-funktion ser ut som en bra sak för lösenordsförvaring. Vi vill inte lagra lösenord direkt (annars skulle en tillfällig titt på våra databaser av angriparen ge honom för mycket information; se detta blogginlägg för en diskussion) ; vi vill lagra lösenordsverifieringstoken : något som möjliggör verifiering av ett lösenord (som användaren presenterar) men inte avslöjar lösenordet i sig. Så idén är: Låt oss lagra lösenordets hash. När ett lösenord ska verifieras beräknar vi bara dess hash och ser om det matchar det lagrade värdet. Men det är svårt att gissa lösenordet från hashvärdet hash-funktionen är motståndskraftig mot ”inversion” (se ovan).

Eftersom lösenord är en speciell typ av data (det är data som människor kan komma ihåg), för rätt säkerhet behöver vi en ”förstärkt” hash-funktion:

• Vi vill ha en mycket långsam hash-funktion.
• Vi vill inte ha en hash-funktion, men många distinkta hashfunktioner, så att varje lösenord kommer att hashas med sin egen hashfunktion; det handlar om att avskräcka parallella attacker. Denna process för att förvandla en enda hashfunktion till många varianter kallas saltning .

Se detta svar för en grundlig behandling av ämnet hashing lösenord.

Kommentarer

• Tyvärr men medan ditt svar var extremt grundligt och väl sammanställt fann jag det andra svaret är mer som jag letade efter.

Hashing är en funktion från vissa bitsträng (vanligtvis variabel längd) till en annan bitsträng (vanligtvis mindre och med fast längd).

Hashing används i databaser för datainhämtning och i minnesdatastrukturer som kallas hashtabeller. Det gör att vi kan reducera godtyckliga data, till exempel en teckensträng eller ett komplicerat objekt med många fält, till ett binärt tal som sedan kan användas direkt som ett index i en gles array för att hämta tillhörande data (med några detaljer för hantering av hash kollisioner).

De hashfunktioner som används på ovanstående sätt är ”kusiner” till kryptografiska hashfunktioner. De är utformade efter olika krav. De måste vara snabba att beräkna och uppnå en bra distribution.

I säker databehandling används kryptografiska haschar för att smälta in data i någon representativ, liten bitsträng. Kryptografiska funktioner har olika krav. De är utformade för att vara svåra att vända (för att vara ”fälldörr” eller ”enkelriktad”). Inte bara det, utan ett viktigt krav är att det måste vara svårt att hitta, för en given klartext och hash-värde, en annan klartext som producerar samma hash.

Hashing kan inte bara användas för lösenord, men som en kontrollsumma för verifiering av dataintegritet och som en del av implementeringen av digitala signaturer. För att digitalt signera ett stort dokument måste vi helt enkelt hasha dokumentet för att producera en ”sammandragning” (ett namn som används för utmatningen av en hashfunktion, när något mycket långt hashas). Då läggs bara denna sammandrag genom kryptosystemet för den offentliga nyckeln för att producera en signatur. Du kan se svagheten där: vad händer om en angripare lyckas producera ett dokument som har samma sammandrag? Då ser det ut som att originalsignaturen som produceras över det äkta dokumentet faktiskt är en signatur av ett förfalskat dokument: en förfalskning av signaturtransplantation har genomförts effektivt. ett lösenord, men ändå gör det möjligt för dem att verifiera om användaren som försöker få tillgång känner till det lösenordet. Hashing tillåter inte bara att system inte lagrar lösenord för vanlig text (som måste skyddas mycket noggrant) men det möjliggör att även om hasharna är offentligt exponerade är lösenorden fortfarande säkra (på samma sätt som public key key system kan avslöja allmänna nycklar). Även i praktiken är hash ändå skyddad från allmänhetens tillgång: till exempel /etc/shadow filer på Unix-liknande system, kompletterande världsläsbara /etc/passwd filer .

Hashfunktionen är allt annat än slumpmässig. Randomisering används dock för att motverka angripare som bygger stora ordböcker med lösenord och hash, som gör det möjligt för dem att leta upp en hash-kod och hämta motsvarande lösenord.

För att hash ett lösenord säkrare kan vi helt enkelt lägga till några slumpmässiga bitar till det kallade ”salt”. Olika salter som läggs till samma lösenord leder naturligtvis till olika hash (förhoppningsvis med få eller inga kollisioner).

Om det slumpmässiga saltet är, säg, 32 bitar brett, betyder det att, i teorin, kan ett lösenord hasha på över fyra miljarder olika sätt, vilket gör det mycket opraktiskt att ha en förberäknad ordbok över alla möjliga hash av ett stort antal lösenord.

Naturligtvis, när användaren autentiseras, vet hon ingenting om detta salt. Det är okej eftersom saltet lagras tillsammans med haschen i användarens profil (ofta i kombination med haschen i en enda kompakt bitsträng). När användarens lösenordsinmatning valideras läggs saltet till vilket lösenord som helst gick hon in, så att hasningen utförs med rätt salt. Om lösenordet är korrekt kommer hash att matcha, eftersom saltet som används också är det rätta, efter att ha dragits från användarens profil.

Så det är så slumpmässigheten införlivas i lösenordshashing, samtidigt som det fortfarande låter det fungera.

Det som gör hash svårt att knäcka är att de är byggda från ”fälldörr” eller ”envägs” -funktioner. I matematik finns det många exempel på sådana saker. , enkelt tillägg är en fälldörr. Om vi lägger till några heltal för att producera en summa är det omöjligt att återställa de ursprungliga siffrorna, med kunskap om summan.

Lösenordshash är inte krypterade lösenord. Om en angripare har hash och salt av ett lösenord och råkar gissa lösenordet, då kan hon enkelt bekräfta detta, exakt på samma sätt som inloggningsautentiseringsprogramvaran gör det: hon kör lösenordet plus salt genom hashing-funktionen och ser att rätt hash framträder.

Kommentarer

• Utmärkta skrivförmåga och ett riktigt enkelt y för att förstå svaret som faktiskt är korrekt, men ändå tar itu med alla punkter och behåller ett naturligt flöde till det som gör det så mycket mer omfattande. Att ’ inte är en lätt prestation, tack så mycket för ditt svar!
• mycket informativ. Du täckte alla aspekter.

En av nycklarna till hashing är att den slänger information. Du kan inte vända en hash eftersom den nödvändiga kunskapen är borta. Här är några exempel på funktionella (men ganska värdelösa) hashfunktioner. Om du ger mig ett lösenord kan jag göra något av följande:

• Räkna antalet vokaler
• Ta ASCII-koden för varje bokstav och XOR dem alla tillsammans
• Ta CRC32-kontrollsumman för den binära representationen av lösenordet (den här är faktiskt en riktig hash, bara inte en kryptografisk)

I vart och ett av dessa fall kan jag inte vända processen. Istället måste jag köra om processen när du ger mig lösenordet senare för att se om beräkningen jag kör matchar.

För exempel: Om du först ger mig lösenordet ”apa” kan jag spara nummer 3 (3 vokaler). Senare, när jag försöker verifiera lösenordet ”drake”, kör jag samma kontroll igen och kommer med 2, som matchar inte 3. Så jag vet att du gav mig fel lösenord. Men om du ger mig lösenordet ”melissa” skulle jag felaktigt anta att du skrev rätt lösenord. Detta är en hash kollision .

Regeluppsättningen du tillämpar för att komma fram till numret som representerar ett givet lösenord är din hashfunktion . Dessa betraktas som ”enkelriktade” funktioner eftersom du inte skulle kunna vända dem. Högkvalitativa hashfunktioner är utformade för att begränsa antalet potentiella kollisioner, så att du inte behöver oroa dig för det problemet. Ett steg längre, kryptografiska hashfunktioner är utformade för att göra det svårt att komma på en sträng som kan matcha en given utgång ( och kanske avsiktligt skapa kollisioner). De är också utformade för att begränsa mängden information du kan hämta om en viss ingång från bara hash-utdata.

Så som ett resultat är det enda sättet att berätta vilket lösenord som matchar en viss kryptografisk hash att prova alla möjligheter tills du snubblar på ett som fungerar. Ytterligare motåtgärder (salt, BPKDF2, etc) gör denna gissningsprocess ännu svårare genom att låta personen gissa lösenordet hoppa igenom fler ringar för varje försök.

Observera att jag helt glättade över hur en kryptografisk hashfunktion gör det svårt att komma med ett fungerande lösenord (även om det inte är det ursprungliga). Detta kallas ” preimage attack ”. I det triviala exemplet ovan är att komma på” melissa ”som ett kandidatlösenord som innehåller tre vokaler ett exempel på en sådan attack.

Kryptografiska hashfunktioner gör vanligtvis detta genom att köra ingången men flera” rundor ”av en given process, där produktionen från varje runda blir en del av ingången till nästa.För att räkna ut ingången i den första omgången måste du räkna ut ingången till den andra omgången, vilket i sin tur kräver att du räknar ut ingången till den tredje omgången, etc., vilket innebär att varje gissning av varje komponent måste kontrolleras genom en lång och komplex uppsättning beräkningar. Thomas Pornin har en ganska uttömmande förklaring om hur detta motstånd fungerar; ganska användbar läsning om du verkligen vill förstå det.

1. Bestäm det konstanta värdet på z som uppfyller denna ekvation: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. Behöver du hjälp? OK, x = 32. Fortfarande kan du inte lösa det? Då borde du inte veta svaret i första hand.

   Värdet på y, vilket minskar detta till en enda variabelekvation, vilket gör att lösa det för den enda variabeln trivialt för alla sjätte klassare (möjligen behöver en miniräknare), är en hemlighet som jag bara har delat med människor jag litar på. Utan det kan z vara vad som helst; dess värde är beroende av y och så kan det inte lösas på ett tillfredsställande sätt utan en konstant, känd y. Om du inte ” t vet ditt värde, det beror på att jag inte har litat på dig tillräckligt för att ge dig det privat.

   Detta är den grundläggande principen för kryptografi; den matematiska formeln eller annan deterministisk process är väl -dokumenterad, och en eller flera av de möjliga variablerna med formeln tillåts också vara allmänt kända, så att de två parterna kan komma överens om ett sätt att ställa in sina chiffer så att var och en kan dekryptera vad de andra krypterar. förbli hemlig; om du känner en kan du upptäcka den andra. Den du borde veta är nyckeln och den du kan upptäcka med nyckeln är meddelandet.

   För en hash är det lite annorlunda. En hash kräver inte att en hemlighet ska hållas för att behålla en annan. I stället hasar arbete baserat på en irreversibel matematisk transformation. För alla H (x) = y finns det ingen känd H ^-1 (y) = x förutom att försöka H (x) för alla möjliga x tills du får y. Vanligtvis beror detta på att flera mellanresultat av ekvationen är tvetydiga; till exempel beräknar kvadratroten av ett positivt tal tekniskt både ett positivt och negativt resultat, eftersom antingen nummer kan multipliceras med sig själv för att producera resultatet. Den inversa av en modul är lika tvetydig; numret 1, producerat av x mod 3, kunde ha producerats av valfri x = 3k + 1. Dessa typer av ”enkelriktade” transformationer kombineras på ett sådant sätt att försök att beräkna den inversa hashfunktionen genererar oändliga möjligheter. Det enklare (enklaste) sättet att lösa dem är därför att helt enkelt prova alla möjliga ingångar tills en utgång matchar. Detta tar fortfarande lång tid.

2. Hash är inte slumpmässigt. Som jag tidigare sagt är hash resultatet av en oåterkallelig matematisk operation. Denna operation måste fortfarande vara deterministisk; med en konstant ingång är utgången konstant oavsett hur många gånger du utför åtgärden. Det finns ingen slumpmässig komponent.

   Där du kanske har varit förvirrad är det i termen för vad en hash simulerar, vilket är ett slumpmässigt orakel . Föreställ dig en svart ruta, inuti vilken är en liten man med ett fotografiskt minne och någon mystisk metod för att skapa perfekt slumpmässiga nummer. Du skriver ner något på ett papper och skjuter det genom en springa där mannen får det. Han läser det och en av två saker händer. Antingen har han inte läst det förut, i så fall kommer han att generera ett nytt slumpmässigt nummer och ge det till dig, överlåta både ditt meddelande och numret till hans minne. Eller, han har läst exakt meddelande innan, i vilket fall han kommer ihåg numret han genererade första gången han läste det och ger dig numret. Slumpgeneratorn genererar aldrig ett nummer som det redan har genererat, det har oändlig storlek och den lilla mannen minnet är obegränsat och ofelbart. Därför kommer den lilla mannen aldrig att tro att han har läst ett meddelande förut om han inte har, glöm aldrig att han har läst ett meddelande innan, och så kommer aldrig att producera två olika siffror för exakt samma meddelande eller samma nummer för två olika meddelanden.

   Detta är vad hash-funktioner försöker simulera. De kan inte modellera den här lilla mannen med det fotografiska minnet, för det skulle kräva oändligt lagringsutrymme och obegränsad, universell tillgänglighet, även för att enheter som inte är anslutna till någon annan enhet på något annat sätt. I stället förlitar de sig på en deterministisk men slumpmässig utseende beräkning som ”smälter” meddelandet till dess hash-värde. Samma hash-funktion, får samma meddelande, kommer att producera samma sammandrag, men dessa funktioner är begränsade i antalet hash-värden de får returnera. Detta skapar möjligheten för vad vi kallar hash-kollisioner; det finns fler möjliga meddelanden än hash-värden, så förr eller senare (förhoppningsvis senare), två olika jag ssages kommer att producera samma hash.

3. Hash kan knäckas av tre grundläggande skäl.För det första, eftersom de är en deterministisk, matematisk härledning av sitt budskap, hittar matematiker (och därmed angripare) så småningom en matematisk relation mellan ett meddelande och dess hash, eller mellan två meddelanden och deras resulterande hash. Det som en gång slumpmässigt såg ut är inte längre så. Det skulle möjliggöra ett antal attacker baserat på vilken svaghet som hittats; om det finns ett algoritmiskt sätt, med ett meddelande och dess hash, att generera ett kolliderande meddelande, är det ett problem. Om det finns ett sätt att manipulera ett meddelande och förutsäga den resulterande hash, är det ett annat problem. Om det i själva verket finns ett sätt att vända hashen, producerar ett meddelande från hashen som, när den hashas igen, producerar samma hash, det ”sa allvarliga problemet.

   För det andra, eftersom hash har en begränsad smältningsstorlek kommer förr eller senare två meddelanden att producera samma hash. Det betyder att en angripare inte behöver hitta meddelandet som du använder för att producera en viss hash ; allt han behöver göra är att hitta ett meddelande som ger samma hash. Oddsen för detta är små, teoretiskt sett en chans av hur många möjliga hash det finns, men ändå bättre än en i oändligheten.

   Slutligen, även om det finns många möjliga meddelanden, finns det en mycket mindre antal troliga meddelanden. Meddelandena som vi vanligtvis ger till hashfunktioner har vanligtvis en viss struktur (baserat på språk, ämne, elektronisk formatering och syfte), vilket innebär att, med tanke på en del av meddelandet, kan vi mer exakt gissa andra delar av meddelandet. Detta betyder, i informationsvetenskapliga termer, att meddelanden som konverteras till hash ofta har lägre entropi än själva hashfunktionen; tydligt uttryckt kan en hashfunktion som producerar 256-bitars digererar teoretiskt producera vilken permutation som helst av dessa bitar, 2 ^ 256. Men om det finns, säg, bara 10 000 möjliga meddelanden som någonsin kan matas in i denna hashfunktion av ett system som studeras för attack, kommer bara 10 000 av de 2 ^ 256 möjliga hashvärdena någonsin att ses, och ännu viktigare, en angriparen skulle i värsta fall bara behöva försöka alla 10 000 möjliga ingångar för att hitta den som producerar hashvärdet han letar efter.

Kommentarer

• Och det här …. därför älskar jag IT-säkerhet ’ s stack exchange site-sak.
• Också din förklaring av # 1 är precis vad jag behövde. Men jag har en fråga. Det verkar som att ” hash ” är som nummerversioner för en viss sak (lösenord i det här fallet). Så om jag har en webbplats och 100000 personer registrerar mig. Sedan använder 50% lösenordet ” lösenord ” Jag kan spara massor av utrymme genom att bara lagra det hashade värdet på ” lösenord ” istället för lösenord massor av gånger?
• Tja om du ’ använder en säker hash (> = 256-bitars sammandragstorlek) och lagrar sedan hashvärdet för ” lösenord ” kommer att öka din lagringsstorlek. Dessutom, om en angripare någonsin skulle se att 50% av användarkontona hade samma lösenordshash, ’ d vet att allt han ’ d måste göra är att knäcka ett lösenord och han har tillgång till 50% av användarkontona. Du bör ” salta ” ditt lösenordshash; det finns olika metoder, men slutresultatet är att samma lösenord som hashats av samma algoritm ger en annan sammandragning på grund av ett ytterligare unikt saltvärde för varje konto.