linux user group brescia

On Tue, Oct 26, 2004 at 05:03:40PM +0200, Sergio Bevilacqua wrote:


> i matematici fanno fior fior di teorie partendo da ragionamenti puri, la
> cui dimostrazione provoca, in generale, suicidi di massa...
> gli algoritmi di hashing sono aggeggi puramente matematici... quindi il
> fatto che in pratica non sia ancora stata applicata a casi concreti non
> mi sconvolge né le fa perdere credibilità.

Giusto un paio di cosucce sulle funzioni di hash.
La sostanza e' che una funzione di hash e', per definizione, una funzione
che va dallo spazio dei messaggi, rappresentati dalla combinazione di 
simboli di un alfabeto, ad uno spazio di dimensione limitata (per esempio 
uno spazio rappresentabile mediante 128bit, ovvero 2^128 valori). Per 
definizione un hash e' anche una funzione tale che, data la rappresntazione
in hash, non sia computazionalmente "conveniente" (o possibile) ricavare 
il messaggio originale.

Data la definizione veniamo ad un paio di considerazioni.
1. Converrai con me che passando da uno spazio virtualmente illimitato a 
uno spazio limitato a 2^128 bit, la funzione di hash non puo' essere 
iniettiva, quindi tantomeno invertibile. Un attacco ad un hash puo' avvenire 
quindi mediante forza bruta. A questo punto pero', dato un hash, esistono piu' 
possibili messaggi originali da esso rappresentati. Quale scegli? Qui non si
parla di cifratura e decifratura con chiave simmetrica come DES che, una 
volta identificata la chiave, ricavi con facilita' un solo messaggio.
Il fatto che DES (56bit di spazio delle chiavi) sia crackabile con relativa 
facilita' non significa assolutamente che un hash sia craccabile.


2. Il problema della collisione da te citato indica solo ed esclusivamente
l'esistenza di stringhe di senso compiuto (ad esempio testo) che hanno 
una stessa rappresentazione hash. Da qui al dichiarare un algoritmo di hash
debole o crackabile ce ne corre (e poi debole in base a che parametri?).
Sicuramente la presenza di collisione e' un (flebile) campanello di allarme,
ma prima di poter sfruttare eventuali debolezze strutturali della funzione 
di hash potrebbe passare un tempo talmente grande da rendere inutile
l'opera di crack dell'hash.

Caio,
Nicola.

PS: Mi scuso per la prolissita'
PPS: I matematici che leggono la ml abbiano pazienza per eventuali 
strafalcioni (sono un po' arruginito sulla matematica)


-- 
Real programmers don't write in Pascal, or Bliss, or Ada, or any of
those pinko computer science languages. Strong typing is for people
with weak memories.