Newsgroup: it.comp.programmare
Titolo: Una questione sul CRC

Da quel che ho visto esistono molti programmi in grado di fare il crc, e
quindi mi chiedevo se il codice è un codice libero che può essere inserito
in qualsiasi programma oppure se è protetto da copyright (e se lo stesso
vale per i formati md5 e sfv).
Inoltre volevo sapere se esiste da qualche parte un sito da cui prendere,
non dico il codice, ma per lo meno le formule utilizzate nel calcolo del
crc.
Infine, ultima domanda, è possibile che un file modificato in 2 punti
diversi possa dare lo stesso crc e risultare quindi non corrotto?
Grazie
Susa

 ha scritto nel messaggio
news:2xlQ8.53062$TS.14...@news1.tin.it...


Immensamente GRAZIE!!!!

diversi possa dare lo stesso crc e risultare quindi non corrotto?
Se usi un buon algoritmo è praticamente impossibile.
-- 
Marco Barisione (ICQ 84277092)

 Non è assolutamente un copyright.
L'XOR probabilmente no (anche se qualcuno ne ha brevettato l'uso per le 
bitmap :-@ ), non escludo che altri algoritmi possano essere (sic) 
brevettati.
-- 
Valter Minute
vmi...@inwind.it
 (the reply address of this message is invalid)

 qualche cosa;
Vorrei soltanto precisare che il CRC è il resto di una divisione binaria tra
due polinomi. Eseguire tanti XOR a caso non equivale a eseguire un CRC.
Nella divisione binaria le sottrazioni vengono eseguite senza riporto e
prestito, quindi in pratica equivalgono a uno XOR.
Un polinomio binario è qualcosa del tipo
1 + x + x^2 + x^3 + x^4 + x^5 + ..... + x^n
Ogni coefficiente (che moltiplica la x) può valere 1 o 0 e quindi ecco
apparire i numeri binari.
Per chi vuole approfondire e capire veramente come funziona il CRC e perchè
bisogna usare un polinomio anzichè un altro, vada qui:
http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
Kiuhnm

 
http://www.ross.net/crc/
WOW! Mi hai preceduto di un soffio :-)
Kiuhnm

 
Veramente sul mio server il tuo post č di un minuto in anticipo 
rispetto al mio.
Considerando che ho una gamba ingessata posso accontentarmi del secondo 
posto :)


 posto :)
LOL! Compra la sedia con le ruote!!!
Kiuhnm

 diversi possa dare lo stesso crc e risultare quindi non corrotto?
con CRC32 è possibile. E' solo poco probabile. Con MD5 è *teoricamente* 
possibile, ma tuttora non si conoscono due stringhe che abbiano lo 
stesso hash MD5
-- 
 < 
http://www.reactos.com/
 >  Open source clone of Windows NT. Current
     Don't stand, REACT!      version 0.0.19. C, C++ and ASM developers
                              and beta testers are welcome!

 stesso hash MD5
Fico!!! E non si potrebbe vedere quale algoritmo utilizza md5? Mi servirebbe
per un mio progetto...

 stesso hash MD5
Non vedo il problema...se non si vogliono correre rischi basta usare un
CRC256!
L'importante č che la distribuzione sia lineare in modo che alcuni CRC non
siano piů probabili di altri.
Nessuno vieta inoltre di usare qualcosa di diverso e magari di piů complesso
del CRC.
Kiuhnm

Se usi un buon algoritmo č praticamente impossibile.
sbagliatissimo.
le collisioni sono possibili e ciň va tenuto in considerazione.
hashare qualcosa cvhe sia piů grande di 4byte(8 16 quanti ne vuoi) in
4 byte(8 16 quanti ne vuoi) porta cmq ad una perdita di informazione. 
il fatto che molti algoritmi di hash/crc (mi viene in mente l'ethernet
crc e md5) diano risultati molto diversi per dati molto simili ) non
significa tuttavia che le collisioni non siano possibili. (non stiamo
parlando di compressione non a perdita. stiamo parlando di hash
imperfetti.)



se non vuoi correre rischi l'unico modo č usare una compressione non a
perdita o un hash con le stesse dimensioni dei dati iniziali. in caso
contrario le collisioni sono possibili, per quanto sempre piů
improbabili con l'aumentare dei bit utilizzati.

 complesso del CRC.
Appunto, esiste MD5 :-P


Mi sono appena studiato l'algo MD5 cosě adesso almeno so come funziona...
:-)
Abbandonando il discorso MD5...
I metodi di controllo (CheckSum, CRC, MD4, MD5, ecc...) vengono utilizzati
per sapere in modo statisticamente "sicuro" se dei dati sono stati
modificati (errori di trasporto dati, manomissione volontaria, ecc...).
La prima cosa alla quale ho pensato č: "che cosa importa quale algoritmo si
utilizza? L'importante č che la distribuzione sia lineare. Distribuzioni non
lineari potrebbero essere utili conoscendo il tipo di dati trattati (per es.
testo, op-code, ecc...) in modo da utilizzare al meglio tutti i bit.
Adesso invece penso che, visto che in fondo si lavora con dati che subiscono
quasi sempre modifiche minime, sia importante sviluppare algoritmi con
distribuzione NON lineare.
Per esempio un algo potrebbe dedicare piů "spazio" alle modifiche minime e
sempre meno "spazio" alle grandi modifiche. Questo mi sembra molto pratico.
Perché il CheckSum fa schifo?
Perché i dati che hanno lo stesso CS sono molto vicini tra loro (distanza =
numero di bit invertiti).
Il CheckSum rende veramente facile la manomissione manuale in quanto č
facile non alterare il CheckSum, perň, se i file fossero sottoposti a veri e
propri scrambler, penso che il CheckSum sarebbe efficace quanto il CRC o
l'MD.
Siccome invece i file sono sottoposti a modifiche minime, il CheckSum č
molto meno sicuro degli altri metodi.
Sto vaneggiando???
Che cosa ne pensate?
Kiuhnm

4 byte(8 16 quanti ne vuoi) porta cmq ad una perdita di informazione. 
Mi potresti inviare un file e la sua versione modificata in due punti
(come chiede l'OP) che abbiano lo stesso MD5? Quante probabilità ci
sono che questo possa accadere?


sono che questo possa accadere?
guarda voleva solo essere una precisazione. mi ha solo _sorpreso_ il
fatto che tu abbia usato la parola impossibile. si, sono stato un
pignolo di merda.
no, non posso mandarti due file "modificati" con 2 md5 identici.
riguardo la seconda domanda essendo md5 un hash di 16byte(128bit)
si ha la sicurezza si una collisione dopo
     128   
    2      tentativi
andando di bruteforce, è quindi probabile che si trovi una collisione
dopo una media di 2^64 tentativi.
con una "macchina" che riesca a calcolare 2.000.000.000 di md5 in un
secondo, servirebbero 2^64/2E+9 secondi di media per crackare un hash
md5. Dato un anno di 365 giorni (365 * 24 * 60 * 60 = 31536000 secondi
= KT ) servirebbero 
  128/2
 2            1    
 ------ *  -------- = circa 292 anni di media per crackare un md5.
 2E+9         KT
se fosse vera la Legge di Moore per cui La potenza di calcolo
aumenta in media di un fattore 10 ogni 5 anni, tra 20 anni l'equazione
sarebbe questa (ammesso che oggi si disponga di un cluster o che altro
che riesca ad hashare 2E+9 md5 in un secondo) :
        128/2
       2      
 --------------- = 230.584.300 secondi = circa 7 anni.
 2E+9 *(20/5)*10
ma,
visto che i vecchi sono saggi,
e visto che il mi nonno di solito diceva "in america sono tre secoli
avanti"
         64
        2      
 ---------------- = 15.372.286 = 177 giorni circa.
   2E+9 * 600
da ciò deduciamo che:
un americano in 177 giorni con un cluster di macchine che noi forse
vedremo solo tra 300 anni colliderà una tua password hashata in md5.
data la legge di gumperson "La probabilità che qualcosa accada è
inversamente proporzionale alla sua desiderabilità", traiamo la
conclusione che un ucraino ( nazionalità scelta a caso ) con un 286
colliderà un md5 in un tentativo.
la tua password era "pippo".
due cose semiserie dopo tante stupidate (non me ne vogliate se ho
sprecato banda)
nel 94 è stata ideata una macchina da van Oorschot e Wiener che
avrebbe fatto collidere un hash md5 in una media di 24 giorni.
la macchina al tempo sarebbe costata 10M USD.
"P. van Oorschot and M. Wiener, Parallel collision search with
application to hash functions and discrete logarithms, Proceedings of
2nd ACM Conference on Computer and Communication Security (1994). "
sono state _valutate_ diverse tecniche per collidere md5, il
bruteforce è la tecnica più stupida, nessuno ha mai provato che md5
non possa essere colliso in altro modo se non con bruteforce.
la probabilità gioca con la sfiga.
-- 
u_32 mylife(u_8 *thoughts,u_32 s)
{
 u_32 h = 0;
 u_32 i = 0;
 for(;i<s;i++)h=((h*0x01000193U)^(thoughts[i]));
 return h;
}

fatto che tu abbia usato la parola impossibile.
Infatti non ho usato "impossibile" ma "praticamente impossibile", c'è
una grande differenza :-)
