Reversing CRC

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.

Update I found a great article by Stigge, Pl�tz, M�ller and Redlich about reversing CRC. They pretty much nailed it by bringing it down to elementary algebra. They explain an algorithm which is able to patch data at any given point to adjust the CRC to any desired value.

45 thoughts on “Reversing CRC”

  1. 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….:(

  2. 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

  3. 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

  4. 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

  5. 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

    >>> crc32.reset()
    >>> crc32.update(chr(0x4f) + chr(0xb9) + chr(0x2c) + chr(0x11) + chr(0x1f))
    >>> crc32.hash
    2474486004L # hash of ORIGINAL message (the one you want to have the final message too with the patch)
    >>> crc32.reset()
    >>> crc32.update(chr(0x4f) + chr(0xb9) + chr(0x2a) + chr(0x11) + chr(0x1f))
    >>> crc32.hash
    2549142598L # hash of OWN message
    >>> crc32.patch(2474486004)
    ‘sK\x80\xbc’ # the patch
    >>> crc32.reset()
    >>> crc32.update(chr(0x4f) + chr(0xb9) + chr(0x2a) + chr(0x11) + chr(0x1f) + ‘sK\x80\xbc’)
    >>> crc32.hash
    2474486004L # hash when the PATCH has been applied on your OWN message so it gets the ORIGINAL message’s hash

    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).

  6. hi there Bas…
    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 🙂 )…and will revert back to u in case of any probs 😉 ….Thanks friend.. thanks a lot….

    Take care
    Bye for now….
    Regards…
    Mohit

  7. 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..

  9. 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

  10. 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 = 0x3ab551ce (of ‘\x61’)
    target crc = 0xe1ca95ee
    patch bytes = 0x58f5b11e
    crc32(‘\x61\x58\xf5\xb1\x1e’) = 0x1e356a11

    Which as you might have noticed is not 0x3ab551ce. Am I trying to do something stupid with your patch bytes?

    Thanks in advance. Excellent website.

  11. 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 0x1234ab 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.

  13. 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

  14. 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’]

  16. 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!

  17. 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.

  18. @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.

  19. 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)

  20. 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 replace deadbeaf with yours (2ca91a04). And replace the desired hash 12345678 with yours. (c8fd18cb).

    Run the script via python crc.py and 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.

  21. 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 0x12345678:”
    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 .. ^^

  23. 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.

  24. 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, ‘)’, f3 and b1.
    Obviously you should use the ASCII code of ‘)’ and the character represented by the hexadecimal notation ‘ef’.

  25. 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?

  26. 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.

  27. Hi

    I need a java library or algorithm to generate 4 bit CRC.
    Can anyone plz help ?

    Regards

  28. Hey,
    I just found your page after crawling the internet for days and weeks and it looks like I’m getting close to the solution of my problem. I already read Anarchriz’s paper on reversing crc, but I just can’t find the solution to my problem.

    The thing is:
    I’ve got a file with some binary content. There are multiple data blocks (Header, data, CRC code). They are separated by 00 bytes, like this:

    ———————————–
    12 34 56 78 00 87 65 43 21 00 33 33 33 33

    Header 00 Data 00 CRC code
    ———————————–

    As you can see, the crc code is already embedded in the file.The file is checked by an application, and it compares the crc value of the whole file with the crc value, that is written into it. ( In this case 33 33 33 33).

    With your method and your scripts, I created 4 “fakeTheCRC” bytes and appended them. Now the file had the CRC that were written into it. But there is still a problem.
    The application checks if there is anything after the crc code (e.g. the “fake bytes”). So i have to go another way.

    For now, It doesn’t matter which data is contained in the file, we can leave that out.

    So for the correct crc, I have to:
    1. Define a user-defined crc, e.g. 33 33 33 33
    2. Calculate the data that is needed to get this crc

    Now my problem is:
    – How do I achieve this? I simply have to plan, I tried many many things, but I just don’t know what to do…

    I hope you still answer questions after 5 years 😉

    Regards

  30. Hi Bas,

    I have tried the reverse crc code and it works perfectly, that is: to get the four bytes when I input only four bytes for the CRC32 checksum generation. I now have C# CRC64 generation code with me. I would like to know if I can reverse CRC64 checksum to get four-8 bytes back. If there’s a way, please explain what I have to do. It would be nice if you can provide CRC64 reverse samples, steps.

    Regards,
    Tushar

  32. Dear Bas,

    Well, I can’t understand a lot in your reversing technique. If I have got 16 Characters in a full string, how can I get all these 16 characters back from the CRC32 Checksum? I tried to code but I was lost and totally confused. If you can tell in simple words how to do this. Thanks.

    Tushar

  33. I am unable to properly generate the check-sum of all the string characters in a loop. There are more than 20 characters in a string. Do to incorrect steps I took, therefore no character is being reversed. You haven’t given the steps for how I should update check-sum for all the string characters block by block, or character by character, in a loop. Please clarify this problem.

  34. I can directly manipulate the crc of file?

    example:

    original.txt … crc = CC89F9B7
    patch.txt … crc = 1FC2FCD4

    …. run your script…done..

    patch.txt = crc from original.txt

  35. It doesn’t seem to work for crc32 used in cksum (UNIX).. is that correct?

  37. I’m trying to run your script

    CRC that i want: 0xA0A70404

    CRC on my file: 0x2985ef5d

    Running code:
    crc32 = Crc32Provider()
    crc32._hash = crc32.xorOut ^ NumberFromHexadecimal(‘2985ef5d’)
    print “Required patch to make the new hash:”
    p = crc32.patch(NumberFromHexadecimal(‘a0a70404′))
    print p
    print “Applying patch, resulting hash:”
    crc32.update(p)
    print NumberToHexadecimal(crc32.hash)
    print “It works ^_^”

    Tells me to add these 4 bytes:
    a4,’p’,’^’,’+’

    (0xA4,0x70,0x5E,0x2B)

    I try to append this bytes on the file, but the new cksum is not 0xa0a70404, but 0x5EC210BA…

    Do you see anything wrong that i do? Do you get the same bytes if you try?

    Thanks in advance!

  38. Here’s an example that doesn’t seem to work:
    current hash:A6A43EDA
    wanted hash:A0A70404

    Is this possible? What would the hash patch be in ASCII?

  39. Dear Sir:
    I am a chinese student,I want to ask you a question that is there a limit of the length of the message, for example,could I calculate the checksum of the message which length is more bigger than 32767 with crc-16?
    I am looking forward to hear from you.

  40. Bas, I’m developing a tool for my workplace (We provide IT support) to ideally strip the password of .pst files. I am aware of Nirsoft’s utility PstPassword, however we constantly fight with false positives with Symantec (ugh!) and so we wanted something we could control the coding for. I can not find anything on this other than it is a modified CRC32 algorithm. Can you point me in the right direction on how to pull the CRC32 hash from the .pst and reserse it to get alternative passwords?

    We can talk more over e-mail if you want to send me a message there.

    Thanks!

  42. Can I get a copy of the python code please ? Your link seems to be down. Please email me or mirror here. TY!

  43. I’ve noticed a few people asking about the possibility of the PST password being reversed. Does anyone know how to do this in C# ?
    My python abilities are really bad. Sorry.

    I would really appreciate anyone that can help.

    Simon

  44. Hi Bas…
    I am trying to do same thing which Mohit has asked you (Mohit says:
    3 Aug 2005 at 1:14 pm), mentioned in comment section. Can I get the code which you send to Mohit? I am struggling a lot and hope that you will send me..Thanks in advance.

Leave a Reply

Your email address will not be published. Required fields are marked *