Hva er regnbuebord og hvordan brukes de?

Rainbow Tabeller forveksles ofte med en annen, enklere teknikk som utnytter en beregningstid torage avveining i passordgjenoppretting: hash-tabeller.

Hash-tabeller er konstruert ved å haske hvert ord i en passordordbok. Passord-hash-parene er lagret i en tabell, sortert etter hash-verdi. For å bruke en hash-tabell, ta bare hashen og utfør et binært søk i tabellen for å finne det opprinnelige passordet, hvis det er tilstede.

Rainbow Tabeller er mer komplekse. Å lage en regnbuetabell krever to ting : en hashing-funksjon og en reduksjonsfunksjon. Hash-funksjonen for et gitt sett med Rainbow Tables må samsvare med det hashede passordet du vil gjenopprette. Reduksjonsfunksjonen må transformere en hash til noe som kan brukes som passord. En enkel reduksjonsfunksjon er til Base64 kod hasjen, og avkort den til et visst antall tegn.

Regnbuetabeller er konstruert av «kjeder» med en viss lengde: 100.000 for eksempel. For å konstruere kjeden, velg en tilfeldig frøverdi. Deretter bruk hashing- og reduksjonsfunksjonene på dette frøet, og dets utgang, og fortsett å itere 100.000 ganger. Bare frøet og den endelige verdien lagres. Gjenta denne prosessen for å lage så mange kjeder som ønsket.

For å gjenopprette en passord ved hjelp av Rainbow Tables, passordhashen gjennomgår prosessen ovenfor for samme lengde: i dette tilfellet 100.000, men hvert ledd i kjeden beholdes. Hvert ledd i kjeden sammenlignes med den endelige verdien av hver kjede. Hvis det er samsvar, kan kjeden rekonstrueres, slik at både utdata fra hver hashingfunksjon og utdata fra hver reduksjonsfunksjon holdes. Den rekonstruerte kjeden vil inneholde hash av passordet det er snakk om, samt passordet som produserte det.

Styrken til en hash-tabell er at å gjenopprette et passord er lynrask (binært søk) og den som bygger hash-tabellen kan velge hva som går inn i den, for eksempel de 10.000 beste passordene. Svakheten i forhold til Rainbow Tables er at hash-tabeller må lagre hvert enkelt hash-passordpar.

Rainbow Tables har fordelen den som konstruerer disse tabellene, kan velge hvor mye lagring som kreves ved å velge antall lenker i hver kjede. Jo flere koblinger mellom frøet og den endelige verdien, jo flere passord blir fanget. En svakhet er at personen som bygger kjedene ikke velger passordene de fanger, slik at Rainbow Tables ikke kan optimaliseres for vanlige passord. Passordgjenoppretting innebærer også å beregne lange kjeder av hashes, noe som gjør gjenoppretting til en dyr operasjon. Jo lenger kjedene er, jo flere passord blir fanget i dem, men det kreves mer tid til å finne et passord inni.

Hash-tabeller er bra for vanlige passord, Rainbow Tables er bra for tøffe passord. Den beste tilnærmingen vil være å gjenopprette så mange passord som mulig ved hjelp av hashtabeller og / eller konvensjonell sprekker med en ordbok med de største N-passordene. For de som er igjen, bruk Rainbow Tables.

Kommentarer

• Herregud, jeg innrømmer at jeg er sjokkert – jeg diskuterer og forklarer Rainbow-tabeller alle tiden, og hele denne tiden ser det ut til at jeg har vært en av » ofte forvirret «! Jeg ville helt 1000 ganger, jeg lærte virkelig noe nytt her (og jeg trodde jeg visste svaret). Glad jeg tross alt stilte spørsmålet … Takk!
• Skjønt å være spesifikk (nå som du åpnet øynene mine, gjorde jeg litt mer research :)), er Rainbow Tables differensiert fra Hellman Hash Chains ved å bruke flere forskjellige reduksjonsfunksjoner. Mer komplisert … men egentlig en vakker idé (Ah! Er det hvorfor de ‘ kalles » Rainbow » tabeller?)
• Jeg er enig i at dette er en veldig god forklaring. I svaret mitt forklarte jeg det enkelt og forklarte det også galt ved å være for enkelt.Det fine med Rainbow-bord er at de ikke ‘ lagrer hver hash-verdi. Jeg skal redigere min, men også stemme dette, da det definitivt er en bedre forklaring.
• Hmm … Selv om jeg mer tenker på det, i virkelige systemer er Rainbow Tables ikke i nærheten like nyttige som hasjbord. Som du sa, for vanlige passord er hash-tabeller mye bedre (siden de er raskere enn størrelsen, og størrelseskravene for en passordordbok er selvfølgelig mye mindre enn hele det mulige passordområdet). Og hvem ‘ tuller vi? De fleste passord faller inn i den kategorien. Det er veldig sjelden (og vil være det en stund) at du trenger å ringe inn RT.
• Dessverre mistet du meg her: » For å gjenopprette et passord ved hjelp av Rainbow Tables, gjennomgår passordet prosessen ovenfor i samme lengde. » Hvordan kan passordet gjennomgå prosessen når det ‘ er ikke engang kjent? Mente du passord hash? Det er også ‘ dette: » Hver lenke i kjeden sammenlignes med den endelige verdien av hver kjede. » Jeg kan ikke se en situasjon der en lenke i kjeden vil matche den endelige verdien i kjeden, siden lenkeverdien vil bli hash og redusert kontinuerlig.

Det er mange gode forklaringer på hva regnbuetabeller er, denne Hvordan Rainbow Tables fungerer er spesielt bra. Også Wikipedia-artikkelen har også en veldig god forklaring. For litt mer inngående lesing er det definitive papiret om emnet Making a Raster Cryptanalytic Time-Memory Trade-Off .

En enkel forklaring på Rainbow Tables er at de bruker en tidsminneutvekslingsteknikk. Betydning i stedet for å ta en mål-hash-verdi og en ordliste med ord, så hash hvert ord og gjør sammenligningen på farten (brute force-tilnærming ved å bruke noe sånt som John ), du hash i stedet alle verdiene i ordboken på forhånd (dette kan ta veldig lang tid, avhengig av ordbokens størrelse). Men når det er gjort, kan du sammenligne så mange hashes du vil mot de forhåndshashede verdiene i regnbuetabellene, dette er betydelig raskere enn å beregne hasjene igjen.

Forklaringen jeg skrev her tidligere i et forsøk på å være kort var misvisende, siden det ikke forklarte bruken av reduksjoner som regnbuebord bruker. For en bedre forklaring til jeg omskriver denne biten, se @Crunge svar .

Du kan enten lage regnbuetabellene selv ved hjelp av et program som RainbowCrack eller du kan laste dem ned fra kilder som The Shmoo Group , Free Rainbow Tables prosjektnettsted, Ophcrack -prosjekt og mange andre steder, avhengig av hvilken type hashes du trenger tabeller til.

For å beskytte mot et Rainbow Table-basert angrep, er den mest effektive metoden for å bekjempe det å sikre at hver hash i et system er saltet . Dette gjør forhåndsgenererte regnbuebord ubrukelige, og vil bety at en angriper må generere et tilpasset sett med bord som skal brukes mot de målrettede hasjene, noe som bare ville være mulig hvis de kjente saltet.

Kommentarer

• Videre (vurder å redigere dette i), hvis du bruker et annet salt for hvert passord, registrerer det ukryptert i databasen, så angrepet trenger å generere et tilpasset sett med tabeller for hver hash, som vil beseire gjenstanden for øvelsen – hele poenget med regnbuetabellen er å tvinge hele passordområdet og deretter få alle passordene for en brute-force innsats; hvis du ‘ bare får ett passord per regnbuetabell, så kan du like godt direkte tvinge hasjen.

Formål og relevans

Regnbuetabeller hjelper til med å knekke vanskelige passord, dvs. de som ikke engang finnes i en stor ordbok. Passord ble historisk lagret som vanlige hashes i databaser, og det er hva regnbuetabeller er effektive mot: lag et enkelt regnbuetabell (sakte) og kjør et hvilket som helst antall databaser fulle av hasjer mot det (raskt).

I disse dager bruker flere og flere ordentlige algoritmer for lagring av passord som Bcrypt, Scrypt eller Argon2. Se: Hvordan kan du [lagre] passord på en sikker måte? Disse algoritmene er ikke lenger «sårbar» for regnbuetabeller: siden hver hasj er unik, selv om passordene er like, fungerer ikke regnbuetabeller lenger.

Derfor er regnbuetabeller upopulære i dag.Selv om noe moderne som Argon2 ikke brukes, vet utviklere i dag vanligvis at de i det minste burde bruke et salt. Det er allerede nok til å gjøre et regnbuetabell ubrukelig.

Slik fungerer de

Opprette en tabell

Tenk deg at vi lager et regnbuebord med bare to kjeder, hver med lengde 5. Regnbuetabellen er for den fiktive hashfunksjonen MD48, som gir ut 48 bits (bare 12 heksadesimale tegn). Når vi bygger kjedet, 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 begynner med 0 fordi det er den første kjeden (vi trenger bare litt verdi til å begynne med). Når vi hash dette med MD48, blir det til cfcd208495d5. Nå bruker vi en «reduser» -funksjon som i utgangspunktet formaterer denne hashen til en passord, og vi ender med «z». Når vi hash det igjen, får vi fbade9e36a3f, og reduserer det igjen og får renjaj820 Det er noen flere sykluser, og det endelige resultatet er WLgOSj.

Samme for den andre kjeden. Vi starter bare med en annen verdi og gjør det samme. Dette ender med 0uUoAD.

Vår komplette regnbuetabell er nå dette:

WLgOSj => 0 0uUoAD => 1 

Det er alt du trenger å lagre.

Slå opp en hash

La oss si at vi fant en hash på nettet, 7668b2810262. La oss knekke den ved hjelp av bordet vårt!

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 å leke med det selv ble eksemplene ovenfor opprettet ved hjelp av dette Python-skriptet: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Skaleringsegenskaper

Kort sagt:

• Rask oppslag betyr større tabeller, forutsatt at dekning forblir den samme.
• Bedre dekning betyr enten langsommere oppslag, eller større tabeller.
• Mindre tabeller betyr enten langsommere oppslag, eller dårligere dekning.

Følgende avsnitt antar at tiden per hash + reduksjon er 1 µs, og ikke redegjør for kollisjoner. Dette er alle ballpark-tall, ment som eksempler og ikke eksakte verdier.

Oppslagstid

Hvis en hash + -reduksjonsoperasjon tar en mikrosekund, vil det ta omtrent tre timer å generere en tabell med en million kjeder og 10.000 reduksjoner per kjede:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 timer.

Å ta et oppslag i den tabellen tar i gjennomsnitt 10 millisekunder. Dette er fordi vi vanligvis må gjennom chain_length/2 reduksjoner før vi finner hvilken kjede som inneholder hasjen. For eksempel må vi kanskje gjøre 3000 reduksjoner på en hash før vi finner en verdi som er i tabellen. Deretter må vi gjøre kjeden på nytt fra begynnelsen til vi finner den samsvarende verdien. Hvis vi bare måtte gjøre 3000 for å finne det i tabellen vår, så må vi gjøre 7000 reduksjoner fra begynnelsen for å komme til riktig punkt i kjeden. I utgangspunktet gjør vi like mange operasjoner når vi ser opp som når vi genererer en enkelt kjede. Derfor er oppslagstiden 10 000 ganger en mikrosekund, som er ti millisekunder (eller et centisekund, hvis du vil).

Lagringskrav

Når du vil lage en full, rask oppslagstabell for en hash-funksjon, til og med MD5, trenger du fortsatt hundre milliarder milliarder terabyte lagring. Det » s ikke veldig nyttig. Men hva om vi bare vil dekke små passord til 10 tegn?

Hvis vi vil bruke maksimalt 30 sekunder på å lete etter en hash, og forutsatt at vi trenger 1 mikrosekund (en milliontedel av et sekund) per hash + reduser syklusen, så kan vi ha en kjedelengde på: 1 million × 30 = 30 millioner. Det er 26 ¹⁰ (eller 10 ¹⁴ ) mulige småpassord på 10 tegn, og per kjede dekker vi 30 millioner verdier. Det gir oss 4 millioner kjeder. Vi vet at hver kjede bare har en start- og sluttverdi lagret, og at verdiene er 10 tegn hver. Så 2 × 10 × 4 million = 76 MiB-data.

Å generere tabellen ved å gjenta gjennom alle passord med 10 tegn tar lang tid: 30 sekunder per kjede, ganger 4 millioner kjeder er ca 91 år. Mange mennesker ville imidlertid være interessert i et slikt bord, så ved å samle 1092 CPUer (= 91 × 12) tar det bare 1 måned. Dette viser hvor liten en slik tabell kan sammenlignes med passordplassen den dekker: oppslag tar bare 30 sekunder, og du må bare lagre 76MiB-data.

Konklusjon

Rainbow-tabeller kan være betraktet som en time-memory trade-off : man lagrer bare en liten del av tabellen og gjenoppretter den gjennom litt ekstra beregning ved oppslagstid. Dette er en del av grunnen til at salter, eller rettere sagt, en god passordlagringsalgoritme som Scrypt eller Argon2 er viktig for å holde passord trygge.En regnbuetabell kan bare gjenopprette et saltet passord hvis tabellen inneholder en oppføring som er stor nok til å inneholde både saltet og passordet, noe som ville være ekstremt ineffektivt og beseire hele formålet.

Merk at en lignende ting gjelder med kryptering: når folk krypterer filer med et passord, kan det bygges en regnbuebord for å knekke filene. La oss si at programvaren bruker AES, og den første blokken av filen skal dekrypteres til «passordkorrekt» ved å bruke brukerens medfølgende passord, så vil en regnbuetabell bruke AES i stedet for en hash-funksjon.

Når du håndterer et passord (en hemmelighet som har ukjent styrke, og spesielt hvis brukeren kan bruke den på nytt), må du alltid kjøre den gjennom en riktig (langsom) algoritme for lagring av passord for å gjøre den langsom og unik å knekke. >

Kommentarer

• God forklaring. Hvis jeg forsto det riktig, ligger kraften til regnbuebord i å ha en god reduksjonsfunksjon, ikke sant? Hvordan kommer jeg på en god en? Og hvordan unngår jeg kollisjoner for alle kandidater på tvers av kjedene?
• @ Kyu96 Gode spørsmål! Jeg vet ikke ‘, men jeg vil være interessert hvis du finner en. Denne siden handler bare om det generelle spørsmålet om hva et regnbuebord er, ikke detaljer som hvordan man designer en algoritme. Du bør åpne et nytt spørsmål , men dette nettstedet handler om » som beskytter eiendeler mot digitale trusler » (iirc ). Jeg tror det vil være temaet for søstersiden vår, crypto.stackexchange.com , som handler om » matematikken og egenskapene til kryptografiske systemer, deres analyse (» kryptanalyse «) og underordnede emner som generelt utgjør kryptologi, som tilfeldig antall generasjon. »