Metodo forza bruta

Il metodo forza bruta (anche ricerca esaustiva), in informatica, è un algoritmo di risoluzione di un dato problema che consiste nel verificare tutte le soluzioni teoricamente possibili fino a che si trova quella effettivamente corretta. Il suo principale fattore positivo è che esso consente teoricamente di trovare sempre la soluzione corretta ma, per contro, questa è sempre la soluzione più lenta o dispendiosa: viene utilizzato come ultima risorsa sia in crittanalisi, sia in altre parti della matematica, ma solamente in quei casi in cui esso sia l'unico procedimento conosciuto o nei casi in cui altri algoritmi più performanti, tipo l'attacco a dizionario, abbiano fallito.

Descrizione

Utilizzo in crittoanalisi

In ambito crittanalitico, questo metodo si utilizza in genere per trovare la chiave di un sistema che impiega un cifrario per individuare il quale non si conosca alcun attacco migliore ed è noto appunto come attacco di forza bruta. Questo fu, ad esempio, il metodo utilizzato dal controspionaggio polacco per decifrare i messaggi tedeschi della macchina Enigma, ideata da Arthur Scherbius. Per ottenere il risultato, infatti, essi utilizzarono la famosa 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 chiavi di dimensione sempre maggiore. 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 della chiave (come $O(2^{n})$ , per la precisione), il tempo di cifratura e decifrazione in genere ha poca dipendenza dalla lunghezza della chiave. Per fare un esempio, utilizzando chiavi di 256 bit, AES è più veloce del Data Encryption Standard (DES), che può utilizzare solamente chiavi da 56 bit.

Un esempio pratico di attacco di forza bruta è quello di tentare di aprire una valigetta con serratura a combinazione provando tutte le possibili combinazioni delle rotelle numerate, che in genere sono solo tre e contengono ognuna una cifra da zero a nove; le combinazioni totali, ossia i numeri da 000 a 999, sono in tutto 1 000, e altrettanti sono i tentativi massimi necessari per trovare la combinazione esatta. Per aumentare la protezione della valigetta da questo tipo di attacchi è possibile 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 1 000 a 10 000. Bisogna prestare attenzione però al trade off, cioè il rapporto tra tempo-memoria e tempo-processori: come spiegato da Daniel J. Bernstein nell'articolo riportato, un calcolatore con $2^{32}$ 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 a 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 italiana di otto caratteri come password, la sua sicurezza (il numero di possibilità che un attaccante deve testare) non è di $2^{63}$ tentativi (una sicurezza equivalente a una chiave casuale di 64 bit) ma piuttosto il numero totale di parole italiane di otto caratteri (una sicurezza equivalente a meno di 16 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.

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ò compensare la lentezza di esecuzione con la quantità di risorse; 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). Questa caratteristica ha motivato, nei recenti anni, 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 non è applicabile a sistemi informatici dove sia possibile esclusivamente un attacco online, né a sistemi che utilizzino protezioni fisiche quali lucchetti metallici; non è possibile velocizzarne l'apertura provando due o più chiavi alla volta.