Ordbogssøgning

Ordbogsangreb ( Engelsk ordbogsangreb ) - et angreb på sikkerhedssystemet ved hjælp af metoden til fuldstændig opregning ( engelsk brute-force ) af de tilsigtede adgangskoder , der bruges til autentificering , udført ved sekventielt at gennemgå alle ord ( adgangskoder i deres rene form eller deres krypterede billeder) af en bestemt type og længde fra ordbogen for efterfølgende at hacke systemet og få adgang til klassificeret information . [1] Denne begivenhed er i de fleste tilfælde af negativ karakter, i modstrid med moralske og lovgivningsmæssige normer.

Ordbogssøgning og adgangskodekompleksitet

Fra sandsynlighedsteoriens synspunkt er valget af et kodeord deterministisk og logisk. Adgangskoden kan være: fødselsdato, navn, objekt, et sæt tal, en sekvens af bogstaver tæt anbragt på tastaturet. I det generelle tilfælde er ovenstående sammenkædet .

Resultatet af disse antagelser er, at forudbestemmelse i adgangskodevalg spiller en nøglerolle i valget af algoritmer, som ordbogssøgningsmetoden er baseret på .

Der er to typer angreb:

Online : Angreb, hvor den eneste måde for en angriber at bekræfte, at en given adgangskode er korrekt, er ved at interagere med serveren.
Offline : Et angreb, hvor en angriber er i stand til at kontrollere alle gyldige adgangskoder uden at skulle vende tilbage til serveren.

Det er muligt at beregne en adgangskodestyrkescore, især for at bestemme andelen af vellykkede ordbogsangreb . Sandsynligheden for succes kan defineres som forholdet mellem antallet af knækkede adgangskoder i et ordbogsangreb og det samlede antal forsøg.

Historisk information

Brugen af Internet Worm i 1988 giver et veldokumenteret tilfælde af adgangskodeknækning. [2] Ormen forsøgte at knække adgangskoder ved at arbejde med en række ordbøger. Den første fase af angrebet brugte et sæt ord, der indeholdt brugernavne taget fra Unix-systemets adgangskodefil. Hvis dette ikke lykkedes, blev der brugt en intern ordbog med 432 almindeligt anvendte internetjargonord. Hvis andet trin ikke lykkedes, blev der brugt en Unix -ordbog med 24474 ord. Ormen tjekkede også for en tom adgangskode. Angrebne websteder rapporterede, at omkring 50 % af adgangskoder blev knækket med denne strategi.

Det næste skridt var Daniel Kleins arbejde . [3] For at give sine resultater indsamlede han krypterede Unix -systemadgangskodefiler . Denne samling indeholdt cirka 15.000 forskellige brugernavn/adgangskode-par ( login/adgangskode ) . Klein konstruerede en række ordbøger og et sæt mekanismer til at muliggøre permutationer. Ordbogen han leverede bestod af cirka 60.000 genstande. Dette ark indeholdt navne, steder, fiktive referencer, bibelske termer, udtryk fra W. Shakespeares digte osv. Efter at have anvendt en permutationsstrategi (brug af store bogstaver, åbenlyse substitutioner, permutationer af tal), modtog han en adgangskodeplads på mere end 3,3 millioner muligheder. Brug af denne ordbog hjalp Klein med at knække 24,2% af alle adgangskoder på visse servere.

I 1991-1992. Eugene Spafford( eng. Eugene Spafford ) formåede at bygge, baseret på statistik, en ordbog, hvormed 20% af adgangskoder på udvalgte servere bukkede under for at knække. [fire]

I 2000 gennemførte et team af forskere fra University of Cambridge en undersøgelse, hvor 195 hash- kodeord blev angrebet, hvoraf 35% blev knækket. [5]

Tabel: Procentdel af adgangskoder fundet i systematisk forskning

Forsker(e) / projekt	Tid	Adgangskoder bekræftet	Procentdel af fund, [%]
Internetorm [2]	1988	tusindvis	~50
Kleins undersøgelse [3]	1990	15.000	24.2
Spaffords undersøgelse[fire]	1992	13787	20.0
Forskere fra University of Cambridge [5]	2000	195	35,0

Grundlæggende principper for opbygning af en ordbog

I de fleste adgangskoder er der en fonetisk lighed med ordene i naturligt (engelsk) sprog; grunden til dette er letheden ved at huske denne form for information om en given adgangskode. Denne egenskab tages i betragtning i "Markov-filtre" baseret på Markov-kæden , som er en standardteknik i naturlig sprogbehandling. Tilstedeværelsen af ikke-alfabetiske tegn i adgangskoden kan tolkes som at anvende en tilstandsmaskine til et bestemt sæt elementer.

Markov filtre

En menneskeskabt alfabetisk adgangskode er ujævnt fordelt i rummet af alfabetiske sekvenser. Denne tilstand kan tages i betragtning med stor nøjagtighed i "Markov-filtre" af nul og første orden: [6]

nul-ordens Markov-model : hvert symbol genereres i henhold til sin egen sandsynlighedsfordeling og uafhængig af tidligere symboler.
førsteordens Markov-model : hvert digram (ordnet par) af symboler tildeles en sandsynlighed, og hvert symbol genereres i betinget afhængighed af det foregående.

Matematisk,

nul orden af Markov-modellen:

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

første ordre af 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}),

hvor er sandsynligheden for fordeling af en sekvens af tegn, er karakteren af denne sekvens, er frekvensen af et individuelt tegn eller digram i teksten. $P(\cdot)$ $x_{i}$ $\nu$

For at eliminere usandsynlige strenge i ordbogen bruges sandsynlighedsdiskretisering - et to-niveau system med en tærskel er introduceret : $\theta$

nul orden af Markov-modellen:

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

første ordre af 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 \}.

Bemærkninger

første-ordens Markov-modellen viser bedre resultater (giver en højere procentdel af hacking) i forhold til nul-ordens Markov-modellen . Undtagelsen er, når kodeordsstrategien bruger forkortelser, der består af de første bogstaver i hvert ord i en abstrakt sætning;
frekvensfordelingen af bogstaver i adgangskoden afhænger af det specifikke sprog, som ordbogen er kompileret til (en generalisering af denne metode er kombinationen af formodede sprog til oprettelse af en adgangskode).

Filtre ved hjælp af tilstandsmaskiner

For at oprette statsmaskiner introduceres nogle begrænsninger og antagelser i forhold til den knækkede adgangskode:

i en alfanumerisk adgangskode er alle tal i slutningen;
det første bogstav i en alfabetisk adgangskode er mere tilbøjelig til at være stort end de andre;
i et alfabetisk kodeord er antallet af små bogstaver større end antallet af store bogstaver.

Deterministiske endelige automater er ideelle midler til udtryk med de foreslåede begrænsninger. [6]

Det første trin i opbygningen af en ordbog baseret på endelige automater er at skabe en sekvens af regulære udtryk ( \" små bogstaver " , \" caps før små bogstaver " , \" alle caps kommer før små bogstaver " , osv.).

En ordbog er defineret som et sæt ord, der matcher Markov-filtre og et begrænset antal regulære udtryk anvendt på dem.

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

Algoritmer

Ændret ordbog af nul-ordens Markov-modellen

Algoritmen, der bruges til at bygge ordbogen, er lidt anderledes end Markov-filteret på nulniveau (i dette tilfælde vil en anden tærskel blive brugt for forskellige ordlængder i ordbogen ). [6] $\theta$

Den ændrede ordbog er defineret som

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

Omskriv filteret (ordbogen) i additiv form

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

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

Lad . Derefter definerer vi delordbøger . Bemærk, at er defineret, fordi , derfor ikke afhænger af valget af . ${\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$

For ethvert præfiks indeholder den delvise ordbog alle mulige sekvenser af tegn, der kan knyttes til det præfiks , så den resulterende streng opfylder alle Markov-egenskaber.

Generelt kan der skrives en delordbog

\mid D_{\nu,\,tærskel,\,total\,længde,\,niveau,\,aktuel\,længde}\midt

Rekursiv algoritme til beregning af størrelsen af en delordbog [6]

partial_size1 ( current_length , level ) { if level >= threshold : return 0 if total_length = current_length : return 1 sum = 0 for hver char i alfabetet sum = sum + partial_size1 ( current_length + 1 , level + mu ( char )) return sum }

Rekursiv algoritme til at finde en nøgle fra en ordbog (tager et indeks i tasterummet som input og returnerer den tilsvarende nøgle ) [6]

get_key1 ( aktuel_længde , indeks , niveau ) { if total_length = current_length : returner "" sum = 0 for hvert tegn i alfabetet new_level = level + mu ( char ) // slået op fra forudberegnet array size = partial_size1 [ current_length + 1 ][ new_level ] if sum + size > index // '|' henviser til strengsammenkædning retur char | get_key1 ( aktuel_længde + 1 , indeks - sum , nyt_niveau ) sum = sum + størrelse // kontrol kan ikke nå her print "indeks større end keyspace størrelse" ; exit }

Bemærkninger

partial_size1 evalueres kun én gang (ikke én gang pr. nøgle );
get_key1 beregnes under krypteringsanalyse ;
for at se hele tasterummet skal du køre get_key1 med current_length = 0 og level = 0 .

Ordforråd af førsteordens Markov-modellen

Som med nulordsmetoden defineres delvise ordbøger .

Når du har slået en streng op i en delvis ordbog , skal du bekymre dig om det sidste tegn (under hensyntagen til digrammet og dets fordeling)

partial_size2 ( current_length , prev_char , level ) { if level >= threshold : return 0 if total_length = current_length : return 1 sum = 0 for hvert tegn i alfabetet hvis current_length = 0 new_level = mu ( char ) else new_level = level + mu ( prev_char , char ) sum = sum + partiel_størrelse2 ( nuværende_længde + 1 , char , nyt_niveau ) } get_key2 ( aktuel_længde , indeks , prev_char , niveau ) { if total_length = current_length : returner "" sum = 0 for char i alfabetet hvis nuværende_længde = 0 new_level = mu ( char ) andet new_level = level + mu ( prev_char , char ) size = partial_size2 ( current_length + 1 , char , new_level ) if sum + size > index return char | get_key2 ( aktuel_længde + 1 , indeks - sum , char , nyt_niveau ) sum = sum + størrelse // kontrol kan ikke nå her print "indeks større end keyspace størrelse" ; exit }

Kommentar

brugen af hybride algoritmer giver bedre resultater for kryptoanalyse ved ordbogssøgning . [6]

Grundlæggende tællere til ordbogsangreb

Bekæmpelse af online ordbogsangreb

Der er flere måder at imødegå online ordbogsangreb på :

forsinket svar : for det angivne login/adgangskode - par bruger serveren en lille, specielt genereret Ja/nej -svarforsinkelse (f.eks. ikke mere end ét svar pr. sekund;
kontolåsning : en konto låses efter adskillige (et forudbestemt antal) mislykkede login-/adgangskodeforsøg ( for eksempel låses en konto i en time efter fem forkerte adgangskodeforsøg);
ved hjælp af Proof-of-Work ;
brug af salt og slow hash-funktioner på klientsiden.

Bemærkninger

disse foranstaltninger forhindrer i de fleste tilfælde et ordbogsangreb og den medfølgende adgangskode, der knækker inden for en rimelig tid;
Dataene for implementering af modvirkende online ordbogsangreb tillader langsigtet blokering af brugerkonti med det korrekte valg af angrebsperiode.

Brugergodkendelsesprotokoller

Det antages, at den korrekte login/adgangskode -kombination er indtastet af brugeren af denne konto , mens ordbogsangrebet udføres af et automatisk program. Det kræves, at et forsøg på at indtaste den korrekte adgangskode er "beregningsmæssigt simpelt" for mennesker og "beregningsmæssigt svært" for maskiner.

Protokollen er en test, der tillader serveren at skelne et menneske fra en bot . Den blev først foreslået af M. Naor ( eng. Moni Naor ) og kaldes den omvendte Turing-test ( eng. Reverse Turing-test (RTT) ), et andet navn for den er CAPTCHA . Reverse Turing-testen skal opfylde følgende betingelser: [7]

automatisk generering;
let implementering for en person;
kompleksitet for maskiner;
lav chance for at gætte svaret.

Billedtesten opfylder alle ovenstående betingelser.

Protokol 1 (kombination af Turings omvendte test med ethvert autentificeringssystem) [8]

Brugeren bliver bedt om at svare på en RTT-besked, før godkendelsen starter (inden login/adgangskode indtastes ).

Kommentar

Denne metode er ikke optimal for store systemer, da det er ret irriterende og psykologisk svært for brugeren at indtaste svaret på RTT-testen hver gang før godkendelse . [otte]

Protokol 2 (brugerloginprotokol, ændret version af protokol 1) [8]

Hvis brugeren er logget ind, sender serveren en cookie til brugerens computer , der indeholder en registrering af brugerens godkendelse og gyldighedsperioden for denne meddelelse (forudsat at manglende evne til at ændre informationen i cookien uden at give serveren besked (dette kan garanteres ved at tilføje en MAC ( beskedgodkendelseskode ), som beregnes ved hjælp af en nøgle , der kun er kendt af serveren).

1. bruger indtaster login/adgangskode . Hvis hans computer indeholder cookies leveret af denne server, hentes cookien af serveren; 2. login/ adgangskodegodkendelse ; 3. hvis login/adgangskode er sandt, så en. hvis cookien er i en gyldig tilstand (verificeret af den dato, den blev ændret af serveren), og posten, der identificerer brugeren (og gemt i cookien ) matcher det indtastede login , så får brugeren adgang til serveren; b. Ellers genererer serveren en RTT-test og sender den til brugeren. Brugeren får først adgang til serveren efter et korrekt svar på RTT-anmodningen ; 4. hvis login/adgangskodeparret er forkert, så en. med en sandsynlighed (hvor dette er en systemparameter, for eksempel ), tilbydes brugeren at bestå en RTT-test, og uanset svaret er adgangen til serveren blokeret;

s

0\leq p\leq 1

p=0,05

b. med sandsynlighed blokeres forbindelsen med det samme.

1-s

Bemærkninger

det antages, at brugeren bruger et lille antal computere, og det er usandsynligt, at angrebet vil blive udført fra en af dem;
login-processen bruger en webbrowser og cookies er påkrævet;
Protokollens algoritme er bygget på en sådan måde, at processen med at generere en RTT-besked kun forekommer i to tilfælde: når cookieindtastningen på brugerens computer er ugyldig, og når login/adgangskodeparret er forkert. Dette giver dig mulighed for at afloade servere ved hjælp af denne protokol;
sandsynlighed er en funktion af login/adgangskode -parret . Der er tilfælde, hvor der for faste login-/adgangskodeværdier enten kun vil opstå kontolåse eller kun generering af RTT-meddelelser i tilfælde af flere fejl. $s$

Bekæmpelse af offline-ordbogsangreb

Offline ordbogsangreb kan forhindres eller gøres vanskeligere på følgende måder:

tilføjelse af en kendt værdi til hashing - salt ( engelsk salt )
ved hjælp af en langsom hash-funktion, f.eks. krypt

Hardwareimplementering

Trusted Platform Module (TPM) er en hardwarechip, der gør det muligt for computere at holde data sikre. Besiddelse af hemmelige oplysninger (herefter - authData ) er nødvendig for at få adgang til og bruge TPM-nøgler .

Under angrebet kan kryptanalytikeren lære: [9]

login for authData og TPM - svaret på denne anmodning;
delt hemmelighed( eng. shared secret ) forbundet med authData og TPM - svaret .

Kompilering af ordbøger baseret på modtaget information bruges i et offline ordbogsangreb til at bestemme authData .

Kampmetoder - ved hjælp af en modificeret SPEKE kryptografisk metode( Simple Password Exponential Key Exchange ), som er baseret på Diffie-Hellman-nøgleudvekslingsalgoritmen (lader to parter oprette en delt hemmelighed $s$ ( eng. stærk delt hemmelighed ), baseret på en svag delt hemmelighed $w$ ( eng. svag hemmelighed ), som de deler).

Protokol (modificeret kryptografisk metode SPEKE)

1. brugeren udfører den kommando , der kræves til autorisation med authData ; 2. brugerproces og TPM er inkluderet i SPEKE-protokollen $d$
, bruger som en svag fælles hemmelighed $d$ $w$ ;
3. Brugerprocessen vælger en tilfældig og sender den til TPM , hvor er hash-funktionen ; 4. TPM vælger en tilfældig og sender til brugerprocessen; 5. hver af dem beregner en hemmelighed ; 6. erstattes af som HMAC-nøgle . $x$ ${\displaystyle H(d)^{x))$ $H$
$y$ ${\displaystyle H(d)^{y))$
$s=H(d)^{xy}$
$w$ $s$

Bemærkninger

begrænsningerne for valget er beskrevet i Diffie-Hellman nøgleudvekslingsalgoritmen ; $d,w,h,x,y$
valget af hash-funktion bestemmes af krypteringsmetoden i kryptoprocessoren ( TPM-chip ). $H$
protokollen er genstand for forbedringer. [9]

Se også

Noter

↑ Shirey R. Anmodning om kommentarer : 4949 . - august 2007.
↑ 1 2 Spafford Eugene. Internet Worm: Crisis and Aftermath (engelsk) . - Meddelelser fra ACM, juni 1989. - P. 678-687 .
↑ 1 2 Daniel V. Klein. En undersøgelse af og forbedringer af adgangskodesikkerhed // USENIX Association. - 1990.
↑ 1 2 Spafford Eugene. Observerer genbrugelige adgangskodevalg // USENIX Association. - 31. juli 1992. Arkiveret fra originalen den 20. juli 2011.
↑ 1 2 Yan Jianxin, Blackwell Alan, Anderson Ross, Gran Alasdair. Kodeords huskelighed og sikkerhed - nogle empiriske resultater / Markus Kuhn. - september 2000.
↑ 1 2 3 4 5 6 Narayanan Arvind, Shmatikov Vitaly. Hurtige ordbogsangreb på adgangskoder ved hjælp af tid -rum- afvejning . — 7.-11. november 2005.
↑ Naor Moni. Verifikation af et menneske i løkken eller identifikation via Turing-testen . - 13. september 1996.
↑ 1 2 3 Pinkas Benny, Sander Tomas. Sikring af adgangskoder mod ordbogsangreb .
↑ 1 2 Chen Liqun, Ryan Mark. Ofine ordbogsangreb på TCG TPM svage autorisationsdata og løsning (engelsk) .

Ordbogssøgning