La forza "brutta"

L'anno scorso, prendendo lo spunto da un commento su FB di un amica, scrissi il pezzo Parole chiave e forza bruta dove semplicemente mi limitavo a chiarire quella che è una conoscenza comune per chi ha studiato informatica ma che, probabilmente, non è altrettanto palmare all'uomo (o alla donna) qualunque.

Il concetto era questo: i calcolatori, per quanto sempre più potenti, non sono comunque in grado di risolvere in tempi accettabili dei problemi che richiedono soluzioni di tipo combinatorio (ovvero dove si deve combinare insieme qualcosa). Il motivo è che la complessità di una soluzione combinatoria è esponenziale e non lineare: questo significa che un problema di complessità esponenziale richiede un tempo di risoluzione esponenziale rispetto alla sua dimensione: a sua volta questo significa che aumentando anche di poco la dimensione del problema il tempo di risoluzione cresce enormemente di più.

La cronaca ci riporta in questi giorni un caso interessante: Violata la sicurezza della scatola nera che sblocca tutti gli iPhone di Marco Tonelli da LaStampa.it

L'articolo spiega che è stata ideata una macchinetta che, usando un algoritmo di forza bruta (ovvero provando tutte le combinazioni), è in grado di individuare la parola chiave che blocca un iPhone.
L'ultimo paragrafo contiene poi due dati interessanti: la macchinetta è in grado di trovare una parola chiave di 4 cifre in 2 ore e di 6 cifre in poco più di 3 giorni.

Mi sono quindi divertito a effettuare qualche calcolo.
Siccome l'ordine di grandezza di questo tipo di problemi è esponenziale allora, in prima approssimazione, avrà una forma del tipo: c* b^n (ovvero: una costante “c” che moltiplica una base “b” elevata all'esponente “n” pari alla dimensione del problema, ovvero al numero di caratteri della parola chiave).
Ho fatto quindi un piccolo sistema:
1) c*b^4=2
2) c*b^6=75 (3 giorni più 3 ore)

Da 1) ho ricavato: c=2/b^4 e sostituendolo in 2) si ha: 2*b^2=75 e quindi b=Radice(75/2)=6.1237
Sostituendo b=6.1237 in c=2/b^4 si ottiene c=0.0014

In altre parole:
0.0014*6.1237^4=2 (circa!)
0.0014* 6.1237^6=75 (circa!)

Grazie a questi numeri è quindi possibile stimare il tempo che occorre (in ore) per trovare una parola chiave di 8 caratteri. Cioè:
0.0014*6.1237^8=2768.47 ore pari a 115.35 giorni (un po' meno di 4 mesi)

Invece per una parola chiave di 10 caratteri occorrerebbe un tempo pari a:
0.0014*6.1237^10=104.268 ore, pari a 4.345 giorni, pari a 11.9 anni.

Invece la penultima parola chiave che usavo per il mio calcolatore era di 15 caratteri: se l'avessi usata per l'iPhone (che non possiedo) sarebbe stata trovata in:
0.0014*6.1237^15=907.677.687 ore, pari a 37.819.904 giorni, pari a 103.616 anni. Sempre che in questi cento millenni non andasse mai via la corrente costringendo la macchinetta a ricominciare dall'inizio!

In realtà c'è qualcosa che non mi torna: non so che tipo di parole chiave accetta un iPhone, ovvero che caratteri siano ammissibili. Presumendo che si possano adoperare caratteri alfanumerici e i simboli classici della tastiera si avrebbero allora un totale di 26*2 (maiuscole e minuscole) + 10 (cifre numeriche) + 33 (altri caratteri) = 95 simboli. Questo significa che la base “b” calcolata poc'anzi dovrebbe essere 95.
Il fatto che invece risulti essere poco più di 6 secondo me si può spiegare col fatto che i dati riportati dall'articolo siano dei tempi medi. Probabilmente l'algoritmo è sì basato sulla forza bruta ma usa degli stratagemmi, come un vocabolario, per analizzare prima le sequenze più probabili.
Questo perché le parole chiave usate dalle persone sono più spesso della forma “Anna91” piuttosto che “/D6qq)”...

Questo significa anche che nei casi più “sfortunati” il tempo richiesto per trovare la soluzione sarà sensibilmente più lungo. Probabilmente i 103.616 anni richiesti per individuare la mia vecchia parola chiave di 15 caratteri sono una stima MOLTO ottimistica!

Conclusione: ovviamente io uso parole di 15 caratteri solo perché non ho niente da nascondere: se fossi un trafficante di droga o un terrorista sarei molto più paranoico: userei parole chiave lunghe il doppio e, comunque, non scriverei niente di importante sul calcolatore!

Share