Dicţionar search

Atacul de dicționar ( atac de dicționar englez ) - un atac asupra sistemului de securitate folosind metoda de enumerare completă ( forța brută engleză ) a parolelor destinate utilizate pentru autentificare , efectuat prin revizuirea secvențială a tuturor cuvintelor ( parole în forma lor pură sau criptate ). imagini) de un anumit tip și lungime din dicționar pentru a pirata ulterior sistemul și a avea acces la informații clasificate . [1] Acest eveniment, în cele mai multe cazuri, este de natură negativă, contrar normelor morale și legislative.

Căutare în dicționar și complexitate parole

Din punctul de vedere al teoriei probabilităților , alegerea unei parole este deterministă și logică. Parola poate fi: data nașterii, nume, obiect, un set de numere, o succesiune de litere strâns distanțate pe tastatură. În cazul general, cele de mai sus sunt concatenate .

Rezultatul acestor ipoteze este că predeterminarea în alegerea parolei joacă un rol cheie în alegerea algoritmilor pe care se bazează metoda de căutare în dicționar .

Există două tipuri de atacuri:

Online : atacuri în care singura modalitate prin care un atacator poate verifica dacă o anumită parolă este corectă este interacțiunea cu serverul.
Offline : un atac în care un atacator poate verifica toate parolele valide fără a fi nevoie să se întoarcă la server.

Este posibil să se calculeze un scor de putere a parolei, în special, pentru a determina proporția de atacuri de succes ale dicționarului . Scorul de probabilitate de succes poate fi definit ca raportul dintre numărul de parole sparte într- un atac de dicționar și numărul total de încercări.

Informații istorice

Utilizarea Internet Worm în 1988 oferă un caz bine documentat de spargere a parolelor. [2] Viermele a încercat să spargă parole lucrând cu o serie de dicționare. Prima etapă a atacului a folosit un set de cuvinte care conțineau nume de utilizator preluate din fișierul de parole al sistemului Unix. Dacă acest lucru nu a avut succes, a fost folosit un dicționar intern de 432 de cuvinte din jargon de pe Internet utilizate în mod obișnuit. Dacă al doilea pas nu a avut succes, a fost folosit un dicționar Unix de 24474 de cuvinte. Viermele a verificat și o parolă goală. Site-urile atacate au raportat că aproximativ 50% dintre parole au fost sparte cu succes folosind această strategie.

Următorul pas a fost opera lui Daniel Klein . [3] Pentru a furniza rezultatele sale, el a colectat fișiere criptate cu parole de sistem Unix . Această colecție conținea aproximativ 15.000 de perechi diferite nume utilizator/parolă ( login/parolă ) . Klein a construit o serie de dicționare și un set de mecanisme pentru a permite permutările. Dicționarul oferit de el a constat din aproximativ 60.000 de articole. Această fișă cuprindea nume, locuri, referințe fictive, termeni biblici, expresii din poemele lui W. Shakespeare etc. După aplicarea unei strategii de permutare (folosirea literelor majuscule, înlocuiri evidente, permutări de numere), a primit un spațiu de parolă de peste 3,3 milioane de posibilități. Folosirea acestui dicționar l-a ajutat pe Klein să spargă 24,2% din toate parolele de pe anumite servere.

În 1991-1992. Eugene Spafford( ing. Eugene Spafford ) a reușit să construiască, pe baza statisticilor, un dicționar cu care 20% din parolele de pe serverele selectate au cedat cracking-ului. [patru]

În anul 2000, o echipă de cercetători de la Universitatea din Cambridge a realizat un studiu în care au fost atacate 195 de parole hashed , dintre care 35% au fost sparte cu succes. [5]

Tabel: Procentul de parole găsite în cercetarea sistematică

Cercetător(i) / proiect	Timp	Parolele verificate	Procent de constatare, [%]
vierme de internet [2]	1988	mii	~50
Studiul lui Klein [3]	1990	15000	24.2
studiul lui Spafford[patru]	1992	13787	20,0
Cercetători de la Universitatea din Cambridge [5]	2000	195	35,0

Principii de bază pentru construirea unui dicționar

În majoritatea parolelor, există o similitudine fonetică cu cuvintele din limba naturală (engleză); motivul pentru aceasta este ușurința de a reține acest tip de informații despre o anumită parolă. Această proprietate este luată în considerare în „Filtrele Markov” bazate pe lanțul Markov , care este o tehnică standard în procesarea limbajului natural. Prezența caracterelor non-alfabetice în parolă poate fi interpretată ca aplicarea unei mașini de stări unui anumit set de elemente.

Filtre Markov

O parolă alfabetică generată de om este distribuită inegal în spațiul secvențelor alfabetice. Această condiție poate fi luată în considerare cu mare precizie în „filtrele Markov” de ordinul zero și primul: [6]

modelul Markov de ordinul zero : fiecare simbol este generat conform propriei distribuții de probabilitate și independent de simbolurile anterioare.
model Markov de ordinul întâi : fiecărei digrame (pereche ordonată) de simboluri i se atribuie o probabilitate și fiecărui simbol este generat în dependență condiționată de cel precedent.

Din punct de vedere matematic,

ordinul zero al modelului Markov:

P(\alpha )=\prod _{x\in \alpha }\nu (x),

primul ordin al modelului Markov:

P(x_{1}x_{2}\ldots x_{n})=\nu (x_{1})\prod _{i=1}^{n-1}\nu (x_{i+ 1 }\mid x_{i}),

unde este probabilitatea de distribuție a unei secvențe de caractere, este caracterul acestei secvențe, este frecvența unui caracter individual sau a unei diagrame în text. $P(\cdot )$ $x_{i}$ $\nu$

Pentru a elimina șirurile puțin probabile din dicționar, se utilizează discretizarea probabilității - este introdus un sistem cu două niveluri cu un prag : $\theta$

ordinul zero al modelului Markov:

D_{\nu ,\theta }=\{\alpha :\prod _{x\in \alpha }\nu (x)\geq \theta \},

primul ordin al modelului Markov:

D_{\nu ,\theta }=\{x_{1}x_{2}\ldots x_{n}:\nu (x_{1})\prod _{i=1}^{n-1 }\nu (x_{i+1}\mid x_{i})\geq \theta \}.

Remarci

modelul Markov de ordinul întâi arată rezultate mai bune (oferă un procent mai mare de hacking) în raport cu modelul Markov de ordinul zero . Excepția este atunci când strategia de parole folosește abrevieri formate din primele litere ale fiecărui cuvânt dintr-o propoziție abstractă;
distribuția de frecvență a literelor din parolă depinde de limba specifică pentru care este compilat dicționarul (o generalizare a acestei metode este combinația de limbi presupuse pentru crearea unei parole).

Filtre folosind mașini de stat

Pentru a crea mașini de stat , sunt introduse unele restricții și ipoteze în legătură cu parola spartă:

într-o parolă alfanumerică, toate numerele sunt la sfârșit;
prima literă dintr-o parolă alfabetică este mai probabil să fie scrisă cu majuscule decât celelalte;
într-o parolă alfabetică, numărul de litere mici este mai mare decât numărul de litere mari.

Automatele finite deterministe sunt mijloace ideale pentru expresii cu constrângerile propuse. [6]

Primul pas în construirea unui dicționar bazat pe automate finite este crearea unei secvențe de expresii regulate ( \" minuscule " , \ " majuscule înainte de litere mici " , \ " toate majusculele vin înainte de litere mici " , etc.).

Un dicționar este definit ca un set de cuvinte care se potrivesc cu filtrele Markov și cu un număr finit de expresii regulate aplicate acestora.

D_{\nu ,\theta ,\left\langle M_{i}\right\rangle }=\{\alpha :\prod _{x\in \alpha }\nu (x)\geq \theta, \,\există i:M_{i}\ni \alpha \}.

Algoritmi

Dicționar modificat al modelului Markov de ordinul zero

Algoritmul folosit pentru a construi dicționarul este ușor diferit de filtrul Markov de nivel zero (în acest caz, un prag diferit va fi folosit pentru diferite lungimi de cuvinte în dicționar ). [6] $\theta$

Dicționarul modificat este definit ca

D_{\nu ,\theta ,l}=\{\alpha :|\alpha |=l,\prod _{x\in \alpha }\nu (x)\geq \theta \}.

Rescrieți filtrul (dicționarul) sub formă de aditiv

D_{\nu ,\theta ,l}=\{\alpha :|\alpha |=l,\sum _{x\in \alpha }\mu (x)\geq \lambda \},

unde . $\mu (x)=\log \nu (x),\,\lambda =\log \theta$

Lasă . Apoi definim dicționare parțiale . Rețineți că este definit deoarece , prin urmare, nu depinde de alegerea . $\{\alpha :|\alpha |=l',\prod _{x\in \alpha }\nu (x)=\theta '\)$ $D_{\nu,\theta,l,\theta ',l'}=\{\beta :\alpha \beta \in D_{\nu,\theta,l))\)$ $D_{\nu,\theta,l,\theta ',l')$ $\prod _{x\in \alpha \beta }\nu (x)=\prod _{x\in \alpha }\nu (x)\prod _{x\in \beta }\nu (x )=\theta '\prod _{x\in \beta }\nu (x)$ $\alfa$

Pentru orice prefix , dicționarul parțial conține toate secvențele posibile de caractere care pot fi atașate acelui prefix , astfel încât șirul rezultat satisface toate proprietățile Markov.

În general, se poate scrie un dicționar parțial

\mid D_{\nu ,\,prag,\,total\,lungime,\,nivel,\,actual\,lungime}\mid

Algoritm recursiv pentru calcularea dimensiunii unui dicționar parțial [6]

dimensiune_parțială1 ( lungimea_actuală , nivel ) { dacă nivelul >= prag : returnează 0 dacă lungimea_totală = lungimea_actuală : returnează 1 sumă = 0 pentru fiecare caracter în alfabet sum = sum + dimensiune_parțială1 ( lungime_curent + 1 , nivel + mu ( car ) ) returnează sumă }

Algoritm recursiv pentru găsirea unei chei dintr-un dicționar (preia un index din spațiul de taste ca intrare și returnează cheia corespunzătoare ) [6]

get_key1 ( lungimea_actuală , index , nivel ) { if total_length = current_length : returnează „” sum = 0 pentru fiecare caracter din alfabet new_level = level + mu ( char ) // căutat din matrice precalculată dimensiune = partial_size1 [ current_length + 1 ][ new_level ] dacă sum + size > index // '|' se referă la concatenarea șirurilor return char | get_key1 ( lungimea_actuală + 1 , index - sumă , nou_nivel ) sum = sumă + dimensiune // controlul nu poate ajunge aici print "index mai mare decât dimensiunea keyspace" ; ieșire }

Remarci

partial_size1 este evaluat o singură dată (nu o dată pe cheie );
get_key1 este calculată în timpul criptoanalizei ;
pentru a vedea întregul keyspace , trebuie să rulați get_key1 cu current_length = 0 și level = 0 .

Vocabularul modelului Markov de ordinul întâi

Ca și în cazul metodei ordinului zero, dicționarele parțiale sunt definite .

După ce căutați un șir într-un dicționar parțial , trebuie să vă faceți griji cu privire la ultimul caracter (ținând cont de diagramă și distribuția acesteia)

partial_size2 ( lungimea_actuală , caracterul anterior , nivel ) { dacă nivelul >= prag : returnează 0 dacă lungimea_totală = lungimea_actuală : returnează 1 sumă = 0 pentru fiecare caracter din alfabet dacă lungimea_actuală = 0 nivel_nou = mu ( car ) altfel new_level = nivel + mu ( prev_char ) , char ) sum = sum + partial_size2 ( lungime_actuală + 1 , char , new_level ) } get_key2 ( lungimea_actuală , index , caracterul anterior , nivel ) { dacă lungimea_totală = lungimea_actuală : returnează „” sum = 0 pentru caracter în alfabet dacă lungimea_actuală = 0 new_level = mu ( car ) altfel new_level = level + mu ( prev_char , char ) size = partial_size2 ( current_length + 1 , char , new_level ) if sum + size > index return char | get_key2 ( lungimea_actuală + 1 , sumă index , caracter , nivel_nou ) _ sum = sum + size // controlul nu poate ajunge aici print "index mai mare decât dimensiunea keyspace" ; ieșire }

cometariu

utilizarea algoritmilor hibrizi dă rezultate mai bune pentru criptoanaliza prin căutare în dicționar . [6]

Contoare de bază pentru atacurile de dicționar

Contracararea atacurilor de dicționar online

Există mai multe moduri de a contracara atacurile de dicționar online :

răspuns întârziat : pentru perechea de autentificare/parolă furnizată , serverul utilizează o întârziere mică, special generată de răspuns Da/nu (de exemplu, nu mai mult de un răspuns pe secundă;
blocarea contului : un cont este blocat după mai multe (un număr prestabilit) încercări nereușite de conectare/parolă ( de exemplu, un cont este blocat timp de o oră după cinci încercări de parolă incorectă);
folosind Proof-of-Work ;
utilizarea funcțiilor de sare și hash lent pe partea clientului.

Remarci

aceste măsuri, în cele mai multe cazuri, previn un atac de dicționar și spargerea parolei însoțitoare într-un timp rezonabil;
Datele implementării contracarării atacurilor de dicționar online permit blocarea pe termen lung a conturilor de utilizator cu selectarea corectă a perioadei de atac.

Protocoale de autentificare a utilizatorului

Se presupune că combinația corectă de autentificare/parolă este introdusă de utilizatorul acestui cont , în timp ce atacul dicționarului este efectuat de un program automat. Este necesar ca încercarea de a introduce parola corectă să fie „computațional simplă” pentru oameni și „computațional dificilă” pentru mașini.

Protocolul este un test care permite serverului să distingă un om de un bot . A fost propus pentru prima dată de M. Naor ( ing. Moni Naor ) și se numește testul Reverse Turing ( ing. Testul Reverse Turing (RTT) ), un alt nume pentru acesta este CAPTCHA . Testul Reverse Turing trebuie să îndeplinească următoarele condiții: [7]

generare automată;
ușurința de implementare pentru o persoană;
complexitate pentru mașini;
șanse mici de a ghici răspunsul.

Testul de imagine satisface toate condițiile de mai sus.

Protocolul 1 (combinație a testului invers al lui Turing cu orice sistem de autentificare) [8]

Utilizatorului i se cere să răspundă la un mesaj RTT înainte de a începe autentificarea (înainte de a introduce datele de conectare/parola ).

cometariu

Această metodă nu este optimă pentru sistemele mari, deoarece este destul de iritant și dificil din punct de vedere psihologic pentru utilizator să introducă răspunsul la testul RTT de fiecare dată înainte de autentificare . [opt]

Protocolul 2 (protocol de conectare a utilizatorului, versiunea modificată a protocolului 1) [8]

Dacă utilizatorul este conectat cu succes, serverul trimite un cookie către computerul utilizatorului care conține o înregistrare a autentificării utilizatorului și perioada de valabilitate a acestui mesaj (presupunând că incapacitatea de a modifica informațiile din cookie fără a anunța serverul (acest lucru poate fi garantat prin adăugarea unui MAC ( cod de autentificare a mesajelor ), care se calculează folosind o cheie cunoscută doar de server).

1. utilizatorul introduce login/parola . Dacă computerul său conține cookie -uri furnizate de acest server, cookie -ul este preluat de server; 2. autentificare autentificare /parolă ; 3. dacă autentificare/parola sunt adevărate, atunci A. dacă cookie -ul este într-o stare validă (verificată după data la care a fost modificat de către server) și înregistrarea de identificare a utilizatorului (și stocată în cookie ) se potrivește cu autentificarea introdusă , atunci utilizatorului i se acordă acces la server; b. în caz contrar, serverul generează un test RTT și îl trimite utilizatorului. Utilizatorul are acces la server numai după un răspuns corect la cererea RTT ; 4. dacă perechea login/parolă este incorectă, atunci A. cu o probabilitate (unde este un parametru de sistem, de exemplu ), utilizatorului i se propune să treacă un test RTT și indiferent de răspuns, accesul la server este blocat;

p

0\leq p\leq 1

p=0,05

b. cu probabilitate , conexiunea este blocată imediat.

1-p

Remarci

se presupune că utilizatorul folosește un număr mic de computere și este puțin probabil ca atacul să fie efectuat de la unul dintre ele;
procesul de conectare folosește un browser web și sunt necesare cookie -uri ;
Algoritmul protocolului este construit în așa fel încât procesul de generare a unui mesaj RTT să aibă loc doar în două cazuri: când introducerea cookie -ului de pe computerul utilizatorului este invalidă și când perechea login/parolă este incorectă. Acest lucru vă permite să descărcați servere folosind acest protocol;
probabilitatea este o funcție a perechii login/parolă . Există cazuri când, pentru valori fixe de autentificare/parolă , fie vor avea loc numai blocări de cont, fie numai generarea de mesaje RTT în cazul unor erori multiple. $p$

Contracararea atacurilor de dicționar offline

Atacurile de dicționar offline pot fi prevenite sau îngreunate în următoarele moduri:

adăugarea unei valori cunoscute la hashing - salt ( în engleză sare )
folosind o funcție hash lentă, de ex. cripta

Implementarea hardware

Trusted Platform Module (TPM) este un cip hardware care permite computerelor să păstreze datele în siguranță. Deținerea de informații secrete (denumite în continuare authData ) este necesară pentru a accesa și utiliza cheile TPM .

În timpul atacului, criptoanalistul poate afla: [9]

autentificați -vă pentru authData și răspunsul TPM la această solicitare;
secret împărtășit( ing . secret partajat ) asociat cu authData și răspunsul TPM .

Compilarea dicționarelor pe baza informațiilor primite este utilizată într-un atac de dicționar offline pentru a determina authData .

Metode de luptă - folosind o metodă criptografică SPEKE modificată( Schimb exponențial de chei de parolă simplă ), care se bazează pe algoritmul de schimb de chei Diffie-Hellman (permite două părți să creeze un secret partajat $s$ ( ing. strong shared secret ), bazat pe un secret slab împărtășit $w$ ( ing. secret slab ), pe care îl împărtășesc).

Protocol (metoda criptografică modificată SPEKE)

1. utilizatorul execută comanda necesară pentru autorizarea cu authData ; 2. Procesul utilizatorului și TPM sunt incluse în protocolul SPEKE $d$
, folosind ca un secret slab împărtășit $d$ $w$ ;
3. Procesul utilizatorului selectează unul aleator și îl trimite la TPM , unde este funcția hash ; 4. TPM alege unul aleatoriu și trimite procesului utilizatorului; 5. fiecare dintre ele calculează un secret ; 6. este înlocuit cu ca cheie HMAC . $X$ $H(d)^{x)$ $H$
$y$ $H(d)^{y)$
$s=H(d)^{xy}$
$w$ $s$

Remarci

restricțiile privind alegerea sunt descrise în algoritmul de schimb de chei Diffie-Hellman ; $d,w,h,x,y$
alegerea funcției hash este determinată de metoda de criptare din criptoprocesor ( cip TPM ). $H$
protocolul este supus îmbunătățirii. [9]

Vezi și

Note

↑ Shirey R. Cerere de comentarii : 4949 . - august 2007.
↑ 1 2 Spafford Eugene. Viermele de internet: criză și consecințe (engleză) . - Comunicările ACM, iunie 1989. - P. 678-687 .
↑ 1 2 Daniel V. Klein. Un studiu și îmbunătățiri ale securității parolelor // Asociația USENIX. — 1990.
↑ 1 2 Spafford Eugene. Observarea alegerilor de parole reutilizabile // Asociația USENIX. - 31 iulie 1992. Arhivat din original la 20 iulie 2011.
↑ 1 2 Yan Jianxin, Blackwell Alan, Anderson Ross, Gran Alasdair. Memorabilitatea și securitatea parolelor - câteva rezultate empirice / Markus Kuhn. — septembrie 2000.
↑ 1 2 3 4 5 6 Narayanan Arvind, Shmatikov Vitaly. Atacurile rapide ale dicționarului asupra parolelor folosind compromisul timp- spațiu . — 7–11 noiembrie 2005.
↑ Naor Moni. Verificarea unui om în buclă sau Identificarea prin testul Turing . - 13 septembrie 1996.
↑ 1 2 3 Pinkas Benny, Sander Tomas. Securizarea parolelor împotriva atacurilor de dicționar .
↑ 1 2 Chen Liqun, Ryan Mark. Atacul de dicționar Ofine asupra datelor de autorizare slabe TCG TPM și soluție (engleză) .

Link -uri

RFC 2828 - Glosar de securitate pe internet
RFC 4949 - Glosar de securitate pe internet, versiunea 2
Dilema parolei puternice . Consultat la 13 noiembrie 2011. Arhivat din original pe 27 februarie 2012.
Dicționare (engleză) . Consultat la 13 noiembrie 2011. Arhivat din original pe 27 februarie 2012.
CAPTCHA (engleză) (link indisponibil) . Consultat la 13 noiembrie 2011. Arhivat din original pe 27 februarie 2012.
Oechslin Philippe. Realizarea unui schimb criptoanalitic mai rapid între timp și memorie (engleză) . Consultat la 13 noiembrie 2011. Arhivat din original pe 27 februarie 2012.
John the Ripper spargerea parolei (engleză) (downlink) . Consultat la 13 noiembrie 2011. Arhivat din original pe 27 februarie 2012.