Newsgroup: it.comp.sicurezza.crittografia
Titolo: Algoritmo di "riassunto" di un testo (Hash?)

Salve a tutti,
sono in cerca di un algoritmo che mi calcoli il "riassunto" di una serie 
di dati.
La caratteristica che questo algoritmo deve avere è che al variare dei 
dati, il valore assunto dal digest non debba essere del tutto dissimile 
dal digest originale.
Mi spiego.
Se calcolo il digest delle frasi "Ciao a tutti" e "Ciao a Totti" 
utilizzando l'MD5, i digest che ottengo sono estremamente diversi.
A me invece servirebbe un algoritmo che mi creasse dei digest molto 
simili, tali per cui si potrebbe capire, analizzando i digest, che le 
due frasi di partenza sono simili.
Una cosa simile a quella che fa la funzione Soundex 
(
http://en.wikipedia.org/wiki/Soundex
) però su testi anche molto lunghi.
L'utilizzo è presto spiegato.
Ho creato un antispam (di cui non voglio fare pubblicità) in cui gli 
utenti si scambiano delle definizioni di spam.
Ogni definizione altro non è che l'MD5 di alcune parti della mail.
Ovviamente gli spammer, spesso e volentieri, creano varie versioni della 
stessa mail, magari con un pezzo di testo o anche solo parti di 
punteggiatura "diverse".
In questo modo però ogni versione genererà un nuovo MD5.
Quello che a me serve invece è che i digest generati per ogni versione 
della mail siano tanto più simili quanti meno dati sono cambiati (mi 
aspetto che se sono variate solo 1 o 2 parole su un testo di 200 parole, 
i digest possano essere addirittura uguali).
Mi scuso se non ho utilizzato terminologia specifica, ma cercando su 
google non sono riuscito a trovare granchè, in quanto non so neanche di 
preciso qual'è l'argomento da cercare.
Grazie
Nicola Ottomano

Nicola Ottomano ha scritto:

La cosa sembra interessante ma non credo o non so (dimostro la mia 
ignoranza) se esista un algoritmo simile ... in ogni caso in bocca al 
lupo ...
-- 
[CapoBecchino]
msn: capobecchino |[@]| hotmail |[.]| com
SEZIONE OFFERTE IRRIPETIBILI: Muori oggi avrai uno sconto del 50%

 i digest possano essere addirittura uguali).
E'una idea interessante, ma penso che dovrai orientarti su qualcosa di
abbastanza diverso dai classici algoritmi di hashing; in effetti un
paradigma quasi costante è quello di cercare di "spalmare" le
differenze sul più grande numero di bit possibili in modo da
distruggere eventuali pattern che potrebbero portare a trovare una
correlazione (probabilistica) tra variazioni nell'hash e variazioni
del messaggio.
Forse ti converrebbe cercare qualcosa di adatto a testi più ampi ma
rimanendo in una casistica di algoritmi digest di diversa concezione
simili a Soundex o NYSIIS.

giorgio.tani ha scritto:

Il problema di Soundex e NYSIIS è che si basano su singole parole o su 
aggragati di due/tre parole. Su un testo molto lungo, invece, creano un 
digest (se così si può chiamare) poco utile, in quanto basato solo sulla 
prima porzione del testo stesso.
Nicola

Si potrebbe pensare a concatenare i diversi digest o serve
necessariamente un output di lunghezza fissa?
Oppure, cambiando approcio al problema, si potrebbe pensare ad un
sistema di ranking, similmente a quanto fanno i motori di ricerca, per
vedere se nel testo sono presenti parole (o link) abitualmente usate
nello spam ed eventualmente limitare il digest alle parole più
rilevanti.
Purtroppo il problema degli hash classici è che cercano di fare
proprio l'opposto di quanto serve nel caso in oggetto, cioè fanno si
che ciascun bit in entrata modifichi in modo uniforme su tutta
l'ampiezza dell'hash quanti più possibili bit in uscita, proprio per
far si che le differenze negli output tra le varianti di uno stesso
input siano distribuite in maniera statisticamente uniforme tra i vari
possibili valori che può assumere l'hash, per renderlo resistente
contro tentativi di correlazione negli scenari in cui l'attaccante
possa inviare alla funzione degli input scelti appositamente.

 possa inviare alla funzione degli input scelti appositamente.
Esattamente questo il problema... bisognerebbe capire innanzitutto come 
può essere definito l'algoritmo che sto cercando (non è hash, allora 
cos'è?) e poi cercare in quella direzione...
bye

 cos'č?) e poi cercare in quella direzione...
Sai che la cosa si fa interessante ... ora ci studio e ti fo sapere ... ;)
-- 
[CapoBecchino]
msn: capobecchino |[@]| hotmail |[.]| com
SEZIONE DIVERTIMENTO & AFFINI: La maestra a pierino: " Pierino 
all'interrogazione non hai risposto a nessuna domanda. Cosa vuoi fare da 
grande?" e Pierino: " ...l'agente segreto!"

 cos'è?) e poi cercare in quella direzione...
La definizione di hash è piuttosto ampia, vi può tranquillamente
rientrare anche una funzione che manchi della proprietà di diffusione
e quindi dell'effetto valanga, che è quanto servirebbe nello scenario
descritto... però temo che gli algoritmi di hash più usati non
rientrino in questo caso, anzi, una buona fetta di ricerca post MD5
(quindi SHA/SHA2, RIPEMD, Tiger, Whirlpool...) è andata proprio verso
hash da utilizzare in crittografia, e quindi con una robusta capacità
di diffusione, perchè è un campo che ha avuto una notevole espansione
negli ultimi anni, diciamo da metà anni '90 con il boom delle reti
pubbliche ed Internet e i problemi di sicurezza che hanno comportato
per la massa degli utenti.
Forse potrebbe essere un inizio l'algoritmo di hashing utilizzato nel
metodo Rabin-Karp?
E' abbastanza leggero e la diffusione/effetto valanga non mi sembra
sia stata presa in considerazione perchè si applica a scenari molto
diversi dalla crittografia.
http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

 i digest possano essere addirittura uguali).
Il mio suggerimento:
Prendi le 200 parole, le codifichi in base64 (giusto per comodità)
estrai una lettera ogni 5% di testo codificato (dipende dalla tua media 
di testo e dall'accuratezza del digest che vuoi ottenere) su 1000 
caratteri ottieni una stringa di 20 chr
tra i due digest fai un confronto carattere per carattere per vedere 
QUANTO sono simili.
purtroppo non ho il tempo di fare prove per avvalorare questo mio 
suggerimento.
saluti e buon lavoro

 cos'è?) e poi cercare in quella direzione...
DSpam fa qualcosa di molto simile, creando una sorta di "genoma" del
messaggio. Puoi provare a dare un'occhiata al codice e provare a capire
se/cosa/quanto puoi derivare da quella logica.
Ciao, e in bocca al lupo!

William Maddler ha scritto:

Grazie, ma DSPAM utilizza un algorimo bayesiano leggermente 
modificato... cosa molto diversa da ciò che sto cercando.
Nicola

 Il mio suggerimento:
[CUT]
Era quello che avevo pensato ma, se uno spammer varia uno o più 
caratteri all'interno del testo mi frega.
L'idea che sto cercando di seguire è quella di trovare dei "segni di 
riconoscimento" nella mail. Un pò come avviene per gli esseri umani 
dove, anche se uno cambia il taglio di capelli, resta comunque 
riconoscibile.
Poi si potrebbe codificare questi dati ed inviarli agli altri utenti.
Il problema di questo approccio è che vi è una parte basata sulla 
probabilità, quindi un'analisi euristica, che porta indubbiamente 
all'individuazione di falsi positivi.
Invece io voglio eliminare le varie analisi euristiche, proprio per 
evitare questo problema.
bye

Nicola Ottomano ha scritto:

Perché non provare una cosa molto semplice basata unicamente sulla conta
dei caratteri dal codice ASCII 32 (spazio) fino al codice ASCII 122 (z
minuscola) mettendo il conteggio di ogni singolo carattere in un byte
(se arrivi a passare 255, il conteggio riparte da 0).
Una volta conteggiati i caratteri, hai un hash di 90 byte che in realtà
è una matrice di byte.
Supponiamo di avere inviato "vieni al ballo?". Controllando come ti ho
detto, avrai un certo hash. Se pero scrivi "vieni al bello?", l'hash non
sarà completamente differente ma invece molto simile dato che avrai 1
lettera 'a' contata di meno ed una lettera 'e' contata di più.
Idea idiota oppure no?
-- 
Ciao.
Leo.
Web: 
www.leonardomiliani.com
E-mail: 
leon...@leonardomiliani.com
Scegli software opensource - Choose opensource software

Buona idea, anche se si genererebbero poi dei falsi positivi sul numero 
di lettere (due testi molto diversi potrebbero dare gli stessi valori).
Però non male come idea... magari spezzettare il testo in due o più 
parti ed analizzarle separatamente (magari in una mail vi è la 
predominanza di una lettera nella prima parte, in un'altra vi è 
predominanza nella seconda parte... danno lo stesso "hash" ma si capisce 
che sono diverse...)
Se vi vengono altre idee fatemi sapere.
Nicola

 di lettere (due testi molto diversi potrebbero dare gli stessi valori).
Beh, sì. Però però stiamo parlando di un simil-digest per cui se la
somma di controllo deve essere legata al testo immesso allora la mia
idea penso possa essere utile (d'altronde, anche tu all'inizio del
thread hai usato 2 esempi simili: "Ciao a tutti" e "Ciao a totti").


 
Si, infatti.
Poi, partendo da questa idea di base, si possono trovare accorgimenti 
per prevenire un certo tipo di problemi.
bye

Nicola Ottomano ha scritto:

Hai poi elaborato qualcosa? Son curioso... ^__^


 
Ci sto lavorando saltuariamente (il sw antispam è rilasciato 
gratuitamente, quindi il tempo da dedicarci non è molto) ma non sto 
ottenendo i risultati sperati.
Se implemento l'algoritmo che voglio io, la scansione di ogni mail porta 
via molto tempo (anche 1-2 secondi)... se devi scaricare 200 mail 
capisci che il gioco non vale la candela (2 sec per scaricare + 2 sec 
per analizzare sono 4 sec totali per ogni mail!!!).
Per il momento sto cercando di capire come velocizzare il tutto.
Nicola

 (se arrivi a passare 255, il conteggio riparte da 0).
Era quello che avevo pensato anche io, ma che bisogno hai di fare il modulo
256? Tanto vale usare una word per ogni carattere (e personalmente
ignorerei la differenza tra maiuscolo/minuscolo). Su sistemi a 32 bit
impieghi comunque un solo ciclo. In questo modo non perdi in velocità e hai
una firma più accurata.
4 byte invece di uno, ma la metà delle lettere -> firma di lunghezza doppia.
Non credo che questo generi molte collisioni; il problema è che non
costituisce una metrica (due firme distanti non significano due testi
distanti).
Io andrei verso l'utilizzo di parole. Prendi un buon tokenizer e conti le
presenze di ogni parola, tenendo presente che due parole simili (es. Viagra
e viag1a) le dovresti contare come una sola.
Nicola, perchè non ci dici il nome del progetto? Non ti preoccupare, non la
prenderemo come una pubblicità =)
-- 
  Narcolessico
 
http://binaryunit.blogspot.com

 prenderemo come una pubblicità =)
Ok, tanto penso che molti lo abbiano già capito: Sinapsi Antispam
(lascio a te cercarlo su google) :)
Nicola
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (MingW32)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iD8DBQFHILDNCRSSKrn1pIgRAslEAJoCJJIc/PMPKB8sFGzfpMjM6ik4FwCgkzN7
xkj4xpp5xCgQWA6Sz+5rI4A=
=knjv
-----END PGP SIGNATURE-----

 > prenderemo come una pubblicità =)
Ok, tanto penso che molti lo abbiano già capito: Sinapsi Antispam
(lascio a te cercarlo su google)  :)
Nicola
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (MingW32)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iD8DBQFHILFdCRSSKrn1pIgRAq50AJsEYTOpJ/v59TvlaJ3u83EwhJ1ZcQCfdoDY
iyakik4n8J+YaMvtIXG0EIM=
=v1da
-----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Strano... perchè nel precedente messaggio non mi riconosce la firma?
Nicola
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (MingW32)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iD8DBQFHILJZCRSSKrn1pIgRAo/WAJ9pylim98x4CIfrujXDqz+cGB9ktwCcDhyt
nFRw3U2TYnNAb452qh9mZOk=
=7vsp
-----END PGP SIGNATURE-----

Una metrica normale tra stringhe?
http://it.wikipedia.org/wiki/Distanza_di_Levenshtein
Algoritmi fuzzy?
http://en.wikipedia.org/wiki/Fuzzy_string_searching
Non cos'altro proporre...
-- 
  Narcolessico
 
http://binaryunit.blogspot.com

Altro:
http://www.ippari.unict.it/~faro/tk/tiki-index.php?page=Distanza+tra+stringhe
-- 
  Narcolessico
 
http://binaryunit.blogspot.com

Nicola Ottomano ha scritto:

Forse non hai importato la tua chiave nel lettore NG che usi?
-- 
  Narcolessico
 
http://binaryunit.blogspot.com

 Forse non hai importato la tua chiave nel lettore NG che usi?
No... il lettore ng è thunderbird.
Il messaggio dove dico "Strano... perchè nel precedente messaggio non mi
riconosce la firma?" me lo riconosce come firmato.
Mentre il messaggio precedente (quello delle ore 17.08) con lo stesso
account e firma non mi viene riconosciuto... bah...
Nicola
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (MingW32)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iD8DBQFHIcGmVfCSsqiS7xERAlWtAJ9SJEUsgG1MaBqXdneJVYxXmsr56ACdF+cO
QmZWwBHRA0zi983vYS0OVbY=
=uZjD
-----END PGP SIGNATURE-----

 Non cos'altro proporre...
Grazie comunque per averci provato :)
Nicola
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (MingW32)
Comment: Using GnuPG with Mozilla - 
http://enigmail.mozdev.org
iD8DBQFHI0aXCRSSKrn1pIgRAsALAKCoCCu2BqXzDo/x09GshPKm+9QFjgCg5Ido
lzDVd3ia+/KRxR2jHZxrcDI=
=sIA/
-----END PGP SIGNATURE-----

 capire se le due stringhe sono simili tra loro.
Allora l'md5 è l'ultima delle cose che ti serve! =)
Invece di un solo MD5, perchè non fai il checksum di
1. Titolo
2. Primi x caratteri (1..x) del msg
2. Secondi x caratteri (x+1..2x) del msg
...
k. k.esimi x caratteri ((k-1)x...fine) del msg
Ovviamente puoi fissare x e ottieni k, o viceversa (forse ci conviene il
viceversa). Oppure farlo per ogni riga.
Poi prendi gli ultimi 5-6 caratteri dell'md5 di ogni pezzo e li unisci
insieme in una stringa. Questa impronta, se uno dei pezzi cambia, cambia di
poco.
Se poi all'md5 sostituisci la mera somma dei caratteri (con risultato
testuale, anche + che base64), hai proprio una metrica.
Es.
1. Ciao
2. Compra il v1agra
3. XXX
Somma:
1. 1a
2. c21
3. g4
Firma:
01ac210g4
Un messaggio differente di poco avrà impronta simile:
1. Ciao
2. Compra il vlagra
3. XXY
Firma:
01ac290g5
Se un solo carattere cambia, la firma cambia di poco. Anzi, puoi applicare
una delle metriche conosciute per avere una distanza tra due messaggi!
Per ora usi l'md5, che è un'impronta ma ha le caratteristiche delle f. hash
(tipo 2 msg diversi di poco hanno hash diversi di molto) che proprio non ti
servono. Anzi, ti serve il contrario!
-- 
  Narcolessico
 
http://binaryunit.blogspot.com

 viceversa). Oppure farlo per ogni riga.
[CUT]
Non fattibile. Di solito in una mail di spam non cambia solo un
carattere ma alcuni nel testo e, molto spesso, se ne aggiungono altri,
giusto per rompere le scatole agli antispam.
Idem per il titolo (vedi gli ultimi messaggi di spam "October 70% off",
"October 78% off"...)
Di fatto avrei una roba inutilizzabile.
L'unica soluzione, a mio avviso, sarebbe un algoritmo fuzzy... il
problema è che dovrebbe avere le caratteristiche di un algoritmo di hash
(digest di lunghezza definita) senza però la gestione delle collisioni
(MD5 fa in modo che trovare collisioni sia difficilissimo... io voglio
l'esatto contrario).
Nicola

 l'esatto contrario).
Prova a dare un'occhiata anche agli algoritmi di allineamento sequenze usati
in bioinformatica. Forse uno come blast (implementato efficientemente con
la prog. dinamica) potrebbe fare al caso tuo. Però, data una nuova mail di
spam, dovresti confrontarla con diversi "modelli".
Ultima possibilità: conti le occorrenze di ogni parola; ordini le parole
alfabeticamente e ad ognuna assegni un punteggio; consideri due parole
uguali se hanno pochi scarti. Poi eventualmente fai un digest delle parole
più frequenti...
-- 
  Narcolessico
 
http://binaryunit.blogspot.com