Úplný výčet (neboli metoda "brute force" , angl. brute force ) - metoda řešení matematických problémů . Odkazuje na třídu metod pro nalezení řešení vyčerpáním všech možných možností . Složitost vyčerpávající rešerše závisí na počtu všech možných řešení problému. Pokud je prostor pro řešení velmi velký, pak vyčerpávající hledání nemusí přinést výsledky po několik let nebo dokonce staletí.
Jakýkoli problém z třídy NP lze vyřešit vyčerpávajícím hledáním. Současně, i když lze výpočet účelové funkce z každého konkrétního možného řešení problému provést v polynomiálním čase , v závislosti na počtu všech možných řešení, může vyčerpávající výčet vyžadovat exponenciální průběžnou dobu.
V kryptografii se k odhadu kryptografické síly šifer používá výpočetní složitost vyčerpávajícího vyhledávání . Konkrétně se říká, že šifra je bezpečná, pokud neexistuje metoda „rozluštění“ podstatně rychlejší než vyhledávání hrubou silou . Šifrovací útoky hrubou silou jsou nejuniverzálnější, ale také nejdelší.
V angličtině termín „ brute-force “ diskutovaný v tomto článku obvykle označuje třídu hackerských útoků . Obecnějšímu pojetí, matematické metodě vyčerpání všech možných možností řešení problému, přitom odpovídá termín „ Proof by vyčerpáním “.
"Metoda vyčerpání" zahrnuje celou třídu různých metod. Obvykle problémové tvrzení implikuje uvažování o konečném počtu stavů daného logického systému za účelem zjištění pravdivosti logického tvrzení prostřednictvím nezávislé analýzy každého stavu [1] . Způsob dokazování tvrzení se skládá ze dvou částí:
Přestože se vyčerpávající vyhledávání v praxi ve většině aplikovaných problémů nepoužívá (zejména nesouvisejících s prolamováním šifer ), existuje řada výjimek. Zejména když se vyčerpávající vyhledávání přesto ukáže jako optimální nebo představuje počáteční fázi ve vývoji algoritmu, je jeho použití oprávněné. Příkladem optimálnosti vyčerpávajícího vyhledávání je algoritmus pro odhad doby výpočtu řetězových součinů matic, který nelze oproti algoritmu založenému na metodě "hrubé síly" urychlit [2] . Tento algoritmus se používá k řešení klasického problému dynamického programování - stanovení priorit pro výpočet maticových produktů následujícího tvaru: .
Prvotním úkolem je vypočítat daný řetězec (maticový součin) v co nejkratším čase. Je možné implementovat triviální sekvenční algoritmus, který vypočítá požadovaný produkt. Protože maticový součin je asociativní operace , lze vypočítat řetězový součin libovolnou volbou dvojice prvků řetězce a nahrazením výslednou maticí . Pokud zopakujete popsané časy procedur, pak zbývající výsledná matice bude odpověď: . Tento vzorec lze znázornit následovně. Uvažujme maticový řetězec: . Existuje následujících 5 způsobů, jak vypočítat produkt odpovídající tomuto řetězci :
Správným výběrem pořadí výpočtů můžete dosáhnout výrazného zrychlení výpočtů. Chcete-li to vidět, zvažte jednoduchý příklad řetězce 3 matic. Předpokládáme, že jejich velikosti jsou stejné, resp . Standardní algoritmus pro násobení dvou matic velikostí vyžaduje výpočetní čas úměrný počtu (počtu vnitřních součinů, které mají být vypočítány) [3] . Vyhodnocením řetězce v pořadí tedy získáme tečkové produkty k výpočtu , plus další tečkové produkty k výpočtu druhého maticového součinu. Celkový počet skalárních součinů: 7500. Jinou volbou pořadí výpočtů dostaneme plus skalární součiny, tedy 75000 skalárních součinů [3] .
Řešení tohoto problému tedy může výrazně zkrátit čas strávený výpočtem maticového řetězce. Toto řešení lze získat vyčerpávajícím výčtem: je třeba zvážit všechny možné posloupnosti výpočtů a vybrat z nich tu, která při výpočtu řetězce zabírá nejmenší počet skalárních součinů. Je však třeba vzít v úvahu, že tento algoritmus sám o sobě vyžaduje exponenciální výpočetní čas [2] , takže u dlouhých maticových řetězců může být zisk z výpočtu řetězce nejúčinnějším způsobem (optimální strategie ) zcela ztracen. najít tuto strategii [4] .
V teorii algoritmů existuje několik široce použitelných obecných pojmů . Metoda hrubé síly je jednou z nich. Vyčerpávající vyhledávání lze totiž použít v těch případech, kdy máme co do činění s diskrétním deterministickým systémem, jehož stavy lze snadno analyzovat [5] .
Dalším ukázkovým příkladem základního konceptu v teorii algoritmů je princip „ rozděl a panuj “. Tento koncept je použitelný v případě, kdy lze systém rozdělit do mnoha subsystémů, jejichž struktura je podobná struktuře původního systému [6] . V takových případech jsou subsystémy také přístupné oddělení nebo jsou triviální [6] . Pro takové systémy je původně nastolený problém triviální. Implementace konceptu „rozděl a panuj“ je tedy rekurzivní .
Rekurze je zase druh vyčerpávajícího hledání. Rekurze je tedy použitelná pouze pro diskrétní systémy [7] . Tento požadavek se však nevztahuje na stavy daného systému, ale na jeho substrukturu . Důsledné zvážení všech úrovní poskytuje vyčerpávající řešení problému, který je kladen na celý diskrétní systém.
Ve srovnání s jinými příklady úplného výčtu je rysem metody rekurze to, že konečné řešení je založeno na více než jednom triviálním subsystému. V obecném případě je řešení tvořeno na základě celé množiny subsystémů.
Pro následující příklady klasických problémů rozděl a panuj je hrubá síla buď jediným známým řešením, nebo původní implementací, která byla dále optimalizována:
V kryptografii je kryptografický útok hrubou silou nebo brute force [12] ( anglicky Brute-force attack ) založen na útoku hrubou silou – prolomení hesla prohledáním všech možných klíčových možností. Jeho vlastností je možnost jej použít proti jakékoli prakticky používané šifře [13] ( k výjimkám, tedy zabezpečení z pohledu teorie informace, viz také šifrovací blok a Informačně-teoretická bezpečnost ). Tato možnost však existuje pouze teoreticky, často vyžaduje nereálné náklady na čas a zdroje. Pokud je rozhodovací prostor příliš velký, může tento typ útoku selhat několik let nebo dokonce staletí. Použití útoku hrubou silou je nejvíce opodstatněné v případech, kdy není možné najít slabá místa v napadeném šifrovacím systému (nebo v uvažovaném šifrovacím systému žádná slabá místa nejsou). Když jsou takové nedostatky nalezeny, jsou na základě jejich vlastností vyvinuty techniky kryptoanalýzy , což pomáhá zjednodušit hackování.
Odolnost proti útoku hrubou silou určuje šifrovací klíč použitý v kryptosystému. Takže s rostoucí délkou klíče exponenciálně roste složitost praskání touto metodou. V nejjednodušším případě je N - bitová šifra prolomena, v nejhorším případě za čas úměrný 2 N [14] [15] . Průměrná doba hackování je v tomto případě dvakrát kratší a je 2 N -1 . Existují způsoby, jak zvýšit odolnost šifry vůči „hrubé síle“, například zmatek ( obfuskace ) zašifrovaných dat, díky čemuž není triviální rozlišit šifrovaná data od nešifrovaných.
Kryptografické útoky založené na metodě „brute force“ jsou nejuniverzálnější, ale zároveň nejpomalejší. Používají ho hlavně začínající hackeři . Efektivní pro jednoduché šifrovací algoritmy a klíče o délce až 64 bitů. Pro moderní klíče s délkou 128 bitů nebo více (někdy je pro klíč faktorizován velký počet 200 číslic) jsou neefektivní. Každé heslo lze uhodnout vyčerpávajícím hledáním. Současně, i když lze výpočet účelové funkce z každého konkrétního možného řešení problému provést v polynomiálním čase, v závislosti na počtu všech možných řešení, útok může vyžadovat exponenciální dobu běhu.
Pro zvýšení rychlosti výběru klíčů se používá paralelizace výpočtů. Existují dva typy paralelizace:
Procesor provádí tři operace současně:
Tato operace může trvat jen setinu sekundy. Pak procesory zapojené paralelně a synchronně pracují rychlostí (protože jsou pouze tři operace), kde je rychlost provedení jedné operace jedním procesorem.
Při reverzním útoku hrubou silou je jedno (obvykle sdílené) heslo testováno proti více uživatelským jménům. V tomto případě platí také paralelizace, ale procesory musí zkontrolovat, zda jiný uživatel takové heslo nemá. V takové strategii se útočník obvykle nesnaží proniknout do účtu jednoho konkrétního uživatele. Proti reverzním útokům je zavedena politika hesel, která zakazuje používání identických hesel.
V tabulce je uveden odhadovaný čas pro hledání hesel hrubou silou v závislosti na jejich délce. Předpokládá se, že v hesle může být použito 36 různých znaků ( latinská písmena jedna velká písmena + čísla) a rychlost hrubé síly je 100 000 hesel za sekundu ( třída útoku B , typická pro obnovu hesla z mezipaměti Windows ( soubory .PWL ) na Pentiu 100 ) [16] .
Počet znaků | Počet možností | Statečnost | Čas hledání |
---|---|---|---|
jeden | 36 | 5 bitů | méně než sekundu |
2 | 1296 | 10 bitů | méně než sekundu |
3 | 46 656 | 15 bitů | méně než sekundu |
čtyři | 1 679 616 | 21 bit | 17 sekund |
5 | 60 466 176 | 26 bit | 10 minut |
6 | 2176782336 | 31 bit | 6 hodin |
7 | 78 364 164 096 | 36 bit | 9 dní |
osm | 2,821 109 9x10 12 | 41 bit | 11 měsíců |
9 | 1,015 599 5x10 14 | 46 bit | 32 let |
deset | 3,656 158 4x10 15 | 52 bitů | 1162 let |
jedenáct | 1,316 217 0x10 17 | 58 bit | 41 823 let |
12 | 4,738 381 3x10 18 | 62 bitů | 1 505 615 let |
Hesla o délce do 8 znaků včetně obecně nejsou bezpečná. U moderních počítačů je toto číslo mnohem vyšší. 64bitový klíč (heslo) je tedy na moderním počítači vytříděn přibližně za 2 roky a vyhledávání lze snadno distribuovat mezi mnoho počítačů.
Moderní osobní počítače umožňují prolomení hesel hrubou silou s účinností uvedenou v tabulce výše. S optimalizací hrubou silou založenou na paralelním počítání však lze účinnost útoku výrazně zvýšit [18] . To může vyžadovat použití počítače přizpůsobeného pro vícevláknové výpočty . V posledních letech se rozšířila výpočetní řešení využívající GPU , jako je Nvidia Tesla . Od vytvoření architektury CUDA společností Nvidia v roce 2007 se objevilo mnoho řešení (viz např. Cryptohaze Multiforcer , Pyrit Archived 20. listopadu 2012 na Wayback Machine ), která umožňují zrychlené hádání klíčů pomocí technologií jako CUDA, FireStream , OpenCL .
V procesu zlepšování systému bezpečnosti informací ve vztahu k útoku hrubou silou lze rozlišit dva hlavní směry:
Je tedy nemožné dosáhnout vysoké úrovně ochrany zlepšením pouze jednoho z těchto parametrů [19] . Existují příklady, jak se ukázalo, že autentizační systém založený na optimální složitosti hesla je zranitelný vůči zkopírování databáze do místního počítače útočníka, načež byl vystaven útoku hrubou silou pomocí lokálních optimalizací a výpočetních nástrojů, které nejsou dostupné s vzdálená kryptoanalýza [20] . Tento stav věcí vedl některé odborníky na počítačovou bezpečnost k doporučení kritičtějšího přístupu k bezpečnostním standardním postupům, jako je používání hesel , která jsou co nejdelší [21] . Níže je uveden seznam některých praktických metod [22] [23] [24] zvýšení spolehlivosti kryptosystému ve vztahu k útoku hrubou silou:
Pro urychlení výčtu využívá metoda větví a vazeb eliminaci podmnožin proveditelných řešení, která zjevně neobsahují optimální řešení [25] .
Jednou z metod, jak zvýšit rychlost výběru klíčů, je paralelizace výpočtů . Existují dva přístupy k paralelizaci [26] :
Počítačové systémy, které k autentizaci používají hesla, musí nějakým způsobem určit, zda je zadané heslo správné. Triviálním řešením tohoto problému je vést seznam všech platných hesel pro každého uživatele, ale tento přístup není imunní vůči únikům databáze. Jednoduchý, ale nesprávný způsob, jak se chránit před únikem báze, je vypočítat kryptografickou hashovací funkci z hesla.
Metoda je nesprávná v tom, že je možné provést vyhledávání předem, a když potřebujete prolomit heslo, podívejte se na výsledek. Duhová tabulka je optimalizací této metody [27] . Jeho hlavní výhodou je výrazné snížení množství použité paměti [28] [27] .
PoužitíDuhová tabulka je vytvořena sestavením řetězců možných hesel. Každý řetězec začíná náhodným možným heslem, poté je podroben hashovací funkci a redukční funkci. Tato funkce převede výsledek hashovací funkce na nějaké možné heslo (pokud například předpokládáme, že heslo je dlouhé 64 bitů, pak funkce redukce může vzít prvních 64 bitů hashe, bitové přidání všech 64 bitů bloky hashe atd.). Mezilehlá hesla v řetězci jsou zahozena a do tabulky jsou zapsány pouze první a poslední prvky řetězců. Vytvoření takových tabulek vyžaduje více času, než zabere vytvoření běžných vyhledávacích tabulek, ale mnohem méně paměti (až stovky gigabajtů, při objemu pro běžné tabulky N slov, duhové potřebují jen asi N 2/3 ) [28 ] . Zároveň, i když vyžadují více času (ve srovnání s konvenčními metodami) k obnovení původního hesla, jsou v praxi schůdnější (sestavení běžné tabulky pro 6znakové heslo s bajtovými znaky, 256 6 = 281 474 976 Bude vyžadováno 710 656 paměťových bloků, zatímco pro duhu - pouze 256 6 ⅔ \u003d 4 294 967 296 bloků).
Pro obnovení hesla se tato hodnota hash sníží a vyhledá se v tabulce. Pokud není nalezena žádná shoda, pak se znovu použije hashovací funkce a redukce. Tato operace pokračuje, dokud není nalezena shoda. Po nalezení shody se řetězec, který ji obsahuje, obnoví, aby se našla zahozená hodnota, kterou bude požadované heslo.
Výsledkem je tabulka, která dokáže s vysokou pravděpodobností heslo v krátké době obnovit [29] .
Přestože jakákoli ochrana informačního systému musí být především spolehlivá ve vztahu k útoku hrubou silou, případy úspěšného použití tohoto útoku narušitelem jsou zcela běžné.
Šifrovací stroj Enigma, vynalezený v roce 1918, byl široce používán německým námořnictvem od roku 1929. Během dalších let byl systém modifikován a od roku 1930 byl aktivně využíván německou armádou a vládou během druhé světové války [31] .
První zachycení zpráv zašifrovaných kódem Enigma se datuje do roku 1926. Zprávy si však dlouho nemohli přečíst. Během druhé světové války docházelo ke konfrontaci mezi polskými a německými kryptografy. Poláci, kteří získali další výsledek v prolomení německého kryptosystému, čelili novým potížím, které přinesli němečtí inženýři, kteří neustále upgradovali systém Enigma. V létě 1939 , kdy se stala zřejmou nevyhnutelnost invaze do Polska, předalo předsednictvo výsledky své práce britské a francouzské rozvědce [32] .
Další práce vloupání byly organizovány v Bletchley Park . Hlavním nástrojem kryptoanalytiků byl dešifrovací stroj Bomba . Jeho prototyp vytvořili polští matematici v předvečer druhé světové války pro polské ministerstvo obrany. Na základě tohoto vývoje a s přímou podporou jeho tvůrců byla v Anglii navržena „pokročilejší“ jednotka.
Teoretickou část práce provedl Alan Mathison Turing [33] . Jeho práce na kryptografické analýze algoritmu implementovaného v šifrovacím stroji Enigma vycházela z dřívější dešifrovací analýzy předchozích verzí tohoto stroje, kterou v roce 1938 provedl polský kryptoanalytik Marian Rejewski . Principem fungování dešifrovače vyvinutého Turingem bylo vyjmenovat možné možnosti pro šifrovací klíč a pokusy o dešifrování textu, pokud byla známa struktura dešifrované zprávy nebo část otevřeného textu [34] .
Z moderního hlediska nebyla šifra Enigma příliš spolehlivá, ale pouze kombinace tohoto faktoru s přítomností mnoha zachycených zpráv, kódových knih, zpravodajských zpráv, výsledků vojenského úsilí a dokonce i teroristických útoků umožnila „ otevřít" šifru [32] .
Po válce Churchill z bezpečnostních důvodů nařídil zničení těchto strojů.
V roce 2007 začala skupina společností, které jsou členy organizace Wi-Fi Alliance , prodávat bezdrátové zařízení pro domácí sítě s podporou nového standardu Wi-Fi Protected Setup. Mezi výrobce bezdrátových routerů podporujících tuto technologii patřily takové velké společnosti jako Cisco/Linksys , Netgear , Belkin a D-Link . Standard WPS měl výrazně zjednodušit proces nastavování bezdrátové sítě a její použití lidem, kteří nemají rozsáhlé znalosti v oblasti síťové bezpečnosti. Koncem roku 2011 však byly zveřejněny informace o vážných zranitelnostech WPS, které umožnily útočníkovi uhodnout PIN kód [35] bezdrátové sítě během několika hodin s výpočetními prostředky běžného osobního počítače [36 ] .
Koordinační centrum CERT v tuto chvíli nedoporučuje výrobcům vydávat nová zařízení, která tuto technologii podporují. [37]
V roce 2010 byl na konferenci DEFCON18 představen bezpilotní letoun WASP , určený pro hromadný sběr statistik o domácích Wi-Fi sítích. UAV je vybaveno kompaktním palubním počítačem s BackTrack Linuxem , jehož jednou z vlastností byla schopnost automaticky prolomit hesla bezdrátových sítí pomocí hrubé síly [38] [39] .