[ALG] Hoe werkt een checksum ???

[Verwijderd]

1. Hoe werkt een checksum ???
En de volgende sub-vragen komen daar uit :
2. Wat is een modulus ??
3. Wat polynomiaal ? (uit t engels)

En de reden waarom ik dit wil weten :
4. Het is toch niet mogelijk om een checksum die maken die iedere wijziging op bitniveau kan detecteren ter grootte van bijv. één DWORD (32 bits) ?

Ik vraag mij dat af want ik kan niet geloven dat bijv. CRC32 fool-proof is. Hoe kun je nl garanderen dat de data consistent is als je een file van een gig hebt en een checksum ter grootte van een DWORD ?

Je kan dan toch gewoon berekenen welke bytes je kan veranderen zonder dat de CRC wijzigd ?

[matthijsln]

Hier staat een boel over crc uitgelegd: http://www.riccibitti.com/crcguide.htm

Het is inderdaad logisch dat verschillende files dezelfde CRC-32 waarde hebben: er zijn maar 4294967295 verschillende CRC-32's maar meer verschillende bestanden.

[PrisonerOfPain]

een modulus is de rest van een deelsom 13 % 4 = 1

[Verwijderd]

Verwijderd schreef op 20 August 2003 @ 18:14:

Je kan dan toch gewoon berekenen welke bytes je kan veranderen zonder dat de CRC wijzigd ?

Ja, dat wel, echter je kan niet meer bepalen welke bytes je allemaal veranderd.
Of het veranderen van die bytes die je veranderd, brengt als probleem met zich
mee dat je een heleboel bytes die je niet wilt veranderen toch moet veranderen
om op dezelfde crc waarde uit te komen.

Daarom wordt CRC ook meestal niet als beveiliging gebruikt maar meer om te kijken (is ook wel enige mate van beveiliging) of een bestand wel juist is overgekomen etc.

[ Voor 16% gewijzigd door Verwijderd op 20-08-2003 18:45 ]

[Verwijderd]

Hmm interessant ! Daar had ik nog niet aan gedacht.

Er zijn in een DWORD maar FFFFFFFF mogelijkheden of te wel 4294967295 mogelijkheden in decimale notering. Dat maakt het de mogelijkheid tot manipulering nog groter...

Na wat research heb ik nu volgende mogelijkheden waarin een checksum niet meer (voldoende) de consistentie van bepaalde data kan garanderen :
- De data en de checksum worden bij een gegevensoverdracht beiden veranderd en de checksum klopt dan nog steeds met de verkeerde data. Dit is zeer onwaarschijnlijk bij bijv de gegevens in een netwerkpakketje, maar kan uiteraard wel gebeuren door manipulatie van een kwaadwillende persoon.

- Er zijn meer dan verschillende 4294967295 datafiles. (en dus bytecombinaties)

- Door een mathematische zwakheid in de CRC formule is het mogelijk een bestand te manipuleren met of zonder behoud vd oorspronkelijke grootte terwijl de checksum hetzelfde blijft (dat is waar ik zelf al aan dacht). Als de grootte hetzelfde moet blijven is het uiteraard moeilijker. Het lijkt mij onmogelijk bij data die groter is dan de 255e machtswortel uit 4294967295 --> in bytes ? Of zie ik iets over het hoofd bij die 255 (ivm hexadecimaal stelsel met meer mogelijke combinaties ?)

Ik hoop dat hier iemand diepgaand op kan reageren want dit is interessante doch ingewikkelde materie.

[The Bad Seed]

Verwijderd schreef op 20 August 2003 @ 18:53:

- Door een mathematische zwakheid in de CRC formule is het mogelijk een bestand te manipuleren met of zonder behoud vd oorspronkelijke grootte terwijl de checksum hetzelfde blijft (dat is waar ik zelf al aan dacht). Als de grootte hetzelfde moet blijven is het uiteraard moeilijker. Het lijkt mij onmogelijk bij data die groter is dan de 255e machtswortel uit 4294967295 --> in bytes ? Of zie ik iets over het hoofd bij die 255 (ivm hexadecimaal stelsel met meer mogelijke combinaties ?)

Het is inderdaad mogelijk dat 2 bestanden met een totaal verschillende grootte en inhoud een identieke checksum opleveren. Dat is echter geen probleem, want de meeste checksum-algoritmes zijn dusdanig ontworpen dat een kleine wijziging(1bit) in het oorspronkelijke bestand een checksum oplevert die sterk verschilt van de oorspronkelijke.

Mocht je in staat zijn om de comunicatie tussen de 2 partijen te onderscheppen en wijzigingen aan te brengen in het bestand zal je zo goed als onmogelijk jouw aangepaste bestand dezelfde checksum kunnen geven.

[frickY]

De voornaamste reden waarvoor CRC (en LRC; Longitudional Redundancy Check meen ik) voor worden gebruikt, is controleren of een bestand wel of niet is beschadigd.

Een kwaadwillend persoon kan inderdaad een bestand aanpassen op zo een manier dat deze dezelfde checksum houd. Maar het resultaat hiervan zal ongetwijfeld een beschadigd bestand zijn waarmee niet kan worden gewerkt, en geen bestand welke een virus of iets anders bevat zoals het kwaadwillende persoon dat wou.

Hetzelfde geld voor md5, alleen heb je hier een ietwat grotere string (32bit, toch?)

[Knutselsmurf]

Probleem is, dat die algorithmen maar 1 kant opwerken. Van rekenreeks naar checksum kan, maar andersom is niet mogelijk. Hierdoor kun je dus onmogelijk een tekenreeks genereren die een specifieke checksum oplevert. Met onmogelijk bedoel ik hier uiteraard 'binnen redelijke tijd', want brute-force reeksen genereren zal uiteindelijk vast wel een reeks opleveren die aan de vereiste checksum voldoet.....

[onnok]

Even voor de duidelijkheid een checksum is iets anders dan een CRC.

Bij een checksum worden alle databytes bij elkaar opgeteld modules de maximale waarde van de data (bij 32-bits data 0xFFFFFFFF)
Bij een CRC wordt de data door een polynoom gehaald en na elke optelling ook modules de maximale waarde.

Het voordeel van een crc is dat wanneer er ook maar 1 bit in de data veranderd, de hele crc waarde anders is. Terwijl bij een checksum wordt er dan gewoon 1 bij of afgetrokken en lijkt het getal dus nog heel erg op de verwachte waarde.

Het grote nadeel van een CRC is dat het veel meer rekentijd dan een checksum kost. Maar het grote voordeel is dat fouten veel sneller opvallen. Tenminste wanneer er een goed polynoom wordt gekozen.

[SWfreak]

Verwijderd schreef op 20 August 2003 @ 18:14:
1. Hoe werkt een checksum ???
En de volgende sub-vragen komen daar uit :
2. Wat is een modulus ??
3. Wat polynomiaal ? (uit t engels)

Ik geloof dat je het antwoord op vraag 1 al weet, dus ik ga meteen naar
2. modulus is gewoon delen met rest. Dus 3 modulo 2 is de rest die je overhoudt als je 3 door 2 deelt.
3. polynomiaal komt van polynoom. Een polynoom is een functie in de vorm van

code:

f(x) = a + bx + cx^2 + dx^3 + ....

En de reden waarom ik dit wil weten :
4. Het is toch niet mogelijk om een checksum die maken die iedere wijziging op bitniveau kan detecteren ter grootte van bijv. één DWORD (32 bits) ?

Ik vraag mij dat af want ik kan niet geloven dat bijv. CRC32 fool-proof is. Hoe kun je nl garanderen dat de data consistent is als je een file van een gig hebt en een checksum ter grootte van een DWORD ?

Je kan dan toch gewoon berekenen welke bytes je kan veranderen zonder dat de CRC wijzigd ?

Over het algemeen is het zo dat een kleine verandering van de file leidt tot een grote verandering van de checksum. Een paar bytes veranderen heeft dus geen effect. CRC is misschien niet zo sterk, maar md5 is vele malen sterker. Met hele sterke checksum algoritmen kun je er zeker van zijn dat het praktisch ondoenlijk is het bestand dusdanig te veranderen dat de checksum gelijk blijft. Als je bang bent dat zowel bestand als checksum gewijzigd worden, dan moet je bestand en checksum encrypten, dan heb je nergens last meer van. Een aanvaller heeft dan geen toegang meer tot het origineel en kan dus geen zinnige aanpassingen doen.

[Verwijderd]

Dat encrypten werkt echter niet bij executables. Anders dan veranderd de indringer de data van die exe wel in het geheugen want dan word de CRC pas berekend (als dat al gebeurd).

Ik zie bij linux zaken wel eens MD5 staan maar is het niet goed een een checksum te hebben van 1 DWORD voor CRC32 en 1 DWORD voor filesize. Dat verminderd het aantal theoretische mogelijkheden al.

[madwizard]

Knutselsmurf schreef op 20 August 2003 @ 19:44:
Probleem is, dat die algorithmen maar 1 kant opwerken. Van rekenreeks naar checksum kan, maar andersom is niet mogelijk. Hierdoor kun je dus onmogelijk een tekenreeks genereren die een specifieke checksum oplevert. Met onmogelijk bedoel ik hier uiteraard 'binnen redelijke tijd', want brute-force reeksen genereren zal uiteindelijk vast wel een reeks opleveren die aan de vereiste checksum voldoet.....

Voor md5 niet maar voor CRC wel dacht ik. Ik heb wel eens een tekst gelezen over het wijzigen van de CRC in elke gewenste waarde door 4 bytes te veranderen (die vrij simpel te berekenen waren). Tekst is wel ergens te vinden nog denk ik, dacht dat ie op fravia stond vroeger.

[ Voor 4% gewijzigd door madwizard op 20-08-2003 20:06 ]

[RickN]

CRC is eigenlijk het berekenen van de rest van een polynomiale deling. Het is dus makkelijk (zeg maar gerust triviaal) om vanuit een CRC signature een bericht te construeren dat die signature heeft. Het is ook makkelijk om gegeven een bericht een tweede bericht te construeren dat dezelfde signature heeft. Om deze redenen is CRC niet geschikt om beveiliging te bieden tegen een kwaadwillende gebruiker, maar daar is het ook nooit voor bedoeld.

[ Voor 4% gewijzigd door RickN op 21-08-2003 10:47 ]

[farlane]

Een CRC is daarentegen wel geschikt om een beperkte stream gegevens een controlegetal te geven zodat de ontvanger van de stream behoorlijk goed kan controleren of de stream nog klopt.

Zoals gezegd, als er ook maar een bitje omvalt, komt er een compleet andere CRC uit.

[MrBucket]

Relevant linkje, mocht je ooit zelf willen pielen met CRC's:

http://www.repairfaq.org/filipg/LINK/F_crc_v3.html

[PommeFritz]

Een md5 hash is een strong checksum ofwel message digest. Het is een 128 bits hashcode. Omdat het md5 algorithme one-way is, is er geen manier om je bericht te manipuleren zodat je dezelfde md5 digest krijgt als het originele bericht.
(tenminste, geen bekende manier die slimmer is als brute-force, en aangezien we het over 128 bits hebben, betekent dat een ontzaglijk aantal, waardoor het praktisch onmogelijk is).
Een nog sterkere hash is de SHA-1 digest, die is 160 bits.

Dit soort message digests wordt veel gebruikt in cryptografie, en zijn navenant zwaar om te berekenen. Een simpele, snelle checksum zoals de 32 bits CRC of Adler checksum (die door zip gebruikt wordt) is veel sneller te berekenen maar ook cryptografish gezien onveilig.

[farlane]

PommeFritz schreef op 22 August 2003 @ 00:40:
...
Een simpele, snelle checksum zoals de 32 bits CRC of Adler checksum
...

Snel en simpel moet je hier wel in perspectief zien. Voor een serieel communicatieprotocol in een embedded uP met 256 bytes RAM en 1K FLASH is een CRC16 eigenlijk te veel van het goede.

[matthijsln]

farlane schreef op 22 August 2003 @ 01:11:
[...]

Snel en simpel moet je hier wel in perspectief zien. Voor een serieel communicatieprotocol in een embedded uP met 256 bytes RAM en 1K FLASH is een CRC16 eigenlijk te veel van het goede.

In zo'n situatie implementeer je CRC natuurlijk in hardware:

http://www2.rad.com/networks/1994/err_con/crc_hard.htm

[farlane]

matthijsln schreef op 22 August 2003 @ 14:44:
In zo'n situatie implementeer je CRC natuurlijk in hardware:

Als je er aan vast zit wel misschien ( dan kies je je hardware voor wat ie moet doen ),
als je zelf iets mag verzinnen dan wordt het waarschijnlijk een iets simpeler checksum ( checksum in de zin van ' controlegetal' ).
Alles wat je in software kan doen ga je niet in hardware doen.

[matthijsln]

farlane schreef op 22 August 2003 @ 15:16:
[...]

Alles wat je in software kan doen ga je niet in hardware doen.

Inderdaad, waar hebben we die 3D kaarten nou voor nodig

[farlane]

matthijsln schreef op 22 augustus 2003 @ 16:25:
Inderdaad, waar hebben we die 3D kaarten nou voor nodig

Ik denk dat ik het met de genoemde uP in een iets ander segment zit.

[Tomatoman]

Het is al een paar keer genoemd, maar een beetje versplinterd over de verschillende berichten. Daarom zet ik de verschillen tussen checksums en hashes nog even op een rijtej.

Een checksum wordt gebruikt om te controleren of data (vaak bestanden) niet per ongeluk zijn veranderd, bijvoorbeeld door een slechte communicatieverbinding. De meest gebruikte checksums zijn de 'eenvoudige' checksum (gewoon alle bytes bij elkaar optellen) en CRC. Zij zijn geen van beide bedoeld als bestandsbeveiliging.

Er is nog een variant op de checksum en dat is het 'magic number'. Daarbij zorg je ervoor dat de checksum van een bestand altijd dezelfde waarde heeft. Dit doe je door op een vaste positie in het bestand een dusdanige waarde in te vullen dat de checksum gelijk is aan het magic number.

Dan zijn er nog hashes of hash sums. Een hashfunctie versleutelt gegevens op een zodanige wijze dat er een bepaald getal uit tevoorschijn rolt. Dat getal is de hash sum of simpelweg de hash. De versleutelfunctie wordt zodanig gekozen dat het onmogelijk is om uit de hash de originele data terug te herleiden. Het is dus eenrichtingsverkeer. De hashfunctie is dan ook erg ingewikkeld en rekenintensief. Hashes zijn daardoor niet echt bedoeld als een vervanging van checksums. Een van de vele hashfuncties is het (inmiddels voor encryptie wat verouderde) MD5-mechanisme.

Hashes worden veelal gebruikt als authentificatiemechanismen voor data. Stel dat je wilt controleren of iemand een bepaald wachtwoord kent, zonder dat hij het wachtwoord zelf doorgeeft (bijvoorbeeld omdat je een onbeveiligde verbinding gebruikt). Dan vraag je hem om de hash van het wachtwoord uit te rekenen en je doet dat zelf ook. Als de hash van die ander precies hetzelfde is als wat je zelf hebt berekend, weet je zeker dat hij ook het wachtwoord zelf kent (anders had hij immers nooit de hash kunnen berekenen). Het voordeel is dat je op die manier nooit het wachtwoord zelf hoeft te versturen terwijl je toch kunt controleren of die ander het wachtwoord kent. Bij complexe beveiligingssystemen is het allemaal een stuk ingewikkelder, maar vaak zijn hashes wel een van de fundementen van de beveiliging.

[matthijsln]

tomatoman schreef op 22 August 2003 @ 22:58:
Hashes worden veelal gebruikt als authentificatiemechanismen voor data. Stel dat je wilt controleren of iemand een bepaald wachtwoord kent, zonder dat hij het wachtwoord zelf doorgeeft (bijvoorbeeld omdat je een onbeveiligde verbinding gebruikt). Dan vraag je hem om de hash van het wachtwoord uit te rekenen en je doet dat zelf ook. Als de hash van die ander precies hetzelfde is als wat je zelf hebt berekend, weet je zeker dat hij ook het wachtwoord zelf kent (anders had hij immers nooit de hash kunnen berekenen). Het voordeel is dat je op die manier nooit het wachtwoord zelf hoeft te versturen terwijl je toch kunt controleren of die ander het wachtwoord kent. Bij complexe beveiligingssystemen is het allemaal een stuk ingewikkelder, maar vaak zijn hashes wel een van de fundementen van de beveiliging.

Indien je authenticatie doet met een hash wordt meestal niet alleen het password als source voor de hash gebruikt, maar het password met een door de server gegenereerde random string (die maar 1x wordt uitgeven). Dit zorgt ervoor dat de hash altijd verschillend is, zodat je als aanvaller niet gewoon de hash kan geven als authenticatie zonder dat je het password weet.