Preimage attack
I kryptografi försöker en preimage-attack på kryptografiska hashfunktioner hitta ett meddelande som har ett specifikt hashvärde. En kryptografisk hashfunktion bör motstå attacker på dess preimage (uppsättning möjliga indata).
I angreppssammanhang finns det två typer av förbildsmotstånd:
- förbildsresistans : för i stort sett alla förspecificerade utgångar är det beräkningsmässigt omöjligt att hitta någon indata som hashar till den utmatningen; dvs givet y är det svårt att hitta ett x så att h ( x ) = y .
- andra förbildsresistans : för en specificerad ingång är det beräkningsmässigt omöjligt att hitta en annan ingång som producerar samma utdata; dvs givet x är det svårt att hitta en andra ingång x ′ ≠ x så att h ( x ) = h ( x ′) .
Dessa kan jämföras med ett kollisionsmotstånd , där det är beräkningsmässigt omöjligt att hitta två distinkta ingångar x , x ′ som hash till samma utgång; dvs så att h ( x ) = h ( x ′) .
Kollisionsmotstånd innebär andra förbildsmotstånd, men garanterar inte förbildsmotstånd. Omvänt innebär en andra förbildsattack en kollisionsattack (trivialt, eftersom x, förutom x ′ , redan är känt från början).
Tillämpade preimage-attacker
Per definition är en idealisk hashfunktion sådan att det snabbaste sättet att beräkna en första eller andra förbild är genom en brute-force attack . För en n -bitars hash har denna attack en tidskomplexitet 2 n , som anses vara för hög för en typisk utdatastorlek på n = 128 bitar. Om sådan komplexitet är den bästa som kan uppnås av en motståndare, anses hashfunktionen vara förbildsresistent. Det finns dock ett allmänt resultat att kvantdatorer utför en strukturerad förbildsattack i , vilket också innebär en andra förbild och därmed en kollisionsattack.
Snabbare preimage-attacker kan hittas genom att kryptera vissa hashfunktioner och är specifika för den funktionen. Vissa betydande preimage-attacker har redan upptäckts, men de är ännu inte praktiska. Om en praktisk förbildsattack upptäcks skulle det drastiskt påverka många Internetprotokoll. I det här fallet betyder "praktiskt" att det kan exekveras av en angripare med en rimlig mängd resurser. Till exempel är en förbildsattack som kostar biljoner dollar och som tar decennier att förbilda ett önskat hashvärde eller ett meddelande inte praktiskt; en som kostar några tusen dollar och tar några veckor kan vara väldigt praktisk.
Alla för närvarande kända praktiska eller nästan praktiska attacker på MD5 och SHA-1 är kollisionsattacker . [ citat behövs ] I allmänhet är en kollisionsattack lättare att montera än en förbildsattack, eftersom den inte är begränsad av något inställt värde (vilka som helst kan användas för att kollidera). Tidskomplexiteten för en brute-force-kollisionsattack, i motsats till preimage-attacken, är bara .
Begränsade attacker med preimage
Den beräkningsmässiga ogenomförbarheten av en första preimage-attack på en idealisk hashfunktion förutsätter att uppsättningen av möjliga hash-indata är för stor för en brute force-sökning. Men om ett givet hashvärde är känt för att ha producerats från en uppsättning indata som är relativt liten eller är beställd av sannolikhet på något sätt, kan en brute force-sökning vara effektiv. Praktiskt beror på ingångsuppsättningens storlek och hastigheten eller kostnaden för att beräkna hashfunktionen.
Ett vanligt exempel är användningen av hash för att lagra lösenordsvalideringsdata för autentisering. I stället för att lagra klartext av användarlösenord, lagrar ett åtkomstkontrollsystem en hash av lösenordet. När en användare begär åtkomst hashas lösenordet som de skickar in och jämförs med det lagrade värdet. Om den lagrade valideringsdatan blir stulen kommer tjuven bara att ha hash-värdena, inte lösenorden. Men de flesta användare väljer lösenord på förutsägbara sätt och många lösenord är tillräckligt korta för att alla möjliga kombinationer kan testas om snabba hash används, även om hashen är klassad som säker mot förbildsattacker. Särskilda hash som kallas nyckelhärledningsfunktioner har skapats för att bromsa sökningar. Se Lösenordsknäckning .
Se även
- Födelsedagsattack
- Kryptografisk hashfunktion
- Säkerhetssammanfattning av hashfunktion
- Regnbågsbord
- Slumpmässigt orakel
- RFC 4270 : Attacker mot kryptografiska hash i Internetprotokoll
- ^ a b c d Rogaway, P.; Shrimpton, T. (2004). "Grundläggande information om kryptografiska hash-funktioner: definitioner, konsekvenser och separationer för förbildsmotstånd, andra förbildsmotstånd och kollisionsmotstånd" ( PDF) . Snabb mjukvarukryptering . Föreläsningsanteckningar i datavetenskap. Springer-Verlag. 3017 : 371–388. doi : 10.1007/978-3-540-25937-4_24 . ISBN 978-3-540-22171-5 . Hämtad 17 november 2012 .
- ^ Daniel J. Bernstein (2010-11-12). "Kvantattacker mot Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD och Skein" (PDF ) . University of Illinois i Chicago . Hämtad 2020-03-29 .
-
^
Bruce Morton, Clayton Smith (2014-01-30). "Varför vi behöver flytta till SHA-2" . Certifikatmyndighetens säkerhetsråd .
{{ citera webben }}: CS1 underhåll: använder författarens parameter ( länk ) - ^ "MD5 och perspektiv" . 2009-01-01.
- ^ "Google Online Security Blog: Tillkännage den första SHA1-kollisionen" . Hämtad 2017-02-23 .
- ^ Goodin, Dan (2012-12-10). "25-GPU-kluster knäcker alla vanliga Windows-lösenord på <6 timmar" . Ars Technica . Hämtad 2020-11-23 .
