Mitä sateenkaaripöydät ovat ja miten niitä käytetään?

Sateenkaaripöydät sekoitetaan yleisesti toinen, yksinkertaisempi tekniikka, joka hyödyntää laskenta-aikoja torage kompromissi salasanan palauttamisessa: hash-taulukot.

Hash-taulukot muodostetaan hajauttamalla jokainen sana salasanakirjastossa. Salasana-hajautusparit tallennetaan taulukkoon ryhmiteltyinä hajautusarvon mukaan. Jos haluat käyttää hash-taulukkoa, ota vain hash ja suorita taulukossa binäärihaku alkuperäisen salasanan löytämiseksi, jos se on olemassa.

Sateenkaaritaulukot ovat monimutkaisempia. Sateenkaaritaulukon rakentaminen vaatii kahta asiaa : hajautusfunktio ja pelkistystoiminto. Tiettyjen sateenkaaritaulukoiden joukon hajautusfunktion on vastattava palautettavaa hajautettua salasanaa. Pienennystoiminnon on muutettava hash osaksi jotain salasanana käytettävää. Yksinkertainen vähentämistoiminto on Base64 koodaa hash ja katkaise sitten tietty määrä merkkejä.

Sateenkaaritaulukot on rakennettu tietyn pituisista ”ketjuista”: esimerkiksi 100 000. Ketjun rakentamiseksi valitse satunnainen siemenarvo. Sitten käytä hajautus- ja vähennystoimintoja tälle siemenelle ja sen tuotokselle ja jatka iterointia 100 000 kertaa. Vain siemen ja lopullinen arvo on tallennettu. Luo niin monta ketjua kuin haluat, toista tämä prosessi.

Palauta a salasanalla Rainbow-taulukoiden avulla, salasanan hajautus tehdään yllä oleva prosessi saman pituiseksi: tässä tapauksessa 100 000, mutta ketjun jokainen lenkki säilyy. Kutakin ketjun linkkiä verrataan kunkin ketjun lopulliseen arvoon. Jos ottelu on olemassa, ketju voidaan rekonstruoida pitäen sekä kunkin hajautusfunktion lähtö että kunkin pelkistystoiminnon lähtö. Tämä rekonstruoitu ketju sisältää kyseisen salasanan hashin sekä sen tuottaneen salasanan.

Hajautustaulukon vahvuudet ovat, että salasanan palauttaminen on salamannopeaa (binaarihaku) ja henkilö, joka rakentaa hash-taulukko voi valita, mitä siihen menee, kuten 10000 suosituinta salasanaa. Heikkous Rainbow-taulukoihin verrattuna on, että hash-taulukoiden on tallennettava jokainen hash-salasana-pari.

Rainbow-taulukoista on hyötyä siitä, että taulukoiden rakentaja voi valita, kuinka paljon tallennustilaa tarvitaan valitsemalla linkkien määrä jokainen ketju. Mitä enemmän linkkejä siemenen ja lopullisen arvon välillä on, sitä enemmän salasanoja kaapataan. Yksi heikkous on se, että ketjuja rakentava henkilö ei valitse kaappaamiaan salasanoja, jotta Rainbow-taulukoita ei voida optimoida tavallisille salasanoille. Salasanan palauttaminen edellyttää myös pitkien hash-ketjujen laskemista, mikä tekee palautuksesta kalliita toimintoja. Mitä pidempään ketjut ovat, sitä enemmän salasanoja siepataan niihin, mutta enemmän aikaa tarvitaan salasanan löytämiseen sisältä.

Hash-taulukot ovat hyviä tavallisille salasanoille, Rainbow-taulukot ovat hyviä koville salasanoille. Paras tapa olisi palauttaa mahdollisimman monta salasanaa käyttämällä hash-taulukoita ja / tai tavanomaista halkeilua N: n tärkeimmän salasanan sanakirjalla. Jos sinulla on jäljellä, käytä sateenkaaritaulukoita.

Kommentit

• Voi hyvä, myönnän olevani järkyttynyt – keskustelen ja selitän sateenkaaritaulukot kaikki aikaa, ja koko tämän ajan näyttää siltä, että olen ollut yksi ” hämmentyneistä ”! Olin täysin +1 000 kertaa, opin todella jotain uutta täällä (ja ajattelin, että tiesin vastauksen). Onneksi olen esittänyt kysymyksen loppujen lopuksi … Kiitos!
• Vaikka sateenkaaripöydät olisivatkin tarkkoja (nyt kun avasit silmäni, tein lisää tutkimusta :)), ne erotellaan Hellman Hash -ketjuista käyttämällä useita erilaisia pelkistystoimintoja. Todellakin monimutkaisempi … mutta oikeastaan melko kaunis idea (Ah! siksi miksi he ’ kutsutaan uudelleen ” Sateenkaari ” taulukot?)
• Olen samaa mieltä siitä, että tämä on erittäin hyvä selitys. Vastauksessani selitin sen yksinkertaisesti ja selitin myös todella väärin olemalla yksinkertainen.Rainbow-pöytien kauneus on se, että ne eivät tallenna jokaisen hash-arvon. Aion muokata omaani, mutta äänestän myös tästä, koska se on ehdottomasti parempi selitys.
• Hmm … Vaikka mitä enemmän ajattelen sitä, tosielämän järjestelmissä sateenkaaripöydät eivät ole läheskään yhtä hyödyllisiä kuin hash-taulukot. Kuten totesit, tavallisille salasanoille hash-taulukot ovat paljon parempia (koska ne ovat suuruusluokkaa nopeammat, ja salasanasanakirjan kokovaatimukset ovat tietysti paljon pienempiä kuin koko mahdollinen salasanasarja). Ja kuka ’ me olemme tosissamme? Suurin osa salasanoista kuuluu tähän luokkaan, on hyvin harvinaista (ja tulee olemaan jonkin aikaa), että sinun on soitettava RT: ssä.
• Valitettavasti menetit minut täällä: ” Salasanan palauttamiseksi Rainbow-taulukoiden avulla salasana käy läpi saman prosessin yllä olevan prosessin. ” Kuinka salasana voidaan suorittaa prosessissa, kun se ’ ole edes tiedossa? Tarkoititko salasanan hajautusta? Lisäksi ’ s tämä: ” Ketjun jokaista linkkiä verrataan kunkin ketjun lopulliseen arvoon. ” En näe tilannetta, jossa ketjun linkki vastaisi ketjun lopullista arvoa, koska linkin arvoa tiivistetään ja pienennetään jatkuvasti.

Sateenkaaripöydistä on monia hyviä selityksiä, tämä Kuinka sateenkaaripöydät toimivat on erityisen hyvä. Myös Wikipedia-artikkelilla on erittäin hyvä selitys. Hieman syvempää lukemista varten asiaa koskeva lopullinen paperi on Nopeamman salauksen analyyttinen aika-muisti-kompromissi .

Yksinkertainen selitys sateenkaaripöydille on, että ne käyttävät aikamuistinvaihtotekniikkaa. Tarkoitus sen sijaan, että ottaisit tavoitehajautusarvon ja sanasanan, sitten sekoittaisit jokaisen sanan ja tekisit vertailun lennossa (raakavoimainen lähestymistapa käyttämällä jotain esimerkiksi John ) sen sijaan hajautat kaikki sanakirjan arvot etukäteen (tämä voi kestää hyvin kauan sanakirjan koosta riippuen). Mutta kun se on valmis, voit verrata niin monta hajautusta kuin haluat sateenkaaritaulukoiden ennalta hajautettuihin arvoihin, tämä on huomattavasti nopeammin kuin hajautusten laskeminen uudelleen.

Selitys, jonka kirjoitin tähän aikaisemmin pyrkimys olla lyhyt oli harhaanjohtava, koska se ei selittänyt sateenkaaripöytien käyttämien alennusten käyttöä. Parempaa selitystä varten, kunnes kirjoitan tämän bitin, katso @Crunge vastaus .

Voit joko luoda sateenkaaritaulukot itse käyttämällä sovellusta RainbowCrack tai voit ladata ne lähteistä, kuten Shmoo-ryhmä , Ilmaisia sateenkaaritaulukoita -projektin verkkosivusto, Ophcrack -projekti ja monia muita paikkoja riippuen siitä, minkä tyyppisiä hajautuksia varten taulukoita tarvitaan.

Suojaa sateenkaaritaulukkoa käyttäviltä hyökkäyksiltä tehokkain tapa torjua sitä on varmistaa, että jokainen järjestelmän hash on suolattu . Tämä tekee ennalta luotuista sateenkaaripöydistä hyödyttömiä ja tarkoittaisi, että hyökkääjän olisi luotava räätälöity taulukkojoukko käytettäväksi kohdistettuja hajautuksia vastaan, mikä olisi mahdollista vain, jos hän tietää suolan.

Kommentit

• Lisäksi (harkitse tämän muokkaamista sisään), jos käytät eri suolaa jokaiselle salasanalle, kirjaat sen salaamattomana tietokantaan, hyökkäyksen kohteena on luoda kullekin hashille mukautettu taulukko, joka voittaisi harjoituksen kohteen – sateenkaaritaulukon koko tarkoitus on raakaa voimaa koko salasanatila ja sitten saada kaikki salasanat yhdelle raaalle voimalle vaivaa; jos ’ saa vain yhden salasanan sateenkaaritaulukkoa kohden, voit yhtä hyvin raahata tiivisteen.

Tarkoitus ja merkitys

Sateenkaaritaulukot auttavat murtamaan vaikeita salasanoja eli niitä, joita ei edes löydy suuresta sanakirjasta. Salasanat tallennettiin historiallisesti tavallisina hashina tietokantoihin, ja sitä vastaan sateenkaaritaulukot ovat tehokkaita: luo yksi sateenkaaritaulukko (hidas) ja suorita mikä tahansa määrä tietokantoja, jotka ovat täynnä hajautuksia sitä vastaan (nopeasti).

Nykyään yhä useammat järjestelmät käyttävät oikeita salasanojen tallennusalgoritmeja, kuten Bcrypt, Scrypt tai Argon2. Katso: Kuinka salasanat voidaan tallentaa turvallisesti? Nämä algoritmit ovat ei enää ”haavoittuva” sateenkaaripöydille: koska jokainen hash on ainutlaatuinen, vaikka salasanat olisivat samat, sateenkaaripöydät eivät enää toimi.

Siksi sateenkaaripöydät ovat nykyään epäsuosittuja.Vaikka jotain modernia, kuten Argon2, ei käytetä, kehittäjät tietävät nykyään yleensä, että heidän tulisi käyttää ainakin suolaa. Se on jo tarpeeksi, jotta sateenkaaripöytä olisi hyödytön.

Kuinka ne toimivat

Taulukon luominen

Kuvittele, että luomme sateenkaaripöydän, jossa on vain kaksi ketjua, joista jokaisen pituus on 5. Sateenkaaripöytä on fiktiiviselle hash-toiminnolle MD48, joka antaa 48 bittiä (vain 12 heksadesimaalimerkkiä). Ketjua rakennettaessa näemme tämän:

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 

Aloitamme 0, koska se on ensimmäinen ketju (Aluksi tarvitsemme vain jonkin verran arvoa). Kun hajautamme tämän MD48: lla, se muuttuu cfcd208495d5. Nyt sovellamme ”vähennä” -funktiota, joka muotoilee tämän hashin periaatteessa takaisin salasanan, ja päädymme ”z”: iin. Kun hajautamme sen uudelleen, saamme fbade9e36a3f, pienennämme sen sitten uudelleen ja saamme renjaj820 . On vielä joitain syklejä, ja lopullinen tulos on WLgOSj.

Sama toisella ketjulla. Aloitamme vain toisella arvolla ja teemme saman. Tämän loppuosa on 0uUoAD.

Täydellinen sateenkaaritaulukomme on nyt tämä:

WLgOSj => 0 0uUoAD => 1 

Se on kaikki mitä sinun on tallennettava.

Haun haku hash

Sanotaan, että löysimme verkosta hash-koodin, 7668b2810262. Halkaistaan ”murtaa se käyttämällä taulukkoamme!

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 

Yllä olevat esimerkit luotiin tällä Python-komentosarjalla, jotta voit itse pelata sitä itse: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Skaalausominaisuudet

Lyhyesti:

• Nopea haku tarkoittaa isompia taulukoita olettaen, että peitto pysyy samana.
• Parempi kattavuus tarkoittaa joko hitaampia hakuja tai isompia taulukoita.
• Pienemmät taulukot tarkoittavat joko hitaampia hakuja tai huonompaa kattavuutta.

Seuraavissa osissa oletetaan, että aika hash + -vähennystä kohti on 1µs, eikä siinä oteta huomioon törmäyksiä. Nämä ovat kaikki ballpark-numeroita, tarkoitettu esimerkkeinä eikä tarkkoja arvoja.

Hakuaika

Jos hajautus + pienennysoperaatio kestää mikrosekunnin, miljoonan ketjun ja 10000 vähennyksen per ketju taulukon luominen vie noin 3 tuntia:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 tuntia.

Hakeminen kyseisessä taulukossa kestää keskimäärin 10 millisekuntia. Tämä johtuu siitä, että meidän on yleensä suoritettava chain_length/2 -vähennykset ennen kuin löydämme, mikä ketju sisältää hash-koodin. Esimerkiksi meidän on ehkä tehtävä 3000 vähennystä hashilla, ennen kuin löydämme taulukossa olevan arvon. Seuraavaksi meidän on tehtävä tämä ketju uudelleen alusta, kunnes löydämme vastaavan arvon. Jos meidän täytyi vain tehdä 3000 löytääksemme sen taulukostamme, meidän on tehtävä alusta alkaen 7000 vähennystä päästäksemme ketjun oikeaan kohtaan. Pohjimmiltaan teemme yhtä monta operaatiota etsiessämme kuin generoimalla yhden ketjun. Siksi hakuaika on 10000 kertaa mikrosekunti, mikä on kymmenen millisekuntia (tai sentti, jos haluat).

Tallennustarpeet

Kun haluat tehdä täydellisen, nopean hakutaulukon hash-toiminnolle, jopa MD5: lle, tarvitset silti sata miljardia teratavua tallennustilaa. ei ole kovin hyödyllinen. Mutta entä jos haluamme kattaa vain pienet salasanat 10 merkkiin asti?

Jos haluamme viettää enintään 30 sekuntia hajautusasetusta ja olettaen, että tarvitsemme yhden mikrosekunnin (miljoonasosaa sekuntia) hajautuspäivää kohti + vähennä jaksoa, niin ketjun pituus voi olla: 1 million × 30 = 30 miljoonaa. 10 merkin pituisia pieniä salasanoja on 26 ¹⁰ (tai 10 ¹⁴ ), ja ketjua kohti katamme 30 miljoonaa arvoa. Tämä jättää meille 4 miljoonaa ketjua. Tiedämme, että kullekin ketjulle on tallennettu vain alku- ja loppuarvo ja että arvot ovat kukin 10 merkkiä. Joten 2 × 10 × 4 million = 76 MiB-tiedot.

Taulukon luominen iteroimalla kaikki 10-merkkiset salasanat vie kauan: 30 sekuntia ketjua kohti, kertaa 4 miljoonaa ketjua. noin 91 vuotta. Monet ihmiset olisivat kuitenkin kiinnostuneita tällaisesta taulukosta, joten yhdistämällä 1092 keskusyksikköä (= 91 × 12), se vie vain yhden kuukauden. Tämä osoittaa, kuinka pientä tällaista taulukkoa voidaan verrata sen peittämään salasanatilaan: haku vie vain 30 sekuntia ja sinun on tallennettava vain 76 Mt: n dataa.

Päätelmä

Sateenkaaritaulukoita voidaan käyttää pidetään aikamuistinvaihtona : yksi tallentaa vain pienen osan taulukosta ja palauttaa sen ylimääräisellä laskennalla hakuaikaan. Tämä on osa syytä, miksi suolat tai pikemminkin hyvä salasanan tallennusalgoritmi, kuten Scrypt tai Argon2, ovat tärkeitä salasanojen suojaamiseksi.Sateenkaaritaulukko voi palauttaa suolatun salasanan vain, jos taulukossa on tarpeeksi suuri merkintä, joka sisältää sekä suolaa että salasanaa, mikä olisi erittäin tehotonta ja joka ohittaa koko tarkoituksen.

Huomaa, että samanlainen asia koskee salausta: kun ihmiset salaavat tiedostot salasanalla, voidaan rakentaa sateenkaaritaulukko tiedostojen murtamiseksi. Sanotaan, että ohjelmisto käyttää AES: ää, ja tiedoston ensimmäisen lohkon pitäisi purkaa ”salasanakorjaukseksi” käyttäjän antamalla salasanalla, jolloin sateenkaaritaulukko käyttää AES: ää hash-toiminnon sijaan.

Aina kun käsittelet salasanaa (salaisuus, jonka vahvuus on tuntematon, ja varsinkin jos käyttäjä saattaa käyttää sitä uudelleen), suorita se aina oikean (hitaan) salasanan tallennusalgoritmin läpi, jotta se olisi hidas ja ainutlaatuinen murtamiseen.

Kommentit

• Hyvä selitys. Jos ymmärsin sen oikein, sateenkaaripöytien voimana on hyvä pelkistystoiminto, eikö? Kuinka keksin hyvän? Ja miten voin välttää kaikkien ehdokkaiden törmäykset ketjuissa?
• @ Kyu96 Hyviä kysymyksiä! En tiedä vastausta ’, mutta olisin kiinnostunut, jos löydät vastauksen. Tämä sivu on vain yleinen kysymys sateenkaaripöydästä, ei yksityiskohtia, kuten algoritmin suunnittelua. Sinun pitäisi avata uusi kysymys , mutta tällä verkkosivustolla on kyse ” omaisuuden suojaamisesta digitaalisilta uhilta ” (iirc ). Luulen, että se olisi aihe sisarissivustollemme, crypto.stackexchange.com , joka on noin ” salausjärjestelmien matematiikka ja ominaisuudet, niiden analyysi (” kryptoanalyysi ”) ja toissijaiset aiheet, jotka yleensä muodostavat salauksen, kuten satunnaisluku sukupolvi. ”