Steffen svar täcker detta perfekt, men jag ville bara lägga till några fler detaljer.

Allt som ger en matchning är vanligtvis bra

Som säger han, du bryr dig vanligtvis inte om att hitta det verkliga lösenordet, för många applikationer kommer gärna att autentisera dig med alla strängar som händer med hash till hashvärdet som lagras i databasen. Detta gäller oftast för webbapplikationer, men kan vara mindre ofta i andra sammanhang. Det betyder att om du utför en brute force-sökning och hittar något med samma hash kan du logga in på kontot även om det inte är samma lösenord. Detta, som antyds i frågan, är karaktären av hashing och är ett direkt resultat av duvahålsprincipen.

Tills du behöver det faktiska lösenordet

Det kan dock finnas vissa fall där du vill hitta det ursprungliga lösenordet. Detta skulle vara fallet om till exempel en hackare stal ett användarnamn / lösenord från en värdelös tjänst och ville försöka logga in som användare på en mer värdefull tjänst (Facebook, banker, etc ...). Eftersom människor ofta använder samma lösenord överallt, vill du i det här fallet verkligen ha det ursprungliga lösenordet - inte bara något som hasar till samma värde för en viss hashingalgoritm (trots allt kan olika tjänster använda olika hashingmetoder, och de flesta också använd kryptografiska salter - h / t @Taemyr).

Men skillnaden spelar ingen roll

Lyckligtvis (för vår angripare), detta spelar ingen roll. Anledningen är att en uttömmande brute force faktiskt är omöjlig. Istället kommer en hackare att prova saker som sannolikt kan vara lösenord (ordlistor, vanliga lösenord, etc ...). Föreställ dig som ett motexempel trots att det är omöjligt att du har en hash från en webbtjänst och lyckas utföra en brute force-sökning på alla möjliga 256-bitars ASCII-strängar. Du hittar tre ingångar som har samma värde som användarens lösenordshash:

1. BD3EDF42F6D3AF2DAAE93313EB534
2. 7AF7B8B8F84443872C48EC372DBD1
3. lösenord

Vilket skulle du gissa är det verkliga lösenordet? Svaret är tydligt # 3. Jag menar, det finns tekniskt en chans att användaren precis råkade välja ett extremt starkt lösenord (dvs. BD3EDF42F6D3AF2DAAE93313EB534 ) som just hände hash till samma värde som lösenord , men oddsen för det är faktiskt noll.

I denna mening har angriparen en bra fördel. De föredrar att hitta det verkliga lösenordet, och det visar sig att eftersom människor är dåliga att välja slumpmässiga lösenord, är det bästa sättet att göra det inte genom att kontrollera allt hur som helst - det är genom att kontrollera saker som ser ut som lösenord. Detta gör brute-tvångssökning mycket, mycket, mycket, mycket effektivare och ger också angriparen ett mycket mer användbart resultat (det faktiska lösenordet, snarare än någon slumpmässig sträng som råkar ha samma hash).

Huvudmålet med brute forcing är inte att få det ursprungliga lösenordet utan att få ett lösenord som fungerar. Således spelar det ingen roll om det hittade lösenordet inte var det ursprungliga så länge det fungerar.

Det är dock mycket troligt att med effektiv och intelligent brute-tvingning baserad på en ordlista med vanliga lösenord och typiska modifieringar kommer det resulterande lösenordet att vara det verkliga. Detta beror helt enkelt på att de flesta användare inte använder långa slumpmässiga lösenord utan vanliga lösenord med typiska modifieringar och därmed kommer de riktiga lösenorden att hittas först när de gör intelligent brute forcing.

Spelar det någon roll om en brute force-sökning efter ett lösenord returnerar en kollision och inte lösenordet?

Det finns andra svar som hanterar denna fråga ganska bra, så jag ska utforska en annan vinkel: Det spelar ingen roll, eftersom sökningar med brute-force sannolikt aldrig kommer att hitta en kollision istället för det ursprungliga lösenordet.

Antaganden:

• Lösenordet är kortare än den maximala längden med ett visst antal tecken.
• Brute-force-sökningen försöker varje tecken, med början med kortast möjliga lösenord.
• Implementeringen har en mycket låg sannolikhet för kollisioner. Detta gäller även för föråldrade algoritmer som MD5, men inte för den algoritm du angav.
• Kollisioner är enhetligt fördelade.

Låt oss säga att vårt lösenord är "lösenord", som har åtta tecken. Antalet alfanumeriska lösenord mellan ett och åtta tecken är cirka 2.219e + 14.

Låt oss säga att den maximala lösenordslängden är tio. Mellan nio och tio tecken finns det 8.528e + 17 lösenord, eller cirka 3800 gånger så många som mellan en och åtta. Även om vi antar fem kollisioner är sannolikheten att alla fem är längre än vårt "lösenord" cirka 99,9%.

Antalet jag har använt för max lösenordslängd är (förhoppningsvis) mycket mindre än vad som är används vanligtvis och antalet kollisioner är kraftigt överskattat. I praktiken är det inte att hitta en kollision som är kortare än det faktiska lösenordet.

Alla hashingalgoritmer som används i praktiken bör ha ett nyckelutrymme som är omöjligt att göra kraft. Å andra sidan är uppsättningen av faktiska lösenord mycket mer begränsad, så angripare kommer inte att söka i alla möjliga lösenord, utan bara de som används av riktiga användare.

Nu om du har ett bra lösenord och en angripare gör en brute force-attack, är det inte omöjligt att ett annat lösenord skulle ha samma hash. Om nyckelutrymmet för hashen bara var 64 bitar, kan du förvänta dig att några har samma hashkod bland några miljarder lösenord. Så det är inte omöjligt att en angripare hittar ett annat lösenord med samma hash (efter att ha kontrollerat 2 ^ 64 lösenord i genomsnitt). Båda skulle arbeta för angriparen att komma till tjänsten. I verkligheten bör hash-algoritmen ha ett mycket större nyckelutrymme och ingen kommer någonsin hitta ett annat lösenord med samma hash.

Att hitta det alternativa lösenordet gör att du kan logga in på en tjänst. Men de flesta angripare vill uttryckligen ha lösenordet eftersom de inte är intresserade av någon obetydlig tjänst men hoppas att du kommer att använda samma lösenord med andra tjänster. Så det alternativa lösenordet kommer att vara helt värdelöst för dem om inte en annan tjänst använder exakt samma hashingalgoritm och exakt samma salt.

Spelar det någon roll om en brute force-sökning efter ett lösenord returnerar en kollision och inte lösenordet?

Om ett lösenord är den enda mekanismen för åtkomst till en resurs är det ofta spelar ingen roll om det är exakt eller en kollision. Om du anger "hund" eller "katt" och din hashingalgoritm var string.length , kommer antingen att ge dig åtkomst.

Även om detta ofta är fallet är det också en fråga om programmets / tjänstens implementeringsdetaljer. Till exempel kan en webbplats / tjänst utföra giltighetskontroller av äkthet och körning, som bedömer lösenordet och var lösenordet kommer ifrån. Så även om "hund" och "katt" skulle kunna ge åtkomst, om mellanhanden har en regel att lösenord inte kan börja med "d" så är den kollisionen ute.

Dessutom kan vissa säkrare tjänster ibland samla in metadata (även hashad) på det medföljande lösenordet (t.ex. längd, antal byte osv.) och inkonsekvenser i att metadata ibland används för att flagga, neka åtkomst eller återställa lösenord till konton.

OP-exempel

  h (3) = 3 mod 17 = 3  

Är problemet att lösenordets hashutrymme (0-16 ) är mycket mindre än utrymmet för det tillåtna lösenordet, eller finns det något annat jag har utsikt över?

För att ta itu med din fråga om problemet; det finns många problem med exemplet; inklusive enkelhet och för många potentiella kollisioner. Utan regler för verkställighet handlar problemet inte om ingångsfönstrets storlek. Problemet är att hashingalgoritmen leder till för många kollisioner; 3 plus multiplar av 17 ( {3,20,37,54 ...} ) resulterar alla i 3.

Kollisionerna är det som är viktigt eftersom det är hashen som används för autentisering och verifiering; om brute force kan komma in i 20, 37 eller 54 ... och ändå komma åt kontot eller resursen, spelar det ursprungliga lösenordet ingen roll.

För att återgå till den ursprungliga frågan är det ofta så att allt som krävs är kollisionen. Faktum är att det här är ofta hur WiFi-intrång fungerar. Hashet hittas, vilket möjliggör anslutning till den lösenordsskyddade gatewayen.