CRC32 - Checksums forceren mogelijk? Hoe? *

[Verwijderd]

ik weet niet of dit de goede plaats is om deze topic te plaatsen, maar aangezien de andere subfora er ook niet erg geschikt voor leken doe ik het hier maar, ik heb een vraag naar aanleiding van het CRC32 algoritme, voor info check http://www.microconsultants.com/tips/crc/crc.txt dat vond ik een redelijk goede uitleg ervoor, de situatie is als volgt: ik heb 2 bestanden, bestand A en B, ik wil dat bestand B dezelfde CRC32 checksum geeft als bestand A, theoretisch gezien is dit mogelijk door de laatste 8 of zelfs maar 4 bytes geloof ik te brute forcen, en elke keer de checksum te bekijken. Mijn vraag is echter of het ook mogelijk is om te berekenen wat de waarde van deze bits zou moeten worden, door te kijken naar de checksum die het bestand geeft terwijl deze bits 0 zijn (de laatste 50 bytes of iets in die trend, van het bestand zijn allemaal 0 en kunnen vrij veranderd worden zonder enige complicaties). Als je namelijk zou weten wat die checksum is, en wat de poly van het algoritme is, wat algemeen bekend is, dan zou je kunnen berekenen voor welke waarde van de bits de deling in het algoritme de correcte checksum als output geeft, echter dit is vrij gecompliceerd en ik heb er nog geen ervaring mee, en ik vroeg mij dus af of er hier mensen waren die hier meer over wisten..

[Spider.007]

Op zich wel een interessante; maar wellicht meer iets voor WL

CRC32 algoritme > CRC32 - Checksums forceren mogelijk? Hoe? *
SA > WL

[caipirinha]

Checksums zijn inderdaad redelijk makkelijk te forceren, ze zijn dan ook niet als authenticatie algorithme bedoeld. een hash functie daarentegen is dat wel. Ben geen specialist op dit gebied maar ik heb veel gehad aan het boek applied cryptography van Bruce Schneier, ISBN 0-471-12845-7

[Opi]

De orginele data is 11010110110000, de poly is 10011. De orginele checksum is 1110. De gewenste checksum is 1010. De nieuwe data is dan 11010110110100. De berekening van het orgineel en de aangepaste versie staan hieronder.

code:

10011 / 11010110110000 \ 
      10011.........     1
        -----.........   
         10011........   
         10011........   1
         -----........   
          00001.......   
          00000.......   0
          -----.......   
           00010......   
           00000......   0
           -----......   
            00101.....   
            00000.....   0
            -----.....   
             01011....   
             00000....   0
             -----....   
              10110...   
              10011...   1
              -----...   
               01010..   
               00000..   0
               -----..   
                10100.   
                10011.   1
                -----.   
                 01110   
                 00000   0
                 -----   
                  1110 = rest (R)


Gewenste checksum: 1010
10011 / 1101011011abcd \ 
      10011.........
        -----.........
         10011........
         10011........
         -----........
          00001.......
          00000.......
          -----.......
           00010......
           00000......
           -----......
            00101.....
            00000.....
            -----.....
             01011....
             00000.... a = 0     
             -----....
              10110...
              10011... b = 1
              -----...
           01011.. -> was 01010
               00000.. c = 0
               -----..
            101[b]1[/b]0.
                10011. d = 0
                -----.
             01010 -> was 01110
                 00000
                 -----
                  1010 = rest (R) -> was 1110

[MSalters]

Ik wist het niet, maar je linkje geeft aan hoe het kan. Hoofdstuk 3, "the basic idea" legt uit dat de CRC de rest is bij deling. Hoofdstuk 4 legt uit wat voor afwijkende deling gebruikt wordt. Nu, als je die deling uitschrijft in nette CRC stijl voor je bericht, maar je laat de laatste paar bytes open, dan zie je vrij snel dat die terug te halen zijn uit je CRC en de voorafgaande bytes. Zet voor het gemak boven de streep vraagtekens op de laatste posities van het bericht, vul weer aan met 0, en bereken alles tot het punt waar je het eerste vraagteken naar beneden moet halen. Je hebt dan 32 bits b0..b31 over, en als je daar een oplossing c0..c31 voor vindt die op dezelfde CRC32 uitkomt dan is die set bits c0..c31 dus ook een valide oplossing voor je originele probleem.

Wat je feitelijk dus doet is je originele bericht reduceren tot een 64 bits bericht, en daar dan de laatste 32 bits voor bepalen om op je goede CRC uit te komen. Nu is het probleem dat 0 een valide oplossing is. Je vermijd dat door te stellen dat b0=1, en vervolgens b1..b31 op te lossen. Lukt dat niet, dan neem je b0..b1=01. Dat hoef je dus maximaal 32 keer te doen.

Hoofdstuk 7 van je linkje geeft ook nog wel aardig inzicht. Je hebt een polynoom G en een bericht B zodat B mod G = CRC32, en je wilt dus een E zoeken zodat B+E mod G = CRC32. Nou lijkt me dan dat E = G een oplossing is. Heb je die al geprobeerd?

edit:
Opi! Da's niet de bedoeling

[Verwijderd]

hm het punt is alleen dat mijn originele "bericht" een bestand is van ongeveer 170kb, wat veel te groot is om dus als deling te gaan zitten doen, ik moet denk ik de link weten tussen de rest van de deler, en de uiteindelijke checksum, zodat ik de checksum van het bestand - de laatste 32 bits kan berekenen, die terug kan voeren tot de rest bij de deler daar, en dan uitrekenen welke bits ik moet hebben om de juiste deler te krijgen.

[MSalters]

Haha.

Natuurlijk is dat originele bericht helemaal niet te groot om als deling te doen. Zo is de CRC32 namelijk origineel berekend.

[Verwijderd]

alleen is de originele berekening door een programma gedaan en niet met de hand... en het programma gebruikt de deling niet, maar het gebruikt een tabel waar de resultaten voor een complete byte in staan.

[MSalters]

Dus? Dan schrijf je toch een programma, in plaats van het met de hand te doen. Reduceren tot 64 bits is in elk geval triviaal.