Cyclic Redundancy Code
CRC is a hash which is frequently used as a checksum for data in for instance archives. Who hasn’t had bad CRC errors once when opening corrupted zips. CRC is a very old algorithm and over time it changed a lot from the original idea.
The original idea behind CRC was representing the data that you wanted the hash from as a big number and dividing it by a certain number called the polynomial and taking the remainder of the division as the hash. For instance: 23 % 3 = 2 (% is the modulus operator, which is the remainder of a division)
The initial problem was that dividing is a rather intensive operation. They wanted to simplify CRC to make it easier to implement in hardware and make it faster. They did this by getting rid of the carry used in the substraction of the division:
Normal substraction (binary): 10101 - 01100 = 01001
Without carry: 10101 - 01100 = 11001
Substraction without a carry is basicly a eXclusive bitwise OR (XOR), which returns only 1 when one of the operands is 1 and the other 0.
The algorithm required was faster bit still worked bit by bit, which isn’t really what a computer likes. A computer works best with one to four bytes. To make CRC faster they cached 8 operations at the time by precomputing the results for a certain start value and put it in a table called a XOR Table.
The required code for the CRC calculation itself now became very simple:
hash = (hash >> 8 ) ^ table[data ^ (0xff & hash)]
They changed the CRC algorithm once more by making it reflected. This means that the input data is reversed bitwise: 011101011 <-> 110101110. This was done because most of the hardware chips at the time reversed data bitwise. For it was too much work to reflect each byte of incoming data they changed the algorithm that generates the Crc table to create a table which has the effect of reflected data.
This is by the way not totally correct; the result still was different for a reflected than a non-reflected algorithm for they wouldn’t cache the whole piece of data to reverse it but did it per byte at calculation.
At this moment CRC barely resembles the original idea of a modulus.
Reversing CRC
First off, credits for the original idea of CRC patching go to anarchriz.
CRC is a cryptographicly very weak algorithm. It can be easily reversed for it has got the property that with 4 bytes you append to the current computed hash you can get every required hash. You can change the whole message and add 4 patch bytes to patch the hash to the one you like.
The ability to patch a CRC also makes it possible to very efficiently generate all possible source data of a checksum. Although it still is a bruteforce method you got 4 bytes freely and patching is faster than calculating.
Patching is basicly going back the way CRC works. Crc basicly takes the hash, moves it 1 byte to the right (dropping one byte) and xor-ring it with the table entry. The nice thing about normal CRC is that the first byte of a table entry is unique for that entry.
For the first byte of the entry is unique for that entry and it is put in the hash xor-red with 0 for that is what is shifted in from the right you can work back the whole entry used.
For instance:
My is: 0x012345678, this means that it was xorred with the entry in the CRC table that starts with 0x12. When you xor the hash with that full entry the only thing that the next byte was xorred with was the start of a table entry too.
When reversing the current hash you know what will be xorred on the patch you’ll give. Xorring this with your wanted hash is enough.
The resulting algorithm is suprisingly simple:
- Put the current hash byte wise reversed at the start of a buffer. Put the wanted hash byte wise reversed at the end of the current hash in the same buffer.
- Look up the entry in the table that starts with byte 7 in the buffer. Xor this value of position 4, and Xor the entry number on position 3. Repeat this 4 times with the positions each time one decremented. (thus 7,6,5,4 and 4,3,2,1 and 3,2,1,0)
When you’ve done this the required patch bytes are the first 4 bytes in the buffer.
Some Crc variants tend to use duplicates in the crc-table which means there could be more than one original table entry used. You should just branch and try all of them.
I’ve made a simple python script to work with crc32 and to patch a hash.
You can download it Here. And there is a C implementation here.
Update Fixed a bug in the example.
Update Andrea Pannitti wrote an implementation in java.
Hi,
I read your article on CRC32 reversal…I had data as 4f b9 2c 11 1f…and the CRC given out was 93 7d a8 f4…I change this data to 4f b9 2a 11 1f…
The CRC is 97 f0 d4 46….
My requirement is….even though I change the data my CRC should remain the same…ie CRC should remain..93 7d a8 f4
Using ur method…I got the four bytes as A0 CE 4E DA…
I dont know whether I followed the right process….and anyway…..what is to be done with this four bytes I got….
Pls help….I am a kind of newbie….so plz dont flame me….:(
Hello,
First you compute the crc of the original message, lets call this the aim-crc, for this is the one you want to get to.
Then you compute the crc of your own message, the current-crc.
With the algorithm I described you put the aim-crc as the wanted-hash and the current-crc as the current-crc.
The algorithm will return you with ‘patch-data’ which when appended to your own message will make the whole message result in the aim crc.
You can use the python code attached to the post.
One thing to remember though is that the whole algorithm is designed to patch a certain message so that it will get a crc. This will require 4 patch bytes.
Hope this has helped you
hello …
Thanks for ur reply….
I took original message as 45 fe 3a 12, aim CRC as e4 c4 86 f8 ,own message as 21 3e 44 ef ,current CRC as b3 9f aa 35 (calculated by Hash calc of slavasoft).Using ur algo I get ed 5e 7c cc.I appned it to own message which results in 21 3e 44 ef ed 5e 7c cc.But the CRC of this string comes out to be c5 80 59 e4….not e4 c4 86 f8(the aim CRC)
So now what is your suggestion….am i wrong somewhere or may be the hash calculator I am using is not giving the correct output…
Plz excuse me if I am wrong somewhere…
Regards
Mohit
Hi there….sorry for this second comment…..
I again tried with …with original message as 4f b9 2c 11 1f,aim-crc as 93 7d a8 f4 ,own-message as 4f b9 2a 11 1f,current-crc 97 f0 d4 46
After applying the algo the four patch bytes I am getting are as follows :
a0 ce 4e da
I appended this four bytes to 4f b9 2a 11 1f(own message) but I didnt get the aim-crc .
Now what has to be done….?
Regards
Mohit
What you should do is:
1. calculate the CRC of your OWN message.
2. calculate the CRC of the ORIGINAL message.
3. do the patch putting the CRC of the ORIGINAL message first and then the CRC of your OWN message.
4. do the patch algorithm
You should make sure you do the algorithm itself properly.. just download the python source and look in the patch function, which I always use. (calculating it by hand is a pain :-p).
hi there Bas…
)…and will revert back to u in case of any probs 
….Thanks friend.. thanks a lot….
Thanks for ur reply yet again……the case study on which I put the query…..and the consequent patch….seems to be working perfectly right here…so I will…..now study python,then ur python code…and try to implement the same thing in C(in VC++ MFC,as I am a C guy
Take care
Bye for now….
Regards…
Mohit
Hi baas..
u may have wondered abt why i am so interested in CRC32 ‘reversal’.Actually i am developing a .PST file password recovery software for a certaiin company which has hired me specifically for this purpose.This company specializes in data recovery…
now coming to the point…according to one document of Andy Malyshev ….available on the net…the password of .PST is stored as a CRC32 hash in the .PST file.I know the exact location but that particular CRC32 dosent seem to be matching with the usual CRC32 ususal CRC32 …
if the CRC32 matches in some way then I can somehow use the CRC32 reversal program to generate a string which will have the same CRC32 hash as the (forgotten) password…and hence password recovery is possible…
now friend …can you please help me in this matter…Microsoft dosent object to people…using third party recovery programs to recover passwords of their application
what i need to know is “is there any non standard form of CRC32 algo…”which gives non standard result…?if yes….then where are the variations,….in the CRC32 reversal algorithm…??
if u permit….i can give u thw whole of my workings on PST file…at ur mail id…
Thanks in advance….
Rgds
Mohit..
Check your mail-box.
Hi friend…
Thanks a lot …..Baas….
Will contact u in case of any further problems….hope u wont find…
and sorry in advance for any botheration to u later on….
Thanks…
Ba bye…
take care….
regards…
mohit
Hi.
I can’t seem to get this work. I’ve read too much stuff and I still cant get anything to work. I tried to code this in C but it kept messing up, right now I can make patch bytes which I can append to any random string which will fix the CRC of the string to a certain value everytime. Unfortunately I cant control that final CRC value LOL!
One interesting thing i’ve noticed is that if you append the 4 byte crc of a string after it and crc all of that, it returns 0! Perhaps thats obvious to you, but hell I thought it was totally awesome…
Anyway I tried your python script out and got some patch bytes, but when I append them to my original string, I don’t get the original CRC back. One moment, my lovely assistant will demonstrate:
orig crc = 0×3ab551ce (of ‘\x61′)
target crc = 0xe1ca95ee
patch bytes = 0×58f5b11e
crc32(‘\x61\x58\xf5\xb1\x1e’) = 0×1e356a11
Which as you might have noticed is not 0×3ab551ce. Am I trying to do something stupid with your patch bytes?
Thanks in advance. Excellent website.
The python way
>>> crc32 = Crc32Provider()
>>> crc32.hash = NumberFromHexadecimal(‘3ab551ce’)
>>> p = crc32.patch(NumberFromHexadecimal(‘e1ca95ee’))
>>> p
‘i[\xfb\xdb’
>>> crc32.update(p)
>>> print NumberToHexadecimal(crc32.hash)
3ab551ce
Python has some curiousities when using 0×1234ab format for it has some strange long and not long number handling. It is possible you made some errors with that. At least I did when I wrote the library for the first time and I therefore use the NumberToHexadecimal functions to make sure it works with the correct numbers.
I hope this concrete example has helped you a bit more.
Nifty! Thanks!
Hi!
I read your article and I wonder if U know how to calculate or how looks like calculation for CRC 15 CAN. I do not know how to calulate them and how to program in C++.
Thank for any help
Adrian
Hi, me and my friend just used your program and we realised that there’s a mistake in the example that throws people off.
crc32 doesn’t have a setter for hash but crc32.hash is not equal to crc32._hash. So setting crc32._hash to the old hash and doing a crc32.patch gives the wrong value.
Since the swapping thing is off the input just needs to be
crc32._hash = crc32.xorOut^NumberFromHexadecimal['oldcrc']
Ah, thanks! I’ve corrected it.
Just to let you know that your gmail and fsfe.org email addresses were both rejected by the mail delivery system – your gmail is also on your ‘Hire Me’ page, so you should probally update it quickly!
Hey
I was just wondering if anyone could help me out here. As you all know when you edit your file the CRC32 changes and you can right click>properties>filehashes and see how its changed.
But what i want to know is; If i had a CRC32 value in my head and i wanted to change the CRC32 into this valuem, what would i have to do to edit it.
EG Tips.xml >right-click>properties>file hashes and it has
2CA91A04
but maybe i wanted to change it to
C8FD18CB
How would i do that .. please i am desperate i need to know.
@JayTee,
The method I describe works by calculating the four bytes that you need to append to any given file to change the hash to the one you desire. Just modify the Python or Java example to suit your needs.
THanks for replying ..
But i just got into scripts and codes and i would like someone to explain how to change the CRC32 hash to the hash you desire ..
but could u plz explain it to me coz im a noobie and theres about 100 ppl counting on me to figure it out .. (and im not joking)
Download the python example code. If you haven’t got it, download and install Python. Extract the example code to a folder and open up
crc.py.At the bottom of the file you see the code that is run when you directly execute
crc.py. I hope for you it’s a plain CRC hash. In that case replacedeadbeafwith yours (2ca91a04). And replace the desired hash12345678with yours. (c8fd18cb).Run the script via
python crc.pyand it should output the patching bytes. It looks a bit like a mess because it aren’t all printable ASCII characters. This are the repr-ered contents:'\xef)\xf3\xb1'. So, append the bytes ef, ‘)’, f3, b1 to your file and you should be fine.OK
if __name__ == ‘__main__’:
crc32 = Crc32Provider()
print “We take a message which has the hash 0xdeadbeaf”
# Thanks to path:
# http://blog.w-nz.com/archives/2005/07/15/reversing-crc/#comments
crc32._hash = crc32.xorOut ^ NumberFromHexadecimal(‘deadbeaf’)
print “Required patch to make the hash 0×12345678:”
p = crc32.patch(NumberFromHexadecimal(‘12345678′))
print p
print “Applying patch, resulting hash:”
crc32.update(p)
print NumberToHexadecimal(crc32.hash)
print “It works ^_^”
You replace the current CRC32 where it says deadbeaf in this column
crc32._hash = crc32.xorOut ^ NumberFromHexadecimal(‘deadbeaf’)
and you replace desired CRC32 where it says 12345678 in this column
p = crc32.patch(NumberFromHexadecimal(‘12345678′))
then you save it ..
then you run it and then what .. sorry that im noob .. ^^
“Sorry that im noob .. ^^” doesn’t tell me what you don’t understand.
I dont understand is how the CRC of my desired file is changed to my desired CRC.
Do i have to input sumtin in the document to make the CRC change.
The CRC of a document depends solely on the contents of a document. If you change, append or remove contents the CRC will change. What my script does, is to calculate which 4 bytes you should append to a document to let its CRC change to any given CRC. Obviously depending on its current CRC.
In your case (as you can read in my second previous comment) you need to append the following four bytes:
ef, ‘)’,f3andb1.Obviously you should use the ASCII code of ‘)’ and the character represented by the hexadecimal notation ‘ef’.
From your example above it only shows on how to APPEND 4 bytes to the file/content, what if for example a buffer size is fixed and i want to CHANGE 4 bytes of the existing buffer content. How can i do that using your python code?
In some way shorten the stream by four bytes and then append the patch. In theory the algorithm could be adapted for a patch somewhere in the middle. It’s very old code though, so I couldn’t really fix something together for that.
Hi
I need a java library or algorithm to generate 4 bit CRC.
Can anyone plz help ?
Regards