January 10, 2017

'Keygening' Sega Genesis's Devil Crash


Introduction

This post describes the process of how I figured out the password logic used in the Sega Genesis game Devil Crash.

Devil’s Crush (known as Devil Crash in Japan) is a pinball video game developed by NAXAT Soft for the TurboGrafx-16 and released in 1990. The second installment in the Crush Pinball series after Alien Crush, the game has an eerie occult theme with skulls, skeletons, and demons. It was later followed by Jaki Crush and Alien Crush Returns. The game was ported to the Sega Mega Drive, retitled Dragon’s Fury (Devil Crash MD in Japan) which was developed by Technosoft.

Wikipedia - Devil’s Crush

Devil Crash - Main screen Devil Crash - Main screen

As you can see this is a 20+ year old game. Back then it was pretty common for games to have a password in order to save the state of the game and allow players to restart from a certain point (memory cards were not a thing yet, and not all games had an internal battery to save game state in memory).

Devil Crash was no exception. During gameplay, the player could simply pause the game, press the A button and be presented with a password. This password, when used, would get the player to restart the game with the same score and number of balls that they had when it was generated. This password is composed of 10 characters in the range A-Z0-9.

As a kid, I would sometimes try to guess some passwords. Never had much luck with that besides two passwords I was able to figure out. One was 0000000000 (you start the game with 0 points and 0 balls), and the other DEVILCRASH (you start the game with 390000 points and 7 balls). As you can see, those are not too original and pretty obvious.

Everything described in this post has been done by using a ROM from the game.

Let’s hack!

The first step was to run strings against the ROM, and check what I could find. Some interesting stuff show up:

<... snippet ... >

0Nup
OMAKEBGM00
OMAKEBGM01
OMAKEBGM02
OMAKEBGM03
OMAKEBGM04
BGMOFFMODE
TIMETRIAL0
TIMETRIAL1
TECHNOSOFT
DEVILCRASH
16BIT68000
PLAZMALINE
LUCKYLUCKY
0000000000
!&&SANDAA&&
TF2HZTF3EM
!0956335555p

<... snippet ... >

There are many strings there with 10 characters and two of them are the previously known 0000000000 and DEVILCRASH passwords. Seems like those passwords are hard coded in the game. In order to figure out if that is really the case, I decide to try the other strings of length 10 and noticed that they work. Here are the results of using some of them:

Password Score Balls
0000000000 0000000 0
DEVILCRASH 0390000 7
16BIT68000 0068000 16
LUCKYLUCKY 0077700 7
TECHNOSOFT 2000000 10
TF2HZTF3EM 0464900 10
&&SANDAA&& 3333333 33

The TIMETRIAL0 and TIMETRIAL1 passwords, and the ones above them are used to either start a time trial mode or to change the music that is played during the game. The &&SANDAA&& one is interesting; turns out that the game initializes the password field to the value &&&&&&&&&& and this value is rendered as a blank space in the screen. In order to enter this password then, the player should just leave the first two and last two positions of the string empty.

Password screen Password screen

It seems pretty obvious at this point that the game has a table of hardcoded passwords that it consults before trying to apply any kind of validation logic to the entered password.

I was interested in figuring out how the game knows the number of balls and the score associated with these passwords. Since the passwords are hardcoded, I assumed that these values would also be hardcoded in the ROM somewhere. I proceeded to open the ROM with a binary editor and this is what I found:

00006ea0: 70 1d 61 00 29 4c 61 00 29 84 60 00 fc a0 00 00  p.a.)La.).`.....
00006eb0: 00 00 00 00 4f 4d 41 4b 45 42 47 4d 30 30 00 00  ....OMAKEBGM00..
00006ec0: 00 00 00 00 4f 4d 41 4b 45 42 47 4d 30 31 00 00  ....OMAKEBGM01..
00006ed0: 00 00 00 00 4f 4d 41 4b 45 42 47 4d 30 32 00 00  ....OMAKEBGM02..
00006ee0: 00 00 00 00 4f 4d 41 4b 45 42 47 4d 30 33 00 00  ....OMAKEBGM03..
00006ef0: 00 00 00 00 4f 4d 41 4b 45 42 47 4d 30 34 00 00  ....OMAKEBGM04..
00006f00: 00 00 00 00 42 47 4d 4f 46 46 4d 4f 44 45 00 00  ....BGMOFFMODE..
00006f10: 00 00 00 00 54 49 4d 45 54 52 49 41 4c 30 00 00  ....TIMETRIAL0..
00006f20: 00 00 00 00 54 49 4d 45 54 52 49 41 4c 31 00 00  ....TIMETRIAL1..
00006f30: 4e 20 00 0a 54 45 43 48 4e 4f 53 4f 46 54 00 00  N ..TECHNOSOFT..
00006f40: 0f 3c 00 07 44 45 56 49 4c 43 52 41 53 48 00 00  .<..DEVILCRASH..
00006f50: 02 a8 00 10 31 36 42 49 54 36 38 30 30 30 00 00  ....16BIT68000..
00006f60: 27 10 00 03 50 4c 41 5a 4d 41 4c 49 4e 45 00 00  '...PLAZMALINE..
00006f70: 03 09 00 07 4c 55 43 4b 59 4c 55 43 4b 59 00 00  ....LUCKYLUCKY..
00006f80: 00 00 00 00 30 30 30 30 30 30 30 30 30 30 00 32  ....0000000000.2
00006f90: dc d5 00 21 26 26 53 41 4e 44 41 41 26 26 00 00  ...!&&SANDAA&&..
00006fa0: 12 29 00 0a 54 46 32 48 5a 54 46 33 45 4d 00 00  .)..TF2HZTF3EM..

Interesting. The distance between the passwords was always the same (6 bytes + 10 bytes for the password itself). This looked a lot like a table, just as expected.

At this point, it is important for me to mention a few things I’ve observed from running the game:

  • The score in the game is 9 characters long.
  • The two least significant digits of the score are always 00.

So, I took one of the passwords, and decided to have a closer look. Looking at the TF2HZTF3EM one, we have the score 0464900. Translating this number to hex gives us 0x71804. Looking at the above table there isn’t such a value.

It took me a little bit to connect the dots here. The last two digits of the score never change, so I thought it would be safe to assume that those two digits aren’t even stored in the score. I removed the 00 at the end of the score and got 4649, which converted to hex is 0x1229. Going back to the table above, we can see that value in the addres 0x6fa0. Let’s try that for some of the other scores.

Password Score Balls Score Hex (without 00 at the end)
0000000000 0000000 0 0x0000
DEVILCRASH 0390000 7 0x0f96
16BIT68000 0068000 16 0x02a8
LUCKYLUCKY 0077700 7 0x0309
TECHNOSOFT 2000000 10 0x07d0
TF2HZTF3EM 0464900 10 0x1229

We can see that these values match what is in the hex dump above.

Looking at the two bytes that follow each of the scores, it seems that those numbers match the number of balls. The only thing missing are the two bytes before of what was so far established as being the score. I have modified those bytes manually and started the game with them modified, just to find out that they are also part of the score (it makes sense, the maximum score would be 9999999, which needs at least 3 bytes to be represented, so they used 4 bytes to make it easy).

Here is a nicely highlighted version of it:


00006f90: dc d5 00 21 26 26 53 41 4e 44 41 41 26 26 00 00  ...!&&SANDAA&&..
00006fa0: 12 29 00 0a 54 46 32 48 5a 54 46 33 45 4d 00 00  .)..TF2HZTF3EM..

The color code is:

Score
Balls
Password

To summarize it then, we have a table of passwords starting at address 0x6eae where each entry is 16 bytes long and has the following format:

[4 bytes][2 bytes][10 bytes]
[ score ][ balls ][password]

All this information is great. It tells us how the game stores the score and number of balls, and that somewhere it must be checking the passwords against this table before executing whatever algorithm it uses to validate that a password is correct and then decoding it to restore the score and number of balls that the player has.

I proceed to look for a place where the game would be accessing this table of passwords, and was unable to find it. I used IDA to decompile the ROM, and using IDA’s search feature I wasn’t really able to find any code that was accessing the address where the table started. It drove me nuts, because it meant I was getting something wrong that I couldn’t figure out.

I needed a new approach on how to figure out where the game was validating the password entered by the user. I spent a lot of time trying to work just with the disassembly of the ROM and seeing if I could find it, by searching for specific addresses that I believed would be related to the password validation.

No luck with that.

At this point, I was considering writing my own emulator just so I could set some breakpoints in the ROM to try to figure this out. While doing this would have been awesome, I would probably not be writing this text since I would still be coding. With the plethora of emulators out there, there had to be at least one with decent debugging capabilities (turns out, there is one). Looking around, I found MESS that has some sort of debugging capabilities. The debugger was pretty limited, with an interface that was not easy to use (especially in a window manager) and lacking some functions that I wanted such as exporting the RAM contents to a file or even an easy way of searching for data in RAM.

Nevertheless, I ended up using it for some time and thanks to it I figured out where the password was being stored in RAM as I typed it in the password screen.

It would be pretty logical to believe that the password validation logic had to read this address in order to validate it. Looking at IDA again, I had no luck finding any code accessing this part of the memory other than the initialization routine that would clear it when the game first starts.

The address where the password was being stored as the player types it in the password screen is 0xFFF02E. This is the logic that cleans it up during initialization:

lea	($FFFFF02E).w,a0
move.l	#$26262626,d0
move.l	d0,(a0)+
move.l	d0,(a0)+
move.w	d0,(a0)+
move.l	d0,(a0)+
move.l	d0,(a0)+
move.l	d0,(a0)+
move.l	d0,(a0)+
move.l	d0,(a0)+

Again, I hit a dead end that was driving me crazy. I was again considering writing my own emulator, but before that I decided to try to look for one more emulator with debugging capabilities and try to extend those to do what I wanted.

After some poking around I ended up finding DGEN . This is a pretty cool emulator, that has been around for a while and which development seems to have ceased sometime around 2014. Still, it had a really cool debugger, that while still missing at least the feature of dumping the whole RAM to a file, had a great text based user interface that resembled a bit of GDB. Its source code is also pretty straight forward to read.

This was it then, I was going to use this emulator and add new features to the debugger as I needed. I started by adding a feature to dump the RAM to a user specified file, and the code is available here. Turns out that was all the code I needed to write. The debugger had this really cool feature to watch addresses for changes, so I set a watchpoint on the address where the user password was being stored as it is being entered in the password screen and voila! The debugger breaks in a piece of code I had never seen before. I went back to IDA to see why I had missed that part of the code, and turns out that IDA did not decompile that; it was still showing in IDA as data. I forced IDA to use that address as a code segment and poof! All of a sudden I have a nice piece of code that seems to be validating the password entered by the user. I was really lucky at this point, because the logic that writes the password to the screen and that validates it seemed to be together.

Here is the magic piece of assembly code that I found (don’t worry if it does not make sense, I will explain it right after as well as show a translation to C of what it is doing):

TKTK: Make this code show in a div that can be hidden

ROM:6D1C loc_6D1C:                               ; CODE XREF: ROM:6C0Aj
ROM:6D1C                 moveq   #0,d3
ROM:6D1E                 lea     ($FFFFF632).w,a3
ROM:6D22                 lea     ($FFFFF636).w,a4
ROM:6D26                 lea     ($FFFFF02E).w,a0 
ROM:6D2A                 tst.w   ($FFFFF62A).w
ROM:6D2E                 beq.s   TestHardcodedPasswords
ROM:6D30                 lea     ($FFFFF038).w,a0
ROM:6D34                 bra.s   ValidatePassword
ROM:6D36 ;
---------------------------------------------------------------------------
ROM:6D36
ROM:6D36 TestHardcodedPasswords:                 ; CODE XREF: ROM:6D2Ej
ROM:6D36                 lea     ($6EAE).l,a1
ROM:6D3C                 moveq   #0,d4
ROM:6D3E                 moveq   #$10,d6
ROM:6D40
ROM:6D40 loc_6D40:                               ; CODE XREF: ROM:6DA4j
ROM:6D40                 moveq   #0,d5
ROM:6D42                 move.l  (a1)+,d0
ROM:6D44                 move.w  (a1)+,d1
ROM:6D46                 addq.w  #1,d1
ROM:6D48                 lea     (a0),a2
ROM:6D4A                 moveq   #9,d7
ROM:6D4C
ROM:6D4C loc_6D4C:                               ; CODE XREF: ROM:loc_6D52j
ROM:6D4C                 cmpm.b  (a1)+,(a2)+
ROM:6D4E                 beq.s   loc_6D52
ROM:6D50                 moveq   #$FFFFFFFF,d5
ROM:6D52
ROM:6D52 loc_6D52:                               ; CODE XREF: ROM:6D4Ej
ROM:6D52                 dbf     d7,loc_6D4C
ROM:6D56                 tst.w   d5
ROM:6D58                 bne.s   loc_6DA2
ROM:6D5A                 cmp.w   #8,d4
ROM:6D5E                 bcc.w   StartGame?
ROM:6D62                 cmp.w   #6,d4
ROM:6D66                 bne.s   loc_6D72
ROM:6D68                 move.b  #$FF,($FFFFF647).w
ROM:6D6E                 bra.w   loc_6E72
ROM:6D72 ;
---------------------------------------------------------------------------
ROM:6D72
ROM:6D72 loc_6D72:                               ; CODE XREF: ROM:6D66j
ROM:6D72                 cmp.w   #7,d4
ROM:6D76                 bne.s   loc_6D82
ROM:6D78                 move.b  #$FE,($FFFFF647).w
ROM:6D7E                 bra.w   loc_6E72
ROM:6D82 ;
---------------------------------------------------------------------------
ROM:6D82
ROM:6D82 loc_6D82:                               ; CODE XREF: ROM:6D76j
ROM:6D82                 moveq   #0,d0
ROM:6D84                 moveq   #3,d1
ROM:6D86                 cmp.w   #5,d4
ROM:6D8A                 bne.s   loc_6D96
ROM:6D8C                 move.w  #$FFFF,($FFFFF73C).w
ROM:6D92                 bra.w   StartGame?
ROM:6D96 ;
---------------------------------------------------------------------------
ROM:6D96
ROM:6D96 loc_6D96:                               ; CODE XREF: ROM:6D8Aj
ROM:6D96                 addi.w  #$11,d4
ROM:6D9A                 move.w  d4,($FFFFF73C).w
ROM:6D9E                 bra.w   StartGame?
ROM:6DA2 ;
---------------------------------------------------------------------------
ROM:6DA2
ROM:6DA2 loc_6DA2:                               ; CODE XREF: ROM:6D58j
ROM:6DA2                 addq.w  #1,d4
ROM:6DA4                 dbf     d6,loc_6D40
ROM:6DA8
ROM:6DA8 ValidatePassword:                       ; CODE XREF: ROM:6D34j
ROM:6DA8                                         ; ROM:6E52Fj
ROM:6DA8                 bsr.w   ReadPassCharIntoD2
ROM:6DAC                 move.w  d2,d5
ROM:6DAE                 add.w   d5,d5
ROM:6DB0                 add.w   d5,d5
ROM:6DB2                 add.w   d5,d5
ROM:6DB4                 bsr.w   ReadPassCharIntoD2
ROM:6DB8                 move.w  d2,d6
ROM:6DBA                 and.w   #3,d6
ROM:6DBE                 lsr.w   #2,d2
ROM:6DC0                 or.w    d2,d5
ROM:6DC2                 move.w  d6,d4
ROM:6DC4                 addq.w  #1,d4
ROM:6DC6                 movea.l a0,a1
ROM:6DC8                 moveq   #$4D,d0 ; 'M'
ROM:6DCA                 move.b  (a1)+,d0
ROM:6DCC                 ror.b   #7,d0
ROM:6DCE                 moveq   #6,d7
ROM:6DD0
ROM:6DD0 loc_6DD0:                               ; CODE XREF: ROM:6DD6j
ROM:6DD0                 move.b  (a1)+,d2
ROM:6DD2                 ror.b   d7,d2
ROM:6DD4                 eor.b   d2,d0
ROM:6DD6                 dbf     d7,loc_6DD0
ROM:6DDA                 cmp.b   d5,d0
ROM:6DDC                 bne.w   WrongPassword?
ROM:6DE0                 moveq   #0,d0
ROM:6DE2                 moveq   #5,d7
ROM:6DE4
ROM:6DE4 loc_6DE4:                               ; CODE XREF: ROM:6DEEj
ROM:6DE4                 bsr.w   ReadPassCharIntoD2
ROM:6DE8                 sub.w   d4,d2
ROM:6DEA                 lsl.l   #5,d0
ROM:6DEC                 or.w    d2,d0
ROM:6DEE                 dbf     d7,loc_6DE4
ROM:6DF2                 add.l   d0,d0
ROM:6DF4                 add.l   d0,d0
ROM:6DF6                 bsr.w   ReadPassCharIntoD2
ROM:6DFA                 sub.w   d4,d2
ROM:6DFC                 move.w  d2,d1
ROM:6DFE                 and.w   #7,d1
ROM:6E02                 lsl.w   #5,d1
ROM:6E04                 lsr.w   #3,d2
ROM:6E06                 or.w    d2,d0
ROM:6E08                 bsr.w   ReadPassCharIntoD2
ROM:6E0C                 sub.w   d4,d2
ROM:6E0E                 or.w    d2,d1
ROM:6E10                 lea     ($6A88).l,a2
ROM:6E16                 add.w   d6,d6
ROM:6E18                 add.w   d6,d6
ROM:6E1A                 add.w   d6,d6
ROM:6E1C                 lea     (a2,d6.w),a2
ROM:6E20                 move.l  (a2)+,d2
ROM:6E22                 eor.l   d2,d0
ROM:6E24                 move.b  (a2),d2
ROM:6E26                 eor.b   d2,d1
ROM:6E28                 cmp.l   #$98967F,d0
ROM:6E2E                 bls.s   loc_6E32
ROM:6E30                 bra.s   WrongPassword?
ROM:6E32 ;
---------------------------------------------------------------------------
ROM:6E32
ROM:6E32 loc_6E32:                               ; CODE XREF: ROM:6E2Ej
ROM:6E32                 cmp.w   #$64,d1 ; 'd'
ROM:6E36                 bls.s   StartGame?
ROM:6E38                 bra.s   WrongPassword?
; ...
ROM:6E8E ; =============== S U B R O U T I N E ===============================
ROM:6E8E ReadPassCharIntoD2:                     ; CODE XREF: ROM:ValidatePasswordp
ROM:6E8E                                         ; ROM:6DB4p ...
ROM:6E8E                 clr.w   d2
ROM:6E90                 move.b  (a0)+,d2
ROM:6E92                 cmp.w   #$39,d2 ; '9'
ROM:6E96                 bls.s   loc_6E9A
ROM:6E98                 subq.w  #7,d2
ROM:6E9A
ROM:6E9A loc_6E9A:                               ; CODE XREF:
ReadPassCharIntoD2+8j
ROM:6E9A                 subi.w  #$30,d2 ; '0'
ROM:6E9E                 rts
ROM:6E9E ; End of function ReadPassCharIntoD2

That is a lot of assembly. Some things to know about the above code:

  • Register d0 is where the score is stored
  • Register d1 is where the number of balls is stored
  • Register d2 is used to perform the logic over the password
  • Register a0 points to address $FFFFF02E. This is where the typed password is stored in RAM
  • Address $6EAE is where the table of hardcoded passwords start
  • Address $6A88 holds a table of chars that is used as some sort of mask when generating the password by XORing it with the score and number of balls

The above code is the logic that validates the password entered by the player. It reads the password entered and decodes it to extract the score and number of balls as well as validate a checksum. That is the gist of it.

The validation logic

The first part of the code is just checking if the entered password is in the table of hardcoded passwords discussed before. If it is there, it just loads the balls and score from the table and starts the game. That is not what I am intereted in. The logic that follows is what interests me; that is when the password is broken down to pieces to check if it is valid and derive the score and number of balls from it.

First thing that is defined is a function that converts the ASCII characters to a number in the range from 0x00 to 0x23. That is what I called decodePassChar above. It takes a char in the [A-Z0-9] range and converts to a number, according to the following logic:

unsigned char decodePassChar(char p) {
    if(p > 0x39)
        p -= 7;
    p -= 0x30;

    return p;
}

That 7 being subtracted there is just to skip some of the chars in the ASCII table (the ones between ‘9’ and ‘A’). Basically, this function can be replaced with this table:

p return p return p return
‘0’ 0x00 ‘C’ 0x0C ‘O’ 0x18
‘1’ 0x01 ‘D’ 0x0D ‘P’ 0x19
‘2’ 0x02 ‘E’ 0x0E ‘Q’ 0x1A
‘3’ 0x03 ‘F’ 0x0F ‘R’ 0x1B
‘4’ 0x04 ‘G’ 0x10 ‘S’ 0x1C
‘5’ 0x05 ‘H’ 0x11 ‘T’ 0x1D
‘6’ 0x06 ‘I’ 0x12 ‘U’ 0x1E
‘7’ 0x07 ‘J’ 0x13 ‘V’ 0x1F
‘8’ 0x08 ‘K’ 0x14 ‘W’ 0x20
‘9’ 0x09 ‘L’ 0x15 ‘X’ 0x21
‘A’ 0x0A ‘M’ 0x16 ‘Y’ 0x22
‘B’ 0x0B ‘N’ 0x17 ‘Z’ 0x23

There is a table with a hardcoded string that is used to XOR the number of balls and score before encoding it into the password. That table is:

char *table = "MEGA-DRATHUNDER4GANBATTETUKURUZOA";

Let’s take a password generated by the game as an example: QJELEORTEL. This passwords gives the player 3 balls and a score of 17600. Keep in mind that the game does not store the last two digits of the score since they are always zero, so the score encoded in the password will be 176.

We start by converting the characters in the password according to the table above.

Pass Letter Converted Converted Binary Name
Q 0x1A 0001 1010 b1
J 0x13 0001 0011 b2
E 0x0E 0000 1110 b3
L 0x15 0001 0101 b4
E 0x0E 0000 1110 b5
O 0x18 0001 1000 b6
R 0x1B 0001 1011 b7
T 0x1D 0001 1101 b8
E 0x0E 0000 1110 b9
L 0x15 0001 0101 b10

Putting that binary string together, this is what we have after the password has been converted: 0001 1010 0001 0011 0000 1110 0001 0101 0000 1110 0001 1000 0001 1011 0001 1101 0000 1110 0001 0101.

The breakdown of the password is as follows:

Password breakdown

Numbers in orange are non-used values.

These of course, are not the values in their final form. The code now does some transformations to the XORed Balls and Score * values, in order to determine the final values for the number of balls and score. The index value is used to determine what were the bytes from table that were used to XOR the score and the number of balls and its value ranges between 0 and 3 and is “randomly” selected (more on this when discussing the logic that generates the passwords).

Starting with the checksum, here is how it is rebuilt and calculated.

checksum = (b1 << 3) | (b2 >> 2);

This is just concatenating the two parts of the checksum in a single byte. In this case, the checksum results in 0xD4.

We just need to calculate the checksum now, and see if those two values match. The logic to calculate the checksum is:

calc_checksum = rorByte(password[2], 7) ^ rorByte(password[3], 6) ^ 
                rorByte(password[4], 5) ^ rorByte(password[5], 4) ^ 
                rorByte(password[6], 3) ^ rorByte(password[7], 2) ^ 
                rorByte(password[8], 1) ^ rorByte(password[9], 0);

Where password is the ASCII representation of the password. In this case what is happening then is:

calc_checksum = rorByte('E', 7) ^ rorByte('L', 6) ^ 
                rorByte('E', 5) ^ rorByte('O', 4) ^ 
                rorByte('R', 3) ^ rorByte('T', 2) ^ 
                rorByte('E', 1) ^ rorByte('L', 0);

Calculating this, gives us calc_checksum = 0xD4. It is a match!

At this point, we need to take note of the value identified as index, since it is also used to “obfuscate” the score values. In our example, index = 0x03.

Considering that the calculated checksum matches the checksum that is stored in the password, the logic follows to calculate the score associated with this password. The maximum score possible in this game is 0x98967F. This value converted to binary is 1001 1000 1001 0110 0111 1111. This is 24 bits. The score is stored in 4 bytes in the code, meaning that the most significant byte is always set to 0. The way the score is encoded in the password looks like this:

                                         // Bits are all set to 0
int score_xored = 0;                     // 00000000000000000000000000000000

                                         // Replacing the bits with the 
                                         // corresponding byte bX

score_xored = (b3 - (index + 1)) << 27 | // 33333000000000000000000000000000
              (b4 - (index + 1)) << 22 | // 33333444440000000000000000000000
              (b5 - (index + 1)) << 17 | // 33333444445555500000000000000000
              (b6 - (index + 1)) << 12 | // 33333444445555566666000000000000
              (b7 - (index + 1)) <<  7 | // 33333444445555566666777778888800
              (b8 - (index + 1)) <<  2 | // 33333444445555566666777778888800
              (b9 - (index + 1)) >> 3;   // 33333444445555566666777778888899

Basically what this is doing is rebuilding an int. Each of the bytes in which the score is encoded have been incremented by index + 1. So, we need to subtract that value from each of those bytes, and then rotate each one of them to their corresponding position in a 32 bit int.

score7 represents the 5 most significant bits of the value, with score6 right next to it, and so on all the way to score2. This number is then missing the 2 least significant bits, which are encoded in b9. This byte was also added to index + 1, so we just subtract that value, shift that byte right three times in order to get rid of the number of the XORed Balls High value and OR it into the final score_xored. You are probably thinking “but there are only 2 bits available in the score_xored and score1 is 3 bits long in the diagram”. In the diagram score1 is 3 bits long, because it is added to index + 1. The maximum value for index + 1 is 4 (3 bits), so summing index + 1 to b9, the highest possible value that can be achieved is 7, which needs 3 bits to be encoded. It is guaranteed that subtracting index + 1 from b9 will always give a value less or equal than 3.

We now have the score that has been XORed with 4 bytes of the table.

Substituting the values with the ones in our example then:

int score_xored = (0x0E - (3 + 1)) << 27 |
                  (0x15 - (3 + 1)) << 22 |
                  (0x0E - (3 + 1)) << 17 |
                  (0x18 - (3 + 1)) << 12 |
                  (0x1B - (3 + 1)) <<  7 |
                  (0x1D - (3 + 1)) <<  2 |
                  (0x0E - (3 + 1)) >> 3;

The result is score_xored = 0x54554BE5.

In order to facilitate the next step, let’s break this value in 4 bytes.

score_byte1 = 0x54;
score_byte2 = 0x55;
score_byte3 = 0x4B;
score_byte4 = 0xE5;

This score_xored value is XORed with the bytes in table starting at the index index * 8. In this case then, we have:

score_byte1 = table[index * 8] ^ (score_byte1);
score_byte2 = table[index * 8 + 1] ^ (score_byte2);
score_byte3 = table[index * 8 + 2] ^ (score_byte3);
score_byte4 = table[index * 8 + 3] ^ (score_byte4);

Replacing the values:

score_byte1 = table[3 * 8] ^ (0x54);
score_byte2 = table[3 * 8 + 1] ^ (0x55);
score_byte3 = table[3 * 8 + 2] ^ (0x4B);
score_byte4 = table[3 * 8 + 3] ^ (0xE5);

// ... replace once again

score_byte1 = table[24] ^ (0x54);
score_byte2 = table[25] ^ (0x55);
score_byte3 = table[26] ^ (0x4B);
score_byte4 = table[27] ^ (0xE5);

// ... replace once again

score_byte1 = 'T' ^ (0x54);
score_byte2 = 'U' ^ (0x55);
score_byte3 = 'K' ^ (0x4B);
score_byte4 = 'U' ^ (0xE5);

// ... last time

score_byte1 = 0x54 ^ (0x54);
score_byte2 = 0x55 ^ (0x55);
score_byte3 = 0x4B ^ (0x4B);
score_byte4 = 0x55 ^ (0xE5);

// ... result

score_byte1 = 0x00;
score_byte2 = 0x00;
score_byte3 = 0x00;
score_byte4 = 0xb0; // 0xb0 = 176

This gives a score of 176, which is just as expected.

The last thing left to do, is calculate the number of balls from this password. This is pretty much the same approach as the score. Subtract index + 1 from both b9 and b10. This results in 1 bit coming from b9 and 5 bits coming from b10. Just OR together those values, and you are good to go!

balls_xored = ((b9 - (index + 1)) & 0x03) << 5 | (b10 - (index + 1));

Replacing our values:

balls_xored = ((0x0E - (3 + 1)) & 0x03) << 5 | (0x15 - (3 + 1));

// ... result

balls_xored = 0x11;

Just have to take balls_xored and XOR it against table[index + 8 + 4] and then AND the result with 0x7F (in order to get only the 7 least significant bits, since the number of balls is stored in 7 bits).

balls = (balls_xored ^ table[index * 8 + 4]) & 0x7F;

// ... replacing values

balls = (0x11 ^ table[3 * 8 + 4]) & 0x7F;

// ... one more time

balls = (0x11 ^ table[28]) & 0x7F;

// .. and again

balls = (0x11 ^ 'R') & 0x7F;

// ... last time

balls = (0x11 ^ 0x52) & 0x7F; 

// ... result

balls = 0x03;

So we have balls = 3 just as expected.

In the end, there is some logic to validate that the decoded score and number of balls are smaller than their respective maximum values. If any of them is higher, the password is rejected.

In summary:

  • Calculate the checksum of the password
  • Read the index encoded in the password
  • Read the checksum encoded in the password
  • Validate that the checksum calculated and the checksum read match
  • Decode the score
  • Decode the number of balls
  • Validate that the score is smaller than the maximum allowed score
  • Validate that the number of balls is smaller than the maximum allowed

Below is the piece of code I put together that performs all this logic (it is pretty verbose, but that is on purpose):

#include <stdio.h>
#include <stdlib.h>

#define MAX_SCORE 0x98967F

unsigned char rorByte(unsigned char val, unsigned char qty) {
    // if least significant bit is 1, we need to move
    // it to the most significant bit position after
    // the shift
    for(int i = 0; i < qty; i++) {
        char isOne = 0;

        if((val & 0x01) == 0x01) {
            isOne = 1;
        }

        val = val >> 1;
        if(isOne == 1) {
            val = val | 0x80;
        }
    }

    return val;
}

void validate_params(int argc, char **argv) {
    if(argc < 2) {
        printf("Usage: %s <password>\n", argv[0]);
        exit(-1);
    }
}

unsigned char decodePassChar(char p) {
    if(p > 0x39)
        p -= 7;
    p -= 0x30;

    return p;
}

int main(int argc, char **argv) {
    validate_params(argc, argv);

    char *password = argv[1];
    char *table = "MEGA-DRATHUNDER4GANBATTETUKURUZOA";

    unsigned char score_byte1;
    unsigned char score_byte2;
    unsigned char score_byte3;
    unsigned char score_byte4;

    int score_xored;
    int balls_xored;

    int score;
    int balls;
    int index;

    unsigned char checksum;
    unsigned char calc_checksum;

    unsigned char b1  = decodePassChar(password[0]);
    unsigned char b2  = decodePassChar(password[1]);
    unsigned char b3  = decodePassChar(password[2]);
    unsigned char b4  = decodePassChar(password[3]);
    unsigned char b5  = decodePassChar(password[4]);
    unsigned char b6  = decodePassChar(password[5]);
    unsigned char b7  = decodePassChar(password[6]);
    unsigned char b8  = decodePassChar(password[7]);
    unsigned char b9  = decodePassChar(password[8]);
    unsigned char b10 = decodePassChar(password[9]);

    checksum = (b1 << 3) | (b2 >> 2);
    index = b2 & 0x03;

    calc_checksum = rorByte(password[2], 7) ^ rorByte(password[3], 6) ^ 
                    rorByte(password[4], 5) ^ rorByte(password[5], 4) ^ 
                    rorByte(password[6], 3) ^ rorByte(password[7], 2) ^ 
                    rorByte(password[8], 1) ^ rorByte(password[9], 0);


    if(calc_checksum != checksum) {
        printf("Password checksum does not match.\n");
        printf("Expected: [%02X] - Calculated: [%02X]\n", checksum, 
                calc_checksum);
        return -1;
    }

    score_xored = (b3 - (index + 1)) << 27 |
                  (b4 - (index + 1)) << 22 | 
                  (b5 - (index + 1)) << 17 |
                  (b6 - (index + 1)) << 12 |
                  (b7 - (index + 1)) <<  7 |
                  (b8 - (index + 1)) <<  2 |
                  (b9 - (index + 1)) >> 3; 

    score_byte1 = (score_xored >> 24) & 0xFF;
    score_byte2 = (score_xored >> 16) & 0xFF;
    score_byte3 = (score_xored >>  8) & 0xFF;
    score_byte4 = (score_xored >>  0) & 0xFF;

    score_byte1 = table[index * 8] ^ (score_byte1);
    score_byte2 = table[index * 8 + 1] ^ (score_byte2);
    score_byte3 = table[index * 8 + 2] ^ (score_byte3);
    score_byte4 = table[index * 8 + 3] ^ (score_byte4);

    score = 0;
    score = score | score_byte1;
    score = score << 8;
    score = score | score_byte2;
    score = score << 8;
    score = score | score_byte3;
    score = score << 8;
    score = score | score_byte4;

    balls_xored = ((b9 - (index + 1)) & 0x03) << 5  |
                  (b10 - (index + 1));

    balls = (balls_xored ^ table[index * 8 + 4]) & 0x7F;

    if(score > MAX_SCORE) {
        printf("Invalid score. ");
        printf("Score [%d] is greater than maximum allowed [%d]", score, 
                MAX_SCORE);

        return -1;
    }

    if(balls > 99) {
        printf("Invalid number of balls [%d].", balls);
        return -1;
    }

    printf("Password succesfully validated!\n");
    printf("Score: %d\n", score * 100);
    printf("Balls: %d\n", balls);
    return 0;

}

One last thing to notice here, is that this code does not take into account the hardcoded passwords. I skipped that part during my analysis, since I was anxious to see how the validation worked and wanted to implement it.

The password generation logic

It should be pretty straight forward now. Everything that needs to be done is performing the actions from the validation logic in the opposite direction. In order to make the whole process clear, I will also describe this logic step by step. The code here will be more closely related to the assembly code that was analyzed to figure out this logic.

Just as a reminder:

  • There is a table of fixed values used to XOR the score and number of balls and I called it table
  • The password is a 24 bits number
  • The number of balls is a 7 bits number

This process will take the score and number of balls as input, and output the password.

A buffer of size 10 is defined to hold the password and initialized to a dummy value.

char password[10] = "&&&&&&&&&&";

We also define the toAscii function, which is just the reverse of the decodePassChar function defined before (it performs the operation over that table, transforming the number back into an ASCII char).

A random value between 0x00 and 0xFF is chosen, and then AND it with 0x03. Call this value index. The password generation logic in the game is pretty weird for this index value. It calls lots of different code, and ends up with a value between 0x00 and 0xFF which is then ANDed with 0x03 and used. While playing the game, if you tell it to generate the password multiple times you will notice that the password changes. The reason for that is that this index value keeps changing which lead me to believe it is “random”.

From table, take the four bytes starting at table[index * 8] and XOR it with score and save it in score_xored. (Remembering that table is an array of char that is hardcoded in the game).

int index = random() % 4; // random number between 0 and 3
int tmp;
int score = 176; // example score value already divided by 100
int score_xored;

char *table = "MEGA-DRATHUNDER4GANBATTETUKURUZOA";

tmp = table[(index * 8) + 0] << 24 | 
      table[(index * 8) + 1] << 16 | 
      table[(index * 8) + 2] <<  8 | 
      table[(index * 8) + 3]; 

score_xored = score ^ tmp;

Save the two least significant bits of score_xored in a temporary variable called d3.

int d3;
d3 = score_xored & 0x03;

The score_xored is then rotated left 5 bits. We take the least 5 significant and sum them to index + 1 and save them in a tmp variable. This rotation to the left is just to make it easy to isolate the bits that we want to work with. The rotation simply puts those 5 bits in the right most position of the binary number making them the 5 least significant bits. That way it is easy to extract those bits.

score_xored = intRotateLeft(score_xored, 5);
tmp = score_xored & 0x1F; // Take the least 5 significant bits
tmp = tmp + index + 1;

This tmp variable now contains a value between 0x00 and 0x23 (remember, index is a value between 0x00 and 0x03 and we are ANDing the score_xored with 0x1F so the maximum value possible here is 0x1F + 0x03 + 0x01). The tmp value is then converted to an ASCII value according to the toAscii function and stored in the buffer where the final password is. This process is repeated in a loop 6 times, and starts by writing to the third password character all the way to the eighth.

for(int i = 2; i < 8; i++) {
    score_xored = intRotateLeft(score_xored, 5);
    tmp = score_xored & 0x1F; // Take the least 5 significant bits
    tmp = tmp + index + 1;
    password[i] = toAscii(tmp);
}

Up to this point we were able to encode almost all bits of the password, except for the two least significant ones. These two bits were stored in the d3 variable and will be encoded in the 9th character of the password, together with the two most significant bits of the XORed number of balls.

balls_xored = balls ^ table[(index * 8) + 4];
d3 = (d3 << 3) | (balls_xored >> 5); // 2 bits of score + 2 bits of number of balls
d3 = (d3 & 0x1F) + index + 1;
password[8] = toAscii(d3);

The last character of the password contains then the 5 least significant bits of balls_xored.

tmp = (balls_xored & 0x1F) + index + 1;
password[9] = toAscii(tmp);

So all bytes from 2 to 9 have been covered so far. We are just missing the first two bytes of the password.

Now, in order to be able to decode this password we must have the value of index encoded into it (so that the reverse operations can be performed by the routine that validates the password), and for good measure add a checksum byte to the password.

The checksum is stored in the first byte of the password. It is calculated by rotating the bits of the characters calculated up to this point, with the following logic:

checksum = byteRotateRight(password[2], 7) ^ byteRotateRight(password[3], 6) ^ 
           byteRotateRight(password[4], 5) ^ byteRotateRight(password[5], 4) ^ 
           byteRotateRight(password[6], 3) ^ byteRotateRight(password[7], 2) ^ 
           byteRotateRight(password[8], 1) ^ byteRotateRight(password[9], 0);

This checksum value is then stored in the first and second bytes of the password. The 5 most significant bits are stored in the first character and the least 3 significant bits are stored in the second character together with the index. The logic looks like this:

password[0] = toAscii(checksum >> 3);

char b2 = ((checksum & 0x07) << 2) | (index & 0x03);
password[1] = toAscii(b2);

The final code looks like this:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_SCORE 0x98967F

void validate_arguments(int argc, char **argv) {
    unsigned int score;
    unsigned short balls;

    char *score_str;
    char *balls_str;

    if(argc < 3) {
        printf("Usage: %s score balls\n", argv[0]);
        exit(-1);
    }

    score_str = argv[1];
    balls_str = argv[2];

    score = atoi(score_str);
    balls = atoi(balls_str);

    printf("Score provided: %d\n", score);
    printf("Balls provided: %d\n", balls);


    if(strlen(score_str) < 3) {
        printf("Score has to be at least 3 chars long\n");
        exit(-1);
    }

    if((score % 100) != 0) {
        printf("Two least significative digits of the score should be 00\n");
        exit(-1);
    }

    if((score / 100) > MAX_SCORE) {
        printf("Score cannot be greater than %d\n", MAX_SCORE);
        exit(-1);
    }

    if(balls > 99) {
        printf("Number of balls cannot be greater than 99\n");
        exit(-1);
    }

}

char toAscii(char d2) {
    d2 += 0x30;
    if(d2 > 0x39)
        d2 += 7;

    return d2;
}

int intRotateLeft(int val, int qty) {

    // if least significant bit is 1, we need to move
    // it to the most significant bit position after
    // the shift
    for(int i = 0; i < qty; i++) {

        char isOne = 0;

        if((val & 0x80000000) == 0x80000000) { // supposing int is 32 bits
            isOne = 1;
        }

        val = val << 1;

        if(isOne == 1) {
            val = val | 0x01;
        }
    }

    return val;
}



unsigned char byteRotateRight(unsigned char val, unsigned char qty) {
    // if least significant bit is 1, we need to move
    // it to the most significant bit position after
    // the shift
    for(int i = 0; i < qty; i++) {

        char isOne = 0;

        if((val & 0x01) == 0x01) {
            isOne = 1;
        }

        val = val >> 1;

        if(isOne == 1) {
            val = val | 0x80;
        }
    }

    return val;
}

int main(int argc, char **argv) {

    validate_arguments(argc, argv);

    char password[10] = "&&&&&&&&&&";
    srand(time(NULL));
    int index = random() % 4; // random number between 0 and 3

    printf("index = %d\n", index);

    int tmp;
    int score;
    int score_xored;

    int balls;
    int balls_xored;
    int d3;

    char *table = "MEGA-DRATHUNDER4GANBATTETUKURUZOA";

    unsigned char b2;
    unsigned char checksum;

    score = atoi(argv[1]) / 100;
    balls = atoi(argv[2]);

    tmp = table[index * 8 + 0] << 24 | 
          table[index * 8 + 1] << 16 | 
          table[index * 8 + 2] <<  8 | 
          table[index * 8 + 3]; 

    score_xored = score ^ tmp;

    d3 = score_xored & 0x03;

    for(int i = 2; i < 8; i++) {
        score_xored = intRotateLeft(score_xored, 5);
        tmp = score_xored & 0x1F; // Take the least 5 significant bits
        tmp = tmp + index + 1;
        password[i] = toAscii(tmp);
    }

    balls_xored = balls ^ table[(index * 8) + 4];
    d3 = (d3 << 3) | (balls_xored >> 5); // 2 bits of score + 
                                         // 2 bits of number of balls
    d3 = (d3 & 0x1F) + index + 1;
    password[8] = toAscii(d3);

    tmp = (balls_xored & 0x1F) + index + 1;
    password[9] = toAscii(tmp);

    checksum = byteRotateRight(password[2], 7) ^ byteRotateRight(password[3], 6) ^ 
               byteRotateRight(password[4], 5) ^ byteRotateRight(password[5], 4) ^ 
               byteRotateRight(password[6], 3) ^ byteRotateRight(password[7], 2) ^ 
               byteRotateRight(password[8], 1) ^ byteRotateRight(password[9], 0);

    password[0] = toAscii(checksum >> 3);

    b2 = ((checksum & 0x07) << 2) | (index & 0x03);
    password[1] = toAscii(b2);

    printf("Password generated is: %s\n", password);

}

And here are a couple of example runs:

$ ./a.out 123456700 39
Score provided: 123456700
Balls provided: 39
index = 1
Password generated is: DDCJFA9KD5

Score 123456700 and 39 balls Score 123456700 and 39 balls

$ ./a.out 765432100 74
Score provided: 765432100
Balls provided: 74
index = 0
Password generated is: 54ALPPQT48

Score 765432100 and 74 balls Score 765432100 and 74 balls

$ ./a.out 112233400 51
Score provided: 112233400
Balls provided: 51
index = 1
Password generated is: E5CJEPCM5P

Score 112233400 and 51 balls Score 112233400 and 51 balls