Metodo forza bruta

Da Wikipedia, l'enciclopedia libera.

Questa voce è solo un abbozzo (stub). Se puoi, contribuisci adesso a migliorarla secondo le convenzioni di Wikipedia. Per l'elenco completo degli stub di matematica, vedi la relativa categoria.

Il metodo "forza bruta" è un algoritmo di risoluzione di un problema che consiste nel verificare tutte le soluzioni teoricamente possibili fino a che non si trova quella effettivamente corretta. Il metodo è anche noto come ricerca esaustiva della soluzione.

Il suo principale fattore positivo è che porta sempre a trovare la soluzione corretta, ma è anche vero che è 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'unica soluzione conosciuta e quindi anche la migliore.

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ò barattare la velocità 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 utilizzare); questa 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.

[modifica] Utilizzo in crittanalisi

In ambito crittanalitico questo metodo si utilizza in genere per trovare la chiave di un sistema che utilizza un cifrario di cui 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, ideata da Arthur Scherbius. Per ottenere il risultato infatti 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 computers, 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 sempre maggiore 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ⁿ), per la precisione) il tempo di cifratura e decifrazione in genere ha poca dipendenza con la lunghezza della chiave (per fare un esempio AES utilizzando chiavi di 256 bit è più veloce di DES, che può utilizzare solamente chiavi da 56 bit).

Un esempio pratico di attacco di forza bruta è tentare di aprire una valigetta con combinazione provando tutte le possibili combinazioni delle tre ruote 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 1000 a 10.000.

Bisogna prestare attenzione però al trade off tempo-memoria contro tempo-processori: come spiegato da Daniel Bernstein nell'articolo riportato, un calcolatore con 2³² processori è incomparabilmente più veloce del corrispondente calcolatore seriale di pari costo.

[modifica] Utilizzo in sicurezza informatica

Nell'ambito della sicurezza informatica questo metodo si utilizzare 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 italiana di 8 caratteri come password la sua sicurezza (il numero di tentativi che un attaccante deve fare) non è di 2⁶³ tentativi (una sicurezza equivalente a una chiave casuale di 64 bit) ma piuttosto il numero totale di parole italiane di 8 caratteri (una sicurezza equivalente di 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.