Nei giorni scorsi ci siamo
imbattuti nella richiesta, da parte di un organo ufficiale, di recuperare
alcune password di sistema su alcuni pc.
I pc in questione avevano
sistema operativo Microsoft, ma avremmo potuto replicare la cosa anche su altri
OS.
Senza entrare nel dettaglio
delle operazioni svolte mi è sembrato interessante pubblicare un articolo sulle
Rainbow Table, di cui ringrazio F.M., tanto per far comprendere cosa c’è dietro
il mondo delle password.
1.
Introduzione
Ore di lavoro per installare
il nostro Windows XP nuovo fiammante, aggiornato all’ultimo bugfix; scelta una
buona password alfanumerica finalmente cediamo alle tentazioni di Morfeo,
tranquilli che il nostro sistema sia perfettamente sicuro.
Quanti si riconoscerebbero in
tale descrizione?
Quale che sia il vostro
sistema, simili supposizioni sono totalmente infondate (perfettamente sicuro un
sistema multiutente connesso alla rete? non scherziamo!). Quindi giusto per
rovinare il vostro meritato riposo vi informo che chiunque, senza scomodare i
grandi esperti di sicurezza, potrebbe decifrare la vostra password in qualche
decina di secondi (in senso letterale!).
“Ma come? Un normale attacco
brute-force può richiedere anni (o anche secoli con taluni algoritmi!) e sono
sicuro che la mia password non sia così classica da potersi facilmente
ritrovare in un dizionario!”
2.
Password e Hash
Torniamo un attimo indietro e
introduciamo come vengono memorizzate le nostre password: ovviamente non
desideriamo che tali sensibili informazioni risultino leggibili in chiaro
perciò ci affidiamo a particolari algoritmi di
cifratura (detti “one-way”, a
senso unico) che codificano secondo funzioni matematiche non invertibili la
nostre password; ciò significa che non è
possibile decodificarle
direttamente a partire dal risultato cifrato.
Questo valore generato è detto
hash ed è teoricamente univoco, non dovrebbero esistere
due stringhe diverse che codificate generino lo stesso hash:
tale eventualità è chiamata collisione e una sua scoperta porterà
lentamente l’algoritmo ad essere dichiarato non sicuro; tra le altre proprietà
comuni alla maggior parte delle funzioni di hashing ricordo infine la
dimensione prefissata dell’hash qualunque sia la lunghezza del messaggio
cifrato.
Dunque quando digitiamo la
nostra password viene ricalcolato il codice hash con la medesima funzione e
confrontato il risultato con quello in memoria.
Le combinazioni possibili
(variano tra algoritmi) sono superiori all’ordine dei milioni di miliardi,
lasciandoci ingannevolmente sicuri sull’indecifrabilità del nostro codice.
Spendiamo infine poche ultime
righe per introdurre un’altra notevole potenzialità delle funzioni di hashing,
la certificazione: notando infatti che non dovrebbero esistere due messaggi
generanti lo stesso valore hash risulta evidente come quest’ultimo rappresenti
una sorta di impronta digitale dell’informazione che l’ha prodotto. Questa
particolarità permette l’uso di valori hash come certificazione
dell’autenticità di un messaggio: se esso venisse modificato,
quasi sicuramente cambierebbe
anche l’hash corrispondente; ciò è applicabile in qualsiasi contesto, per
esempio è frequentemente in uso nelle reti peer-to-peer per ricercare i files
(anche se i vari peer li avessero memorizzati su disco con nomi diversi l’hash
rimarrebbe uguale).
3.
Le Rainbow Tables
Veniamo ora alle Rainbow
Tables. L’idea part´i negli anni Ottanta dal matematico americano Martin
Hellman: il segreto è una tecnica chiamata timememory trade-off (tradotto
“compromesso tempo-memoria”) di cui le
Rainbow Tables sono una
raffinata evoluzione.
Alla base c’è una
considerazione piuttosto semplice: perchè cifrare ogni volta tutte le possibili
combinazioni fino a ricavare l’hash corrispondente alla password cercata? Se
avessi anzitempo criptato e memorizzato ogni combinazione possibile, una sorta
di elenco telefonico dell’algoritmo, potrei molto più agilmente eseguire una
ricerca nel mio archivio e trovare l’hash corrispondente,risparmiando notevole
tempo; infatti il maggior spreco di burst time della cpu è proprio
nella codifica ripetuta delle password, non nel confronto.
Compreso ciò sussiste solo un
problema: un archivio tale da contenere tutti gli hash frutto delle
combinazioni alfanumeriche di password sufficientemente lunghe supererebbe le
decide di terabyte (1 terabyte = 1024 gigabyte)!
Un comune elaboratore non
possiede né tanta memoria né sufficiente potenza per analizzarla: ecco
intervenire le Rainbow Tables.
3.1.
L’idea di Oechslin
Philippe Oechsin, un esperto
in sicurezza, ha ideato un procedimento per ridurre un archivio di hash in una
tabella molto più piccola.
Non è scopo
di questo breve documento illustrare in modo dettagliato le funzioni
matematiche alla base di questa tecnica: per tali necessità si rimanda al documento
originale dell’autore, di cui è disponibile il link nell’ultima pagina;
qui daremo solo un’idea di
come funzioni il procedimento: per prima cosa codifichiamo la nostra password e
otteniamo l’hash corrispondente; ora dobbiamo definire una formula di riduzione
R(hash) tale che ad un hash faccia
corrispondere una password:
ovviamente non sarà quella di partenza, abbiamo inizialmente ribadito
l’impossibilità di invertire una funzione di hashing!
Iteriamo t volte il seguente
procedimento: generiamo l’hash della nuova password e applichiamo le formula di
riduzione Ri(hashi) i = 1, 2, . . . , t dove i indica i passaggi effettuati.
Definiamo quindi
fi+1 = Ri(HashAlgorith(fi))
dove fi = password i
ovvero ciò che abbiamo appena
detto: la password al passo i+1 è il risultato della formula di riduzione
i-esima applicata all’i-esimo hash.
In questo modo genereremo una
catena “password-hash-password-hash” di migliaia di elementi ma di questi solo
il primo e l’ultimo verranno conservati su disco con un risparmio di memoria
pari a t volte!
Ora quando vorremo confrontare
il nostro hash gli applicheremo ft e controlleremo che il risultato non sia
l’ultimo elemento di una delle nostre catene (di cui come appena detto
conserviamo solo l’inizio e la fine); se ciò non fosse
vero applicheremo in sequenza
ft-1 e ft e
riconfronteremo il risultato con l’ultimo elemento delle catene: continuando
con questo procedimento all’iesimo passaggio dovremmo ricavare che il nostro
hash fa parte di una certa catena X e quindi con discreta probabilità la nostra
password sarà quella che precede nella catena (generata dalla R(i-1)(hash i-1)). Non è possibile risalire la
catena (dovremmo invertire una funzione di hashing!) ma abbiamo memorizzato l’inizio
di tale catena e possiamo perciò riapplicargli in sequenza gli t - i passi necessari a ritrovare la
password del passo precedente.
Essa è un’ottima candidata:
ricaviamone l’hash e confrontiamo il risultato;
questo metodo porta raramente
a falsi allarmi dovuti a eventuali collisioni (generati dalle formule di riduzione)
lungo la catena; al contrario la versione originale di tale metodo applicava
un’unica R(hash i) ad ogni passo, con rilevanti
percentuali di errore.
Tale procedimento che può
apparire di difficile computazione è in realtà velocissimo e, aspetto particolare
delle Rainbow Tables, il tempo di cracking si riduce col quadrato della
grandezza della tabella (cioè, incredibilmente, usare una tabella da 1 gigabyte
è 16 volte più veloce di una da 256 megabyte!).
3.2.
Servizi online
Ora qualcuno domanderà:
“Grazie tanto! Se avessi avuto
la potenza per codificare così tante password atte a realizzare complesse
tabelle non mi sarei dato pena!”
In effetti per computer
casalinghi realizzare una buona tabella è pressoché impossibile a meno di
attese di svariati anni (è comunque possibile realizzare proprie tabelle per
password brevi e con charset limitati in qualche decina
di giorni); se però operassi
con diverse centinaia di server in parallelo potrei ridurre tale tempo a pochi
mesi. Su internet si trovano archivi già pronti per numerosi algoritmi (LM,
NTLM, MD5, SHA1 e altri) realizzati proprio da
chi dispone di tali strutture:
i più semplici sono gratuiti e solitamente non superano il gigabyte, quelli
complessi (spesso costosi) che coprono lunghe combinazioni alfanumeriche e di
simboli superano il terabyte.
Inoltre è spesso possibile
usufruirne direttamente online, lasciando anche la computazione necessaria alla
ricerca a carico dei server: una semplice ricerca con Google fornirà dozzine di
tale siti, sia gratuiti che a pagamento.
4.
Difendiamoci: le salt password
Un quesito è d’obbligo: come
difendersi? Per cominciare rimane sempre buona norma la seguente regole base
nella scelta di una password: minimo otto cifre con uso di caratteri
alfanumerici (maiuscoli e minuscoli) e simboli.
Contro le Rainbow Tables ciò
però non basta, un attacker in possesso di tabelle sufficientemente ampie
forzerebbe comunque tale password: vengono dunque in aiuto le salt password
(“password salate”), una tecnica in uso
sui sistemi *nix e derivati da
oltre 25 anni (ora chiedetevi perchè il buon XP ancora non implementa tale
tecnica!). L’idea delle salt password è tanto semplice quanto efficace: prima
di codificare la password le si aggiunge un
insieme di bit casuali,
tipicamente all’inizio o alla fine, ricavati ad esempio dall’username, dalla
data o dal clock e solo poi si esegue la cifratura.
All’hash corrispondente è poi
ri-aggiunto, in chiaro, tale set di bit (anche qui solitamente all’inizio o
alla fine). Ecco un esempio chiarificatore (i valori dell’hash sono inventati e
non corrispondono a nessun particolare algoritmo):
Password: NuVoLoSo
Salt prescelto: cX
Password da codificare:
cXNuVoLoSo
Hash corrispondente:
ZT~OZ~ONbTL¸c)^AE?
Valore cifrato conservato in
memoria: cXZT~OZ~ONbTL¸c)^AE?
Il vantaggio di tale tecnica è
chiaro: a salt differenti corrispondono hash differenti per password uguali,
rendendo di fatto inutile la tecnica delle Rainbow Tables o di altri dizionari
di hash preconfezionati (senza sapere il
salt a priori nessuno potrà
generarle); l’unica possibilità potrebbe essere nel calcolare tabelle per salt
differenti ma ogni bit del salt duplica la grandezza dell’archivio e il tempo
necessario a realizzarlo!
A titolo di esempio i primi
sistemi Unix utilizzavano un salt a 12 bit unito all’algoritmo DES (Data
Encryption Standard, nonostante da anni sia considerato insicuro è ancora, seppure modificato, usato di default
in molte
distribuzioni!): ciò significa
che ogni password aveva 212 = 4096 diverse combinazioni; è evidente che tale
tecnica espande in modo inaccettabile la grandezza degli archivi e inoltre nei
sistemi odierni spesso il numero dei bit
di salt è ancora maggiore
(generalmente 216 = 65536 combinazioni).
Tralasciando la famiglia
Windows praticamente tutti i sistemi operativi utilizzano la tecnica salt ma ciò
non vale per molti altri applicativi e anche per numerose sessioni PHP e MySQL
(nonostante sia attivabile): in tutti questi
casi un attacco tramite
Rainbow Tables risulta terribilmente efficace.
5.
Conclusioni
Credersi ben protetti solo
perché si dispone dell’ultimo modello di pc, con sistema operativo aggiornato e
dotazione di firewall, antivirus, antispyware, ecc... è una vana chimera per
bambini.
La sicurezza informatica è un
aspetto troppo spesso tralasciato, come drammaticamente dimostra il sistema
operativo più usato al mondo che ad oggi ancora non implementa nemmeno tecniche
semplici e facilmente applicabili come le salt password. Aumentando le
potenzialità (velocità e densità di memoria) degli hard-disk e la potenza delle
cpu, diminuirà il tempo necessario ad attaccare un qualsiasi algoritmo (sia con
metodi time-memory trade-off che con attacchi brute-force); naturalmente anche
gli algoritmi stessi si evolvono ma una basilare conoscenza dell’argomento
aiuterà quantomeno a riflettere sull’intrinseca insicurezza delle password con
cui abitualmente lavoriamo.
E allora: le password sono una
coperta che lascia scoperti i piedi? Beh, a tal proposito aggiungerei una
citazione di Thomas Ptaceck:
“Here’s what you need to know about rainbow tables: no modern password
scheme is vulnerable to them. Rainbow tables are easy to
beat. For each password, generate a random number (a nonce). Hash the password
with the nonce, and store both the hash and the nonce. The server has enough
information to verify passwords (the nonce is stored in the clear). But even
with a small random value, say, 16 bits, rainbow tables are infeasible: there
are now 65,536 “variants” of each hash, and instead of 300 billion rainbow
table entries, you need quadrillions. The nonce in this scheme is called a
“salt”. Cool, huh? Yeah, and Unix crypt —- almost the lowest common denominator
in security systems —- has had this feature since 1976. If this is news to you,
you shouldn’t be designing password systems. Use someone else’s good one. No,
really. Use someone else’s password system. Don’t build your own”.
6.
Fonti e link utili
• Il documento in cui Oechslin
illustra pi´u dettagliatamente la tecnica e le formule alla base delle Rainbow
Tables (vivamente consigliato):
http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf
• Intervista all’autore sulle
possibilità e le capacità delle Rainbow Tables:
https://www.isc2.org/cgi-bin/content.cgi?page=738
• Il programma di Oechslin,
Ophcrack, e alcune tables:
http://ophcrack.sf.net
• Progetto e documentazione
RainbowCrack:
http://www.antsight.com/zsl/rainbowcrack/
• Salt password - Wikipedia:
http://en.wikipedia.org/wiki/Salt_(cryptography)