Ú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 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 brute-force útok exponenciálně roste s rostoucí délkou klíče. 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ěli dlouhého trvání, dnešní symetrické šifrovací algoritmy používají obvykle delší klíče, a to 128 až 256 – bitové.

Existují fyzické argumenty, podle kterých je symetrický klíč o délce 128-bitů proti brute-force útoku dostatečně bezpečný. Takzvaný Landauer 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. 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 128-bit symetrický klíč,  bylo by teoreticky potřeba (2 ^ 128) -1 testovaných bitů. Pokud předpokládáme, že se výpočet probíhá v pokojové teplotě (~300 K), tak dle Von Neumann-Landauer vzorce bude pro výpočet potřeba přibližně 10^18 joulů, což odpovídá spotřebě 30ti gigawatů po dobu jednoho roku. To se rovná 30×10⁹W×365×24×3600 s = 9.46×10¹⁷ J nebo 262.7 TWh (více než 1/100 světové výroby elektřiny). Skutečný výpočet – kontrolujeme každý klíč, a zjišťujeme, zda jsme našli řešení – mohli bychom 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.

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í grafický procesor (GPU) technologie, a také programovatelná hradlová pole (FPGA) technologie. 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 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 provedli 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 256-bit klíčem. K prolomení symetrického klíče o velikosti 256-bitů metodou brute-force je potřeba 2^128 krát vetší výkon než u 128-bit klíče. 50 superpočítačů, které by byly schopny prověřit bilion bilionů (10^18) AES klíčů za vteřinu (pokud by takové zařízení někdy bylo vyrobeno), by teoreticky vyžadovaly přibližně 3*10^51 let k vyčerpání (prozkoumání) všech možných 256-bit klíčů.

Základní předpoklad brute-force útoku je, že byla využita celá délka klíče pro jejich generování, způsob, který se opírá o efektivní generátor náhodných čísel, a o to, že v tomto generačním algoritmu nejsou žádné chyby. Například, několik systémů, které se zdály být vůči brutte-force útoku imunní, byly přesto nabourány, protože jejich „klíčový prostor“ 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 debian/ubuntu edice OpenSSL u kterého se nedostatek bezpečnosti projevil 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