Crea sito

Il principio dei cassetti

Posted by JimsonWeird on settembre - 29 - 2011
10 piccioni in 9 caselle

10 piccioni in 9 caselle

Il principio dei cassetti è uno di quei principi talmente banali della combinatoria da sembrare inutile, ma che nasconde insidie non scontate. Parleremo infatti di come un hacker potrebbe usarlo per violare una chiave crittografica ritenuta sicura. Non sto parlando di un caso ipotetico, ma di uno reale: la codifica in questione si chiama MD5.

Ma per cominciare, partiamo dai piccioni.

[ Pigeonhole principle : principio dei cassetti : principio del colombario : principio della scatola di Dirichlet : principio di Dirichlet]

Se avete un colombario con 9 posti e 10 piccioni vi risulterà evidente che in almeno una casella ci dev’essere più di un piccione.

Potrei fare un altro esempio: abbiamo parlato spesso di dadi (e non ci sperate, non ho finito) ed allora se lanciassimo 7 dadi a 6 facce è ovvio che almeno 2 dadi avranno lo stesso valore, sempre per lo stesso principio (provare per credere)

Dati m oggetti da disporre in n raggruppamenti, se m > n allora almeno un raggruppamento dovrà contenere più di un oggetto.

La formalizzazione non vi spaventerà, vista la semplicità del principio.

[ Principio di Dirichlet : nota storica ]

Tale principio fu formalizzato per la prima volta da Dirichlet nel 1834. Anche prima di lui i piccioni sapevano come disporsi in un colombario e non pensiate che a Dirichlet sia servito per sistemare i suoi polli. Dirichlet lo chiamò Schubfachprinzip (principio dei cassetti, appunto) e lo utilizzò per dimostrare un ben più complesso problema della teoria dei numeri, legato ai numeri primi.

[ l'MD5 ]

Io penso che molti di voi ritengano poco utile un simile principio. Eppure il ragionamento che c’è dietro richiede più attenzione di quanto sembri. Dimentichiamocelo per un attimo.

Pensiamo di avere un sistema di autenticazione e di voler salvare le password degli utenti su un database.

Ci sembra una mossa piuttosto azzardata quella di salvare le password degli utenti così come sono: se uno trovasse il file passwd – o avesse accesso alla tabella, lasciatemi questa libertà di spiegazione – vi troverebbe tutte le password degli utenti in chiaro, senza neanche doversi affannare un po’.

Possiamo pensare di crittografare la password: se la mia password fosse “pigeonhole” potrei convertirla tramite un algoritmo, ad esempio il celebre ROT13 ed allora diverrebbe “cvtrbaubyr”. A questo punto sarei un po’ più sicuro ma… un algoritmo come ROT13 è invertibile: se ne capisco il meccanismo potrò decifrare comunque tutte le password. ( ROT13 soffre anche di un altro piccolo difetto, se cifrate “cvtrbaubyr” otterrete di nuovo “pigeonhole”, ma questa è un’altra storia – sempre interessante ma sarà per la prossima volta)

Nasce così, per mano del grande Ronald Rivest, l’algoritmo MD5: esso non è invertibile. Da una qualsiasi parola, di qualsiasi lunghezza, otterrete una stringa di 128 bit. Anche se conoscete la password cifrata e l’algoritmo MD5 non vi sarà sufficiente per risalire alla password originaria.

Quando un utente entra, la sua password viene di nuovo cifrata con MD5, confrontata con la parola cifrata nel file delle password (parola nota come hash) e se corrispondono l’utente è abilitato. Se ne deduce che, non essendo invertibile, se l’utente perde la password.. dovrà farsela resettare in qualche modo perché non la può recuperare nessuno: non esiste una funzione inversa che ci riporta dall’hash alla password.

Sembra perfetto, no?

[ gli hacker e il principio dei cassetti : hash collision ]

Adesso però, ricordiamoci di nuovo del principio dei cassetti. L’algoritmo MD5 è dunque una funzione che trasforma una qualsiasi parola o frase in un hash di 128 bit (si parla di hash function). Gli hash possibili sono dunque 2^128. Le parole generatrici sono però teoricamente infinite!

Questo equivale a disporre infiniti piccioni – le password che è possibile ideare – in un numero finito di cassetti – 2^128 hash possibili. m > n, poiché infiniti elementi sono senza dubbio più di 2^128. Sapete che vuol dire? Che esiste più di una password che genera lo stesso hash. Dunque non è necessario per un hacker trovare la password originaria. Per il principio dei cassetti, infatti, sarà sufficiente trovare una qualsiasi parola che generi lo stesso hash della vera password. Due piccioni con un cassetto.

Tecnicamente si chiama hash collision (collisione hash) e deriva dal fatto che la funzione hash non è biiettiva: l’insieme delle parole generatrici ha più elementi dell’insieme di destinazione, quello degli hash. Esiste dunque almeno un hash che ha più di una parola generatrice. Ovviamente la probabilità di trovare una collisione è piuttosto rara, ma aumenta per via del paradosso del compleanno quando analizziamo molti hash contemporaneamente. Ciò è sufficiente per poter dire che l’algoritmo MD5 è vulnerabile alle collisioni.

Nota: l’MD5 corrispondente a “pigeonhole” è “f635f8ab6fa4ecf3f822e28cfa1ff10f”

Leave a Reply


Jimson Weird

Un cyberalchimista moderno per un blog ipostatico
e-mail: