Hledání ve slovníku

Slovníkový útok ( anglicky dictionary attack ) - útok na bezpečnostní systém metodou úplného výčtu ( anglicky brute-force ) zamýšlených hesel použitých k autentizaci , prováděný postupnou kontrolou všech slov ( hesel v čisté podobě nebo jejich zašifrovaných obrázky) určitého typu a délky ze slovníku za účelem následného hacknutí systému a získání přístupu k utajovaným informacím . [1] Tato událost má ve většině případů negativní charakter, odporující morálním a legislativním normám.

Složitost vyhledávání ve slovníku a hesel

Z hlediska teorie pravděpodobnosti je volba hesla deterministická a logická. Heslo může být: datum narození, jméno, objekt, sada čísel, posloupnost písmen těsně rozmístěných na klávesnici. V obecném případě je výše uvedené zřetězené .

Výsledkem těchto předpokladů je, že předurčení při volbě hesla hraje klíčovou roli při výběru algoritmů, na kterých je založena metoda vyhledávání ve slovníku .

Existují dva typy útoků:

Online : Útoky, kde útočník může jediným způsobem, jak ověřit správnost daného hesla, interakce se serverem.
Offline : Útok, při kterém je útočník schopen zkontrolovat všechna platná hesla, aniž by se musel vracet na server.

Je možné vypočítat skóre síly hesla, zejména určit podíl úspěšných slovníkových útoků . Pravděpodobnostní skóre úspěchu lze definovat jako poměr počtu prolomených hesel při slovníkovém útoku k celkovému počtu pokusů.

Historické informace

Použití Internet Worm v roce 1988 poskytuje dobře zdokumentovaný případ prolomení hesla. [2] Červ se pokusil prolomit hesla prací s řadou slovníků. První fáze útoku používala sadu slov obsahujících uživatelská jména převzatá ze souboru hesel unixového systému. Pokud to nebylo úspěšné, byl použit interní slovník 432 běžně používaných slov internetového žargonu. Pokud druhý krok nebyl úspěšný, byl použit unixový slovník s 24474 slovy. Červ také zkontroloval prázdné heslo. Napadené stránky uvedly, že pomocí této strategie bylo úspěšně prolomeno asi 50 % hesel.

Dalším krokem byla práce Daniela Kleina . [3] Aby poskytl své výsledky, shromáždil zašifrované soubory unixových systémových hesel . Tato sbírka obsahovala přibližně 15 000 různých párů uživatelské jméno/heslo ( login/password ) . Klein zkonstruoval řadu slovníků a sadu mechanismů umožňujících permutace. Slovník, který poskytl, obsahoval přibližně 60 000 položek. Tento list obsahoval jména, místa, fiktivní odkazy, biblické termíny, výrazy z básní W. Shakespeara atd. Po uplatnění permutační strategie (použití velkých písmen, zřejmé substituce, permutace čísel) získal mezeru pro hesla větší než 3,3 milion možností. Použití tohoto slovníku pomohlo Kleinovi prolomit 24,2 % všech hesel na určitých serverech.

V letech 1991-1992. Eugene Spafford( ang. Eugene Spafford ) se podařilo na základě statistik sestavit slovník, se kterým podlehlo prasknutí 20 % hesel na vybraných serverech. [čtyři]

V roce 2000 provedl tým výzkumníků z University of Cambridge studii, ve které bylo napadeno 195 hašovaných hesel, z nichž 35 % bylo úspěšně prolomeno. [5]

Tabulka: Procento hesel nalezených v systematickém výzkumu

Řešitel(é) / projekt	Čas	Hesla ověřena	Procento nálezů, [%]
Internetový červ [2]	1988	tisíce	~50
Kleinova studie [3]	1990	15 000	24.2
Spaffordova studie[čtyři]	1992	13787	20,0
Výzkumníci z University of Cambridge [5]	2000	195	35,0

Základní principy pro konstrukci slovníku

Ve většině hesel je fonetická podobnost se slovy přirozeného (anglického) jazyka; důvodem je snadné zapamatování tohoto druhu informací o daném heslu. Tato vlastnost je zohledněna v "Markovových filtrech" založených na Markovově řetězci , což je standardní technika zpracování přirozeného jazyka. Přítomnost neabecedních znaků v hesle může být interpretována jako použití stavového automatu na konkrétní sadu prvků.

Markovovy filtry

Abecední heslo vytvořené člověkem je v prostoru abecedních sekvencí rozmístěno nerovnoměrně. Tuto podmínku lze s velkou přesností zohlednit v "Markovových filtrech" nultého a prvního řádu: [6]

Markovův model nultého řádu : každý symbol je generován podle vlastního rozdělení pravděpodobnosti a nezávisle na předchozích symbolech.
Markovův model prvního řádu : každému digramu (uspořádanému páru) symbolů je přiřazena pravděpodobnost a každý symbol je generován v podmíněné závislosti na předchozím.

Matematicky,

nultého řádu Markova modelu:

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

první objednávka Markovova modelu:

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

kde je pravděpodobnost rozdělení posloupnosti znaků, je charakter této posloupnosti, je četnost jednotlivého znaku nebo diagramu v textu. $P(\cdot )$ $x_{i}$ $\nu$

K odstranění nepravděpodobných řetězců ve slovníku se používá pravděpodobnostní diskretizace - je zaveden dvouúrovňový systém s prahem : $\theta$

nultého řádu Markova modelu:

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

první objednávka Markovova modelu:

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

Poznámky

Markovův model prvního řádu vykazuje lepší výsledky (dává vyšší procento hackování) ve srovnání s Markovovým modelem nultého řádu . Výjimkou je situace, kdy strategie hesel používá zkratky skládající se z prvních písmen každého slova v abstraktní větě;
rozložení četnosti písmen v hesle závisí na konkrétním jazyce, pro který je slovník sestaven (zobecněním této metody je kombinace předpokládaných jazyků pro vytvoření hesla).

Filtry pomocí stavových automatů

Pro vytvoření stavových automatů jsou v souvislosti s prolomeným heslem zavedena některá omezení a předpoklady:

v alfanumerickém hesle jsou všechna čísla na konci;
první písmeno v abecedním hesle bude s větší pravděpodobností velké než ostatní;
v abecedním hesle je počet malých písmen větší než počet velkých.

Deterministické konečné automaty jsou ideálními prostředky pro výrazy s navrhovanými omezeními. [6]

Prvním krokem při vytváření slovníku založeného na konečných automatech je vytvoření sekvence regulárních výrazů ( \" malá písmena" , \" velká písmena před malými písmeny" , \"všechna velká písmena před malá" atd.).

Slovník je definován jako sada slov, která odpovídají Markovovým filtrům, a konečný počet regulárních výrazů , které jsou na ně aplikovány.

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

Algoritmy

Upravený slovník Markovova modelu nultého řádu

Algoritmus použitý k vytvoření slovníku se mírně liší od Markovova filtru nulové úrovně (v tomto případě bude pro různé délky slov ve slovníku použit jiný práh ). [6] $\theta$

Upravený slovník je definován jako

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

Přepište filtr (slovník) do aditivní formy

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

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

Nechte _ Poté definujeme dílčí slovníky . Všimněte si, že je definováno , protože proto nezávisí na výběru . ${\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)$ $\alpha$

Pro jakoukoli předponu obsahuje částečný slovník všechny možné sekvence znaků, které lze k této předponě připojit , takže výsledný řetězec splňuje všechny Markovovy vlastnosti.

Obecně lze napsat částečný slovník

\mid D_{\nu ,\,threshold,\,total\,length,\,level,\,current\,length}\mid

Rekurzivní algoritmus pro výpočet velikosti částečného slovníku [6]

částečná_velikost1 ( aktuální_délka , úroveň ) { if úroveň >= práh : návrat 0 if total_length = aktuální_délka : návrat 1 součet = 0 pro každý znak v abecedě součet = součet + částečná_velikost1 ( aktuální_délka + 1 , úroveň + mu ( znak ) ) vrátit součet }

Rekurzivní algoritmus pro nalezení klíče ze slovníku (vezme index v prostoru klíčů jako vstup a vrátí odpovídající klíč ) [6]

get_key1 ( aktuální_délka , index , úroveň ) { if total_length = current_length : return "" součet = 0 pro každý znak v abecedě nová_úroveň = úroveň + mu ( znak ) // vyhledáno z předem vypočítaného pole velikost = částečná_velikost1 [ aktuální_délka + 1 ][ nová_úroveň ] if součet + velikost > index // '|' odkazuje na zřetězení řetězců return char | get_key1 ( aktuální_délka + 1 , index - součet , nová_úroveň ) součet = součet + velikost // ovládací prvek sem nemůže dosáhnout print "index větší než velikost klíčového prostoru" ; odejít }

Poznámky

částečná_velikost1 je vyhodnocena pouze jednou (nikoli jednou na klíč );
get_key1 se vypočítá během kryptoanalýzy ;
Chcete-li zobrazit celý klíčový prostor , musíte spustit get_key1 s aktuální_délkou = 0 a úrovní = 0 .

Slovník Markovova modelu prvního řádu

Stejně jako u metody nulového řádu jsou definovány dílčí slovníky .

Po vyhledání řetězce v částečném slovníku se musíte starat o poslední znak (s ohledem na digram a jeho distribuci)

částečná_velikost2 ( aktuální_délka , předchozí_znak , úroveň ) { pokud úroveň >= práh : vrátí 0 , pokud celková_délka = aktuální_délka : vrátí 1 součet = 0 pro každý znak v abecedě , pokud aktuální_délka = 0 nová_úroveň = mu ( znak ) jinak nová_ úroveň = úroveň + mu ( předchozí_znak , char ) sum = suma + částečná_velikost2 ( aktuální_délka + 1 , znak , nová_úroveň ) } get_key2 ( current_length , index , prev_char , level ) { if total_length = current_length : return "" součet = 0 pro znak v abecedě , pokud aktuální_délka = 0 nová_úroveň = mu ( znak ) jinak new_level = level + mu ( prev_char , char ) size = částečná_velikost2 ( current_length + 1 , char , new_level ) if sum + size > index return char | get_key2 ( aktuální_délka + 1 , součet indexu , znak , nová_úroveň ) _ suma = suma + velikost // ovládací prvek sem nemůže dosáhnout print "index větší než velikost klíčového prostoru" ; odejít }

Komentář

použití hybridních algoritmů dává lepší výsledky pro kryptoanalýzu hledáním slovníku . [6]

Základní čítače slovníkových útoků

Boj proti online slovníkovým útokům

Existuje několik způsobů, jak čelit online slovníkovým útokům :

zpožděná odpověď : pro zadaný pár přihlašovací jméno/heslo server používá malé, speciálně vygenerované zpoždění odpovědi Ano/ne (například ne více než jednu odpověď za sekundu;
uzamčení účtu : účet je uzamčen po několika (předem stanovený počet) neúspěšných pokusech o přihlášení/heslo ( např . účet je uzamčen na hodinu po pěti nesprávných pokusech o heslo);
pomocí Proof-of-Work ;
použití salt a pomalých hašovacích funkcí na straně klienta.

Poznámky

tato opatření ve většině případů zabrání slovníkovému útoku a doprovodnému prolomení hesla v přiměřené době;
Údaje o implementaci odvrácených online slovníkových útoků umožňují dlouhodobé blokování uživatelských účtů při správném výběru doby útoku.

Protokoly pro ověřování uživatelů

Předpokládá se, že uživatel tohoto účtu zadá správnou kombinaci přihlašovacího jména a hesla , zatímco slovníkový útok provede automatický program. Vyžaduje se, aby pokus o zadání správného hesla byl pro lidi „výpočetně jednoduchý“ a pro stroje „výpočetně obtížný“ .

Protokol je test, který umožňuje serveru rozlišit člověka od robota . Poprvé jej navrhl M. Naor ( eng. Moni Naor ) a nazývá se reverzní Turingův test ( eng. Reverse Turing test (RTT) ), jiný název pro něj je CAPTCHA . Reverzní Turingův test musí splňovat následující podmínky: [7]

automatické generování;
snadnost implementace pro osobu;
složitost pro stroje;
malá šance uhodnout odpověď.

Obrazový test splňuje všechny výše uvedené podmínky.

Protokol 1 (kombinace Turingova reverzního testu s libovolným autentizačním systémem) [8] Před zahájením autentizace (před zadáním login/password

) je uživatel požádán, aby odpověděl na zprávu RTT .

Komentář

Tato metoda není optimální pro velké systémy, protože je pro uživatele poměrně nepříjemné a psychicky obtížné zadávat odpověď na RTT test pokaždé před autentizací . [osm]

Protokol 2 (protokol přihlášení uživatele, upravená verze protokolu 1) [8]

Pokud je uživatel úspěšně přihlášen, server odešle do počítače uživatele cookie , která obsahuje záznam o autentizaci uživatele a dobu platnosti této zprávy (za předpokladu nemožnost změnit informace v cookie bez upozornění serveru (toto lze zaručit přidáním MAC ( kód pro ověření zprávy ), který se vypočítá pomocí klíče známého pouze serveru).

1. uživatel zadá přihlašovací jméno/heslo . Pokud jeho počítač obsahuje soubory cookie poskytované tímto serverem, server tento soubor cookie načte; 2. ověření přihlášením/heslem ; 3. pokud jsou přihlašovací údaje/heslo pravdivé A. pokud je cookie v platném stavu (ověřeno datem, kdy byla změněna serverem) a záznam identifikující uživatele (a uložený v cookie ) se shoduje se zadaným přihlašovacím jménem , pak je uživateli udělen přístup k serveru; b. jinak server vygeneruje test RTT a odešle jej uživateli. Uživatel získá přístup k serveru pouze po správné odpovědi na požadavek RTT ; 4. pokud je pár login/heslo nesprávný, pak A. s pravděpodobností (kde se jedná o systémový parametr, například ), je uživateli nabídnuto absolvování testu RTT a bez ohledu na odpověď je zablokován přístup k serveru;

p

0\leq p\leq 1

p=0,05

b. s pravděpodobností je připojení okamžitě zablokováno.

1-p

Poznámky

předpokládá se, že uživatel používá malý počet počítačů a je nepravděpodobné, že útok bude proveden z jednoho z nich;
proces přihlášení používá webový prohlížeč a jsou vyžadovány soubory cookie ;
Algoritmus protokolu je postaven tak, že k procesu generování RTT zprávy dochází pouze ve dvou případech: když je záznam cookie na počítači uživatele neplatný a když je pár login/heslo nesprávný. To vám umožní snížit zátěž serverů pomocí tohoto protokolu;
pravděpodobnost je funkcí páru přihlašovací jméno/heslo . Existují případy, kdy pro pevné hodnoty login/password dojde buď pouze k uzamčení účtu, nebo pouze ke generování RTT zpráv v případě více chyb. $p$

Boj proti offline slovníkovým útokům

Offline slovníkovým útokům lze zabránit nebo je ztížit následujícími způsoby:

přidání známé hodnoty do hash - salt ( anglicky salt )
pomocí pomalé hashovací funkce, např. scrypt

Implementace hardwaru

Trusted Platform Module (TPM) je hardwarový čip, který umožňuje počítačům uchovávat data v bezpečí. Držení tajných informací (dále jen authData ) je nezbytné pro přístup a používání klíčů TPM .

Během útoku se kryptoanalytik může naučit: [9]

přihlášení pro authData a odpověď TPM na tento požadavek;
sdílené tajemství( anglicky shared secret ) spojené s authData a odpovědí TPM .

Kompilace slovníků na základě přijatých informací se používá v offline slovníkovém útoku k určení authData .

Metody boje - pomocí upravené kryptografické metody SPEKE( Simple Password Exponencial Key Exchange ), která je založena na algoritmu výměny klíčů Diffie-Hellman (umožňuje dvěma stranám vytvořit sdílené tajemství $s$ ( angl. strong shared secret ), založený na slabém sdíleném tajemství $w$ ( angl. slabé tajemství ), které sdílejí).

Protokol (upravená kryptografická metoda SPEKE)

1. uživatel provede příkaz potřebný pro autorizaci pomocí authData ; 2. uživatelský proces a TPM jsou součástí protokolu SPEKE $d$
, který se používá jako slabé sdílené tajemství $d$ $w$ ;
3. Uživatelský proces vybere náhodný a odešle ho do TPM , kde je hashovací funkce ; 4. TPM vybere náhodný a odešle ho uživatelskému procesu; 5. každý z nich vypočítá tajenku ; 6. je nahrazeno jako klíč HMAC . $X$ ${\displaystyle H(d)^{x))$ $H$
$y$ ${\displaystyle H(d)^{y))$
$s=H(d)^{xy}$
$w$ $s$

Poznámky

omezení výběru jsou popsána v Diffie-Hellmanově algoritmu výměny klíčů ; $d,š,v,x,y$
volba hashovací funkce je určena metodou šifrování v kryptoprocesoru ( čip TPM ). $H$
protokol je předmětem vylepšení. [9]

Viz také

Poznámky

↑ Shirey R. Žádost o komentáře : 4949 . — srpen 2007.
↑ 1 2 Spafford Eugene. The Internet Worm: Crisis and Aftermath (anglicky) . - Sdělení ACM, červen 1989. - S. 678-687 .
↑ 1 2 Daniel V. Klein. Průzkum a vylepšení zabezpečení heslem // USENIX Association. — 1990.
↑ 1 2 Spafford Eugene. Sledování volby opakovaně použitelných hesel // USENIX Association. - 31. července 1992. Archivováno z originálu 20. července 2011.
↑ 1 2 Yan Jianxin, Blackwell Alan, Anderson Ross, Gran Alasdair. Zapamatovatelnost a bezpečnost hesel - některé empirické výsledky / Markus Kuhn. — září 2000.
↑ 1 2 3 4 5 6 Narayanan Arvind, Šmatikov Vitalij. Rychlé slovníkové útoky na hesla pomocí kompromisu mezi časem a prostorem . — 7.–11. listopadu 2005.
↑ Naor Moni. Ověření člověka ve smyčce nebo identifikace prostřednictvím Turingova testu . — 13. září 1996.
↑ 1 2 3 Pinkas Benny, Sander Tomas. Zabezpečení hesel proti slovníkovým útokům .
↑ 1 2 Chen Liqun, Ryan Mark. Ofine slovníkový útok na slabá autorizační data TCG TPM a řešení (anglicky) .

Odkazy

RFC 2828 – Internetový bezpečnostní slovník
RFC 4949 – Internetový glosář zabezpečení, verze 2
Dilema silného hesla . Získáno 13. listopadu 2011. Archivováno z originálu 27. února 2012.
Slovníky (anglické) . Získáno 13. listopadu 2011. Archivováno z originálu 27. února 2012.
CAPTCHA (anglicky) (nedostupný odkaz) . Získáno 13. listopadu 2011. Archivováno z originálu 27. února 2012.
Oechslin Philippe. Rychlejší kryptoanalytický obchod s časovou pamětí (anglicky) . Získáno 13. listopadu 2011. Archivováno z originálu 27. února 2012.
John the Ripper cracker password (anglicky) (downlink) . Získáno 13. listopadu 2011. Archivováno z originálu 27. února 2012.