This document is a description of how I defeated the crc-32 "cheat defeat" scheme in Ancient Domains of Mystery. I originally intended it to be a Reverse Engineering White Paper, though it's certainly not as thorough as a respectable White Paper should be. It does give an interesting perspective on the CRC algorithm, general cryptographic hygeine, and the state of the "ADOM Community" in late 1998, which is when this paper was originally written.
If you don't care how I wrote this utility and just want to get it and use it, go to Petula Clark's website (or her mirror or her other mirror).
Please note: I do not support CRCPatch! Make backups. Make sure your CRCPatch version and ADOM version match EXACTLY. They are NOT backwards compatible. If you still can't get it to work, then get a C compiler and an algorithm cookbook describing CRC-32, and write your own utility.
Thomas Biskup has written the savegame editing detection code for two purposes. First, to prevent people from cheating at his game. I view this as a challenge to be heartily accepted by the hacking and reverse engineering community. Second, however, is to create a market for his commercial product, ADOM Deluxe, which will include full character and game editing capability. In this second purpose I am wholeheartedly behind Thomas. At the time of this writing (March 2000), Thomas has still not released the Deluxe version of his game. Once a commercial version of the product is available to the public that fulfills the purpose of this editing scheme, I will stop writing cheat editors, patches and the like. Thomas has written a wonderful game, and he deserves to be recompensed for it.
If you enjoy playing ADOM, I encourage you to buy the Deluxe version once it is available. Don't gripe, don't fuss, don't put it off, just do it. This industry needs independent game developers, and they can't exist without your support.
Thomas Biskup's game, Ancient Domains of Mystery, is perhaps the coolest offering on the roguelike plate. There is a large, interesting community of players and developers surrounding the game, and it's fun to play and discuss the various aspects of Adom.
Whenever a group of people gather on a given topic for any length of time, a culture emerges. Usually the nature of a democratic forum prevents the culture from adopting extreme positions, even though many of the members of that community may have such strong feelings. By and large, the Adom community is no different. One position that has been championed to the extreme, however, is a disdain for cheating, hacking, scumming or abusing the game in any way. People who engage in such activity are publicly and forcefully scorned in the Adom community.
I could go on about how this has affected the Adom community for both good and ill, but I won't. Personally, I like the Adom community just fine the way it is.
But let's get one thing straight: I am an outsider to that community. I cheat. I cheat a lot. I don't play games for the challenge of playing them; I play to relax. Personally, games that are difficult or challenging are not the way I like to spend my time. I am by profession a programmer who happens to have an enjoyable, rewarding, high-stress job where I am frustrated and challenged every day with the pressures of the software community. When I get home, I like to do something different.
For me, the perfect way to blow off some stress is to load up Quake, stick in a Gravity Kills CD, crank it to max, switch to God Mode, and slaughter everything in the game with nothing but the hatchet. For me, *that's* entertainment.
On the other hand, I work with software every day. I design, debug, and maintain code on a regular basis. Sometimes, when I want to play a game, an enjoyable challenge for me is to figure out how to cheat. How to edit the game itself, or its save files, or otherwise influence the game in my favor. My personal feeling is that the challenge of cheating is as much fun, or more, than that offered by the game itself, because if I win the game, I have only that satisfaction. But if I defeat the code in the game, I can enjoy my victory AND enjoy the satisfaction of having improved my programming skills and having learned something new.
Thomas Biskup is nothing if not responsive to the hue and cry from the Adom community. In the latest release of Adom, "gamma 10", the game now actively attempts to detect and discourage cheating. Specifically, a Cyclic Redundancy Check (CRC) is performed on the saved game to determine if the game has been edited. If it has, a pithy message that "You have suddenly run out of luck!" appears, and the game drastically alters its difficulty level to punish would be cheaters.
When I first found this out, I was disappointed. Thomas seemed to be saying "Thou shalt not cheat," and frankly my first opinion was "Well fine; I just won't play your game anymore." After time, however, I realized that (a) That's no skin off Thomas' nose, and (b) I was missing out on what had been a very pleasant pastime. In the end, the only person suffering from my decision was me. Worse, I had played gamma 10 long enough to get hooked on the new features, and going back to gamma 9 was a letdown, even with the ability to create amazingly powerful, "fun" characters. So it was that I began looking into besting the challenge of the CRC.
I know a little bit about CRC, and that's why my first reaction was to walk away from it. CRC is NOT a simple algorithm to understand. In fact, in complexity, it's very similar to some cryptographic algorithms. To make the CRC match up correctly, I realized that I would have to do two things: Identify and use the same CRC algorithm, and apply that algorithm to exactly the same sections of the savegame file as Adom. Without those two facts, the chance of getting the correct checksum is about one in four billion.
The math of CRC would take about 500 pages to explain. That's well beyond the scope of this document, but the gist of it is as follows: CRC computes a number that reflects the value and position of the bits in a byte of data. It does this by making the individual bits exponents in a polynomial of the form:
Looks daunting, doesn't it? Stay calm. Basically, there are 8 bits in a byte, so n=8. If the bit at position p
is 1, we add x^p to the number. If it's 0, we don't. It's that simple. If the data were 00000110, the polynomial
for that byte would be x^2 + x^1. To get the CRC for that number, we divide it by a fixed number that is different
from one CRC algorithm to another. CRC-16 uses x^16 + x^15 + x^2 + x^1. It's important to note, however, that in
every algorithm, the divisor is fixed. So to get the CRC-16 checksum for 00000110, we simply calculate this
number:
At first glance, this looks WAY too complex to be useful in any time-critical sense. Furthermore, what is this x we keep seeing? The value of x is a magic number that is calculated in that 500-page treatise I mentioned earlier. The upshot is that using a special value of x and the proper exponents in the divisor (16, 15, 2 and 1 in the CRC-16 example above), we can solve the entire equation with bitwise operations, and no division or exponents to speak of. As a whole, the operation moves rather quickly.
Now, even though the calculations move quickly, there is a further optimization that can be made if the developer is willing to sacrifice a few hundred bytes of RAM. Since there are only 256 possible values for a byte, there are only 256 possible solutions for that formula above. So why not calculate the CRC checksums for every byte in advance and store them in a table? Then, when we need to verify some data, all we have to do is look up each byte's checksum as we read it. This optimization is very common, and in fact it's the key to breaking gamma 10's CRC scheme.
Adom 0.9.9 gamma 10 uses the CRC-32 algorithm.
CRC-32 performs two extra steps over 16-bit implementations: The CRC is preconditioned and postconditioned. In essence, the crc is initialized not to zero but to all ones. The only real advantage to doing this is that it enables CRC-32 to distinguish different-length runs of zero at the beginning of a file--CRC-16 will deliver identical checksums for files that differed only in the number of zeroes at the beginning. After the data has been processed, the bits in the CRC are inverted again. This adds nothing to the algorithm in terms of data integrity validation, but it's part of CCITT's standard for CRC-32, so everybody does it.
I have never disassembled Adom.exe, and to be honest, I don't know exactly how Thomas is verifying the integrity of the file. I know he doesn't just write the file, CRC it and append the checksum. I also know he doesn't just CRC one linear block of data--In testing, I found several separate places in the file where a change in the data goes undetected by the verifier.
My theory is that Thomas is loading the game data into its proper structure in RAM, and then performing a CRC on just the characetr data structure. Because the structure doesn't write directly to disk in a linear fashion, breaking the CRC algorithm would be a problem solvable only by disassembly of Adom itself. At this point I realized that there was no way (short of total disassembly) I would be able to figure out how to forge the CRC code at the end of the character file.
But that doesn't mean we can't edit our characters safely. It only means we can't forge our checksums.
One of the most important things a person can learn about cryptography is that there is no such thing as an unbreakable code. There are only codes that are harder than others to break. CRC is, sadly, an easy algorithm to break, if we are willing only to disassemble the code and reverse engineer it--a practice that cryptanalysts get paid handsomely to perform. However, reverse engineering a game to defeat it is not something I'm going to waste much time on. There's got to be another way.
Another of the most important things a person can learn about cryptography is that most people just don't understand it. When I originally found out that Thomas was using CRC-32, my immediate reaction was that I just don't know enough about CRC to successfully attack it. After a while, however, I began to wonder why Thomas would use the CRC-32 algorithm when it's only real benefit over the 16-bit algorithms is the detection of random lengths of leading zeroes in a byte stream--not a problem ever encountered in Adom save files. I began to realize that, due to the complexity of the algorithm, it was likely that Thomas himself didn't know a lot about CRC--and quite probably didn't know enough to implement it effectively (This is exactly the problem most people have with cryptography and, incidentally, one of the reasons the Allies won World War II in spite of the German Enigma ciphers). CRC-32 is available in any algorithm cookbook, and every cookbook states up front that modifying the code would not be a smart thing as the mathematics are very carefully arranged to provide maximum data integrity without sacrificing speed. Change the algorithm, and you're either going to slow it down, screw it up, or both.
I have already stated that gamma 10 uses the CRC-32 algorithm. But there are many implementations of the CRC algorithm; CRC-32 is just one flavor. How did I know that Thomas was using CRC-32?
Because the executable file contains the optimized table of byte-lookup for CRC-32.
Master Lock Corporation used to run a television commercial showing a man shooting one of their padlocks with a high-powered rifle. The would-be thief was foiled by the ultrasecure design of the lock, which prevented the hasp from being sprung even when the body of the lock had nearly been destroyed. A very entertaining ad, but consider the "reality" of the situation: Imagine someone is breaking into your shed with a high-powered rifle, and they see that you have put a Master Lock on the door. Do they give up and walk away, or do they ask themselves, "I wonder who made that hinge?"
This attitude has to be considered when designing cryptographic equipment. A chain is only as strong as it's weakest link. The security of a system is only as good as its weakest component.
Before I explain how to defeat the CRC algorithm in ADOM, I must bore you with one last detail of the crc algorithm: the exact mechanics of how the lookup table is used.
CRC starts with its checksum set to 0xFFFFFFFF. When a new byte of data arrives, we xor it with the current checksum, and mask off the lowest byte. This is the byte we use as an index into the lookup table. Next we go back to our running checksum, shift all the bits right one byte, and xor THAT value with the value we got from the lookup table. This means that the leftmost eight bits of the crc are copied straight in from the lookup table for each byte, because the leftmost byte is 0x00 after the shift, and A xor 0 = A.
If that description doesn't help, here's the actual code from my algorithm cookbook (notice that after the shift, the crc is masked with 0x00FFFFFF to make extra sure that the high-order byte is cleared):
l = (crc ^ buffer[j]) & 0x000000FFL;
crc = ( (crc >> 8) & 0x00FFFFFFL ) ^ crc32_lookup[l];
The whole point here is, the only thing we can see in Adom is the actual values in the crc32_lookup[] array. You can't hit what you can't see, so the only thing we can edit is also that table. What can we do with the lookup table?
We know that A xor 0 = A. So we can make the high-order byte read anything we like, because it's going to be read straight from the table and XOR'ed with 0. But the three low-order bytes are going to get XOR'ed with the three low-order bytes of the lookup value, and every bit in the lookup's low-order bytes will cause the corresponding bit in the checksum to flip. So whatever we do, we want the three low-order bytes to be 0x000000. Now we can stick any value we want into the high byte, and that will be copied faithfully with each byte that is read. As long as the input buffer has at least four bytes (enough to copy the high byte all the way across the checksum), and all 256 bytes in in the lookup table are identical, we can pick exactly the checksum we want.
Remember, however, that after the last byte has been worked into the checksum, all the bits in the checksum are flipped. So if you want the checksum to come out 0x00000000, you need to make sure it reads 0xFFFFFFFF before the flip, and hence every value in the lookup table needs to be 0xFF000000.
One problem with a checksum of 0: Zero has many uses in C, and Thomas writes a zero as the checksum when a character has been caught cheating. So it is possible, likely even, that Thomas never even checks a zero checksum:
/* Possible code in Adom */
if( !crc || /* If the crc is zero, bail out */
crc != CheckCRC() )
{
/* cheater! */
}
While it may be possible for a valid checksum to read 0 (the lookup value for byte 217 begins with 0xFF), it is certainly very unlikely. The last four bytes of the file would have to be byte 217, and the running checksum would have to be in such a state that the lower three bytes would come around to 0xFF as well in time to be flipped to 0. Since Adom save files don't typically end with four byte 217's, it's a very safe bet.
Another problem with the checksum table is the data itself. The legal CRC-32 lookup value for a byte of 0 is 0x00000000. When Thomas compiled Adom, he had some sort of optimization turned on. He probably uses the table as a static array, which in C automatically gets initialized to zero. Hence, the compiler does not bother to generate code to load the lookup code for element 0, and the data segment of Adom.exe only contains 255 lookup codes--and for all our hacking, the lookup code for byte 0 will always be 0x00000000.
We have some choices: We can disassemble Adom, find the leading byte and set it, and recompile. We can set all the other bytes to our desired value and hope that a zero does not appear in the last four bytes of the data. Or we can use 0x00000000 as ALL the table values.
CRCF uses the third option. It's the cleanest of the three options, and it causes ADOM to generate checksums of 0xFFFFFFFF every time.
That's it, really. Find that table, and overwrite it with zeroes. Now you're ready to edit your characters at will, making sure their checksums read 0xFFFFFFFF when you're done. The nice part is that Adom ALWAYS generates 0xFFFFFFFF now, so you can create new characters and play them "honestly" without problems, and when you decide to edit them, no care need be given to the checksum--it's already set where you want it.
If the Adom community actively derives pleasure from knowing that honesty is enforced where it cannot be persuaded, perhaps I no longer enjoy being around that community. I have enjoyed being around the community, even with the knowledge that I was not an "insider." But with this move, I almost feel the crowd turning violently ethnocentric, intolerant of outsiders, and pursuing them with holy-war fanatacism. Having grown up in a racial hotbed, where hate crimes are still happening today, I have no tolerance for this kind of attitude.
I make the above statement knowing that it's almost certainly an exaggeration, an overstatement, and a heavy-handed accusation if taken at face value. I don't intend it that way, and I don't really see that happening in the community. But there are people out there who are going to be upset when this document is released. Thomas Biskup is sure to be one of them--he has no doubt spent a lot of time adding the CRC code to begin with, and CRCF negates much of that work's value.
But consider this: if we accept the enforcement mentality, we run the risk of becoming like my above statement. By releasing CRCF, I hope to change the very tone of cheating in Adom from a holy war, to a simple challenge. The challenge to play the game on a different level.
Keep writing, Thomas; I love your game. And I intend to keep on cheating. :)
Jumping Spider is an avid programmer and game player, with many and varied interests. His handle comes from the three phidippus audax he used to keep in his office as pets. Since writing CRCF, he actually got a real job as a video game programmer, which is why he's so eager to see Thomas write a commercial version. He and his wife currently live in Salt Lake City, Utah. You can e-mail him with questions, comments, and ideas--but not support for CRCF--here.