|
Il '''metodo "forza bruta"''' (anche noto come '''ricerca esaustiva''' della soluzione) è un [[algoritmo]] di risoluzione di un problema che consiste nel verificare tutte le soluzioni teoricamente possibili fino a che si trova quella effettivamente corretta. Il metodo è anche noto come '''ricerca esaustiva''' della soluzione.
Il suo principale fattore positivo è che portaconsente teoricamente sempre adi trovare la soluzione corretta, ma èper anche vero checontro è sempre la soluzione più lenta o dispendiosa; viene utilizzato come ultima risorsa sia in [[crittanalisi]] che in altre parti della [[matematica]] solamente in quei casi dove sia l'unicaunico soluzione conosciuta e quindi anche laprocedimento miglioreconosciuto.
Quando sul sistema è possibile un [[attacco offline]] (ovvero quando l'attacco si può eseguire su una copia di lavoro locale del sistema da attaccare) si può barattarecompensare la velocitàlentezza di esecuzione con la quantità di risorse necessarie: laddove un singolo computer possa "provare" 100.000 chiavi al secondo, due computer possono provarne il doppio e così via (la velocità aumenta linearmente con le risorse utilizzate);. questaQuesta caratteristica ha nei recenti anni motivato molti attacchi "distribuiti" sfruttando solo i cicli inutilizzati di migliaia e migliaia di comuni computer ([[Internet]] facilita di molto l'organizzazione di questo tipo di attacchi). Questo ovviamente non è applicabile a sistemi informatici dove sia possibile esclusivamente un [[attacco online]], né a sistemi che utilizzino protezioni fisiche quali lucchetti metallici: non è ovviamente possibile sveltirne l'apertura provando due o più chiavi alla volta.
== Utilizzo in [[crittoanalisi]] ==
In ambito crittanalitico questo metodo si utilizza in genere per trovare la [[chiave crittografica|chiave]] di un sistema che utilizzaimpiega un [[cifrario]] diper individuare il cuiquale non si conosca alcun attacco migliore, ed è noto appunto come '''attacco di forza bruta'''. Questo fu ad esempio il metodo utilizzato dal controspionaggio polacco e poi inglese per decifrare i messaggi tedeschi della macchina [[Enigma (crittografia)|Enigma]], ideata da [[Arthur Scherbius]]. Per ottenere il risultato infatti, essi utilizzarono la famosa ''[[Bomba (calcolatore)|Bomba]]'' ideata da [[Marian Rejewski]], una speciale macchina calcolatrice in grado di sottoporre il messaggio cifrato ad un attacco di forza bruta, fino a trovare la soluzione. La macchina venne poi perfezionata dagli inglesi, grazie al contributo del grande matematico [[Alan Turing]]. Questi primi rudimentali e mastodontici calcolatori erano lentissimi, se paragonati agli attuali computer, e potevano impiegare interi mesi per decifrare un breve messaggio. In tempi più recenti, per supplire alla sempre maggiore velocità dei computer disponibili in commercio, divenne necessario utilizzare [[chiave crittografica|chiavi]] di sempre maggiore [[Dimensione chiave|dimensione]]. Questa crescita delle dimensioni della chiave è sostenibile, dato che mentre lo spazio delle chiavi (e quindi il tempo necessario per un attacco forza bruta) aumenta esponenzialmente con la lunghezza delle chiave (come O(2<sup>n</sup>), per la precisione) il tempo di cifratura e decifrazione in genere ha poca dipendenza con ladalla lunghezza della chiave (per fare un esempio, [[Advanced Encryption Standard|AES]], utilizzando chiavi di 256 [[Bit (informatica)|bit]], è più veloce del [[Data Encryption Standard]] (DES), che può utilizzare solamente chiavi da 56 [[Bit (informatica)|bit]]).
Un esempio pratico di attacco di forza bruta è quello tentare di aprire una valigetta con serratura a combinazione provando tutte le possibili combinazioni delle tre ruote(in genere non sono più di tre) rotelle numerate. Per aumentare la protezione della valigetta da questo tipo di attacchi è necessario aumentare il numero di ruote numerate; siccome il numero di combinazioni in questo caso cresce secondo le potenze di dieci, con una ruota in più le possibili combinazioni passano da 10001.000 a 10.000.
Bisogna prestare attenzione però al ''trade off'', cioè tempo-memoria contro tempo-processori: come spiegato da [[Daniel J. Bernstein]] nell'articolo riportato, un calcolatore con 2<sup>32</suP> processori è incomparabilmente più veloce del corrispondente calcolatore seriale di pari costo.
== Utilizzo in [[sicurezza informatica]] ==
Nell'ambito della [[sicurezza informatica]] questo metodo si utilizza soprattutto per trovare la ''[[password]]'' di accesso ad un sistema. La differenza principale tra attaccare una [[chiave crittografica]] e attaccare una [[''password]]'' è che la prima è solitamente stata generata in modo totalmente casuale mentre una password, per la sua stessa natura di dover essere ricordata e inserita da esseri umani, è generalmente meno densa di informazioni. Utilizzando una parola [[lingua italiana|italiana]] di 8 caratteri come password la sua sicurezza (il numero di tentativi che un attaccante deve fare) non è di 2<sup>63</sup> tentativi (una sicurezza equivalente a una chiave casuale di 64 [[Bit (informatica)|bit]]) ma piuttosto il numero totale di parole italiane di 8 caratteri (una sicurezza equivalente a meno di 16 [[Bit (informatica)|bit]]). È quindi palese l'importanza di utilizzare password molto lunghe (spesso chiamate [[passphrase]]) oppure generate casualmente; queste due scelte non fanno altro che barattare la facilità di memorizzazione con la lunghezza e il tempo necessario per inserire manualmente la password.
==Voci correlate==
| 