Rainbowtables / Regnbågstabeller
================================
Introduktion
============
För att förstå vad en rainbowtable är måste man först förstå konceptet hash-algoritm, eller med ett annat namn; envägsalgoritm. Om du redan är bekant med den typen av algoritm, så kan du hoppa över följande sektion.
Hashalgoritmer (och envägsalgoritmer)
=====================================
Hashalgoritm är en typ av envägsalgoritm, vilket är precis vad namnet säger, en algoritm som bara fungerar åt ena hållet. Om mot förmodan begreppet algoritm är för dig främmande, så kan man förklara en algoritm såhär:
En uppsättning instruktioner om hur någonting ska behandlas.
Detta någonting har således ett tillstånd innan algoritmen, och ett sluttillstånd efter den. Man skulle kunna säga att ett matrecept är en enkel typ av algoritm som nog de flesta stött på. Det algoritmen behandlar är då råvaror, som i sitt ursprångstillstånd kanske är smör, socker, ägg var för sig. Algoritmen förklarar noga vad som ska göras, och resultatet är ett sluttillstånd.
En envägsalgoritm är en algoritm som utför sådana steg så att man omöjligt kan ta sluttillståndet, och göra algoritmen baklänges för att få tillbaka vad man började med. Hashalgoritm är som redan nämnt, en typ av envägsalgoritm. Den tar indata och producerar från den en utdata, vanligen kallad hash. Indatan kan oftast vara hur mycket somhelst, och utdatans storlek varierar. Några exempel:
MD2,MD4,MD5,SHA1, - 128 Bitar
SHA256 - 256 Bitar
SHA384 - 384 Bitar
SHA512 - 512 Bitar
RIPEMD160 - 160 Bitar
Tillämpningsområden för hashalgoritmer
======================================
Det finns olika tillämpningsområden för hashalgoritmer. Till exempel kan det användas som ett fingeravtryck för en fil. En hash räknas ut för hela filen och anges tillsammans med distribution av filen. Om någonting ändras i filen så avviker hashen oftast radikalt, vilket är en egenskap som bör förväntas hos en bra hashalgoritm. På detta sätt kan man verifiera filens integritet. Det vill säga, att den inte blivit skadad, eller ändrad av någon elak part.
Det tillämpningsområde som är av störst intresse för oss är hur det används för att lagra lösenord. För att en så känslig uppgift som ett lösenord inte lätt ska hamna i fel händer så sparas oftast lösenord inte i klartext hos servern där man gör en kontoregistrering. Om någon får tag på databasen, så kan de ändå inte köra hashen baklänges för att få användarens lösenord, vilket ger ökad säkerhet. När en kontoregistrering sker så skickas alltså lösenordet som indata till en hashalgoritm, och endast utdatan sparas. Vid varje inloggning som görs mot kontot så hashar servern det vid inloggningen angivna lösenordet, och jämför detta med det redan sparade värdet. Om de matchar varandra så var indatan ganska troligt samma som den gången då du registrerade dig. För en anledning till användandet av ordet 'troligt' se senare avsnitt angående teori.
Metoder för att knäcka hash
===========================
Det man dock kan göra för att ta reda vad för indata som skickades till hashfunktionen för att ge upphov till en viss hash kan man genomföra olika attacker. Metodiken är att man prövar olika tänkbara värden genom att skicka dessa värden genom en hashfunktion, och se om utdatan matchar det man söker. Vanliga tekniker för detta är Brute-Force och Dictionary Attack. En mer ovanlig teknik, är det som denna guide tar upp; Rainbowtable Cracking.
Vad är en Rainbow Table?
========================
Att köra en brute-force på nytt varje gång man stöter på en hash man vill knäcka är ganska tidskrävande. Förenklat så skulle man kunna säga att en rainbowtable innehåller varje kombination man prövar, tillsammans med vilken hash som producerades. Tack vare detta så behöver man vid varje brute-force inte räkna ut alla kombinationer och deras motsvarande hashvärde på nytt, utan man har endast ett program som gör en sökning i regnbågstabellen istället! Det man byter är utrymme för den enorma plats regnbågstabellerna tar upp, mot processortid. Man gör alltså alla uträkningar en gång, och sparar dom för all framtid så man inte behöver göra dom igen! På detta sätt kan tider som månader minskas till minuter, och år till halvtimmar. Precis som att man vid en brute-force väljer olika parametrar såsom charset (teckenuppsättning) och minsta längd samt maximal längd att pröva, så är också detta fallet med en regnbågstabell. Man genererar också tabellen för en, och endast en, typ av hashalgoritm.
Detta är den enkla versionen av det, rainbow-tekniken är lite mer avancerad än så. En rainbow table byggs upp av kedjor. En kedja har ett startvärde, och ett slutvärde. Startvärdet slumpas ur alla de olika tecken och teckenlängd man valt. Efter detta görs en typ av deterministisk iteration på värdet ett bestämt antal gånger, och efter allt detta sätts det sista värdet till slutet på kedjan. I tabellen sparas endast startvärdet, och slutvärdet, inget därimellan. En regnbågstabell består av flera stycken sådana här kedjor. Man bestämmer vid tabellgenereringen dessa parametrar; kedjelängd, samt antal kedjor.
Hur går det då till att söka i dessa? Jo, din hash som du vill hitta motsvarande klartext till itereras med samma funktion lika många gånger som tabellens längd på kedjor. Om du bland någon av dessa värden av iterationen hittar ett slut på en kedja vet du att klartexten till hashen finns i den kedjan, och du vet hur långt från slutet den var, alltså kan du göra om iterationerna från startvärdet, och där få klartexten. Även detta är en förenkling. Bland annat så används olika iterationsfunktioner för varje iteration, detta för att undvika att två kedjor vid ett tillfälle genererar samma värde, och på så sätt producerar samma data på nytt. Denna sökning gör såklart ett program för dig.
På grund av att startvärdena är slumpmässiga så är sannolikheten att önskad klartext går att hitta också slumpberoende. Därför anges ofta procentuella chanser för rainbowtables.
Hur skapar jag en Rainbow Table?
================================
Det finns olika program för att generera rainbowtables. Det mest vedertagna programmet för generering är nog 'rtgen' som ingår i Rainbowcrack-paketet, vilket återfinns här: http://www.antsight.com/zsl/rainbowcrack/.Detta är ett paket med rainbow-relaterade program gjort av Zhu Shuanglei. Sedan finns det ett mer användaranpassat program vid namn WinRtgen av gruppen oxid.it. Detta program är grafiskt och kombinerar funktionerna hos programmen 'rtgen' och 'rtsort'. WinRtgen finns på http://oxid.it.
WinRtgen med sitt grafiska gränssnitt är väldigt lätt att använda. Det svåra är egentligen vilka inställningar du skapar dina tabeller med. I programmet visas när du experimenterar med inställningar både procentuell chans för tabellen, samt storlek. En benchmark kan köras vilken avslöjar genereringstid för din(a) tabell(er).
Hur du ska ha inställningarna är svårt att säga, man kan pröva sig fram, eller använda sig av lite mer avancerade skript för att se utvecklingskurvor då olika inställningar för tabellen ändras och på så sätt göra sitt val. Enkel förklaring vad resultatet av förändringar hos parametrarna är kommer här:
Chain Length - Eftersom bara start och slutvärde sparas så påverkar inte längden, det vill säga hur många värden som ska räknas ut från kedjan, storleken på filen. Dock täcker den såklart mer och en ökad procentuell chans fås av ökad chain length. Dock ökar också genereringstiden och även tiden det tar att söka i en tabell. Detta för att vid sökning så måste lika många iterationer ske på hashvärdet du söker efter, som det gjordes för en enskild kedja. Samt så måste en sökning ske mot varje av dessa värden. Det gäller alltså att hitta en bra balans.
Chain Count - Anger hur många kedjor du vill ha i en tabell. Påverkar filstorleken samt den procentuella chansen då antalet kedjor du gör ökar, alltså större täckning av klartextområdet. Varje sparad kedja tar upp 16 byte. Filstorleken räknas alltså ut som: (Antalet Kedjor) x (16)
Antal tabeller - Man skapar oftast inte alls bara en tabellfil, utan flera stycken sådana. Detta ökar täckningen av klartextområdet. Dock fungerar det på grund av slumpmässigheten inte som så att en tabell med 40% chans och en till sådan tabell ger 80%. För att räkna ut procentuella chansen gör du följande uträkning:
Så två tabeller med 40% ger alltså:
Med tre tabeller hade det blivit: 78.4%
(Ökningen avtar alltså)
[MATTE]
Matematik för de intresserade. Derivatan för sannolikhetsfunktionen ger förändringen av den procentuella chansen då [a = procentuell chans för en tabell] och [n = antal tabeller]
Var hittar jag Rainbow Tables?
==============================
Det finns några ute på nätet. Hemsidor som bör kollas upp:
http://www.hashbreaker.com
http://www.freerainbowtables.com
http://rainbowtables.shmoo.com/
================================
Introduktion
============
För att förstå vad en rainbowtable är måste man först förstå konceptet hash-algoritm, eller med ett annat namn; envägsalgoritm. Om du redan är bekant med den typen av algoritm, så kan du hoppa över följande sektion.
Hashalgoritmer (och envägsalgoritmer)
=====================================
Hashalgoritm är en typ av envägsalgoritm, vilket är precis vad namnet säger, en algoritm som bara fungerar åt ena hållet. Om mot förmodan begreppet algoritm är för dig främmande, så kan man förklara en algoritm såhär:
En uppsättning instruktioner om hur någonting ska behandlas.
Detta någonting har således ett tillstånd innan algoritmen, och ett sluttillstånd efter den. Man skulle kunna säga att ett matrecept är en enkel typ av algoritm som nog de flesta stött på. Det algoritmen behandlar är då råvaror, som i sitt ursprångstillstånd kanske är smör, socker, ägg var för sig. Algoritmen förklarar noga vad som ska göras, och resultatet är ett sluttillstånd.
En envägsalgoritm är en algoritm som utför sådana steg så att man omöjligt kan ta sluttillståndet, och göra algoritmen baklänges för att få tillbaka vad man började med. Hashalgoritm är som redan nämnt, en typ av envägsalgoritm. Den tar indata och producerar från den en utdata, vanligen kallad hash. Indatan kan oftast vara hur mycket somhelst, och utdatans storlek varierar. Några exempel:
MD2,MD4,MD5,SHA1, - 128 Bitar
SHA256 - 256 Bitar
SHA384 - 384 Bitar
SHA512 - 512 Bitar
RIPEMD160 - 160 Bitar
Tillämpningsområden för hashalgoritmer
======================================
Det finns olika tillämpningsområden för hashalgoritmer. Till exempel kan det användas som ett fingeravtryck för en fil. En hash räknas ut för hela filen och anges tillsammans med distribution av filen. Om någonting ändras i filen så avviker hashen oftast radikalt, vilket är en egenskap som bör förväntas hos en bra hashalgoritm. På detta sätt kan man verifiera filens integritet. Det vill säga, att den inte blivit skadad, eller ändrad av någon elak part.
Det tillämpningsområde som är av störst intresse för oss är hur det används för att lagra lösenord. För att en så känslig uppgift som ett lösenord inte lätt ska hamna i fel händer så sparas oftast lösenord inte i klartext hos servern där man gör en kontoregistrering. Om någon får tag på databasen, så kan de ändå inte köra hashen baklänges för att få användarens lösenord, vilket ger ökad säkerhet. När en kontoregistrering sker så skickas alltså lösenordet som indata till en hashalgoritm, och endast utdatan sparas. Vid varje inloggning som görs mot kontot så hashar servern det vid inloggningen angivna lösenordet, och jämför detta med det redan sparade värdet. Om de matchar varandra så var indatan ganska troligt samma som den gången då du registrerade dig. För en anledning till användandet av ordet 'troligt' se senare avsnitt angående teori.
Metoder för att knäcka hash
===========================
Det man dock kan göra för att ta reda vad för indata som skickades till hashfunktionen för att ge upphov till en viss hash kan man genomföra olika attacker. Metodiken är att man prövar olika tänkbara värden genom att skicka dessa värden genom en hashfunktion, och se om utdatan matchar det man söker. Vanliga tekniker för detta är Brute-Force och Dictionary Attack. En mer ovanlig teknik, är det som denna guide tar upp; Rainbowtable Cracking.
Vad är en Rainbow Table?
========================
Att köra en brute-force på nytt varje gång man stöter på en hash man vill knäcka är ganska tidskrävande. Förenklat så skulle man kunna säga att en rainbowtable innehåller varje kombination man prövar, tillsammans med vilken hash som producerades. Tack vare detta så behöver man vid varje brute-force inte räkna ut alla kombinationer och deras motsvarande hashvärde på nytt, utan man har endast ett program som gör en sökning i regnbågstabellen istället! Det man byter är utrymme för den enorma plats regnbågstabellerna tar upp, mot processortid. Man gör alltså alla uträkningar en gång, och sparar dom för all framtid så man inte behöver göra dom igen! På detta sätt kan tider som månader minskas till minuter, och år till halvtimmar. Precis som att man vid en brute-force väljer olika parametrar såsom charset (teckenuppsättning) och minsta längd samt maximal längd att pröva, så är också detta fallet med en regnbågstabell. Man genererar också tabellen för en, och endast en, typ av hashalgoritm.
Detta är den enkla versionen av det, rainbow-tekniken är lite mer avancerad än så. En rainbow table byggs upp av kedjor. En kedja har ett startvärde, och ett slutvärde. Startvärdet slumpas ur alla de olika tecken och teckenlängd man valt. Efter detta görs en typ av deterministisk iteration på värdet ett bestämt antal gånger, och efter allt detta sätts det sista värdet till slutet på kedjan. I tabellen sparas endast startvärdet, och slutvärdet, inget därimellan. En regnbågstabell består av flera stycken sådana här kedjor. Man bestämmer vid tabellgenereringen dessa parametrar; kedjelängd, samt antal kedjor.
Hur går det då till att söka i dessa? Jo, din hash som du vill hitta motsvarande klartext till itereras med samma funktion lika många gånger som tabellens längd på kedjor. Om du bland någon av dessa värden av iterationen hittar ett slut på en kedja vet du att klartexten till hashen finns i den kedjan, och du vet hur långt från slutet den var, alltså kan du göra om iterationerna från startvärdet, och där få klartexten. Även detta är en förenkling. Bland annat så används olika iterationsfunktioner för varje iteration, detta för att undvika att två kedjor vid ett tillfälle genererar samma värde, och på så sätt producerar samma data på nytt. Denna sökning gör såklart ett program för dig.
På grund av att startvärdena är slumpmässiga så är sannolikheten att önskad klartext går att hitta också slumpberoende. Därför anges ofta procentuella chanser för rainbowtables.
Hur skapar jag en Rainbow Table?
================================
Det finns olika program för att generera rainbowtables. Det mest vedertagna programmet för generering är nog 'rtgen' som ingår i Rainbowcrack-paketet, vilket återfinns här: http://www.antsight.com/zsl/rainbowcrack/.Detta är ett paket med rainbow-relaterade program gjort av Zhu Shuanglei. Sedan finns det ett mer användaranpassat program vid namn WinRtgen av gruppen oxid.it. Detta program är grafiskt och kombinerar funktionerna hos programmen 'rtgen' och 'rtsort'. WinRtgen finns på http://oxid.it.
WinRtgen med sitt grafiska gränssnitt är väldigt lätt att använda. Det svåra är egentligen vilka inställningar du skapar dina tabeller med. I programmet visas när du experimenterar med inställningar både procentuell chans för tabellen, samt storlek. En benchmark kan köras vilken avslöjar genereringstid för din(a) tabell(er).
Hur du ska ha inställningarna är svårt att säga, man kan pröva sig fram, eller använda sig av lite mer avancerade skript för att se utvecklingskurvor då olika inställningar för tabellen ändras och på så sätt göra sitt val. Enkel förklaring vad resultatet av förändringar hos parametrarna är kommer här:
Chain Length - Eftersom bara start och slutvärde sparas så påverkar inte längden, det vill säga hur många värden som ska räknas ut från kedjan, storleken på filen. Dock täcker den såklart mer och en ökad procentuell chans fås av ökad chain length. Dock ökar också genereringstiden och även tiden det tar att söka i en tabell. Detta för att vid sökning så måste lika många iterationer ske på hashvärdet du söker efter, som det gjordes för en enskild kedja. Samt så måste en sökning ske mot varje av dessa värden. Det gäller alltså att hitta en bra balans.
Chain Count - Anger hur många kedjor du vill ha i en tabell. Påverkar filstorleken samt den procentuella chansen då antalet kedjor du gör ökar, alltså större täckning av klartextområdet. Varje sparad kedja tar upp 16 byte. Filstorleken räknas alltså ut som: (Antalet Kedjor) x (16)
Antal tabeller - Man skapar oftast inte alls bara en tabellfil, utan flera stycken sådana. Detta ökar täckningen av klartextområdet. Dock fungerar det på grund av slumpmässigheten inte som så att en tabell med 40% chans och en till sådan tabell ger 80%. För att räkna ut procentuella chansen gör du följande uträkning:
Kod:
1 - (1 - chansförentabell)^(antal tabeller)
Så två tabeller med 40% ger alltså:
Kod:
1 - (1 - 0.4)^2 1 - (0.6)^2 = 1 - 0.6 * 0.6 = 1 - 0,36 = 0.64 = 64%
Med tre tabeller hade det blivit: 78.4%
(Ökningen avtar alltså)
[MATTE]
Matematik för de intresserade. Derivatan för sannolikhetsfunktionen ger förändringen av den procentuella chansen då [a = procentuell chans för en tabell] och [n = antal tabeller]
Kod:
[/MATTE]f(n) = 1 - a^n f'(n) = -n * a^n * ln a
Var hittar jag Rainbow Tables?
==============================
Det finns några ute på nätet. Hemsidor som bör kollas upp:
http://www.hashbreaker.com
http://www.freerainbowtables.com
http://rainbowtables.shmoo.com/
