Útok hrubou silou

Útok hrubou silou (anglicky brute force attack) je většinou pokus o rozluštění šifry bez znalosti jejího klíče k dešifrování. V praxi se jedná o systematické testování všech možných kombinací nebo omezené podmnožiny všech dostupných kombinací.

Využití

Útok hrubou silou se často používá pro uhádnutí dvojice uživatel a heslo. Je možné používat náhodná (resp. generická) přihlašovací jména a hesla při pokusech o autentizaci, případně možné varianty omezit. Například získat seznam uživatelských jmen a zkoušet prolomit pouze heslo. Pokud se heslo snažíme získat pomocí předem připraveného slovníku (seznamu), jedná se už o Slovníkový útok. Protože si uživatelé často volí málo silné heslo, je tento jednoduchý (a automatizovatelný) útok poměrně úspěšný a široce rozšířený. V případě, že útočník získá jednosměrně zašifrované heslo (typicky pomocí kryptografického hashe), může se pomocí slovníku pokoušet různá hesla zašifrovávat a porovnávat je se známým zašifrovaným tvarem. V okamžiku nalezení shody je nalezena i fráze pro přístup k dané službě. Proto je vhodné zašifrovaná hesla ukládat na místa, kde nejsou snadno dostupná.

Teoretické limity

Čas potřebný pro útok hrubou silou roste exponenciálně s rostoucí délkou klíče, protože se tím zvětšuje i prostor klíče (anglicky key space). Podle historických předpisů USA byla délka symetrických klíčů stanovena na maximálně 56 bitů (např. Data Encryption Standard), tyto předpisy neměly dlouhého trvání, dnešní symetrické šifrovací algoritmy používají obvykle delší klíče, a to 128 až 256bitové.

Existují fyzické argumenty, podle kterých je symetrický klíč o délce 128bitů proti brute-force útoku dostatečně bezpečný. Takzvaný Landauerův limit vyplývající z fyzikálních zákonů určuje dle vzorce kT * ln(2) nejnižší potřebnou hranici vynaložené energie k prolomení klíče, kde T je teplota procesoru v kelvinech, k je Boltzmannova konstanta a hodnota přirozeného logaritmu ze 2 je 0,693. Z principu nemůže žádné výpočetní zařízení využít méně energie než té, která vyplývá z výše uvedeného vzorce. Kdybychom chtěli jednoduše otestovat všechny možné varianty pro 128bitový symetrický klíč,  bylo by teoreticky potřeba (2¹²⁸−1) testovaných bitů. Pokud předpokládáme, že výpočet probíhá v pokojové teplotě (~300 K), tak dle Von Neumann-Landauerova vzorce bude pro výpočet potřeba přibližně 10¹⁸ joulů, což odpovídá spotřebě 30 gigawatů po dobu jednoho roku. To se rovná 30×10⁹W×365×24×3600 s = 9.46×10¹⁷ J nebo 262,7 TWh (vice než 1/100 světové výroby elektřiny). Pro skutečný výpočet – kontrolujeme každý klíč a zjišťujeme, zda jsme našli řešení – bychom mohli potřebovat mnohokrát více výše spočtené energie. Kromě toho, je toto pouze energie potřebná pro cyklický průchod klíčem; skutečný čas potřebný k otestování každého bitu je velký a nevyplatí se nám čekat.

Navíc tyto výpočty předpokládají, že hodnoty klíče jsou vygenerovány konvenčně (ne pseudonáhodně), ale v dnešní době se při generování používá entropie. Bylo prokázáno, že i přes výše uvedený teoretický limit je možné sestavit hardware, který takový výpočet zvládne (viz reversible computing), zatím ale žádný takový počítač nebyl sestrojen.

Moderní GPU jsou dobře přizpůsobeny pro opakující se úlohy spojené s hardwarovým prolomením hesla.

Dostupný komerční následovník vládní ASICs Solution, také známý jako custom hardware attack, zveřejnil dvě technologie, které dokáží aplikovat brutte-force útok na některé dnešní šifry. První je moderní technologie grafického procesoru (GPU), a také technologie programovatelných hradlových polí (FPGA). Výhoda GPU spočívá v jejich široké dostupnosti a poměru cena – výkon, FPGA technologie je zase energicky výhodnější pro kryptografické operace. Obě technologie se pro brutte-force útok snaží využít výhody paralelního zpracování. Počet procesorů, které pro prolomení hesla využívá technologie GPU se pohybuje v řádů stovek, u FPGA je to i několik tisíc procesorů. Tyto technologie jsou mnohem účinnější než konvenční procesory. Různé výzkumy v oblasti kryptografické analýzy prokázaly velkou energetickou účinnost dnešních FPGA technologií, například počítač COPACOBANA složený z FPGA spotřebuje stejné množství energie jako jeden konvenční PC (600 W), ale pro některé algoritmy má účinnost 2 500 počítačů. Některé firmy provedly hardware-based FPGA kryptografické analýzy, a to od testování samotné FPGA PCI-Express karty až po specializované FPGA počítače. Šifry WPA a WPA2 byly metodou brute-force úspěšně napadeny tím, že se snížilo pracovní zatížení o faktor 50 v porovnání s konvenčním PC a o několik set v případě FPGA počítače.

Šifrovací metoda AES pracuje s 256bitovým klíčem. K prolomení symetrického klíče o velikosti 256 bitů metodou brute-force je potřeba 2¹²⁸ krát větší výkon než u 128bitového klíče. Celkem 50 superpočítačů, které by byly schopny prověřit trilion (10¹⁸) AES klíčů za sekundu (pokud by takové zařízení někdy bylo vyrobeno), by teoreticky vyžadovaly přibližně 3×10⁵¹ let k vyčerpání (prozkoumání) všech možných 256bitových klíčů.

Základní předpoklad brute-force útoku je, že byla využita celá délka klíče pro jejich generování, což vyžaduje efektivní generátor náhodných čísel a skutečnost, že v algoritmu generujícím náhodná čísla nejsou chyby. Například několik systémů, které se zdály být vůči brute-force útoku imunní, byly přesto nabourány, protože prostor klíče (anglicky key space) je mnohem menší, než se původně myslelo a to díky nedostatku entropie v jejich generátoru pseudonáhodných čísel. Mezi tyto systémy patří NETSCAPE implementace SSL (slavně prolomeno Ian Golbergem a Davidem Wagnerem v roce 1995) a linuxové distribuce Debian/Ubuntu, ve kterých se projevil nedostatek entropie v programu OpenSSL v roce 2008. Podobný nedostatek entropie v klíči vedl k prolomení Enigmy.

Související články

• Řešení hrubou silou
• Vernamova šifra – šifra odolná vůči útoku hrubou silou