Vad är regnbågsbord och hur används de?

Rainbow Tabeller förväxlas ofta med en annan, enklare teknik som utnyttjar en beräkningstid torage avvägning i lösenordåterställning: hashtabeller.

Hashtabeller är konstruerade genom att hasa varje ord i en lösenordsordbok. Lösenord-hash-paren lagras i en tabell, sorterade efter hash-värde. För att använda en hash-tabell, ta bara hashen och utför en binär sökning i tabellen för att hitta det ursprungliga lösenordet, om det finns.

Rainbow Tabeller är mer komplexa. Att konstruera en regnbågstabell kräver två saker : en hashing-funktion och en reduceringsfunktion. Hash-funktionen för en viss uppsättning Rainbow-tabeller måste matcha det hashade lösenordet du vill återställa. Reduktionsfunktionen måste förvandla en hash till något som kan användas som lösenord. En enkel reduktionsfunktion är att Base64 koda hashen och trunka den sedan till ett visst antal tecken.

Regnbågstabeller är konstruerade av ”kedjor” med en viss längd: till exempel 100 000. För att konstruera kedjan väljer du ett slumpmässigt frövärde. Sedan tillämpa hash- och reduktionsfunktionerna på detta utsäde och dess utdata, och fortsätt itera 100 000 gånger. Endast utsädet och slutvärdet lagras. Upprepa processen för att skapa så många kedjor som önskas.

För att återställa en lösenord med Rainbow Tables, lösenordshashen genomgår ovanstående process för samma längd: i detta fall 100 000 men varje länk i kedjan bibehålls. Varje länk i kedjan jämförs med det slutliga värdet för varje kedja. Om det finns en matchning kan kedjan rekonstrueras, så att både utmatningen för varje hashfunktion och utmatningen för varje reduktionsfunktion behålls. Den rekonstruerade kedjan kommer att innehålla hash för lösenordet i fråga såväl som lösenordet som producerade det.

Styrkorna med en hash-tabell är att det är blixtsnabbt att återställa ett lösenord (binär sökning) och den person som bygger hash-tabellen kan välja vad som går in i den, till exempel de 10 000 bästa lösenorden. Svagheten jämfört med Rainbow Tables är att hash-tabeller måste lagra varje enskilt hash-lösenordspar.

Rainbow Tables har fördelen att den person som konstruerar dessa tabeller kan välja hur mycket lagring som krävs genom att välja antalet länkar i varje kedja. Ju fler länkar mellan fröet och det slutliga värdet, desto fler lösenord fångas in. En svaghet är att den som bygger kedjorna inte väljer lösenorden de fångar så att Rainbow Tables inte kan optimeras för vanliga lösenord. Återställning av lösenord innebär också att man beräknar långa kedjor av haschar, vilket gör återställning till en dyr operation. Ju längre kedjorna är, desto fler lösenord fångas in i dem, men mer tid krävs för att hitta ett lösenord inuti.

Hashtabeller är bra för vanliga lösenord, Rainbow Tables är bra för tuffa lösenord. Det bästa tillvägagångssättet skulle vara att återställa så många lösenord som möjligt med hjälp av hashtabeller och / eller konventionell sprickbildning med en ordlista över de bästa N-lösenorden. För de som finns kvar, använd Rainbow Tables.

Kommentarer

• Åh godhet, jag erkänner att jag är chockad – jag diskuterar och förklarar Rainbow tabeller alla tiden, och hela tiden verkar det som om jag har varit en av de ” vanligen förvirrade ”! Jag skulle helt +1000 gånger, jag lärde mig verkligen något nytt här (och jag trodde att jag visste svaret). Glad att jag trots allt ställde frågan … Tack!
• För att vara specifik (nu när du öppnade mina ögon gjorde jag lite mer forskning :)), skiljer sig Rainbow Tables från Hellman Hash Chains genom att använda flera olika reduktionsfunktioner. Mer komplicerat … men verkligen en vacker idé (Ah! Är det varför de ’ kallas ” Rainbow ” tabeller?)
• Jag håller med om att detta är en mycket bra förklaring. I mitt svar förklarade jag det enkelt och förklarade det också fel genom att vara för enkelt.Skönheten i Rainbow-borden är att de inte ’ lagrar alla hashvärden. Jag kommer att redigera min men också rösta på det här eftersom det definitivt är en bättre förklaring.
• Hmm … Men ju mer jag tänker på det, i verkliga system är Rainbow Tables inte så användbara som hashbord. Som du sa, för vanliga lösenord är hashtabeller mycket bättre (eftersom de är i storleksordning snabbare, och storlekskraven för en lösenordsordbok är naturligtvis mycket mindre än hela det möjliga utbudet av lösenord). Och vem ’ skojar vi? De flesta lösenord faller inom den kategorin, det är väldigt sällsynt (och kommer att vara under en tid) att du behöver ringa in RT.
• Tyvärr förlorade du mig här: ” För att återställa ett lösenord med Rainbow Tables genomgår lösenordet ovanstående process för samma längd. ” Hur kan lösenordet genomgå processen när det ’ är inte ens känt? Menade du lösenordshashen? Det finns också ’: ” Varje länk i kedjan jämförs med slutvärdet för varje kedja. ” Jag kan inte se en situation där en länk i kedjan skulle matcha det slutliga värdet i kedjan, eftersom länkvärdet kontinuerligt skulle hashas och minskas.

Det finns många bra förklaringar till vad regnbågsbord är, den här Hur Rainbow tabeller fungerar är särskilt bra. Även Wikipedia-artikeln har också en mycket bra förklaring. För lite mer djupgående läsning är det slutgiltiga papperet om ämnet Gör en snabbare kryptanalytisk tidsminnesavvägning .

En enkel förklaring till Rainbow Tables är att de använder sig av en tidsminnesavvägningsteknik. Betydelse istället för att ta ett mål-hash-värde och en ordlista med ord, då hasar varje ord och gör jämförelsen i farten (brute force-tillvägagångssätt med något som John ), istället hasar du alla värden i ordlistan i förväg (det kan ta mycket lång tid beroende på ordboksstorlek). Men när det är klart kan du jämföra så många hash som du vill mot de för hashade värdena i regnbågstabellerna, detta är betydligt snabbare än att beräkna hasharna igen.

Förklaringen jag skrev här tidigare i ett försök att vara kort var vilseledande, eftersom det inte förklarade användningen av minskningar som regnbågsbord använder. För en bättre förklaring tills jag skriver om den här biten, se @Crunge-svar .

Du kan antingen skapa regnbågstabellerna själv med en applikation som RainbowCrack eller så kan du ladda ner dem från källor som The Shmoo Group , Projektwebbplats för Free Rainbow Tables , Ophcrack -projekt och många andra platser beroende på vilken typ av hash du behöver tabeller för.

För att skydda mot en Rainbow Table-baserad attack är den mest effektiva metoden att bekämpa den att se till att varje hash i ett system saltas . Detta gör förgenererade regnbågsbord värdelösa och skulle innebära att en angripare måste skapa en anpassad uppsättning bord att använda mot de riktade hasharna, vilket bara skulle vara möjligt om de kände saltet.

Kommentarer

• Dessutom (överväg att redigera detta i), om du använder ett annat salt för varje lösenord, registrerar det okrypterat i databasen, sedan attackerade skulle behöva generera en anpassad uppsättning tabeller för varje hash, vilket skulle besegra föremålet för övningen – hela poängen med regnbågstabellen är att brute force hela lösenordsutrymmet och sedan få alla lösenord för en brute-force ansträngning; om du ’ bara får ett lösenord per regnbågstabell, kan du lika gärna tvinga hashen direkt.

Syfte och relevans

Rainbow-tabeller hjälper till att knäcka svåra lösenord, dvs. de som inte ens kan hittas i en stor ordlista. Lösenord lagrades historiskt som vanliga haschar i databaser, och det är vad regnbågstabeller är effektiva mot: skapa en enda regnbågstabell (långsam) och kör valfritt antal databaser fulla av haschar mot den (snabbt).

I dessa dagar använder fler och fler ordentliga algoritmer för lösenordslagring som Bcrypt, Scrypt eller Argon2. Se: Hur säkrar du [lagrar] lösenord? Dessa algoritmer är inte längre ”sårbar” för regnbågsbord: eftersom varje hash är unikt, även om lösenorden är lika, fungerar regnbågsbord inte längre.

Det är därför regnbågsbord är opopulära idag.Även om något modernt som Argon2 inte används, vet utvecklare numera vanligtvis att de åtminstone borde använda ett salt. Det räcker redan för att göra ett regnbågsbord värdelöst.

Hur de fungerar

Skapa en tabell

Föreställ dig att vi skapar ett regnbågstabell med bara två kedjor, vardera med längd 5. Regnbågstabellen är för den fiktiva hashfunktionen MD48, som matar ut 48 bitar (endast 12 hexadecimala tecken). När vi bygger kedjan ser vi detta:

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD 

Vi börjar med 0 eftersom det är den första kedjan (vi behöver bara lite värde till att börja med.) När vi hash detta med MD48 blir det till cfcd208495d5. Nu tillämpar vi en ”reducera” -funktion som i grund och botten formaterar denna hash till en lösenord och slutar med ”z”. När vi hash det igen får vi fbade9e36a3f, sedan minskar det igen och får renjaj820 Det finns några fler cykler och det slutliga resultatet är WLgOSj.

Samma för den andra kedjan. Vi börjar bara med ett annat värde och gör samma sak. Detta slutar med 0uUoAD.

Vår kompletta regnbågstabell är nu den här:

WLgOSj => 0 0uUoAD => 1 

Det är allt du behöver lagra.

Leta upp en hash

Låt oss säga att vi hittade en hash online, 7668b2810262. Låt oss knäcka den med vårt bord!

Looking for hash "7668b2810262", reduced to "aL". hashed=>reduced "aL" to ieioB hashed=>reduced "ieioB" to WLgOSj Found a match, "WLgOSj" is in our rainbow table: WLgOSj => 0 The chain starts with "0". Let"s walk that chain and look for the hash. hashed "0" to cfcd208495d5 hashed "z" to fbade9e36a3f hashed "renjaj820" to 7668b2810262 That hash matches! Found the password: renjaj820 

För att leka med det själv skapades ovanstående exempel med detta Python-skript: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Skalningsegenskaper

Kort sagt:

• Snabba sökningar betyder större tabeller, förutsatt att täckningen förblir densamma.
• Bättre täckning betyder antingen långsammare uppslag eller större tabeller.
• Mindre tabeller betyder antingen långsammare uppslag eller sämre täckning.

Följande avsnitt antar att tiden per hash + -minskning är 1 µs och inte tar hänsyn till kollisioner. Dessa är alla ballparknummer, menade som exempel och inte exakta värden.

Uppsökningstid

Om en hash + reduktionsoperation tar en mikrosekund, tar det cirka 3 timmar att generera en tabell med en miljon kedjor och 10 000 reduktioner per kedja:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 timmar.

Det tar i genomsnitt 10 millisekunder att söka i den tabellen. Detta beror på att vi vanligtvis måste gå igenom chain_length/2 minskningar innan vi hittar vilken kedja som innehåller hash. Vi kan till exempel behöva göra 3000 reduktioner på en hash innan vi hittar ett värde som finns i tabellen. Därefter måste vi göra om kedjan från början tills vi hittar matchande värde. Om vi bara behövde göra 3000 för att hitta det i vår tabell, måste vi göra 7000 minskningar från början för att komma till rätt punkt i kedjan. I grund och botten gör vi lika många operationer när vi tittar upp som när vi genererar en enda kedja. Sökningstiden är därför 10 000 gånger en mikrosekund, vilket är tio millisekunder (eller en centisekund, om du vill).

Lagringskrav

När du vill skapa en fullständig, snabb uppslagningstabell för en hashfunktion, till och med MD5, skulle du fortfarande behöva hundra miljarder terabyte lagring. Det ” s inte särskilt bra. Men vad händer om vi bara vill täcka små bokstäver till 10 tecken?

Om vi vill spendera högst 30 sekunder på att leta efter en hash, och förutsatt att vi behöver 1 mikrosekund (en miljon sekund) per hash + minska cykeln, då kan vi ha en kedjelängd på: 1 million × 30 = 30 miljoner. Det finns 26 ¹⁰ (eller 10 ¹⁴ ) möjliga gemena lösenord på 10 tecken, och per kedja täcker vi 30 miljoner värden. Det lämnar oss med 4 miljoner kedjor. Vi vet att varje kedja endast har ett start- och slutvärde lagrat och att värdena är tio tecken vardera. Så 2 × 10 × 4 million = 76 MiB-data.

Att generera tabellen genom att itera igenom alla 10-tecken lösenord tar lång tid: 30 sekunder per kedja, gånger 4 miljoner kedjor är cirka 91 år. Många människor skulle dock vara intresserade av en sådan tabell, så genom att slå samman 1092 processorer (= 91 × 12) tar det bara en månad. Detta visar hur liten en sådan tabell kan jämföras med lösenordsutrymmet som den täcker: uppslag tar bara 30 sekunder och du behöver bara lagra 76MiB-data.

Slutsats

Rainbow-tabeller kan vara betraktas som en tidsminnesavvägning : man lagrar bara en liten del av tabellen och återställer den genom lite extra beräkning vid uppslagstiden. Detta är en del av anledningen till att salter, eller snarare, en bra algoritm för lagring av lösenord som Scrypt eller Argon2 är viktiga för att hålla lösenorden säkra.En regnbågstabell kan bara återställa ett saltat lösenord om tabellen innehåller en post som är tillräckligt stor för att innehålla både saltet och lösenordet, vilket skulle vara extremt ineffektivt och besegra hela syftet.

Observera att en liknande sak gäller för kryptering: när människor krypterar filer med ett lösenord kan en regnbågstabell byggas för att knäcka filerna. Låt oss säga att programvaran använder AES, och det första blocket i filen ska dekrypteras till ”lösenordskorrigering” med användarens medföljande lösenord, då skulle en regnbågstabell använda AES istället för en hash-funktion.

När du hanterar ett lösenord (en hemlighet som har okänd styrka, och speciellt om användaren kan återanvända det), kör det alltid genom en korrekt (långsam) lösenordsalgoritm för att göra det långsamt och unikt att spricka. >

Kommentarer

• Bra förklaring. Om jag förstod det rätt, ligger kraften i regnbågsbord i att ha en bra reduceringsfunktion, eller hur? Hur kommer jag på en bra? Och hur undviker jag kollisioner för alla kandidater över kedjorna?
• @ Kyu96 Bra frågor! Jag vet inte ’ men jag skulle vara intresserad om du hittar en. Den här sidan handlar bara om den allmänna frågan om vad ett regnbågsbord är, inte detaljer som hur man utformar en algoritm. Du bör öppna en ny fråga , men den här webbplatsen handlar om ” som skyddar tillgångar från digitala hot ” (iirc ). Jag tror att det skulle vara ämnet för vår systersida, crypto.stackexchange.com , som handlar om ” matematik och egenskaper hos kryptografiska system, deras analys (” kryptanalys ”