Sateenkaari pöytä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. helmikuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Rainbow table ( englanniksi  rainbow table ) on erityinen versio hakutaulukoista ( englanniksi  lookup table ) kryptografisten hajautusfunktioiden kääntämiseen käyttämällä järkevän kompromissin mekanismia taulukon hakuajan ja muistin varatun välillä ( englanninkielinen  aika-muisti kompromissi ).

Rainbow-taulukoita käytetään murtautumaan vaikeasti palautettavissa oleviin hash - salasanoihin ja hyökkäämään symmetrisiin salakirjoihin, jotka perustuvat tunnettuun tekstiin .

Suolaavaimen johtamistoiminnon käyttäminen tekee tästä hyökkäyksestä mahdotonta. Rainbow-taulukot ovat Martin Hellmanin [1]
ehdottaman aikaisemman ja yksinkertaisemman algoritmin kehitys .

Edellytykset

Tietokonejärjestelmien, jotka käyttävät salasanoja todentamiseen , on jotenkin määritettävä, onko syötetty salasana oikea. Helpoin tapa ratkaista tämä ongelma on pitää luettelo kunkin käyttäjän kaikista kelvollisista salasanoista. Tämän menetelmän haittana on, että jos luvaton pääsy luetteloon, hyökkääjä selvittää kaikkien käyttäjien salasanat. Yleisempi tapa on tallentaa salaushajautusarvot tunnuslauseesta. Useimmat tiivisteet lasketaan kuitenkin nopeasti, joten tiivisteisiin pääsevä hyökkääjä voi nopeasti tarkistaa mahdollisten salasanojen kelpoisuuden. Tämän välttämiseksi sinun on käytettävä pidempiä salasanoja, mikä lisää hyökkääjän tarkistettavien salasanojen luetteloa. Yksinkertaisille salasanoille, jotka eivät sisällä suolaa , hyökkääjä voi etukäteen laskea hash-arvot kaikille yleisille ja lyhyille salasanoille ja tallentaa ne taulukkoon. Nyt voit nopeasti löytää ottelun valmiiksi hankitusta taulukosta. Mutta mitä pidempi salasana, sitä suurempi taulukko ja sitä enemmän muistia tarvitaan sen tallentamiseen. Vaihtoehtona on tallentaa vain hajaketjujen ensimmäiset elementit. Tämä vaatii enemmän laskentaa salasanan etsimiseen, mutta vähentää huomattavasti tarvittavan muistin määrää. Ja sateenkaaripöydät ovat parannettu versio tästä menetelmästä, joka välttää törmäykset.

Ennalta lasketut hash-ketjut

Tässä artikkelissa kuvatut hash-ketjut eroavat Hash-ketjun artikkelissa kuvatuista .

Oletetaan, että meillä on hash-funktio H, jonka hash-pituus n ja äärellinen joukko salasanoja P. Tavoitteenamme on luoda tietorakenne , joka mille tahansa hash-arvolle h löytää joko P:n elementin p siten, että H( p )= h , tai määrittää, ettei tällaista elementtiä ole olemassa. Yksinkertaisin tapa tehdä tämä on laskea H( p ) kaikille P :n p:lle, mutta tällainen taulukko vaatisi Θ (|P| n ) muistia, mikä on liikaa.

Hash-ketjut ovat tekniikka tämän muistin tarpeen vähentämiseksi. Pääideana on määritellä pelkistysfunktio R, joka kartoittaa hash-arvot arvoihin P:stä. Huomaa, että R ei ole hash-funktion inversio. Aloittaen alkuperäisestä salasanasta ja käyttämällä vuorotellen H:ta ja R:tä jokaiseen tuloksena olevaan arvoon, saamme ketjun vuorottelevia salasanoja ja hajautusarvoja. Esimerkiksi 6 merkin pituiselle salasanajoukolle ja 32-bittisiä arvoja tuottavalle hash-funktiolle ketju voi näyttää tältä:

Ainoa pelkistystoiminnon vaatimus on palauttaa arvot samoista aakkosista kuin salasanat.

Taulukon luomiseksi valitsemme satunnaisen joukon alkuperäisiä salasanoja P:stä, laskemme jokaiselle salasanalle jonkin kiinteän pituisen k ketjut ja tallennamme jokaisesta ketjusta vain ensimmäisen ja viimeisen salasanan.

Jokaiselle tiiviste h , jonka arvon haluamme kääntää (etsi sitä vastaava salasana), laskemme sekvenssin R(…R(H(R(h)))…). Jos jokin väliarvoista osuu yhteen minkä tahansa ketjun pään kanssa, otamme tämän ketjun alun ja palauttamme sen kokonaan. Suurella todennäköisyydellä koko ketju sisältää hash-arvon h ja sitä edeltävä salasana on haluttu.

Yllä olevassa esimerkissä, jos meillä on alun perin hajautusarvo 920ECF10, se luo seuraavan sekvenssin:

Koska kiebgtketjun loppu on taulukostamme, otamme vastaavan aloitussalasanan aaaaaaja laskemme ketjun, kunnes löydämme hashin 920ECF10:

Haluttu salasana on siis sgfnyd.

On syytä huomata, että palautettu ketju ei aina sisällä vaadittua hash-arvoa h . Tämä on mahdollista, kun tapahtuu H- tai R-funktion törmäys . Anna esimerkiksi tiiviste FB107E70, joka tietyssä vaiheessa luo salasanan kiebgt:

Mutta FB107E70 ei näy salasanan luomassa ketjussa aaaaaa. Tätä kutsutaan vääräksi positiiviseksi . Tässä tapauksessa jätämme vastaavuuden huomioimatta ja jatkamme h :n luoman sekvenssin arviointia . Jos luotu sekvenssi saavuttaa pituuden k ilman hyviä osumia, tämä tarkoittaa, että etsittyä salasanaa ei ole koskaan löydetty esilasketuista ketjuista.

Taulukon sisältö ei riipu käänteisen hajautusarvon arvosta, se lasketaan etukäteen ja sitä käytetään vain pikahakuun. Ketjun pituuden lisääminen pienentää pöydän kokoa, mutta lisää aikaa, joka kuluu halutun elementin löytämiseen ketjusta.

Yksinkertaisilla hash-ketjuilla on useita haittoja. Vakavin on mahdollisuus yhdistää kaksi ketjua yhdeksi (sama arvon tuottaminen eri ketjuissa). Kaikki yhdistämisen jälkeen luodut arvot ovat samat molemmissa ketjuissa, mikä kaventaa salasanojen määrää. Koska esigeneroituja ketjuja ei tallenneta kokonaisuudessaan, on mahdotonta verrata kaikkia luotuja arvoja tehokkaasti keskenään. Hajautusfunktiosta H huolehtii pääsääntöisesti salasanasalauksen tarjoava osapuoli, joten suurin ongelma on pelkistysfunktiossa R.

Toinen vakava ongelma on sellaisen R-toiminnon valinta, joka luo salasanoja vaaditulla kattavuudella ja jakelulla. Tulostusaakkosrajoitus on vakava rajoite tällaisen funktion valinnassa.

Rainbow-pöydät

Rainbow-pöydät ovat jatkoa hash-ketjutaulukon idealle. Ne ratkaisevat tehokkaasti törmäysongelman ottamalla käyttöön pelkistysfunktioiden sarjan R 1 , R 2 , …, R k . Pelkistysfunktioita käytetään vuorotellen hajautusfunktion välissä: H, R 1 , H, R 2 , …, H, R k . Tällä lähestymistavalla kaksi ketjua voidaan yhdistää vain, jos saman iteroinnin arvot täsmäävät . Siksi törmäysten varalta riittää tarkistaa vain ketjujen lopulliset arvot, mikä ei vaadi lisämuistia. Taulukon kokoamisen viimeisessä vaiheessa voit etsiä kaikki yhdistetyt ketjut, jättää vain yhden ja luoda uusia täyttääksesi taulukon tarvittavalla määrällä erilaisia ​​ketjuja. Tuloksena olevat ketjut eivät ole täysin vapaita törmäyksistä, mutta ne eivät kuitenkaan sulaudu täysin yhteen.

Vähennysfunktioiden sekvenssien käyttö muuttaa tapaa, jolla taulukosta haetaan. Koska hash löytyy mistä tahansa ketjusta, on luotava k erilaista ketjua:

Myös väärän positiivisen määritelmä muuttuu: jos "arvaamme" väärin halutun tiivisteen sijainnin, tämä hylkää vain yhden k generoidusta ketjusta; samaan aikaan voi silti olla mahdollista löytää oikea hash tälle taulukkoketjulle, mutta eri kohdasta.

Vaikka sateenkaaritaulukot vaativat enemmän ketjuja seuratakseen, niissä on suurempi salasanojen tiheys taulukkomerkintää kohti. Toisin kuin hash-ketjutaulukossa, useiden pelkistystoimintojen käyttö vähentää mahdollisten törmäysten määrää taulukossa, mikä mahdollistaa sen kasvamisen ilman suuren ketjujen yhdistämisen vaaraa.

Esimerkki

Siinä on hash ( re3xes) kääntämistä varten (vastaavan salasanan palauttamiseksi) ja sateenkaaritaulukko, joka on saatu käyttämällä kolmea vähennystoimintoa.

  1. Laske ketjun pituus 1 alkuperäisestä tiivisteestä: R 3 ("re3xes")="rambo". Tämä salasana ei ole minkään taulukkoketjun loppu.
  2. Laske ketju, jonka pituus on 2: R 3 (H(R 2 ("re3xes")))="linux23".
  3. Tämä salasana löytyy taulukosta. Otetaan löydetyn ketjun alku (salasana passwd).
  4. Palautamme pöytäketjun, kunnes saamme alkuperäisen tiivisteen re3xes.
  5. Haluttu hash löytyy ketjusta, hyökkäys onnistuu. Tätä hash-arvoa edeltävä salasana cultureon haettava salasana.

Aika ja muisti

Sateenkaaritaulukko luodaan rakentamalla mahdollisten salasanojen ketjuja. Tällaisten taulukoiden luominen vaatii enemmän aikaa kuin tavallisten hakutaulukoiden luominen, mutta paljon vähemmän muistia (jopa satoja gigatavuja, kun tavallisten N sanan taulukoiden tilavuus on, sateenkaaritaulukot tarvitsevat vain noin N 2/3 ). Samaan aikaan, vaikka ne vaativat enemmän aikaa (verrattuna yksinkertaisiin menetelmiin, kuten sanakirjahyökkäys ) alkuperäisen salasanan palauttamiseen, ne ovat käytännössä toteuttamiskelpoisempia (jos haluat rakentaa tavallisen taulukon 6-merkkiselle salasanalle tavumerkeillä, tarvitset 256 6 = 281 474 976 710 656 muistilohkoa, kun taas sateenkaarelle - vain 256 6 ⅔ = 4 294 967 296 lohkoa).

Taulukot voivat murtaa vain hajautusfunktion, jota varten ne on luotu, eli MD5 -taulukot voivat murtaa vain MD5-tiivistefunktion. Tämän tekniikan teorian kehitti Philippe Oechslin [2] nopeana muunnelmana aika-muistin kompromissista [3] . Teknologiaa käytettiin ensimmäisen kerran Ophcrack -ohjelmassa Microsoft Windowsissa käytettyjen LanMan-tiivisteiden ( LM-hash ) murtamiseen . Myöhemmin kehitettiin edistyneempi ohjelma RainbowCrack , joka voi toimia useiden hajautusten kanssa, esimerkiksi LanMan, MD5, SHA1 ja muut.

Seuraava askel oli UDC -ohjelman luominen , jonka avulla voit rakentaa Hybrid Rainbow -taulukoita ei merkkijoukon, vaan sanakirjojen avulla, jonka avulla voit palauttaa pidempiä salasanoja (itse asiassa rajoittamattoman pituisia).

Sovellus

Taulukoita luotaessa on tärkeää löytää paras toisiinsa liittyvien parametrien suhde:

Yllä olevat parametrit riippuvat taulukon luomisen aikana määritetyistä asetuksista:

Tässä tapauksessa generointiaika riippuu lähes yksinomaan halutusta valinnan todennäköisyydestä, käytetystä merkistöstä ja salasanan pituudesta. Taulukoiden viemä tila riippuu halutusta nopeudesta valita 1 salasana valmiista taulukoista.

Vaikka sateenkaaritaulukoiden käyttö helpottaa raa'an voiman (eli raa'an voiman ) käyttöä salasanojen arvaamiseen, joissakin tapauksissa niiden luomiseen/käyttöön tarvittava prosessointiteho ei salli yksittäisen käyttäjän saavuttaa haluttuja tuloksia hyväksyttävässä ajassa. . Esimerkiksi salasanoille, jotka ovat enintään 8 merkkiä ja jotka koostuvat kirjaimista, numeroista ja erikoismerkeistä, jotka on !@#$%^&*()-_+=tiivistetty MD5-algoritmilla, voidaan luoda taulukoita seuraavilla parametreilla:

Samaan aikaan salasanan löytämisen todennäköisyys näillä taulukoilla on 0,7542 (75,42 %), itse taulukot vievät 596 GiB , niiden luominen Pentium-3 1 GHz -tietokoneella kestää 3 vuotta ja 1 salasanan etsiminen valmiiden taulukoiden käyttäminen vie enintään 22 minuuttia.

Taulukon luontiprosessi voidaan kuitenkin rinnastaa, esimerkiksi yhden taulukon laskenta edellä mainituilla parametreilla kestää noin 33 tuntia. Tässä tapauksessa, jos meillä on käytössämme 100 tietokonetta, kaikki taulukot voidaan luoda 11 päivässä.

Suojaus sateenkaaripöytiä vastaan

Yksi yleisimmistä suojautumismenetelmistä hakkerointia vastaan ​​sateenkaaritaulukoiden avulla on peruuttamattomien hash-funktioiden käyttö, joihin sisältyy suola (" suola ", "muuntaja"). Siemenen ja salasanan sekoittamiseen on monia mahdollisia järjestelmiä. Harkitse esimerkiksi seuraavaa toimintoa salasanan hajautusarvon luomiseksi:

hash = MD5 (salasana + suola)

Tällaisen salasanan palauttamiseksi hyökkääjä tarvitsee taulukot kaikille mahdollisille suola-arvoille. Tällaista mallia käytettäessä suolan tulee olla riittävän pitkä (6‒8 merkkiä), muuten hyökkääjä voi laskea kullekin suolaarvolle taulukot, satunnaiset ja erilaiset kullekin salasanalle. Siten kahdella identtisellä salasanalla on eri hash-arvot, ellei samaa suolaa käytetä.

Pohjimmiltaan suola lisää salasanan pituutta ja mahdollisesti monimutkaisuutta. Jos taulukko on suunniteltu tietylle pituudelle tai rajoitetulle merkkijoukolle, suola voi estää salasanan palauttamisen. Esimerkiksi vanhoissa Unix-salasanoissa käytettiin suolaa, joka oli vain 12 bittiä pitkä. Tällaisten salasanojen murtamiseen hyökkääjän täytyi laskea vain 4096 taulukkoa, jotka voidaan vapaasti tallentaa teratavuisille kiintolevyille. Siksi nykyaikaisissa sovelluksissa he käyttävät yleensä pidempää suolaa. Esimerkiksi bcrypt - hajautusalgoritmi käyttää 128-bittistä suolaa [4] . Tämä suolan pituus tekee esilaskennasta yksinkertaisesti merkityksettömän. Toinen mahdollinen tapa torjua esilaskentahyökkäyksiä on avainten venyttely .  Esimerkiksi:

avain = hash (salasana + suola) 1 - 65536 do avain = hash(avain + salasana + suola)

Tämä menetelmä vähentää esilaskennan tehokkuutta, koska väliarvojen käyttö pidentää yhden salasanan laskemiseen tarvittavaa aikaa ja vähentää siten niiden laskelmien määrää, jotka hyökkääjä voi suorittaa tietyllä aikavälillä [5] Tätä menetelmää käytetään seuraavat hajautusalgoritmit: MD5 , joka käyttää 1000 toistoa, ja bcrypt . [6] . Vaihtoehtona on käyttää näppäinvahvistusta , jota usein luullaan näppäinvenyttelyksi .  Tätä menetelmää käyttämällä suurennamme avaimen kokoa lisäämällä satunnaista suolaa, joka sitten poistetaan hiljaa, toisin kuin avaimen venyttämisessä, jossa suola säilyy ja sitä käytetään myöhemmissä iteraatioissa [7] .

Käyttö

Käytännössä kaikki Unix , GNU/Linux ja BSD OS -jakelut käyttävät hajautusarvoja suolan kanssa järjestelmän salasanojen tallentamiseen, vaikka monet sovellukset, kuten Internet-komentosarjat, käyttävät yksinkertaista tiivistettä (yleensä MD5 ) ilman "suolaa". Microsoft Windows- ja Windows NT -käyttöjärjestelmät käyttävät LM -hash- ja NTLM -tiivisteitä , jotka eivät myöskään käytä "suolaa", mikä tekee niistä suosituimpia sateenkaaritaulukoiden luomisessa.

Muistiinpanot

  1. ↑ Hellman M. Kryptusanalyyttinen aika-muistin kompromissi  // IEEE Transactions on Information Theory. - 1980. - heinäkuu ( osa 26 , nro 4 ). - S. 401-406 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1980.1056220 .
  2. ↑ Philippe Oechslin . Haettu 28. elokuuta 2006. Arkistoitu alkuperäisestä 23. marraskuuta 2005.
  3. ↑ Philippe Oechslinin esitys CRYPTO'03-konferenssissa Arkistoitu 26. syyskuuta 2007 Wayback Machinessa (PDF)
  4. ↑ Alexander, Steven. Salasanasuojaus nykyaikaisille käyttöjärjestelmille  //  ;login:. - USENIX Association, 2004. - Kesäkuu ( osa 29 , nro 3 ).
  5. ↑ Ferguson, Neils; Bruce Schneier. Käytännön kryptografia  . - Indianapolis: John Wiley & Sons , 2003. - ISBN 0-471-22357-3 .
  6. ↑ Provos, Niels; Mazieres, David Tulevaisuuteen mukautuva salasanajärjestelmä  (määrittämätön)  // FREENIX-kappaleen julkaisu: 1999 USENIX Annual Technical Conference. - Monterey, CA, USA: USENIX Association, 1999. - 6. kesäkuuta.
  7. ↑ U. Manber , "Yksinkertainen malli salasanojen murtamiseen yksisuuntaisten toimintojen perusteella", Computers & Security, v.15, n.2, 1996, s. 171-176. (Englanti)

Linkit