Haku sanakirjasta

Sanakirjahyökkäys ( englanninkielinen  sanakirjahyökkäys ) - hyökkäys turvajärjestelmää vastaan, jossa käytetään todentamiseen käytettävien tarkoitettujen salasanojen täydellisen luetteloimisen menetelmää ( englanniksi  brute-force ) , joka suoritetaan tarkistamalla peräkkäin kaikki sanat ( salasanat puhtaassa muodossaan tai salattuina). kuvat) tietyntyyppisiä ja -pituisia sanakirjasta , jotta järjestelmä voidaan myöhemmin hakkeroida ja päästä käsiksi turvaluokiteltuihin tietoihin . [1] Tämä tapahtuma on useimmissa tapauksissa luonteeltaan negatiivinen, vastoin moraali- ja lainsäädäntönormeja.

Sanakirjahaun ja salasanan monimutkaisuus

Todennäköisyysteorian näkökulmasta salasanan valinta on determinististä ja loogista. Salasana voi olla: syntymäaika, nimi, esine, numerosarja, kirjainsarja näppäimistön välissä. Yleisessä tapauksessa yllä oleva on ketjutettu .

Näistä oletuksista on seurauksena , että salasanan valinnan ennakkomäärittelyllä on keskeinen rooli sanakirjahakumenetelmän perustana olevien algoritmien valinnassa .

Hyökkäyksiä on kahdenlaisia:

On mahdollista laskea salasanan vahvuuspisteet erityisesti onnistuneiden sanakirjahyökkäysten osuuden määrittämiseksi . Onnistumisen todennäköisyyspisteet voidaan määritellä sanakirjahyökkäyksessä murrettujen salasanojen määrän suhteeksi yritysten kokonaismäärään.

Historiallista tietoa

Internet  Wormin käyttö vuonna 1988 tarjoaa hyvin dokumentoidun tapauksen salasanan murtamisesta. [2] Mato yritti murtaa salasanoja työskentelemällä sanakirjojen kanssa. Hyökkäyksen ensimmäisessä vaiheessa käytettiin sanajoukkoa, joka sisälsi Unix-järjestelmän salasanatiedostosta otettuja käyttäjätunnuksia. Jos tämä ei onnistunut, käytettiin sisäistä sanakirjaa 432 yleisesti käytetystä Internetin ammattislangista. Jos toinen vaihe ei onnistunut, käytettiin 24474 sanan Unix -sanakirjaa. Mato tarkisti myös tyhjän salasanan. Hyökkäyssivustot raportoivat, että noin 50 % salasanoista murtui onnistuneesti tällä strategialla.

Seuraava askel oli Daniel Kleinin työ .  [3] Saadakseen tuloksiaan hän keräsi salattuja Unix- järjestelmän salasanatiedostoja . Tämä kokoelma sisälsi noin 15 000 erilaista käyttäjätunnus/salasana -paria ( kirjautuminen/salasana ) . Klein rakensi joukon sanakirjoja ja joukon mekanismeja permutaatioiden mahdollistamiseksi. Hänen toimittamassaan sanakirjassa oli noin 60 000 kohtaa. Tämä arkki sisälsi nimiä, paikkoja, kuvitteellisia viittauksia, raamatullisia termejä, ilmaisuja W. Shakespearen runoista jne. Sovellettuaan permutaatiostrategiaa (isojen kirjainten käyttö, ilmeiset korvaukset, numeroiden permutaatiot) hän sai yli 3,3:n salasanatilan miljoona mahdollisuutta. Tämän sanakirjan käyttö auttoi Kleinia murtamaan 24,2 % kaikista salasanoista tietyillä palvelimilla.  

Vuosina 1991-1992. Eugene Spafford( eng.  Eugene Spafford ) onnistui rakentamaan tilastojen perusteella sanakirjan, jonka avulla 20 % salasanoista valituilla palvelimilla murtui. [neljä]

Vuonna 2000 Cambridgen yliopiston tutkijaryhmä suoritti tutkimuksen, jossa hyökättiin 195 hajautettua salasanaa vastaan, joista 35 % murtui onnistuneesti. [5]

Taulukko: Systemaattisessa tutkimuksessa löydettyjen salasanojen prosenttiosuus
Tutkija(t) / projekti Aika Salasanat vahvistettu Löydön prosenttiosuus, [%]
Internet-mato [2] 1988 tuhansia ~50
Kleinin tutkimus [3] 1990 15 000 24.2
Spaffordin tutkimus[neljä] 1992 13787 20.0
Cambridgen yliopiston tutkijat [5] 2000 195 35.0

Sanakirjan rakentamisen perusperiaatteet

Useimmissa salasanoissa on foneettinen samankaltaisuus luonnollisen (englannin) kielen sanojen kanssa; Syynä tähän on helppo muistaa tällaiset tiedot tietystä salasanasta. Tämä ominaisuus otetaan huomioon "Markov-suodattimissa", jotka perustuvat Markov-ketjuun , joka on normaali tekniikka luonnollisen kielen käsittelyssä. Ei-aakkosmerkkien esiintyminen salasanassa voidaan tulkita tilakoneen soveltamiseksi tiettyyn elementtijoukkoon.

Markov-suodattimet

Ihmisen luoma aakkosellinen salasana jakautuu epätasaisesti aakkosjärjestyksen tilaan. Tämä ehto voidaan ottaa suurella tarkkuudella huomioon nolla- ja ensimmäisen asteen "Markov-suodattimissa": [6]

  1. nollakertainen Markov-malli : jokainen symboli generoidaan oman todennäköisyysjakauman mukaan ja riippumatta aikaisemmista symboleista.
  2. ensimmäisen asteen Markovin malli : jokaiselle symbolien digrammille (järjestetylle parille) on määritetty todennäköisyys ja jokainen symboli generoidaan ehdollisesti edellisestä.

Matemaattisesti,

Markovin mallin nollajärjestys:

Markov-mallin ensimmäinen tilaus:

missä  on merkkijonon jakaantumistodennäköisyys,  on tämän sarjan luonne,  on yksittäisen merkin tai kaavan esiintymistiheys tekstissä.

Epätodennäköisten merkkijonojen poistamiseksi sanakirjasta käytetään todennäköisyyden diskretisointia - otetaan käyttöön kaksitasoinen järjestelmä, jossa on kynnys :

Markovin mallin nollajärjestys:

Markov-mallin ensimmäinen tilaus:

Huomautukset

  1. ensimmäisen asteen Markov-malli näyttää parempia tuloksia (antaa suuremman hakkerointiprosentin) verrattuna nolla-asteen Markov-malliin . Poikkeuksena on tapaus, jossa salasanastrategiassa käytetään lyhenteitä, jotka koostuvat abstraktin lauseen jokaisen sanan ensimmäisistä kirjaimista;
  2. kirjaimien taajuusjakauma salasanassa riippuu tietystä kielestä, jolle sanakirja on käännetty (tämän menetelmän yleistys on oletettujen kielten yhdistelmä salasanan luomiseksi).

Suodattimet tilakoneilla

Tilakoneiden luomiseksi otetaan käyttöön joitain rajoituksia ja oletuksia, jotka liittyvät murtautuneeseen salasanaan:

  1. aakkosnumeerisessa salasanassa kaikki numerot ovat lopussa;
  2. aakkosellisen salasanan ensimmäinen kirjain kirjoitetaan todennäköisemmin isolla kuin muut kirjaimet;
  3. aakkosellisessa salasanassa pienten kirjainten määrä on suurempi kuin isojen kirjainten määrä.

Deterministiset äärelliset automaatit ovat ihanteellisia keinoja lausekkeille, joilla on ehdotetut rajoitukset. [6]

Ensimmäinen askel äärellisiin automaateihin perustuvan sanakirjan rakentamisessa on luoda säännöllisten lausekkeiden sarja ( \" pienet kirjaimet" , \"isot ennen pieniä kirjaimia" , \"kaikki isot kirjaimet tulevat ennen pieniä kirjaimia" jne.).

Sanakirja määritellään joukkona sanoja, jotka vastaavat Markov-suodattimia, ja rajallinen määrä niihin käytettyjä säännöllisiä lausekkeita .

Algoritmit

Nolla-asteen Markovin mallin muokattu sanakirja

Sanakirjan rakentamiseen käytetty algoritmi eroaa hieman nollatason Markov-suodattimesta (tässä tapauksessa sanakirjan eri sanapituuksille käytetään eri kynnystä ). [6]

Muokattu sanakirja määritellään nimellä

Kirjoita suodatin (sanakirja) uudelleen additiiviseen muotoon

missä .

Anna . Sitten määrittelemme osittaiset sanakirjat . Huomaa, että se on määritelty, koska , joten se ei riipu valinnasta .

Minkä tahansa etuliitteen osittaisessa sanakirjassa on kaikki mahdolliset merkkijonot , jotka voidaan liittää kyseiseen etuliitteeseen , joten tuloksena oleva merkkijono täyttää kaikki Markovin ominaisuudet.

Yleensä voidaan kirjoittaa osittainen sanakirja

Rekursiivinen algoritmi osittaisen sanakirjan koon laskemiseen [6]

osittainen_koko1 ( nykyinen_pituus , taso ) { jos taso > = kynnys : palauttaa 0 jos kokonaispituus = nykyinen_pituus : palauttaa 1 summa = 0 jokaiselle merkille aakkosissa summa = summa + osittainen_koko1 ( nykyinen_pituus + 1 , taso + mu ( merkki } ) paluu summa _

Rekursiivinen algoritmi avaimen löytämiseksi sanakirjasta (ottaa syötteeksi avaintilassa olevan indeksin ja palauttaa vastaavan avaimen ) [6]

get_key1 ( nykyinen_pituus , indeksi , taso ) { if total_length = nykyinen_pituus : palauta "" summa = 0 jokaiselle merkille aakkosissa new_level = taso + mu ( merkki ) // haettiin esilasketusta taulukosta koko = partial_size1 [ current_length + 1 ] [ new_level ] if summa + size > index // '|' viittaa merkkijonon ketjutuksen paluumerkkiin | get_avain1 ( nykyinen_pituus + 1 , indeksi - summa , uusi_taso ) summa = summa + koko // ohjaus ei pääse tähän tulosta "indeksi suurempi kuin näppäintilan koko" ; poistu }

Huomautukset

  1. partial_size1 arvioidaan vain kerran (ei kerran avainta kohti );
  2. get_key1 lasketaan kryptausanalyysin aikana ;
  3. nähdäksesi koko avaintilan , sinun on suoritettava get_key1 , jonka arvo on current_length = 0 ja level = 0 .
Ensimmäisen asteen Markovin mallin sanasto

Kuten nollajärjestyksen menetelmässä, osittaiset sanakirjat määritellään .

Kun olet etsinyt merkkijonon osittaisesta sanakirjasta , sinun on huolehdittava viimeisestä merkistä (ottaen huomioon kaava ja sen jakautuminen)

osittainen_koko2 ( nykyinen_pituus , edellinen_merkki , taso ) { jos taso >= kynnys : palauttaa 0 , jos kokonaispituus = nykyinen_pituus : palauttaa 1 summa = 0 jokaiselle merkille aakkosissa , jos nykyinen_pituus = 0 uusi_taso = mu ( merkki ) else new_level = taso + mu ( esimerkki ) , merkki ) summa = summa + osittainen_koko2 ( nykyinen_pituus + 1 , merkki , uusi_taso ) } get_key2 ( nykyinen_pituus , indeksi , edeltävä merkki , taso ) { if total_length = current_length : return "" summa = 0 merkille aakkosissa if current_length = 0 new_level = mu ( merkki ) else _ _ uusi_taso = taso + mu ( edellinen_merkki , merkki ) koko = osittainen_koko2 ( nykyinen_pituus + 1 , merkki , uusi_taso ) if summa + koko > indeksin palautusmerkki | _ get_key2 ( nykyinen_pituus + 1 , indeksi - summa , merkki , uusi_taso ) summa = summa + koko // ohjaus ei pääse tähän tulosta "indeksi suurempi kuin näppäintilan koko" ; poistu }

Kommentti

  1. hybridialgoritmien käyttö antaa parempia tuloksia sanakirjahaun kryptausanalyysissä . [6]

Perusvastaajat sanakirjahyökkäyksiä vastaan

Verkkosanakirjahyökkäysten torjunta

On olemassa useita tapoja torjua online-sanakirjahyökkäyksiä :

  1. viivästetty vastaus : annetulle  kirjautumistunnus/salasana - parille palvelin käyttää pientä, erityisesti luotua Kyllä/ei vastausviivettä (esimerkiksi korkeintaan yksi vastaus sekunnissa;
  2. tilin lukitus :  tili lukitaan useiden (ennalta määrätyn määrän) epäonnistuneiden kirjautumis-/salasanayritysten jälkeen ( esimerkiksi tili lukitaan tunniksi viiden väärän salasanayrityksen jälkeen);
  3. käyttämällä Proof-of-Work -ohjelmaa ;
  4. suolan ja hitaiden hajautustoimintojen käyttö asiakaspuolella.

Huomautukset

  1. nämä toimenpiteet estävät useimmissa tapauksissa sanakirjahyökkäyksen ja siihen liittyvän salasanan murtamisen kohtuullisessa ajassa;
  2. Verkkosanakirjahyökkäysten torjunnan toteutuksen tiedot mahdollistavat käyttäjätilien pitkäaikaisen eston hyökkäysjakson oikealla valinnalla.
User Authentication Protocols

Oletuksena on, että tämän tilin käyttäjä syöttää oikean kirjautumistunnuksen/salasanan yhdistelmän , kun taas sanakirjahyökkäyksen suorittaa automaattinen ohjelma. Vaaditaan, että yrityksen syöttää oikea salasana on "laskennallisesti yksinkertainen" ihmisille ja "laskennallisesti vaikea" koneille.

Protokolla on testi, jonka avulla palvelin voi erottaa ihmisen robotista . Sen ehdotti ensimmäisenä M. Naor ( eng.  Moni Naor ), ja sitä kutsutaan käänteiseksi Turingin testiksi ( eng.  Reverse Turing -testi (RTT) ), toinen nimi sille on CAPTCHA . Käänteisen Turingin testin on täytettävä seuraavat ehdot: [7]

  1. automaattinen sukupolvi;
  2. toteuttamisen helppous henkilölle;
  3. koneiden monimutkaisuus;
  4. pieni mahdollisuus arvata vastaus.

Kuvatesti täyttää kaikki yllä olevat ehdot.

Protokolla 1 (Turingin käänteisen testin yhdistelmä minkä tahansa autentikointijärjestelmän kanssa) [8]

Käyttäjää pyydetään vastaamaan RTT-sanomaan ennen autentikoinnin alkamista (ennen sisäänkirjautumistunnuksen/salasanan syöttämistä ).

Kommentti

Tämä menetelmä ei ole optimaalinen suurille järjestelmille, koska käyttäjän RTT-testin vastauksen syöttäminen joka kerta ennen autentikointia on melko ärsyttävää ja psykologisesti vaikeaa . [kahdeksan]

Protokolla 2 (käyttäjän sisäänkirjautumisprotokolla, protokollan 1 modifioitu versio) [8]

Jos käyttäjä kirjautuu sisään onnistuneesti, palvelin lähettää käyttäjän tietokoneelle evästeen , joka sisältää tietueen käyttäjän todennuksesta ja tämän viestin voimassaoloajasta (olettaen kyvyttömyys muuttaa evästeen tietoja ilmoittamatta siitä palvelimelle (tämä voidaan taata lisäämällä MAC ( viestin todennuskoodi ), joka lasketaan vain palvelimen tuntemalla avaimella ). 

1. käyttäjä syöttää sisäänkirjautumistunnuksen/salasanan . Jos hänen tietokoneessaan on tämän palvelimen tarjoamia evästeitä , palvelin hakee evästeen ; 2. sisäänkirjautumisen/salasanan todennus ; 3. Jos kirjautumistunnus/salasana ovat totta, silloin a. jos eväste on kelvollisessa tilassa (vahvistettu palvelimen muokkauspäivämäärään mennessä) ja käyttäjän tunnistava (ja evästeeseen tallennettu tietue ) vastaa syötettyä kirjautumistunnusta , käyttäjälle myönnetään pääsy palvelimeen; b. muussa tapauksessa palvelin luo RTT-testin ja lähettää sen käyttäjälle. Käyttäjä pääsee palvelimelle vasta oikean vastauksen jälkeen RTT-pyyntöön ; 4. jos kirjautumistunnus/salasana -pari on väärä, niin a. todennäköisyydellä (jos tämä on järjestelmäparametri, esimerkiksi ), käyttäjää tarjotaan läpäisemään RTT-testi ja vastauksesta riippumatta pääsy palvelimeen estetään; b. todennäköisyydellä yhteys estetään välittömästi.

Huomautukset

  1. oletetaan, että käyttäjä käyttää pientä määrää tietokoneita ja on epätodennäköistä, että hyökkäys suoritetaan jostain niistä;
  2. kirjautumisprosessissa käytetään verkkoselainta ja evästeitä tarvitaan;
  3. Protokollan algoritmi on rakennettu siten, että RTT-sanoman generointi tapahtuu vain kahdessa tapauksessa: kun käyttäjän tietokoneessa oleva eväste on virheellinen ja kun kirjautumis-/salasana-pari on virheellinen. Tämän avulla voit purkaa palvelimia käyttämällä tätä protokollaa;
  4. todennäköisyys on kirjautumis-/salasana -parin funktio . On tapauksia, joissa kiinteillä kirjautumis-/salasana -arvoilla tapahtuu joko vain tilin lukitseminen tai vain RTT-viestien luominen useiden virheiden tapauksessa.

Offline-sanakirjahyökkäysten torjunta

Offline - sanakirjahyökkäykset voidaan estää tai vaikeuttaa seuraavilla tavoilla:

  • tunnetun arvon lisääminen hajautussuolaan ( englanniksi suola ) 
  • käyttämällä hidasta hash-funktiota, esim. scrypt
Laitteiston toteutus

Trusted Platform Module (TPM)  on laitteistosiru, jonka avulla tietokoneet voivat pitää tiedot turvassa. Salaisten tietojen (jäljempänä authData ) hallussapito on välttämätöntä TPM-avaimien käyttämiseksi ja käyttämiseksi .

Hyökkäyksen aikana kryptanalyytikko voi oppia: [9]

  1. kirjaudu sisään saadaksesi authData ja TPM - vastaus tähän pyyntöön;
  2. yhteinen salaisuus( eng. share  secret ) liittyy authDataan ja TPM - vastaukseen .

Sanakirjojen kokoamista vastaanotetun tiedon perusteella käytetään offline-sanakirjahyökkäyksessä authDatan määrittämiseen .

Taistelumenetelmät - käyttämällä modifioitua SPEKE- salausmenetelmää( Simple Password Exponential Key Exchange ), joka perustuu Diffie-Hellman-avaintenvaihtoalgoritmiin (sallii kahden osapuolen luoda jaetun salaisuuden ( eng.  strong shared secret ), perustuu heikkoon yhteiseen salaisuuteen ( eng.  heikko salaisuus ), jonka he jakavat).

Protokolla (muokattu salausmenetelmä SPEKE)

1. käyttäjä suorittaa valtuutukseen vaaditun komennon authDatalla ; 2. käyttäjäprosessi ja TPM sisältyvät SPEKE-protokollaan
, käytetään heikkona jaettuna salaisuutena ;
3. Käyttäjäprosessi valitsee satunnaisen ja lähettää sen TPM :ään , jossa  on hash-funktio ; 4. TPM valitsee satunnaisen ja lähettää sen käyttäjäprosessille; 5. jokainen heistä laskee salaisuuden ; 6. korvataan HMAC - avaimella .


Huomautukset

  1. valinnan rajoitukset on kuvattu Diffie-Hellman-avaimenvaihtoalgoritmissa ;
  2. hash-funktion valinta määräytyy kryptoprosessorin ( TPM-sirun ) salausmenetelmän mukaan .
  3. protokollaa voidaan parantaa. [9]

Katso myös

Muistiinpanot

  1. Shirey R. Kommenttipyyntö : 4949 . – elokuu 2007.  
  2. 1 2 Spafford Eugene. Internet-mato: Crisis and Aftermath (englanniksi) . - ACM:n tiedonannot, kesäkuu 1989. - P. 678-687 .  
  3. 1 2 Daniel V. Klein. Tutkimus ja parannukset salasanasuojaukseen //  USENIX Association. – 1990.  
  4. 1 2 Spafford Eugene. Uudelleenkäytettävien salasanavaihtoehtojen tarkkaileminen  //  USENIX Association. - 31. heinäkuuta 1992. Arkistoitu alkuperäisestä 20. heinäkuuta 2011.
  5. 1 2 Yan Jianxin, Blackwell Alan, Anderson Ross, Gran Alasdair. Salasanojen muistettavuus ja turvallisuus - joitain empiirisiä tuloksia / Markus Kuhn. – syyskuuta 2000.  
  6. 1 2 3 4 5 6 Narayanan Arvind, Shmatikov Vitaly. Nopeat sanakirjahyökkäykset salasanoihin käyttämällä aika - avaruusvaihtoa . – 7.–11. marraskuuta 2005.  
  7. Naor Moni. Ihmisen varmistus silmukassa tai tunnistus Turingin testillä . – 13. syyskuuta 1996.  
  8. 1 2 3 Pinkas Benny, Sander Tomas. Salasanojen suojaaminen sanakirjahyökkäyksiä vastaan ​​.  
  9. 1 2 Chen Liqun, Ryan Mark. Ofine-sanakirjahyökkäys TCG TPM:n heikkoja valtuutustietoja vastaan ​​ja ratkaisu (englanti) .  

Linkit