Wat zijn regenboogtafels en hoe worden ze gebruikt?

Rainbow Tables worden vaak verward met een andere, eenvoudigere techniek die gebruikmaakt van een rekentijd Torage-afweging bij wachtwoordherstel: hashtabellen.

Hash-tabellen worden geconstrueerd door elk woord in een wachtwoordwoordenboek te hashen. De wachtwoord-hash-paren worden opgeslagen in een tabel, gesorteerd op hash-waarde. Om een hashtabel te gebruiken, neem je simpelweg de hash en voer je een binaire zoekopdracht in de tabel uit om het originele wachtwoord te vinden, als dit aanwezig is.

Rainbow Tables zijn complexer. Om een regenboogtafel te maken zijn twee dingen nodig : een hashfunctie en een reductiefunctie. De hashfunctie voor een bepaalde set Rainbow Tables moet overeenkomen met het gehashte wachtwoord dat je wilt herstellen. De reductiefunctie moet een hash omzetten in iets dat bruikbaar is als wachtwoord. Een eenvoudige reductiefunctie is naar Base64 codeer de hash en verkort deze tot een bepaald aantal tekens.

Rainbow-tabellen zijn opgebouwd uit “ketens” van een bepaalde lengte: 100.000 bijvoorbeeld. Om de ketting samen te stellen, kiest u een willekeurige seed-waarde. pas de hashing- en reductiefuncties toe op deze seed en de uitvoer, en herhaal 100.000 keer. Alleen de seed en de uiteindelijke waarde worden opgeslagen. Herhaal dit proces om zoveel ketens te maken als je wilt.

Om een wachtwoord met behulp van Rainbow Tables, ondergaat de wachtwoordhash het bovenstaande proces voor dezelfde lengte: in dit geval 100.000 maar elke schakel in de ketting blijft behouden. Elke schakel in de ketting wordt vergeleken met de uiteindelijke waarde van elke ketting. Als er een overeenkomst is, kan de ketting worden gereconstrueerd, waarbij zowel de uitvoer van elke hashfunctie als de uitvoer van elke reductiefunctie behouden blijft. Die gereconstrueerde ketting zal de hash van het wachtwoord in kwestie bevatten, evenals het wachtwoord dat het heeft geproduceerd.

De sterke punten van een hashtabel zijn dat het herstellen van een wachtwoord razendsnel gaat (binair zoeken) en de persoon bouwt de hashtabel kan kiezen wat erin gaat, zoals de top 10.000 wachtwoorden. Het zwakke punt in vergelijking met Rainbow Tables is dat hashtabellen elk afzonderlijk hash-wachtwoordpaar moeten opslaan.

Rainbow Tables hebben het voordeel dat de persoon die deze tabellen maakt, kan kiezen hoeveel opslagruimte nodig is door het aantal links in te selecteren. elke ketting. Hoe meer links tussen de seed en de uiteindelijke waarde, hoe meer wachtwoorden er worden vastgelegd. Een zwak punt is dat de persoon die de ketens bouwt niet de wachtwoorden kiest die ze vastleggen, zodat Rainbow Tables niet kan worden geoptimaliseerd voor gewone wachtwoorden. Wachtwoordherstel omvat ook het berekenen van lange ketens van hashes, waardoor herstel een dure operatie wordt. Hoe langer de ketens, hoe meer wachtwoorden erin worden vastgelegd, maar er is meer tijd nodig om een wachtwoord erin te vinden.

Hash-tabellen zijn goed voor gewone wachtwoorden, Rainbow Tables zijn goed voor moeilijke wachtwoorden. De beste aanpak zou zijn om zoveel mogelijk wachtwoorden te herstellen met behulp van hashtabellen en / of conventioneel kraken met een woordenboek met de top N wachtwoorden. Voor degenen die overblijven, gebruik Rainbow Tables.

Reacties

• Oh mijn hemel, ik geef toe dat ik geschokt ben – ik bespreek en leg alle Rainbow-tafels uit. en al die tijd lijkt het erop dat ik een van de ” ben die vaak verward zijn “! Ik zou totaal +1000 keer, ik heb hier echt iets nieuws geleerd (en ik dacht dat ik het antwoord wist ). Blij dat ik de vraag toch heb gesteld … Dank je!
• Hoewel om specifiek te zijn (nu je mijn ogen opendeed, deed ik wat meer onderzoek :)), worden Rainbow Tables onderscheiden van Hellman Hash Chains door verschillende verschillende reductiefuncties. Inderdaad ingewikkelder … maar echt een heel mooi idee (Ah! Is dat waarom ze ‘ worden genoemd ” Rainbow ” tabellen?)
• Ik ben het ermee eens dat dit een zeer goede uitleg is. In mijn antwoord legde ik het eenvoudig uit en legde het ook echt verkeerd uit door te simpel te zijn.Het mooie van Rainbow-tabellen is dat ze niet ‘ elke hash-waarde opslaan. Ik ga de mijne bewerken, maar ook stemmen omdat het zeker een betere verklaring is.
• Hmm … Hoewel hoe meer ik erover nadenk, in echte systemen zijn Rainbow Tables lang niet zo nuttig als hash-tabellen. Zoals u al zei, zijn hashtabellen voor gewone wachtwoorden veel beter (aangezien ze sneller in de orde van grootte zijn en de vereisten voor de grootte van een wachtwoordwoordenboek natuurlijk veel kleiner zijn dan het volledige mogelijke bereik van wachtwoorden). En met wie ‘ maken we een grapje? De meeste wachtwoorden vallen in die categorie, het is zeer zeldzaam (en zal enige tijd duren) dat u RT moet bellen.
• Helaas bent u me hier kwijtgeraakt: ” Om een wachtwoord te herstellen met Rainbow Tables, ondergaat het wachtwoord het bovenstaande proces voor dezelfde lengte. ” Hoe kan het wachtwoord het proces ondergaan als het ‘ s niet eens bekend? Bedoelde je de wachtwoordhash? Bovendien is er ‘ dit: ” Elke schakel in de ketting wordt vergeleken met de uiteindelijke waarde van elke ketting. ” Ik zie geen situatie waarin een schakel in de keten overeenkomt met de uiteindelijke waarde in de keten, aangezien de waarde van de schakel continu wordt gehasht en verminderd.

Er zijn veel goede verklaringen voor wat regenboogtafels zijn, deze Hoe Rainbow Tables werken is bijzonder goed. Ook het Wikipedia-artikel heeft ook een zeer goede uitleg. Voor een beetje meer diepgaande lezing is het definitieve artikel over het onderwerp Een snellere cryptanalytische afweging tussen tijd en geheugen maken .

Een eenvoudige uitleg van Rainbow Tables is dat ze gebruik maken van een techniek voor het inruilen van tijdgeheugen. Dit betekent in plaats van een doel-hashwaarde en een woordenboek met woorden te nemen en vervolgens elk woord te hashen en de vergelijking on the fly uit te voeren (brute force-benadering met iets als John ), u hasht in plaats daarvan alle waarden in het woordenboek van tevoren (dit kan erg lang duren, afhankelijk van de woordenboekgrootte). Maar als het klaar is, kun je zoveel hashes vergelijken als je wilt met de vooraf gehashte waarden in de regenboogtabellen, dit is aanzienlijk sneller dan het opnieuw berekenen van de hashes.

De uitleg die ik hier eerder schreef in een poging om kort te zijn was misleidend, aangezien het geen verklaring gaf voor het gebruik van reducties waarvan regenboogtafels gebruik maken. Voor een betere uitleg totdat ik dit bit herschrijf, zie @Crunge antwoord .

Je kunt ofwel de regenboogtabellen zelf genereren met een applicatie zoals RainbowCrack of u kunt ze downloaden van bronnen zoals The Shmoo Group , Gratis Rainbow Tables -projectwebsite, Ophcrack -project en vele andere plaatsen, afhankelijk van het type hashes waarvoor je tabellen nodig hebt.

Om te beschermen tegen een Rainbow Table-gebaseerde aanval is de meest effectieve methode om deze te bestrijden, ervoor te zorgen dat elke hash binnen een systeem salted is. Dit maakt vooraf gegenereerde regenboogtabellen onbruikbaar en zou betekenen dat een aanvaller een aangepaste set tabellen zou moeten genereren om tegen de beoogde hashes te gebruiken, wat alleen mogelijk zou zijn als ze het zout kenden.

Reacties

• Verder (overweeg om dit in te bewerken), als je een ander salt gebruikt voor elk wachtwoord, het onversleuteld in de database opneemt, dan zal de aangevallen zou een aangepaste set tabellen voor elke hash moeten genereren, wat het doel van de oefening zou verslaan – het hele punt van de regenboogtafel is om de hele wachtwoordruimte bruut te forceren en vervolgens alle wachtwoorden voor één brute kracht te krijgen inspanning; als je ‘ slechts één wachtwoord per regenboogtafel krijgt, dan kun je net zo goed direct de hash brute forceren.

Doel en relevantie

Rainbow-tabellen helpen bij het kraken van moeilijke wachtwoorden, dwz wachtwoorden die niet eens in een groot woordenboek kunnen worden gevonden. Wachtwoorden werden historisch opgeslagen als gewone hashes in databases, en dat is waar regenboogtabellen effectief tegen zijn: maak een enkele regenboogtabel (langzaam) en draai een willekeurig aantal databases vol met hashes ertegen (snel).

Tegenwoordig gebruiken steeds meer systemen de juiste algoritmen voor wachtwoordopslag, zoals Bcrypt, Scrypt of Argon2. Zie: Hoe wachtwoorden veilig [op te slaan]? Die algoritmen zijn niet langer “kwetsbaar” voor regenboogtabellen: aangezien elke hash uniek is, zelfs als de wachtwoorden gelijk zijn, werken regenboogtabellen niet langer.

Daarom zijn regenboogtafels tegenwoordig niet populair.Zelfs als iets moderns als Argon2 niet wordt gebruikt, weten ontwikkelaars tegenwoordig meestal dat ze op zijn minst een zout moeten gebruiken. Dat is al genoeg om een regenboogtafel onbruikbaar te maken.

Hoe ze werken

Een tabel maken

Stel je voor dat we een regenboogtafel maken met slechts twee kettingen, elk met een lengte van 5. De regenboogtafel is voor de fictieve hashfunctie MD48, die 48 bits (slechts 12 hexadecimale tekens) uitvoert. Bij het opbouwen van de keten zien we dit:

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 

We beginnen met 0 omdat het de eerste keten is (we hebben alleen wat waarde nodig om mee te beginnen). Als we dit hashen met MD48, verandert het in cfcd208495d5. Nu passen we een “reduce” -functie toe die deze hash in feite terug opmaakt in een wachtwoord, en we eindigen met “z”. Als we dat opnieuw hashen, krijgen we fbade9e36a3f, verkleinen we het weer en krijgen we renjaj820 Er zijn nog wat cycli en het eindresultaat is WLgOSj.

Hetzelfde voor de tweede keten. We beginnen gewoon met een andere waarde en doen hetzelfde. Dit eindigt in 0uUoAD.

Onze complete regenboogtafel is nu deze:

WLgOSj => 0 0uUoAD => 1 

Dat is alles wat u hoeft op te slaan.

Een hash opzoeken

Laten we zeggen dat we een hash online hebben gevonden, 7668b2810262. Laten we hem kraken met behulp van onze tabel!

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 

Om er zelf mee te spelen, zijn de bovenstaande voorbeelden gemaakt met behulp van dit Python-script: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Eigenschappen schalen

In het kort:

• Snel zoeken betekent grotere tabellen, ervan uitgaande dat de dekking hetzelfde blijft.
• Betere dekking betekent langzamere zoekopdrachten of grotere tabellen.
• Kleinere tabellen betekent langzamere zoekopdrachten of slechtere dekking.

De volgende secties gaan ervan uit dat de tijd per hash + reductie 1 µs is, en houden geen rekening met botsingen. Dit zijn allemaal ballpark-nummers, bedoeld als voorbeelden en geen exacte waarden.

Opzoektijd

Als een hash + reductiebewerking een microseconde duurt, zou het genereren van een tabel met een miljoen ketens en 10.000 reducties per keten ongeveer 3 uur duren:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 uur.

Het opzoeken in die tabel duurt gemiddeld 10 milliseconden. Dit komt doordat we meestal chain_length/2 reducties moeten doorlopen voordat we kunnen bepalen welke keten de hash bevat. Het kan bijvoorbeeld zijn dat we 3000 reducties op een hash moeten doen voordat we een waarde vinden die in de tabel staat. Vervolgens moeten we die ketting vanaf het begin opnieuw doen totdat we de overeenkomende waarde hebben gevonden. Als we maar 3000 moesten doen om het in onze tabel te vinden, dan moeten we vanaf het begin 7000 reducties doen om op het juiste punt in de keten te komen. In principe doen we evenveel bewerkingen bij het opzoeken als bij het genereren van een enkele ketting. Daarom is de opzoektijd 10.000 keer een microseconde, wat tien milliseconden is (of een centiseconde, als je wilt).

Opslagvereisten

Als je een volledige, snelle opzoektabel wilt maken voor een hash-functie, zelfs MD5, “heb je nog steeds honderd miljard miljard terabytes aan opslagruimte nodig. Dat” is niet erg behulpzaam. Maar wat als we alleen wachtwoorden in kleine letters willen bedekken tot 10 tekens?

Als we maximaal 30 seconden willen besteden aan het zoeken naar een hash, en ervan uitgaande dat we 1 microseconde (een miljoenste van een seconde) per hash nodig hebben + cyclus verkorten, dan kunnen we een kettinglengte hebben van: 1 million × 30 = 30 miljoen. Er zijn 26 ¹⁰ (of 10 ¹⁴ ) wachtwoorden in kleine letters van 10 tekens mogelijk, en per ketting dekken we 30 miljoen waarden. Dat levert ons 4 miljoen kettingen op. We weten dat elke ketting alleen een begin- en eindwaarde heeft opgeslagen, en dat de waarden elk 10 tekens zijn. Dus 2 × 10 × 4 million = 76 MiB-gegevens.

Het genereren van de tabel door alle wachtwoorden van 10 tekens te herhalen kost veel tijd: 30 seconden per keten, maal 4 miljoen ketens is ongeveer 91 jaar. Veel mensen zouden echter geïnteresseerd zijn in zon tafel, dus door 1092 CPUs (= 91 × 12) te poolen, duurt het slechts 1 maand. Dit laat zien hoe klein zon tabel kan worden vergeleken met de wachtwoordruimte die het beslaat: opzoeken duurt slechts 30 seconden en je hoeft slechts 76MiB-gegevens op te slaan.

Conclusie

Rainbow-tabellen kunnen beschouwd als een afweging tussen tijd en geheugen : men slaat slechts een klein deel van de tabel op en herstelt het door wat extra berekening van de opzoektijd. Dit is een deel van de reden waarom salts, of liever gezegd, een goed wachtwoordopslagalgoritme zoals Scrypt of Argon2 belangrijk zijn om wachtwoorden veilig te houden.Een regenboogtafel kan alleen een gezouten wachtwoord terugkrijgen als de tabel een invoer bevat die groot genoeg is om zowel het zout als het wachtwoord te bevatten, wat extreem inefficiënt zou zijn en het hele doel tenietdoet.

Merk op dat iets soortgelijks geldt voor versleuteling: wanneer mensen bestanden versleutelen met een wachtwoord, kan een regenboogtafel worden gebouwd om de bestanden te kraken. Laten we zeggen dat de software AES gebruikt en dat het eerste blok van het bestand moet worden gedecodeerd naar “wachtwoordcorrect” met het door de gebruiker opgegeven wachtwoord, dan zou een regenboogtafel AES gebruiken in plaats van een hash-functie.

Telkens wanneer u een wachtwoord hanteert (een geheim dat van onbekende sterkte is, en vooral als de gebruiker het misschien hergebruikt), voer het dan altijd door een correct (langzaam) wachtwoordopslagalgoritme om het traag en uniek te maken om te kraken.

Reacties

• Goede uitleg. Als ik dat goed heb begrepen, ligt de kracht van regenboogtafels in het hebben van een goede reductiefunctie, toch? Hoe kom ik met een goede? En hoe voorkom ik botsingen voor alle kandidaten over de ketens heen?
• @ Kyu96 Goede vragen! Ik weet het antwoord niet ‘, maar ik zou het interessant vinden als je er een vindt. Deze pagina gaat alleen over de algemene vraag wat een regenboogtafel is, niet over details zoals het ontwerpen van een algoritme. U moet een nieuwe vraag openen , maar deze website gaat over ” het beschermen van activa tegen digitale bedreigingen ” (iirc ). Ik denk dat het on-topic zou zijn voor onze zustersite, crypto.stackexchange.com , die ongeveer ” is de wiskunde en eigenschappen van cryptografische systemen, hun analyse (” cryptanalyse “) en secundaire onderwerpen die doorgaans cryptologie vormen, zoals een willekeurig getal generatie. ”