Ordbokssökning

Dictionary attack ( English dictionary attack ) - en attack på säkerhetssystemet med metoden för fullständig uppräkning ( engelska brute-force ) av de avsedda lösenorden som används för autentisering , utförd genom att sekventiellt granska alla ord ( lösenord i deras rena form eller deras krypterade bilder) av en viss typ och längd från ordboken för att sedan hacka systemet och få tillgång till hemligstämplad information . [1] Denna händelse är i de flesta fall av negativ karaktär, i strid med moraliska och lagstiftande normer.

Ordbokssökning och lösenordskomplexitet

Ur sannolikhetsteoretisk synvinkel är valet av lösenord deterministiskt och logiskt. Lösenordet kan vara: födelsedatum, namn, objekt, en uppsättning siffror, en sekvens av bokstäver tätt placerade på tangentbordet. I det allmänna fallet är ovanstående sammanlänkade .

Resultatet av dessa antaganden är att förutbestämning av lösenordsval spelar en nyckelroll i valet av algoritmer som ordbokssökningsmetoden bygger på .

Det finns två typer av attacker:

Online : Attacker där det enda sättet för en angripare att verifiera att ett givet lösenord är korrekt är genom att interagera med servern.
Offline : En attack där en angripare kan kontrollera alla giltiga lösenord utan att behöva gå tillbaka till servern.

Det är möjligt att beräkna ett lösenordsstyrkepoäng, särskilt för att bestämma andelen framgångsrika ordboksattacker . Sannolikhetspoängen för framgång kan definieras som förhållandet mellan antalet knäckta lösenord i en ordboksattack och det totala antalet försök.

Historisk information

Användningen av Internet Worm 1988 ger ett väldokumenterat fall av lösenordssprickning. [2] Masken försökte knäcka lösenord genom att arbeta med en serie ordböcker. Det första steget av attacken använde en uppsättning ord som innehöll användarnamn hämtade från lösenordsfilen i Unix-systemet. Om detta inte lyckades användes en intern ordbok med 432 vanliga jargongord på Internet. Om det andra steget inte lyckades användes en Unix -ordbok med 24474 ord. Masken letade också efter ett tomt lösenord. Attackerade webbplatser rapporterade att cirka 50 % av lösenorden lyckades knäckas med denna strategi.

Nästa steg var Daniel Kleins arbete . [3] För att ge sina resultat samlade han in krypterade Unix -systemlösenordsfiler . Denna samling innehöll cirka 15 000 olika par av användarnamn/lösenord ( inloggning/lösenord ) . Klein konstruerade en serie ordböcker och en uppsättning mekanismer för att möjliggöra permutationer. Ordboken han tillhandahöll bestod av cirka 60 000 artiklar. Detta ark innehöll namn, platser, fiktiva referenser, bibliska termer, uttryck från W. Shakespeares dikter , etc. Efter att ha tillämpat en permutationsstrategi (användning av versaler, uppenbara ersättningar, permutationer av siffror) fick han ett lösenordsutrymme på mer än 3,3 miljoner möjligheter. Att använda denna ordbok hjälpte Klein att knäcka 24,2 % av alla lösenord på vissa servrar.

1991-1992. Eugene Spafford( sv. Eugene Spafford ) lyckades bygga, baserat på statistik, en ordbok med vilken 20 % av lösenorden på utvalda servrar dukade under för att spricka. [fyra]

År 2000 genomförde ett team av forskare från University of Cambridge en studie där 195 hashade lösenord attackerades, varav 35 % lyckades knäckas. [5]

Tabell: Andel lösenord hittade i systematisk forskning

Forskare/projekt	Tid	Lösenord verifierade	Procentandel av fynd, [%]
Internetmask [2]	1988	tusentals	~50
Kleins studie [3]	1990	15 000	24.2
Spaffords studie[fyra]	1992	13787	20.0
Forskare från University of Cambridge [5]	2000	195	35,0

Grundläggande principer för att skapa en ordbok

I de flesta lösenord finns det en fonetisk likhet med orden i naturligt (engelska) språk; Anledningen till detta är att det är lätt att komma ihåg denna typ av information om ett givet lösenord. Denna egenskap tas med i beräkningen i "Markov-filter" baserade på Markov-kedjan , som är en standardteknik inom naturlig språkbehandling. Förekomsten av icke-alfabetiska tecken i lösenordet kan tolkas som att en tillståndsmaskin tillämpas på en specifik uppsättning element.

Markov filter

Ett mänskligt genererat alfabetiskt lösenord är ojämnt fördelat i utrymmet av alfabetiska sekvenser. Detta tillstånd kan tas med i beräkningen med stor noggrannhet i "Markov-filter" av noll och första ordningen: [6]

nollordningens Markov-modell : varje symbol genereras enligt sin egen sannolikhetsfördelning och oberoende av tidigare symboler.
första ordningens Markov-modell : varje digram (ordnat par) av symboler tilldelas en sannolikhet och varje symbol genereras i villkorligt beroende av den föregående.

Matematiskt,

nollordning av Markov-modellen:

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

första beställningen av Markov-modellen:

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

var är sannolikheten för distribution av en sekvens av tecken, är karaktären av denna sekvens, är frekvensen av ett enskilt tecken eller digram i texten. $P(\cdot )$ $x_{i}$ $\nu$

För att eliminera osannolika strängar i ordboken används sannolikhetsdiskretisering - ett tvånivåsystem med en tröskel introduceras : $\theta$

nollordning av Markov-modellen:

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

första beställningen av Markov-modellen:

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 \}.

Anmärkningar

första ordningens Markov-modell visar bättre resultat (ger en högre procentandel av hackning) i förhållande till nollordningens Markov-modell . Undantaget är när lösenordsstrategin använder förkortningar som består av de första bokstäverna i varje ord i en abstrakt mening;
frekvensfördelningen av bokstäver i lösenordet beror på det specifika språk som ordboken är sammanställd för (en generalisering av denna metod är kombinationen av förmodade språk för att skapa ett lösenord).

Filter som använder tillståndsmaskiner

För att skapa tillståndsmaskiner introduceras vissa begränsningar och antaganden i förhållande till det knäckta lösenordet:

i ett alfanumeriskt lösenord är alla siffror i slutet;
den första bokstaven i ett alfabetiskt lösenord är mer sannolikt versal än de andra;
i ett alfabetiskt lösenord är antalet små bokstäver större än antalet stora bokstäver.

Deterministiska finita automater är idealiska medel för uttryck med de föreslagna begränsningarna. [6]

Det första steget i att bygga en ordbok baserad på finita automater är att skapa en sekvens av reguljära uttryck ( \" gemener\" , \"kaper före gemener" , \"alla versaler kommer före gemener" etc.).

En ordbok definieras som en uppsättning ord som matchar Markov-filter och ett ändligt antal reguljära uttryck som tillämpas på dem.

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

Algoritmer

Modifierad ordbok för nollordningens Markov-modell

Algoritmen som används för att bygga ordboken skiljer sig något från Markov-filtret på nollnivå (i det här fallet kommer en annan tröskel att användas för olika ordlängder i ordboken ). [6] $\theta$

Den modifierade ordboken definieras som

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

Skriv om filtret (ordboken) i additiv form

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

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

Låt . Sedan definierar vi partiella ordböcker . Observera att det är definierat eftersom , därför inte beror på valet av . ${\displaystyle \{\alpha :|\alpha |=l',\prod _{x\in \alpha }\nu (x)=\theta '\))$ ${\displaystyle D_{\nu ,\theta ,l,\theta ',l'}=\{\beta :\alpha \beta \in D_{\nu ,\theta ,l))\))$ ${\displaystyle 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$

För alla prefix innehåller den partiella ordlistan alla möjliga teckensekvenser som kan kopplas till det prefixet , så den resulterande strängen uppfyller alla Markov-egenskaper.

I allmänhet kan en delordbok skrivas

\mid D_{\nu,\,tröskel,\,total\,längd,\,nivå,\,aktuell\,längd}\miden

Rekursiv algoritm för att beräkna storleken på en partiell ordbok [6]

partial_size1 ( current_length , level ) { if level >= threshold : return 0 if total_length = current_length : return 1 summa = 0 för varje char i alfabetet summa = summa + partial_size1 ( current_length + 1 , level + mu ( char )) return summa }

Rekursiv algoritm för att hitta en nyckel från en ordbok (tar ett index i tangentutrymmet som indata och returnerar motsvarande nyckel ) [6]

get_key1 ( aktuell_längd , index , nivå ) { if total_length = current_length : returnera "" summa = 0 för varje char i alfabetet new_level = level + mu ( char ) // sett upp från förberäknad array size = partial_size1 [ current_length + 1 ][ new_level ] if sum + size > index // '|' hänvisar till strängsammansättning retur char | get_key1 ( aktuell_längd + 1 , index - summa , new_level ) summa = summa + storlek // kontrollen kan inte nå hit print "index större än knappsatsstorlek" ; avsluta }

Anmärkningar

partial_size1 utvärderas endast en gång (inte en gång per nyckel );
get_key1 beräknas under kryptoanalys ;
för att se hela tangentrymden måste du köra get_key1 med current_length = 0 och level = 0 .

Ordförråd av första ordningens Markov-modell

Precis som med nollordningsmetoden definieras partiella ordböcker .

Efter att ha slagit upp en sträng i en delordbok måste du oroa dig för det sista tecknet (med hänsyn till digramet och dess distribution)

partial_size2 ( current_length , prev_char , level ) { if level >= threshold : return 0 if total_length = current_length : return 1 summa = 0 för varje tecken i alfabetet om nuvarande_längd = 0 new_level = mu ( char ) else new_level = level + mu ( prev_char ) , char ) summa = summa + partiell_storlek2 ( aktuell_längd + 1 , char , new_level ) } get_key2 ( current_length , index , prev_char , level ) { if total_length = current_length : return "" summa = 0 för char i alfabetet om nuvarande_längd = 0 new_level = mu ( char ) annat new_level = level + mu ( prev_char , char ) size = partial_size2 ( current_length + 1 , char , new_level ) if sum + size > index return char | get_key2 ( aktuell_längd + 1 , index - summa , char , new_level ) summa = summa + storlek // kontrollen kan inte nå hit print "index större än knappsatsstorlek" ; avsluta }

Kommentar

användningen av hybridalgoritmer ger bättre resultat för kryptoanalys genom ordbokssökning . [6]

Grundläggande räknare för ordboksattacker

Motverka onlineordboksattacker

Det finns flera sätt att motverka onlineordboksattacker :

fördröjt svar : för det angivna inloggnings-/lösenordsparet använder servern en liten, speciellt genererad Ja/nej -svarsfördröjning (till exempel inte mer än ett svar per sekund;
kontolåsning : ett konto låses efter flera (ett förutbestämt antal) misslyckade inloggnings-/lösenordsförsök ( till exempel låses ett konto i en timme efter fem felaktiga lösenordsförsök);
använder Proof-of-Work ;
användning av salt- och långsamma hash-funktioner på klientsidan.

Anmärkningar

dessa åtgärder, i de flesta fall, förhindrar en ordboksattack och att det åtföljande lösenordet spricker inom rimlig tid;
Data för implementeringen av motverkande online ordboksattacker tillåter långvarig blockering av användarkonton med korrekt val av attackperiod.

Användarautentiseringsprotokoll

Det antas att korrekt inloggnings-/lösenordskombination anges av användaren av detta konto , medan ordbokattacken utförs av ett automatiskt program. Det krävs att ett försök att ange rätt lösenord är "beräkningsmässigt enkelt" för människor och "beräkningssvårt" för maskiner.

Protokollet är ett test som gör att servern kan skilja en människa från en bot . Det föreslogs först av M. Naor ( eng. Moni Naor ) och kallas det omvända Turing-testet ( eng. Reverse Turing-test (RTT) ), ett annat namn för det är CAPTCHA . Det omvända turingtestet måste uppfylla följande villkor: [7]

automatisk generering;
enkel implementering för en person;
komplexitet för maskiner;
liten chans att gissa svaret.

Bildtestet uppfyller alla ovanstående villkor.

Protokoll 1 (kombination av Turings omvända test med valfritt autentiseringssystem) [8]

Användaren uppmanas att svara på ett RTT-meddelande innan autentisering startar (innan inloggning/lösenord skrivs in ).

Kommentar

Denna metod är inte optimal för stora system, eftersom det är ganska irriterande och psykologiskt svårt för användaren att ange svaret på RTT-testet varje gång före autentisering . [åtta]

Protokoll 2 (användarinloggningsprotokoll, modifierad version av protokoll 1) [8]

Om användaren lyckas logga in skickar servern en cookie till användarens dator som innehåller en registrering av användarens autentisering och giltighetsperioden för detta meddelande (förutsatt att oförmågan att ändra informationen i cookien utan att meddela servern (detta kan garanteras genom att lägga till en MAC ( meddelandeautentiseringskod ) , som beräknas med en nyckel som endast servern känner till).

1. användare anger inloggning/lösenord . Om hans dator innehåller cookies från denna server, hämtas cookien av servern; 2. inloggnings-/ lösenordsautentisering ; 3. om inloggning/lösenord är sant då a. om cookien är i ett giltigt tillstånd (verifierat av det datum då den ändrades av servern) och posten som identifierar användaren (och lagrad i cookien ) matchar inloggningen som angetts , då ges användaren åtkomst till servern; b. annars genererar servern ett RTT-test och skickar det till användaren. Användaren får tillgång till servern först efter ett korrekt svar på RTT-förfrågan ; 4. om inloggnings-/lösenordsparet är felaktigt, då a. med en sannolikhet (där detta är en systemparameter, till exempel ), erbjuds användaren att klara ett RTT-test och oavsett svaret blockeras åtkomst till servern;

sid

0\leq p\leq 1

p=0,05

b. med sannolikhet blockeras anslutningen omedelbart.

1-s

Anmärkningar

det antas att användaren använder ett litet antal datorer och det är osannolikt att attacken kommer att utföras från en av dem;
inloggningsprocessen använder en webbläsare och cookies krävs;
Protokollets algoritm är byggd på ett sådant sätt att processen att generera ett RTT-meddelande endast sker i två fall: när cookie -posten på användarens dator är ogiltig och när inloggnings-/lösenordsparet är felaktigt. Detta låter dig ladda ner servrar med detta protokoll;
sannolikhet är en funktion av inloggnings-/lösenordsparet . Det finns fall då, för fasta inloggnings-/lösenordsvärden , antingen endast kontolåsningar eller bara generering av RTT-meddelanden i händelse av flera fel kommer att inträffa. $sid$

Motverka offline-ordboksattacker

Offlineordboksattacker kan förhindras eller försvåras på följande sätt:

lägga till ett känt värde till hashing - salt ( engelska salt )
använder en långsam hashfunktion, t.ex. kryptera

Hårdvaruimplementering

Trusted Platform Module (TPM) är ett hårdvaruchip som gör att datorer kan hålla data säkra. Innehav av hemlig information (hädanefter - authData ) är nödvändigt för att komma åt och använda TPM-nycklar .

Under attacken kan kryptoanalytikern lära sig: [9]

logga in för authData och TPM - svaret på denna begäran;
delad hemlighet( eng. shared secret ) associerad med authData och TPM - svaret .

Sammanställning av ordböcker baserat på mottagen information används i en offlineordboksattack för att fastställa authData .

Bekämpningsmetoder - med en modifierad SPEKE- krypteringsmetod( Simple Password Exponential Key Exchange ), som är baserad på Diffie-Hellman-nyckelutbytesalgoritmen (låter två parter skapa en delad hemlighet $s$ ( eng. stark delad hemlighet ), baserad på en svag delad hemlighet $w$ ( eng. svag hemlighet ), som de delar).

Protokoll (modifierad kryptografisk metod SPEKE)

1. användaren kör kommandot som krävs för auktorisering med authData ; 2. användarprocess och TPM ingår i SPEKE-protokollet $d$
, använder som en svag delad hemlighet $d$ $w$ ;
3. Användarprocessen väljer en slumpmässig och skickar den till TPM , där är hash-funktionen ; 4. TPM väljer en slumpmässig och skickar till användarprocessen; 5. var och en av dem beräknar en hemlighet ; 6. ersätts av som HMAC-nyckel . $x$ ${\displaystyle H(d)^{x))$ $H$
$y$ ${\displaystyle H(d)^{y))$
${\displaystyle s=H(d)^{xy))$
$w$ $s$

Anmärkningar

begränsningarna för valet beskrivs i Diffie-Hellman-nyckelutbytesalgoritmen ; $d,w,h,x,y$
valet av hashfunktion bestäms av krypteringsmetoden i kryptoprocessorn ( TPM-chip ). $H$
protokollet är föremål för förbättringar. [9]

Se även

Anteckningar

↑ Shirey R. Begäran om kommentarer : 4949 . – augusti 2007.
↑ 1 2 Spafford Eugene. Internet Worm: Crisis and Aftermath (engelska) . - Meddelanden från ACM, juni 1989. - P. 678-687 .
↑ 1 2 Daniel V. Klein. En undersökning av och förbättringar av lösenordssäkerhet // USENIX Association. — 1990.
↑ 1 2 Spafford Eugene. Observera återanvändbara lösenordsval // USENIX Association. - 31 juli 1992. Arkiverad från originalet den 20 juli 2011.
↑ 1 2 Yan Jianxin, Blackwell Alan, Anderson Ross, Gran Alasdair. Lösenordens minnesbarhet och säkerhet - några empiriska resultat / Markus Kuhn. – september 2000.
↑ 1 2 3 4 5 6 Narayanan Arvind, Shmatikov Vitaly. Snabb ordbok attacker mot lösenord med Time- Space Tradeoff . — 7–11 november 2005.
↑ Naor Moni. Verifiering av en människa i slingan eller identifiering via Turing-testet . — 13 september 1996.
↑ 1 2 3 Pinkas Benny, Sander Tomas. Säkra lösenord mot ordboksattacker .
↑ 1 2 Chen Liqun, Ryan Mark. Ofine ordbok attack på TCG TPM svag auktoriseringsdata och lösning (engelska) .

Länkar

RFC 2828 - Internetsäkerhetsordlista
RFC 4949 - Internetsäkerhetsordlista, version 2
Det starka lösenordsdilemmat . Hämtad 13 november 2011. Arkiverad från originalet 27 februari 2012.
Ordböcker (engelska) . Hämtad 13 november 2011. Arkiverad från originalet 27 februari 2012.
CAPTCHA (engelska) (inte tillgänglig länk) . Hämtad 13 november 2011. Arkiverad från originalet 27 februari 2012.
Oechslin Philippe. Göra en snabbare byte av kryptoanalytiskt tidsminne (engelska) . Hämtad 13 november 2011. Arkiverad från originalet 27 februari 2012.
John the Ripper lösenordsknäckare (engelska) (nedlänk) . Hämtad 13 november 2011. Arkiverad från originalet 27 februari 2012.