It is currently Mon Oct 14, 2019 1:50 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 3 posts ] 
Author Message
PostPosted: Thu Sep 12, 2019 5:48 pm 
Offline
User avatar

Joined: Thu Aug 13, 2015 4:40 pm
Posts: 419
Location: Rio de Janeiro - Brazil
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:
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!


Top
 Profile  
 
PostPosted: Thu Sep 12, 2019 7:11 pm 
Offline
User avatar

Joined: Thu Mar 31, 2016 11:15 am
Posts: 530
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.


Top
 Profile  
 
PostPosted: Mon Sep 16, 2019 8:14 am 
Offline
User avatar

Joined: Thu Aug 13, 2015 4:40 pm
Posts: 419
Location: Rio de Janeiro - Brazil
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!


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: NOOPr and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group