+---------------------------------------------------------+ | Reverse Engineering of Casltevania II's Password System | | by Kingshriek (Dean Fehlau) | | email: kingshriek at yahoo dot com | +---------------------------------------------------------+ 1. Introduction This document contains a reverse engineering of the password system in the US version of Castlevania II: Simon's Quest (CV2). I'm not sure if the system is the same in the European version. The Japanese release, Akumajou Dracula: Noroi no Fuuin was a Famicom Disk System game and saves directly to disk so no password system was needed. It is assumed that the reader is familiar with binary and hexidecimal notation and is comfortable converting both to and from decimal notation. It is also assumed that the reader is familiar with basic logic operations (and, or, xor, left shift, right shift). It will also be helpful if the reader has some familiarity with 6502 assembly and how the CPU RAM is organized. The CV2 password saves the following information : 1. Simon's experience level 2. Number of game days that have elapsed 3. Quantity of garlic and laurels 4. Possession of quest items - Dracula's body parts and crystals 5. Possession of other items - garlic, laurels, magic cross, silk bag 6. Possession of use items - stake, flame, diamond, holy water, 3 daggers 7. The whip that is in possession The terms "quest items", "other items", and "use items" will be used throughout the document. Please see the next section for an exact listing of what each category entails. The information above has been split up in this manner because each one of the seven categories corresponds to a byte that makes up the base password. 2. Notation Before the password system can be discussed, the reader needs to be familiar with the notation used in the document. $zz or $zzzz - memory address ($xx is a zero-page address) 0xzz - value in hexidecimal Operators (in order of precedence): + , - Addition, Subtraction << , >> Left Shift, Right Shift <-------- done first & Logical AND ^ Logical XOR | Logical OR <-------- done last 3. How the password in generated Before we get into the password generation algorithm, we need to know where and how the game stores the seven categories of information listed above in memory. Generally, for items that are stored by a single bit, a value of 1 means the item is in possession and a value of 0 means the item is not. The adressess for this information are as follows: $004A - use items bits (from highest order to lowest) 7 - not used, keep set to 0 6 - Oak Stake 5 - Holy Flame 4 - Diamond 3 - Holy Water 2 - Golden Dagger 1 - Silver Dagger 0 - Dagger $004C - quantity of laurels (max. 8) $004D - quantity of garlic (max. 8) $0083 - time elapsed in game days (max. 9) $008B - Simon's level (max. 6) $0091 - quest items bits (from highest order to lowest) 7 - not used, keep set to 0 6 - Blue Crystal ---+ +--- set both to get the Red Crystal 5 - White Crystal ---+ 4 - Dracula's Ring 3 - Dracula's Nail 2 - Dracula's Eye 1 - Dracula's Heart 0 - Dracula's Rib $0092 - other items bits (from highest order to lowest) 7-4 - not used, keep set to 0 3 - Garlic 2 - Laurels 1 - Magic Cross 0 - Silk Bag $0434 - whip (takes on values between 0 and 4) 0 - Leather Whip 1 - Thorn. Whip 2 - Chain Whip 3 - Morning Star 4 - Flame Whip In summary, the ranges for each value are: $004A 0x00-0x7F $004C 0x00-0x08 $004D 0x00-0x08 $0083 0x00-0x09 $008B 0x00-0x06 $0091 0x00-0x7F $0092 0x00-0x0F $0434 0x00-0x04 Now we can begin with the generation algorithm. The password generation code begins at $AF21 in RAM. First, the game stores the contents of all the above addresses into the address range $0520-$0526. It does this in the following manner: $0520 = $8B ; Simon's experience level $0521 = $83 ; Time elapsed in game days $0522 = $4C | $4D << 4 ; # of garlic and laurels (see note below) $0523 = $91 ; quest items $0524 = $92 ; other items $0525 = $4A ; use items $0526 = $0434 ; whip note: # of garlic is stored in the upper 4 bytes of $522 whereas # of laurels is stored in the lower 4 bytes Next, checksums are computed and stored in $0527-$0528. $0527 = ($0520 + $0521 + $0522 + $0523 + $0524 + $0525 + $0526) & 0xFF00 $0528 = ($0520 + $0521 + $0522 + $0523 + $0524 + $0525 + $0526) & 0x00FF For randomization, the password generated uses a value from a counter that updates on every frame (the counter increments by 0x01 and goes through all values 0x00-0xFF). The address of this counter is $1D. A "random" value used in password generation is stored in $0529 after some intermediate calculations, which are stored at $04F7 and $04F6. The randomizer uses a lookup table for the upper 4 bytes of the $0529 byte. The lower 4 bytes of $0529 is the same as the lower 4 bytes of the counter value. Only a single counter value is used for the calculation of $04F7 and $04F6 values. The lookup table begins at $AF19 and is 8 bytes long. $AF19 - $AF20 $AF10: xx xx xx xx xx xx xx xx xx 00 01 02 03 04 01 02 $AF20: 03 xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx Now for the randomization value code. $04F7 = $(0xAF19 + $1D & 0x07) $04F6 = $1D & 0x0F $0529 = $04F6 | $04F7 << 4 Next, a series of logical operations are performed on the bytes $0520-$0529 to generate the bytes $0530-$053F. $0530 = $0520 >> 3 $0531 = ($0520 & 0x07) << 2 | $0521 >> 6 $0532 = ($0521 & 0x3E) >> 1 $0533 = ($0521 & 0x01) << 4 | $0522 >> 4 $0534 = ($0522 & 0x0F) << 1 | $0523 >> 7 $0535 = ($0523 & 0x7C) >> 2 $0536 = ($0523 & 0x03) << 3 | ($0524 & 0xE0) >> 5 $0537 = $0524 & 0x1F $0538 = $0525 >> 3 $0539 = ($0525 & 0x07) << 2 | $0526 >> 6 $053A = ($0526 & 0x3E) >> 1 $053B = ($0526 & 0x01) << 4 | $0527 >> 4 $053C = ($0527 & 0x0F) << 1 | $0528 >> 7 $053D = ($0528 & 0x7C) >> 2 $053E = ($0528 & 0x03) << 3 | $0529 >> 5 $053F = $0529 & 0x1F Next, the data in $0530-$53F is modified based on the random values generated previously. Here, another look-up table is used -- this one containing 2-byte memory address stored with the lower-order byte first. Start at $B228 and add to the address itself the value at $04F6 shifted left by 1. The address found in the look-up table is stored at $10 and $11 with the same byte order. The table begins at $B228 and is 32 bytes long. $B228 - $B247 $B220: xx xx xx xx xx xx xx xx 48 B2 56 B2 64 B2 72 B2 $B230: 80 B2 8E B2 9C B2 AA B2 B8 B2 C6 B2 D4 B2 E2 B2 $B240: F0 B2 FE B2 0C B3 1A B3 xx xx xx xx xx xx xx xx At each address listed in the table above is a series of 14 bytes used to XOR with the data at values $0530-$053D. $B248 - 0E 01 0A 10 04 0F 18 1B 16 07 1E 12 11 1D $B256 - 04 0F 18 1B 16 07 1E 12 0B 12 02 03 11 1D $B264 - 0A 01 0E 10 04 0C 18 1B 16 07 0A 12 11 1D $B272 - 0E 0D 0A 1C 04 0D 1A 1B 06 07 1E 12 15 1D $B280 - 0E 11 0A 10 04 03 18 1B 16 07 12 12 11 1D $B28E - 13 09 0A 12 04 03 18 1B 12 07 16 0A 10 15 $B29C - 02 0D 0A 12 04 0F 0A 1B 12 07 18 12 11 1D $B2AA - 00 1D 0A 18 04 0B 18 1A 14 07 1E 14 11 1D $B2B8 - 0E 0D 0E 12 0C 0F 1A 1B 16 07 1E 12 15 1D $B2C6 - 0E 01 0A 10 04 0F 18 1B 14 07 00 12 11 1D $B2D4 - 00 01 02 03 04 05 06 07 08 09 0A 0B 11 1D $B2E2 - 10 0D 0A 16 04 0F 18 1B 16 07 1E 12 1D 1D $B2F0 - 02 03 0A 12 04 0F 18 0B 16 07 06 16 01 1D $B2FE - 18 05 0A 1A 04 0D 18 1B 16 03 1A 16 17 15 $B30C - 03 05 0A 02 04 0D 08 0F 1E 0B 12 16 11 04 $B31A - 1E 05 0A 1A 07 0D 1A 1F 17 00 1A 16 16 15 The above is done by: for(i = 0x00; i < 0x0e; i++) { $10 = $(0xB228 + ($04F6 << 1)) $11 = $(0xB229 + ($04F6 << 1)) $053i = $053i ^ $($10 + ($11 << 2) + i) } Now, the value stored at $04F7 is added to all the values in the range $0530-$053D. for(i = 0x00; i < 0x0e; i++) { $053i = $053i + $04F7 } Finally, to get the actual bytes that correspond to the actual password, add 1 to each of the bytes in the range $0530-$053F. Store these values at $0540-$054F. for(i = 0x00; i <= 0x0f; i++) { $054i = $053i + 1; } Now, all we need to know is the correspondence between the bytes in $0540-$054F and the characters used in the password. Here is a table that shows the correspondence: A - 0x01 K - 0x0B U - 0x15 4 - 0x1F B - 0x02 L - 0x0C V - 0x16 5 - 0x20 C - 0x03 M - 0x0D W - 0x17 6 - 0x21 D - 0x04 N - 0x0E X - 0x18 7 - 0x22 E - 0x05 O - 0x0F Y - 0x19 8 - 0x23 F - 0x06 P - 0x10 Z - 0x1A 9 - 0x24 G - 0x07 Q - 0x11 0 - 0x1B H - 0x08 R - 0x12 1 - 0x1C I - 0x09 S - 0x13 2 - 0x1D J - 0x0A T - 0x14 3 - 0x1E The final password is the 16 characters given by the correspondence in the table above in the same order as the bytes in $0540 - $054F. 4. How the password is verified Now that we know how to generate a password, lets go in reverse and see how the game verifies user-inputted passwords. The password verification code begins at $AD18 in RAM. Using the character-hex value traslation table above, the inputted password is translated into its hexidecimal equivalent and stored in $0540-$054F. Next, subtract 1 from each value and store the result in $0530-$053F respectively. for(i = 0x00; i <= 0x0f; i++) { $054i = $053i - 1; } Next the intermediate "random values" are found from the bytes in $053E and $053F. $04F6 = $053F & 0x0F $04F7 = ($053F & 0x10) >> 4 | ($053E & 0x07) << 1 Proceding backwards (relative to password generation), updated the values in $0530-$053D by subtracting the value $04F7. for(i = 0x00; i < 0x0e; i++) { $053i = $053i + $04F7 } Next, use the look-up table starting at $B228 to find the XOR table ($B248-$B327) in the same way as the generation code. for(i = 0x00; i < 0x0e; i++) { $10 = $(0xB228 + ($04F6 << 1)) $11 = $(0xB229 + ($04F6 << 1)) $053i = $053i ^ $($10 + ($11 << 2) + i) } Now, we must perform the reverse logical operations to retireve the base values used for the password, which are stored in $0520-$0529. $053x = $053x ^ ($10),x (1st 14 bytes) $0520 = $0530 << 3 | ($0531 & 0x1C) >> 2 $0521 = $0531 << 6 | ($0532 & 0x1F) << 1 | ($0533 & 0x10) >> 4 $0522 = $0533 << 4 | ($0534 & 0x1E) >> 1 $0523 = ($0534 & 0x01) << 7 | ($0535 & 0x1F) << 2 | ($0536 & 0x18) >> 3 $0524 = ($0536 & 0x07) << 5 | ($0537 & 0x1F) $0525 = $0358 << 3 | ($0539 & 0x1c) >> 2 $0526 = $0539 << 6 | ($053A & 0x1F) << 1 | ($053B & 0x10) >> 4 $0527 = ($053B & 0x0F) << 4 | ($053C & 0x1E) >> 1 $0528 = ($053C & 0x01) << 7 | ($053D & 0x1F) << 2 | ($053E & 0x18) >> 3 $0529 = $053E << 5 | ($053F & 0x1F) For the password to be valid, $527 and $528 should be equal to the checksums as computed in the password generation code. The game stores these values temporarily at $0E and $0F. $0E = $0527 $0F = $0528 The game now computes the checksums as in the generation code. $0527 = ($0520 + $0521 + $0522 + $0523 + $0524 + $0525 + $0526) & 0xFF00 $0528 = ($0520 + $0521 + $0522 + $0523 + $0524 + $0525 + $0526) & 0x00FF If $0527 = $0E and $0528 = $0F, then all is good. If not, the password is invalid. A few more validations are necessary before the password is finally okayed. What are they? If you guessed the bounds on the base values at $0520-$0526, you are absolutely correct! The bounds are as follows: $0520 must be < 0x07 $0523 must be < 0x80 $0524 must be < 0x10 $0525 must be < 0x80 $0526 must be < 0x05 $0521 & 0x0F must be < 0x0A ($0521 & 0xF0) >> 4 must be < 0x0A $0522 & 0x0F must be = 0x09 ($0522 & 0xF0) >> 4 must be < 0x09 If all these checks are successful, the password is validated and the game loads the bytes $0520-$526 into the respective places in memory. 5. Closing Notes What is presented here is hopefully and complete and fully correct explanation of how Castlevania II's password system is generated and verified; however, it is most likely that I missed something or didn't explain something clearly. If I'm missing something, or if something in this guide is incorrect or badly explained, feel free to email me at kingshriek at yahoo dot com. Corrections, additions, and constructive criticism will be greatly appreciated. Also, any worthy additions added to a future version of this document will be duly credited to the information provider. Thanks for reading. eof