Mik azok a szivárványos asztalok és hogyan használják őket?

A szivárványos táblákat gyakran összekeverik a egy másik, egyszerűbb technika, amely felhasználja a számítási időt torage kompromisszumot a jelszó-visszaállítás: hash táblákban.

A hashtáblákat úgy alakítják ki, hogy minden szót elvágnak egy jelszószótárban. A jelszó-hash párokat egy táblázatban tárolják, kivonatolási érték szerint rendezve. A hash tábla használatához egyszerűen vegye ki a kivonatot és végezzen bináris keresést a táblázatban az eredeti jelszó megtalálásához, ha van.

A szivárványos táblázatok összetettebbek. A szivárványos tábla elkészítéséhez két dolog szükséges. : hash függvény és redukciós függvény. Az adott Rainbow Tabletsorozat hash funkciójának meg kell egyeznie a helyreállítani kívánt hash jelszóval. A redukciós függvénynek a hash-t jelszóval használható dologgá kell átalakítania. Egyszerű redukciós funkció a Base64-re. kódolja a kivonatot, majd csonkolja meg bizonyos számú karakterre.

A szivárványos táblák például egy bizonyos hosszúságú “láncokból” épülnek fel: például 100 000. A lánc összeállításához válasszon ki egy véletlenszerű értéket. Ezután alkalmazza a hash és a redukció függvényeket erre a magra és annak kimenetére, és folytassa az ismétlést 100 000 alkalommal. Csak a mag és a végső érték tárolódik. Ismételje meg ezt a folyamatot a kívánt számú lánc létrehozásához.

A jelszót a Rainbow Tables segítségével, a jelszó kivonatát átmennek a fenti folyamat ugyanolyan hosszú: ebben az esetben 100 000, de a lánc minden egyes láncszeme megmarad. A lánc minden egyes láncszemét összehasonlítjuk az egyes láncok végső értékével. Ha van egyezés, a lánc rekonstruálható, megtartva mind az egyes kivonatolási, mind az egyes redukciós funkciók kimenetét. Ez a rekonstruált lánc tartalmazza a kérdéses jelszó kivonatát, valamint az azt előállító jelszót.

A hash-tábla erősségei, hogy a jelszó helyreállítása villámgyors (bináris keresés), és az építő személy a hash tábla kiválaszthatja, hogy mi kerül bele, például a legjobb 10 000 jelszó. A gyengeség a Rainbow Tables-hez képest az, hogy a hash-tábláknak minden egyes hash-jelszó párot el kell tárolniuk.

A Rainbow Tables előnye, hogy a táblákat készítő személy kiválaszthatja, hogy mennyi tárhelyre van szükség a linkek számának kiválasztásával. minden lánc. Minél több kapcsolat van a mag és a végső érték között, annál több jelszót rögzít. Az egyik gyengeség az, hogy a láncokat felépítő személy nem választja ki az elfogott jelszavakat, így a Rainbow Tables nem optimalizálható a közös jelszavakra. A jelszó-helyreállítás magában foglalja a hosszú hash-láncok kiszámítását is, így a helyreállítás drága művelet. Minél hosszabbak a láncok, annál több jelszó ragadódik meg bennük, de több időre van szükség a jelszó megtalálásához.

A hash táblák jóak a közös jelszavakhoz, a Rainbow Tables a kemény jelszavakhoz. A legjobb megközelítés az lenne, ha a lehető legtöbb jelszót helyreállítaná hash-táblák és / vagy hagyományos feltörések segítségével, a legfelső N jelszó szótárával. A maradóknak használja a Szivárvány Táblázatokat.

Kommentárok

• Ó, istenem, elismerem, hogy sokkot kaptam – a Szivárvány táblákat átbeszélem és elmagyarázom. idő alatt, és úgy tűnik, egész idő alatt én voltam a ” egyik gyakran zavaros ” egyik tagja! Teljesen 1000 alkalommal tennék meg, itt valóban valami újat tanultam (és azt hittem, tudtam a választ). Örülök, hogy mégis feltettem a kérdést … Köszönöm!
• Annak ellenére, hogy konkrétak legyünk (most, hogy kinyitottad a szemem, még némi kutatást folytattam :)), a szivárványos asztalokat megkülönböztetik a Hellman Hash Chains-től. több különböző redukciós funkció. Valójában összetettebb … de valóban nagyon szép ötlet (Ah! ezért ezért hívják őket ‘ ” Szivárvány ” táblázatok?)
• Egyetértek azzal, hogy ez nagyon jó magyarázat. Válaszomban egyszerűen megmagyaráztam, és azt is, hogy egyszerű voltam, nagyon rosszul magyaráztam.A Rainbow táblázatok szépsége az a tény, hogy nem tárolnak minden hash értéket. Szerkeszteni fogom az enyémet, de szavazni is fogok, mivel ez mindenképpen jobb magyarázat.
• Hmm … Bár minél jobban gondolkodom rajta, a való életben a szivárványos táblák közel sem olyan hasznosak, mint hash táblák. Mint kijelentette, a közös jelszavaknál a hash-táblák sokkal jobbak (mivel nagyságrenddel gyorsabbak, és a jelszószótár méretigénye természetesen jóval kisebb, mint a jelszavak teljes lehetséges tartománya). És ki ‘ viccelünk? A legtöbb jelszó ebbe a kategóriába tartozik, nagyon ritka (és még egy ideig ez lesz), hogy RT-ben kell felhívnia.
• Sajnos itt elvesztettél engem: ” A jelszó helyreállításához a Rainbow Tables segítségével a jelszó ugyanolyan hosszú időn keresztül megy át a fenti folyamaton. ” Hogyan lehet a jelszónak folyamatot végrehajtani, ha >

Sok jó magyarázat van arra, hogy mi a szivárványos tábla, ez Hogyan működnek a szivárványos táblázatok különösen jó. A Wikipedia cikk is nagyon jó magyarázattal szolgál. Kicsit mélyebb olvasás érdekében a témáról szóló végleges cikk a következő: Gyorsabb kriptanalitikus idő-memória kompromisszum készítése .

A Rainbow Tables egyszerű magyarázata, hogy időmemória-kompromisszumos technikát alkalmaznak. Jelentés ahelyett, hogy megcélzott kivonatértéket és szavak szótárát venné, majd egyes szavakat összedobja és menet közben elvégzi az összehasonlítást (a durva erő megközelítése olyasvalamivel, mint John ), ehelyett előre kivonja a szótár összes értékét (ez a szótár méretétől függően nagyon hosszú időt vehet igénybe). De ha elkészült, összehasonlíthat annyi kivonatot, amennyit csak akar, a szivárványos táblázatok előre kivonatolt értékeivel, ez lényegesen gyorsabb, mint az újraszámítás.

A magyarázat, amelyet itt korábban írtam a rövidre törekvés félrevezető volt, mivel nem magyarázta meg a szivárványos asztalok által alkalmazott csökkentések használatát. A jobb magyarázatért, amíg át nem írom ezt a bitet, lásd: @Crunge választ .

A szivárványos táblákat maga is létrehozhatja olyan alkalmazással, mint a RainbowCrack , vagy letöltheti őket olyan forrásokból, mint The Shmoo Group , Ingyenes szivárványos táblázatok projekt webhelye, az Ophcrack projekt és még sok más hely attól függően, hogy milyen típusú kivonatokra van szüksége táblázathoz.

A Rainbow Table alapú támadások elleni védelem érdekében a leghatékonyabb módszer az ellene való küzdelem érdekében az, hogy a rendszeren belül minden hash sózott legyen . Ez használhatatlanná teszi az előre létrehozott szivárványos asztalokat, és azt jelentené, hogy a támadónak egyéni táblákat kellene készítenie a célzott hashek ellen, amelyek csak akkor lehetségesek, ha ismerik a sót.

Megjegyzések

• Továbbá (fontolja meg ennek szerkesztését), ha minden jelszóhoz más sót használ, és titkosítatlanul rögzíti az adatbázisban, akkor a a támadottnak egyedi táblákat kell készítenie minden egyes hash számára, amely legyőzné a gyakorlat tárgyát – a szivárványos tábla lényege, hogy a teljes jelszóteret erőszakkal el kell erőltetni, majd meg kell kapnia az összes jelszót egy nyers erőhöz. erőfeszítés; ha ‘ csak egy jelszót kap szivárványtáblánként, akkor közvetlenül is nyersen kényszerítheti a kivonatot.

Cél és relevancia

A szivárványos táblázatok segítenek feltörni a nehéz jelszavakat, vagyis azokat, amelyek még egy nagy szótárban sem találhatók meg. A jelszavakat történelmileg sima kivonatokként tárolták az adatbázisokban, és ez ellen a szivárványos táblák hatékonyak: hozzon létre egy szivárványos táblázatot (lassú), és futtasson tetszőleges számú, hashokkal teli adatbázist ellene (gyorsan).

Manapság egyre több rendszer használ megfelelő jelszó-tárolási algoritmusokat, mint például a Bcrypt, a Scrypt vagy az Argon2. Lásd: Hogyan lehet biztonságosan [tárolni] a jelszavakat? Ezek az algoritmusok már nem “sérülékeny” a szivárványos táblákra: mivel minden hash egyedi, még akkor is, ha a jelszavak megegyeznek, a szivárványos táblák már nem működnek.

Ezért nem népszerűek a szivárványos táblák.Még akkor is, ha valami modernet, például az Argon2-t nem használnak, manapság a fejlesztők általában tudják, hogy legalább sót kell használniuk. Ez már elég ahhoz, hogy haszontalanná tegye a szivárványos asztalt.

Hogyan működnek

Tábla létrehozása

Képzelje el, hogy létrehozunk egy szivárványos táblázatot, amelynek csak két lánca van, mindegyik 5 hosszú. A szivárványtábla az MD48 kitalált hash függvényre vonatkozik, amely 48 bitet ad ki (csak 12 hexadecimális karaktert). A lánc felépítésekor ezt látjuk:

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 

Azzal kezdjük, hogy 0, mert ez az első lánc (csak valami értékre van szükségünk a kezdéshez). Ha ezt kivonatoljuk az MD48-mal, az cfcd208495d5 -be vált. Most egy “csökkentés” funkciót alkalmazunk, amely alapvetően ezt a kivonatot formázza vissza egy jelszót kapunk, és végül a “z” betűvel állunk elő. Ha ezt újra kivonatoljuk, megkapjuk az fbade9e36a3f szót, majd újra csökkentjük, és megkapjuk a renjaj820 . Van még néhány ciklus, és a végeredmény WLgOSj.

Ugyanez a második láncra is. Csak egy másik értékkel indulunk, és ugyanezt tesszük. Ennek vége a következő: 0uUoAD.

A teljes szivárványos táblánk most ez:

WLgOSj => 0 0uUoAD => 1 

Mindössze annyit kell tárolnia.

Kivonat keresése

Mondjuk, hogy találtunk egy kivonatot az interneten, 7668b2810262. Letörjük a táblázatunk segítségével!

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 

Ahhoz, hogy maga is kijátszhassa vele, a fenti példákat ennek a Python szkriptnek a segítségével hoztuk létre: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Méretezési tulajdonságok

Röviden:

• A gyors keresés nagyobb táblákat jelent, feltételezve, hogy a lefedettség ugyanaz marad.
• A jobb lefedettség lassabb keresést vagy nagyobb táblákat jelent.
• A kisebb táblák lassabb keresést vagy rosszabb lefedettséget jelentenek.

A következő szakaszok feltételezik, hogy a hash + redukció per ideje 1µs, és nem veszik figyelembe az ütközéseket. Ezek mind ballpark-számok, példákként szolgálnak, nem pedig pontos értékek.

Keresési idő

Ha a hash + csökkentési művelet mikroszekundumot vesz igénybe, akkor egy millió láncot és lánconként 10 000 redukciót tartalmazó tábla létrehozása körülbelül 3 órát vesz igénybe:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 óra.

A keresés ebben a táblázatban átlagosan 10 ezredmásodpercet vesz igénybe. Ennek oka, hogy általában chain_length/2 csökkentéseken kell átesnünk, mielőtt megtalálnánk, melyik lánc tartalmazza a kivonatot. Például előfordulhat, hogy 3000 kivonást kell végrehajtanunk egy hash-on, mielőtt megtalálnánk a táblázatban szereplő értéket. Ezután a kezdetektől kezdve újra meg kell csinálnunk azt a láncot, amíg meg nem találjuk a megfelelő értéket. Ha csak 3000-et kellett elvégeznünk, hogy megtaláljuk a táblázatunkban, akkor kezdettől fogva 7000 csökkentést kell végrehajtanunk ahhoz, hogy a lánc megfelelő pontjához érjünk. Alapvetően annyi műveletet hajtunk végre, amikor felnézünk, mint egyetlen lánc létrehozásakor. Ezért a keresési idő 10 000-szerese egy mikroszekundumnak, ami tíz ezredmásodperc (vagy centisekundum, ha akarja).

Tárolási követelmények

Ha teljes, gyors keresési táblázatot szeretne készíteni egy hash függvényhez, még az MD5-hez is, akkor is százmilliárd milliárd terabájt tárhelyre lenne szüksége. s nem túl hasznos. De mi van akkor, ha csak kisbetűs jelszavakat akarunk lefedni 10 karakterig?

Ha legfeljebb 30 másodpercet akarunk eltölteni egy kivonat után, és feltételezzük, hogy hash-ra 1 mikroszekundum (másodperc milliomod része) szükséges + a ciklus csökkentése, akkor a lánc hossza: 1 million × 30 = 30 millió lehet. 26 ¹⁰ (vagy 10 ¹⁴ ) lehetséges 10 karakteres kisbetűs jelszó létezik, és lánconként 30 millió értéket fedünk le. Így 4 millió lánc marad bennünk. Tudjuk, hogy minden láncnak csak kezdő és végértéke van tárolva, és hogy az értékek egyenként 10 karakterek. Tehát 2 × 10 × 4 million = 76 MiB adat.

A tábla generálása az összes 10 karakteres jelszó iterálásával hosszú időt vesz igénybe: 30 másodperc lánconként, 4 millió lánc szorzata pedig körülbelül 91 év. Nagyon sok embert érdekelne azonban egy ilyen tábla, így 1092 processzor összegyűjtésével (= 91 × 12) mindössze 1 hónapra van szükség. Ez megmutatja, hogy egy ilyen tábla milyen kicsi lehet összehasonlítani az általa lefedett jelszóterülettel: a keresés csak 30 másodpercet vesz igénybe, és csak 76 MB-os adatokat kell tárolnia.

Következtetés

A szivárványos táblák lehetnek idő-memória kompromisszumnak tekinthető : az ember a táblázatnak csak egy kis részét tárolja, és a keresési idő némi extra kiszámításával helyreállítja. Ez annak az oka, hogy a sók, vagy inkább egy jó jelszó-tárolási algoritmus, például a Scrypt vagy az Argon2 fontos a jelszavak biztonságának megőrzése érdekében.A szivárványos tábla csak akkor tudja helyreállítani a sózott jelszót, ha a táblázat olyan bejegyzést tartalmaz, amely elég nagy a só és a jelszó megadásához is, ami rendkívül nem hatékony és az egész célt meghiúsítja.

Ne feledje, hogy a titkosításnál hasonló dolog van: amikor az emberek jelszavakkal titkosítják a fájlokat, szivárványos táblát lehet építeni a fájlok feltörésére. Tegyük fel, hogy a szoftver AES-t használ, és a fájl első blokkjának visszafejteni kell a “jelszójavítást” a felhasználó által megadott jelszó használatával, majd egy szivárványos tábla az AES-t használja hash függvény helyett.

Amikor kezel egy jelszót (egy titok, amely ismeretlen erősségű, és különösen, ha a felhasználó esetleg újra felhasználja), mindig futtassa át egy megfelelő (lassú) jelszó-tárolási algoritmuson, hogy lassú és egyedi legyen a feltörésre.

Megjegyzések

• Jó magyarázat. Ha jól értettem, a szivárványos asztalok ereje abban rejlik, hogy jó redukciós funkcióval rendelkeznek, nem igaz? Hogyan juthatok elő egy jóval? És hogyan kerülhetem el az összes jelölt ütközését a láncokban?
• @ Kyu96 Jó kérdések! Nem tudom ‘ a választ, de érdekelne, ha találna ilyet. Ez az oldal csak arról az általános kérdésről szól, hogy mi a szivárványos tábla, és nem olyan részletek, mint például egy algoritmus megtervezése. új kérdést kell nyitnia , de ez a webhely arról szól, hogy ” megvédi az eszközöket a digitális fenyegetések ellen ” (iirc ). Úgy gondolom, hogy ez a témánk lenne a testvéroldalunknak, a crypto.stackexchange.com oldalnak, ami a ” a kriptográfiai rendszerek matematikája és tulajdonságai, elemzésük (” kriptanalízis “) és a kriptológiát általában alkotó kiegészítő témák, például véletlenszám generáció. ”