Puzzle Quest

When I started playing around with Puzzle Quest, I saw great potential. This was a network-enabled game that relied heavily on the RNG. This meant that it would be possible to predict and manipulate the RNG to create situations favorable to the player and unfavorable to the enemy (for example, matching gems falling from the top and lining up on the board). Eagerly, I began to work towards this goal – but when I discovered how network play is implemented, I was greatly disappointed. During network play, I expected the game to decide on a random seed at the start of the game, and then simply send the players' inputs over the wire, keeping the state of the game in sync. However, what I found was depressing – so depressing, that I lost most of my interest in developing any cheat for the game any further. The network protocol not only sends the players' inputs, but also the entire game board and the players' health and mana reserves. What's even worse, there is no validation of received data, so it's easily possible to swap arbitrary gems, as well as cast arbitrary spells not bound by your repertoire and mana reserves. This kind of puts a sophisticated cheat like mine in a silly position.

After my discovery, I decided to continue with my cheat, but alter my strategy. One of the things sent over the network and joyfully accepted by the client is the RNG seed (a few seeds, actually, for the various game components). The original idea was to predict the outcomes of the various available moves using the current RNG seeds; the new idea was to try various combinations of available moves and new seeds to find a move as good as possible within the allocated time. The end-result can be observed in the videos above. The cheat will automatically "correct" any move you make by editing the random seed with the best seed that complements that move. It also suggests the best overall move off-screen (in the window caption). The video looks like I'm playing as usual, thinking moves through, and being very very lucky (while the dragons, not so much). In a few places, for example at 9:25 and 12:05 in the second video, I "rely on luck" in favor of obvious good moves.

With the HUD enabled, the screen looks like this:

The cheat displays a numerical score for each available move. Scores for gem swap moves are drawn between the two gems to be swapped. The "invalid" move (which can sometimes be the best option) is drawn only once, usually in the top-right corner. Scores are colored based on their value – positive scores are redder, negative scores are bluer. The best move is emphasized by a rectangle surrounding the score. Amongst some information in the corner is the best overall move in text form, its score, and the number of possible moves examined so far for the current game state.

Here's a video showing off some of the tricks you can do by editing outgoing network packets. Please excuse my poor attempts at humor.

About the cheat itself:

The cheat is contained in a DLL file, which is injected into a running instance of Puzzle Quest. Once it injects, it hooks several game functions, as well as the IDirect3DDevice9::Present function (to allow it to draw its own HUD).

Searching for potential moves is done as follows:

1. Stubbing out functions that do not affect game logic, but do have external effects (e.g. playing sounds or animations), thus "dumbing" the game;
2. Saving the current state of certain objects (the game board, players' statuses, RNGs, etc.) – this also involves calling the copy constructor for some classes;
3. Selecting a move to be simulated from a precalculated pool of valid moves, plus some random RNG seeds to try;
4. Sending the simulated move directly to the game engine, bypassing the network component;
5. Running the game engine until control is returned to a human player;
6. Checking the differences between the new game state and the old one, calculating a score based on them, and recording the move if a new record is found;
7. Restoring the game state back to the saved state;
8. Unless the cheat user specified to stop the search, jump back to step 3;
9. Unstubbing the game functions stubbed in step 1, and letting the game continue to run as if nothing happened.

Network packet manipulation is done by hooking the function which sends a packet over the network (the game also processes the same packet locally, to prevent code duplication), and modifying/blocking it just before it is sent to the network component (DirectPlay). This is required to inject the appropriate RNG seeds when the user makes a move manually with the mouse (like in the above videos), as well as for the "dirty" cheats which manipulate the game state directly.

The code is written in Delphi (I swear it's the last time I use Delphi for something sophisticated like this), mostly because I wanted to use a hooking library I'm used to use in Delphi.

Interesting little facts I found while code-diving:

• The game uses the Mersenne twister RNG, specifically this implementation.
• An entire apparently-homebrew cryptographic library (wetstd32.dll) is used to prevent memory hacking. My approach completely sidestepped this protection.
• The game seems to (over-)use the singleton pattern for anything and everything. There are over 35 singletons.
• As the game is shutting down, it will create any not-yet-created singletons, then destroy all singletons. Perhaps this was unintentional, and due to code that might have looked like: GetFoo()->Destroy();
• Either from overdesign or perhaps from some abandoned plans, it seems as if parts of the game code would support a number of opponents greater than two.
• The network code isn't very secure, since there is little-to-none input validation. I haven't noticed anything that could allow remote code execution, but it's easy to at least crash the remote player's game.
• The game AI uses a scoring system which only analyzes the gems on the board (it will not think through cascades, etc.), with some optional randomness (depends on opponent). And no, it doesn't cheat.

So, could Infinite Interactive have done things differently to avoid this?

The answer is "yes", and it's not even very hard.

Obviously, the biggest fault is that the game sends a good part of the game's state over the network. This allows one party to edit these variables arbitrarily, as demonstrated in the video above. I'm going to have good faith and assume that the developers were forced to do this as a last-minute bodge to work around synchronization bugs just before the deadline, since – this hole notwithstanding – the design is at least partially sane (synchronized RNGs). (If this is true, I'm willing to bet that the bugs are at least partially due to stale variables in singleton objects.) If the game would just decide on RNG seeds at the start of the game (instead of picking and sending new seeds on each turn), it would be impossible to "milk" the RNGs for good seeds, as shown in the first video. It would still be possible to emulate various moves with the current RNG seed for an advantage (for example, one of the moves could cause some skulls to fall and line up). Even this can be (mostly) prevented if all parties would each send only a fragment of a RNG seed on each turn (along with sending user input) – this way, none of the parties can control or predict the outcome of a move before the move is actually sent over the network. Note that with this scheme it is important that the RNG seeds are hard to predict (Puzzle Quest currently generates the seeds using the system time).

And lastly, let's never forget: never trust anything that you receive from the network, even if the data is encrypted and the code is obfuscated. Eventually, someone smart/patient enough will get around your protection and cause you a headache. Puzzle Quest came dangerously close to remote code execution; imagine the PR/support nightmare you'd have if someone wrote a virus that spread using a security hole in your game.

You may contact me about the contents of this page, however please keep in mind the following:

1. I will not give you the cheat, unless you're a Very Important Person (e.g. Infinite Interactive staff);
2. E-mails containing "words" like "u", "plz" etc. will be ignored;
3. I will not answer questions that can be answered by a few minutes of searching the Internet.

If you doubt any of what's written here, I can demonstrate the cheat over a network game, just drop me a line.