Hvad er regnbue borde, og hvordan bruges de?

Rainbow tabeller forveksles ofte med en anden, enklere teknik, der udnytter en beregningstid torage afvejning i adgangskodegendannelse: hash-tabeller.

Hash-tabeller er konstrueret ved at haske hvert ord i en adgangskodebog. Parret med adgangskode-hash er gemt i en tabel sorteret efter hash-værdi. For at bruge en hash-tabel skal du blot tage hashen og udføre en binær søgning i tabellen for at finde den originale adgangskode, hvis den er til stede.

Rainbow-tabeller er mere komplekse. At konstruere en regnbue-tabel kræver to ting : en hashing-funktion og en reduktionsfunktion. Den hashing-funktion for et givet sæt Rainbow-tabeller skal matche den hashede adgangskode, du vil gendanne. Reduktionsfunktionen skal omdanne en hash til noget, der kan bruges som en adgangskode. En simpel reduktionsfunktion er til Base64 kod hashen, og trunker den derefter til et bestemt antal tegn.

Regnbue-tabeller er konstrueret af “kæder” med en bestemt længde: f.eks. 100.000. For at konstruere kæden skal du vælge en tilfældig frøværdi. Derefter anvend hash- og reduktionsfunktionerne på dette frø og dets output, og fortsæt med at gentage 100.000 gange. Kun frøet og den endelige værdi er gemt. Gentag denne proces for at oprette så mange kæder som ønsket.

For at gendanne en adgangskode ved hjælp af Rainbow Tables, password hash gennemgår ovenstående proces i samme længde: i dette tilfælde 100.000, men hvert led i kæden bevares. Hvert led i kæden sammenlignes med den endelige værdi af hver kæde. Hvis der er en match, kan kæden rekonstrueres, så både output for hver hashing-funktion og output for hver reduktionsfunktion bevares. Den rekonstruerede kæde vil indeholde hash af den pågældende adgangskode såvel som den adgangskode, der producerede den.

Styrkerne ved en hash-tabel er, at det er lynhurtigt at gendanne en adgangskode (binær søgning) og den person, der bygger hash-tabellen kan vælge, hvad der kommer ind i den, f.eks. de 10.000 bedste adgangskoder. Svagheden sammenlignet med Rainbow Tables er, at hash-tabeller skal gemme hvert enkelt hash-password-par.

Rainbow Tables har fordelen, at den person, der konstruerer disse tabeller, kan vælge, hvor meget lager der kræves ved at vælge antallet af links i hver kæde. Jo flere forbindelser mellem frøet og den endelige værdi, jo flere adgangskoder fanges. En svaghed er, at den person, der bygger kæderne, ikke vælger de adgangskoder, de fanger, så Rainbow Tables ikke kan optimeres til almindelige adgangskoder. Gendannelse af adgangskode involverer også beregning af lange hashkæder, hvilket gør gendannelse til en dyr operation. Jo længere kæderne er, jo flere adgangskoder fanges der i dem, men der kræves mere tid til at finde en adgangskode indeni.

Hash-tabeller er gode til almindelige adgangskoder, Rainbow-tabeller er gode til hårde adgangskoder. Den bedste metode ville være at gendanne så mange adgangskoder som muligt ved hjælp af hash-tabeller og / eller konventionel krakning med en ordbog over de øverste N-adgangskoder. Brug de Rainbow Tables til dem, der er tilbage.

Kommentarer

• Åh godhed, jeg indrømmer at være chokeret – Jeg diskuterer og forklarer Rainbow-tabeller alle tid, og hele denne tid ser det ud til, at jeg har været en af ” almindeligt forvirrede “! Jeg ville helt +1000 gange, jeg lærte virkelig noget nyt her (og jeg troede, jeg vidste svaret). Glad for, at jeg trods alt stillede spørgsmålet … Tak!
• Selvom det er specifikt (nu du åbnede mine øjne, gjorde jeg mere research :)), er Rainbow Tables adskilt fra Hellman Hash Chains ved at bruge flere forskellige reduktionsfunktioner. Mere kompleks … men virkelig en smuk idé (Ah! Er det hvorfor de ‘ kaldes ” Rainbow ” tabeller?)
• Jeg er enig i, at dette er en meget god forklaring. I mit svar forklarede jeg det enkelt og forklarede det også forkert ved at være for simpelt.Det smukke ved Rainbow-borde er, at de ikke ‘ ikke gemmer enhver hash-værdi. Jeg vil redigere mine, men også stemme op, da det bestemt er en bedre forklaring.
• Hmm … Selvom jo mere jeg tænker på det, er Rainbow Tables i de virkelige systemer ikke nær så nyttige som hash-tabeller. Som du sagde, er hash-tabeller for almindelige adgangskoder meget bedre (da de er i størrelsesorden hurtigere, og størrelseskravene til en adgangskodebog er selvfølgelig meget mindre end hele det mulige udvalg af adgangskoder). Og hvem tæller vi med ‘? De fleste adgangskoder falder ind under den kategori, det er meget sjældent (og vil vare i nogen tid), at du skal ringe til RT.
• Desværre mistede du mig her: ” For at gendanne en adgangskode ved hjælp af Rainbow Tables gennemgår adgangskoden ovenstående proces i samme længde. ” Hvordan kan adgangskoden gennemgå processen, når den ‘ er ikke engang kendt? Mente du adgangskode hash? Der er også ‘ dette: ” Hvert led i kæden sammenlignes med den endelige værdi for hver kæde. ” Jeg kan ikke se en situation, hvor et link i kæden vil matche den endelige værdi i kæden, da linkværdien kontinuerligt vil blive hashet og reduceret.

Der er mange gode forklaringer på, hvad regnbueborde er, denne Sådan fungerer Rainbow Tables er særlig god. Også Wikipedia-artiklen har også en meget god forklaring. For en lidt mere dybdegående læsning er det endelige papir om emnet Gør en hurtigere kryptanalytisk time-memory afvejning .

En simpel forklaring på Rainbow Tables er, at de gør brug af en time memory trade-off-teknik. Betydning i stedet for at tage en mål-hash-værdi og en ordbog med ord, så hash hvert ord og foretager sammenligningen i farten (brute force-tilgang ved hjælp af noget som John ), du hash i stedet alle værdierne i ordbogen på forhånd (dette kan tage meget lang tid afhængigt af ordbogens størrelse). Men når det er gjort, kan du sammenligne så mange hashes, som du vil, med de forud hashede værdier i regnbuetabellerne, dette er betydeligt hurtigere end at beregne hashes igen.

Forklaringen, jeg skrev her tidligere i et forsøg på at være kort var vildledende, da det ikke forklarede brugen af reduktioner, som regnbueborde bruger. For en bedre forklaring, indtil jeg omskriver denne bit, se @Crunge svar .

Du kan enten generere regnbuetabellerne selv ved hjælp af et program som RainbowCrack eller du kan downloade dem fra kilder som The Shmoo Group , Gratis Rainbow Tables -projektwebsite, Ophcrack -projekt og mange andre steder, afhængigt af hvilken type hashes du har brug for tabeller til.

For at beskytte mod et Rainbow Table-angreb er den mest effektive metode til bekæmpelse af det at sikre, at hver hash i et system er saltet . Dette gør prægenererede regnbueborde ubrugelige og vil betyde, at en angriber bliver nødt til at generere et brugerdefineret sæt tabeller, der skal bruges mod de målrettede hashes, hvilket kun ville være muligt, hvis de kendte saltet.

Kommentarer

• Desuden (overvej at redigere dette i), hvis du bruger et andet salt til hver adgangskode og registrerer det ukrypteret i databasen, så angrebet skulle generere et brugerdefineret sæt tabeller til hver hash, som ville besejre opgavens genstand – hele pointen med regnbuetabellen er at tvinge hele adgangskodens plads og derefter få alle adgangskoderne til en brute-force indsats; hvis du ‘ kun får en adgangskode pr. regnbuetabel, kan du lige så godt direkte tvinge hashen.

Formål og relevans

Regnbuetabeller hjælper med at knække vanskelige adgangskoder, dvs. dem, der ikke engang findes i en stor ordbog. Adgangskoder blev historisk gemt som almindelige hashes i databaser, og det er, hvad regnbue-tabeller er effektive imod: Opret et enkelt regnbue-bord (langsomt) og kør et vilkårligt antal databaser fuld af hashes mod det (hurtigt).

I disse dage bruger flere og flere systemer de korrekte algoritmer til adgangskodelagring som Bcrypt, Scrypt eller Argon2. Se: Hvordan man [gemmer] adgangskoder sikkert? Disse algoritmer er ikke længere “sårbar” overfor regnbue-tabeller: Da hver hash er unik, selvom adgangskoderne er ens, fungerer regnbue-tabeller ikke længere.

Derfor er regnbue-tabeller upopulære i dag.Selvom noget moderne som Argon2 ikke bruges, ved udviklere i dag normalt, at de i det mindste skal bruge et salt. Det er allerede nok til at gøre et regnbue bord ubrugeligt.

Sådan fungerer de

Oprettelse af en tabel

Forestil dig, at vi opretter et regnbue-bord med kun to kæder, hver med længde 5. Regnbue-bordet er til den fiktive hash-funktion MD48, der output 48 bit (kun 12 hexadecimale tegn). Når vi bygger kæden, ser vi dette:

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 starter med 0 fordi det er den første kæde (vi har bare brug for en værdi til at begynde med). Når vi hash dette med MD48, bliver det til cfcd208495d5. Nu anvender vi en “reducer” -funktion, der grundlæggende formaterer denne hash tilbage til en kodeord, og vi ender med “z”. Når vi hash det igen, får vi fbade9e36a3f, reducerer det igen og får renjaj820 Der er nogle flere cyklusser, og det endelige resultat er WLgOSj.

Samme for den anden kæde. Vi starter bare med en anden værdi og gør det samme. Dette slutter med 0uUoAD.

Vores komplette regnbuetabel er nu dette:

WLgOSj => 0 0uUoAD => 1 

Det er alt hvad du skal gemme.

Slå et hash

Lad os sige, at vi fandt en hash online, 7668b2810262. Lad os knække den ved hjælp af vores 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 

For at lege med det selv blev ovenstående eksempler oprettet ved hjælp af dette Python-script: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Skaleringsegenskaber

Kort sagt:

• Hurtige opslag betyder større tabeller, forudsat at dækningen forbliver den samme.
• Bedre dækning betyder enten langsommere opslag eller større tabeller.
• Mindre tabeller betyder enten langsommere opslag eller dårligere dækning.

De følgende afsnit antager, at tiden pr. Hash + -reduktion er 1 µs og ikke redegør for kollisioner. Disse er alle ballpark-numre, menes som eksempler og ikke nøjagtige værdier.

Opslagstid

Hvis en hash + reduktionsoperation tager en mikrosekund, ville det tage cirka 3 timer at generere en tabel med en million kæder og 10.000 reduktioner pr. kæde:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 timer.

Det tager i gennemsnit 10 millisekunder at foretage et opslag i tabellen. Dette skyldes, at vi typisk bliver nødt til at gennemgå chain_length/2 -reduktioner, før vi finder ud af, hvilken kæde der indeholder hashen. For eksempel skal vi muligvis foretage 3000 reduktioner på en hash, før vi finder en værdi, der er i tabellen. Dernæst er vi nødt til at gøre denne kæde igen fra starten, indtil vi finder den matchende værdi. Hvis vi bare skulle gøre 3000 for at finde det i vores tabel, så skal vi lave 7000 reduktioner fra starten for at komme til det rigtige punkt i kæden. Dybest set udfører vi lige så mange operationer, når vi ser op, som når vi genererer en enkelt kæde. Derfor er opslagstiden 10.000 gange en mikrosekund, hvilket er ti millisekunder (eller en centisekund, hvis du vil).

Opbevaringskrav

Når du vil lave en fuld, hurtig opslagstabel for en hash-funktion, endda MD5, har du stadig brug for hundrede milliarder milliarder terabyte lager. Det ” s ikke meget nyttigt. Men hvad hvis vi kun vil dække adgangskoder med små bogstaver indtil 10 tegn?

Hvis vi maksimalt vil bruge 30 sekunder på at lede efter en hash, og forudsat at vi har brug for 1 mikrosekund (en milliontedel af et sekund) pr. Hash + reducer cyklus, så kan vi have en kædelængde på: 1 million × 30 = 30 millioner. Der er 26 ¹⁰ (eller 10 ¹⁴ ) mulige små adgangskoder på 10 tegn, og pr. Kæde dækker vi 30 millioner værdier. Det efterlader os med 4 millioner kæder. Vi ved, at hver kæde kun har en start- og slutværdi gemt, og at værdierne er 10 tegn hver. Så 2 × 10 × 4 million = 76 MiB-data.

At generere tabellen ved at gentage gennem alle 10-tegns adgangskoder tager lang tid: 30 sekunder pr. Kæde, gange 4 millioner kæder er omkring 91 år. Mange mennesker ville dog være interesserede i en sådan tabel, så ved at samle 1092 CPUer (= 91 × 12) tager det kun 1 måned. Dette viser, hvor lille en sådan tabel kan sammenlignes med den adgangskodeplads, den dækker: opslag tager kun 30 sekunder, og du skal kun gemme 76MiB-data.

Konklusion

Rainbow-tabeller kan være betragtes som en time-memory trade-off : man gemmer kun en lille del af tabellen og genopretter den gennem nogle ekstra beregninger ved opslagstid. Dette er en del af grunden til, at salte eller rettere en god adgangskodelagringsalgoritme som Scrypt eller Argon2 er vigtig for at holde adgangskoder sikre.En regnbue-tabel kan kun gendanne et saltet kodeord, hvis tabellen indeholder en post, der er stor nok til at indeholde både salt og adgangskode, hvilket ville være ekstremt ineffektivt og besejrer hele formålet.

Bemærk, at en lignende ting gælder for kryptering: Når folk krypterer filer med en adgangskode, kan der bygges en regnbue-tabel til at knække filerne. Lad os sige, at softwaren bruger AES, og den første blok i filen skal dekrypteres til “passwordcorrect” ved hjælp af brugerens medfølgende adgangskode, så bruger en regnbue-tabel AES i stedet for en hash-funktion.

Når du håndterer en adgangskode (en hemmelighed, der har ukendt styrke, og især hvis brugeren muligvis genbruger den), skal du altid køre den gennem en korrekt (langsom) algoritme til adgangskodelagring for at gøre den langsom og unik at knække.

Kommentarer

• God forklaring. Hvis jeg forstod det korrekt, ligger kraften i regnbueborde i at have en god reduceringsfunktion, ikke? Hvordan finder jeg frem til en god? Og hvordan undgår jeg kollisioner for alle kandidater på tværs af kæderne?
• @ Kyu96 Gode spørgsmål! Jeg ved ikke ‘ svaret, men jeg ville være interesseret, hvis du finder et. Denne side handler kun om det generelle spørgsmål om, hvad et regnbuebord er, ikke detaljer som hvordan man designer en algoritme. Du skal åbne et nyt spørgsmål , men dette websted handler om ” beskytter aktiver mod digitale trusler ” (iirc ). Jeg tror, det ville være et emne for vores søsterside crypto.stackexchange.com , som handler om ” matematik og egenskaber ved kryptografiske systemer, deres analyse (” kryptanalyse “) og underordnede emner, der generelt udgør kryptologi, såsom tilfældigt tal generation. ”