CRC32 operations question

You can talk about almost anything that you want to on this board.

Moderator: Moderators

Post Reply
User avatar
nesrocks
Posts: 459
Joined: Thu Aug 13, 2015 4:40 pm
Location: Rio de Janeiro - Brazil
Contact:

CRC32 operations question

Post by nesrocks » Thu Sep 12, 2019 5:48 pm

So, what I'm trying to do, is to edit a ROM while keeping its CRC32 hash. There is a known sequence of 4 bytes of value "zero" at one section in the ROM that can be reserved for this.
What I want to do is edit the ROM using a level editor (that I'm making), and then the level editor will manipulate these zeroes in such a manner that the ROM's CRC32 hash will be unchanged.

I have found some resources online that tell me how to achieve this, in certain detail, and I've managed to reproduce it mostly in my development environment, but there's one step that I'm having trouble with understanding the math. The user describes the step as follows:

"Step four, and this is a bit funky so see below, perform an inverse CRC32 calculation:"

Code: Select all

0xD046655F * inverse(x32) mod crc_poly
It all boils down to what is "inverse(x32)". If I figure this out, my problem is solved.

He goes on further to explain this:
"P * x32 mod crc_poly is the remainder of (P shifted 32 bits to the right) after dividing by the CRC polynomial, which is how CRCs are computed).
inverse(x32) is the multiplicative inverse of x32 mod crc_poly. Multiplicative inverse means x32 * inverse(x32) mod crc_poly = 1."

The way I understand it, after going through steps 1-3, I will have to bitshift the manipulated hash 32 bits to the right, but that means it will always result in a value of zero since it is always 32 bits long? I am missing something here and I'd really appreciate some help.

Maybe he meant bit shift 32x to the left?

First link to his explanations: https://stackoverflow.com/questions/482 ... 0#48248530
Further info: https://www.reddit.com/r/crypto/comment ... ollisions/
https://twitter.com/bitinkstudios <- Follow me on twitter! Thanks!

User avatar
pubby
Posts: 550
Joined: Thu Mar 31, 2016 11:15 am

Re: CRC32 operations question

Post by pubby » Thu Sep 12, 2019 7:11 pm

My best guess is that inverse(x32) is a constant value that is determined by the CRC polynomial. You can precompute it outside of your code and copy/paste it in.

The multiplication is finite field multiplication, not standard arithmetic.

This is only a guess though.

User avatar
nesrocks
Posts: 459
Joined: Thu Aug 13, 2015 4:40 pm
Location: Rio de Janeiro - Brazil
Contact:

Re: CRC32 operations question

Post by nesrocks » Mon Sep 16, 2019 8:14 am

This issue has been solved. Inverse(x32) for the CRC32 with default polynomial is just a constant $cbf1acda. (thanks zzdd from RHDN!) http://www.romhacking.net/forum/index.p ... 382134#new
https://twitter.com/bitinkstudios <- Follow me on twitter! Thanks!

Post Reply