+-----------------------------------------------------------------------------+
| Reverse Engineering of Adventures of Lolo 3's Password System v. 0.98 |
| by kingshriek (Dean Fehlau) |
| email: kingshriek at yahoo dot com |
+-----------------------------------------------------------------------------+
The document is organized into sections and subsections in the following way.
1. Introduction
2. Notation
3. Password Generation
3.1. Memory Locations
3.2. Reading the Data
3.3. Compressing the Data
3.4. Calculating the Checksum
3.5. The Random Number Generator
3.6. Encrypting the Data
3.7. Unpacking the Data
3.8. Transcribing the Password
4. Password Verification
4.1. Checking the Data
4.2. Packing the Data
4.3. Decrypthing the Data
4.4. Checksum Comparison Test
4.5. Decompressing the Data
4.6. A Little Fixing Up
5. Example of Password Generation
5.1. Initial Data
5.2. Example - Compressing the Data
5.3. Example - Checksum and Random Value
5.4. Example - Encrypting the Data
5.5. Example - Unpacking the Data
5.6. Example - Transcribing the Password
6. Closing Notes
A. Appendix A - Update History
B. Appendix B - Password List and Miscellaneous Facts
C. Appendix C - C code for password generator/verifier
In the document are also tables and snippets of C-like code. They are labeled
Table x.y and Code x.y respectively, where x is the section number and y means
it's the yth table or code in the section.
This document contains a reverse engineering of the password system used in
Adventures of Lolo 3. It also works in the game's Japanese counterpart,
Adventures of Lolo 2 (J). The password system used in the game is far more
complicated than the previous Lolo titles, which used 4-letter passwords
that followed a very noticeable pattern. The passwords in Lolo 3 contain
16 characters (alphanumeric and some special ones), and have built into
them a checksum and a randomizer.
It should be noted that the game contains some special, built-in passwords
(see Appendix B) that are completely outside of the password system. They all
fail the game's and verification check and only serve to do interesting things
on the password screen such as playing different background music or displaying
different characters/monsters from the game.
If you are more interested in the passwords themselves than the process of
generating and verifying them, feel free to head down to Appendix B, which has
a list of passwords to all the levels of the game. The special, built-in
passwords are listed here as well.
For the readers that are interested in the password system, it is assumed that
you are familiar with binary and hexadecimal notation and are comfortable
converting both to and from decimal notation. It is also assumed that you are
familiar with basic logic operations (AND, OR, XOR, left shift, right shift).
Knowing some C and being familiar with its syntax will help you better
understand this document, but it shouldn't be necessary. It will also be
helpful if you have some familiarity with 6502 assembly and how the NES CPU
RAM is organized.
I have also included in this document source code for a simple console
program that generates and degenerates the passwords of Adventures of Lolo 3.
Before the password system can be discussed, the reader needs to be familiar
with the notation used in the document. I tried to use C syntax as much as
possible. The code snippets in the document are pretty much C, aside from
some shorthand addressing I put in (I hope it's easy to understand).
Data representation ('.' is a placeholder for a digit):
$.. or $.... memory address ($xx is a zero-page address)
0b........ value in binary
0x.... value in hexadecimal
Bit order (in a byte, from highest to lowest order):
highest lowest
+-------+-------+-------+-------+-------+-------+-------+-------+
| bit 7 | bit 6 | bit 5 | bit 4 | bit 3 | bit 2 | bit 1 | bit 0 |
+---------------------------------------------------------------+
Operators (in order of precedence):
! Logical NOT <---- done first
+ , - Addition, Subtraction
<< , >> Left Shift, Right Shift
& Bit-wise AND
^ Bit-wise XOR
| Bit-wise OR <---- done last
The characters for the password use some non-standard characters. This
document will use other characters in their place.
Non-standard characters:
+ (cross)
@ (heart)
$ (diamond)
& (triangle)
The symbols '$' and '&' here are not to be confused with the address
symbol '$' and the operator '&'. The meaning of these at each place
where they are used should be obvious to the reader.
In all code sections, the variable 'A' refers to the accumulator
register in the CPU.
This section will describe how the game generates a password when the player
presses the start button on the map screen.
The generation algorithm, which begins at $9AFD in PRG-ROM, uses 5 subroutines.
1. Read data in $0151-$0159, $014F, $52, compress, and store in $DF-$E6
2. Calculate checksum and store in $E7
3. Generate a random value based on the values at $2C and $2D and store in
$E8
4. Encrypt the data in $DF-$E8
5. Unpack the data in $DF-$E8 into $E9-$F8, where the password is stored
As for a less detailed and easier to remember description,
The addresses for the information stored in the password are as follows:
$52 - Character
Character data is stored in bits 0 and 4. Bit 0 determines whether Lolo
or Lala is selected. Bit 4 determines if Lolo and Lala are together or
if the selected character is alone. The other bits are set to 0b0 under
normal gameplay circumstances. The game ignores them anyway. In summary,
0x00 - Lolo, 0x01 - Lala if both Lolo and Lala are together
0x10 - Lolo, 0x11 - Lala if alone
$014F - Location
Location data is stored in bits 0-4. Bits 5-7 are set to 0b0 under
normal gameplay circumstances. The game ignores these bits. There are 19
valid locations - Levels 1 through 17 and the two Grandpa's Tree training
levels. Thus, in normal gameplay $014F has a value in the range 0x00-0x12.
Here's a list of valid location values for $014F:
0x00 - Grandpa's Tree 1
0x01 - Grandpa's Tree 2
0x02 - Level 1
0x03 - Level 2
0x04 - Level 3
.
.
.
0x12 - for Level 17
Each of these locations resides in of the game's 3 map areas - the
Overworld, the Underwater World, and the Underworld. The Overworld is a
2-screen map, whereas the Underwater World and Underworld are 1-screen
maps. Level 3 is split between the two screens of the Overworld. Here's a
list of areas and levels contained within:
0x13, while not a valid location value the game will generate,
corresponds to the right screen portion of Level 3 (0x04 corresponds to
the left screen portion), but is only tied to the coordinates there.
If you create a password with this value (as you have to, the game won't
generate one), the game will try to place you in the Underworld with
these coordinates. Since the Underworld is only a 1 screen map, you will
be placed to the right and off of the map! 0x14-0x1F will remove you from
the map completely!
$0151-$0159 - Level Completion Data
Each byte corresponds to a set of 2 adjacent (in number) levels. Bits 4-7
correspond to the earlier of the two levels and bits 0-3 correspond to
the later of the two levels. $159 only contains one level, Level 17,
which is placed in bits 4-7. The lower 4 bits are not used. In summary,
For floors, the current floor you are on at each level is stored in the
set of 4 bits that correspond to the level. Thus, someone at Level 1,
Floor 4 and Level 2, Floor 3, would have 0x43 as the value for $151.
Special rooms where you get/use items or fight bosses use the value 0x0.
If the level doesn't have a special room or boss (Levels 8,14,15,16),
then you won't be able to enter the level. Thus, 0x00 at $153 would
place you at the bosses of Levels 5 & 6. Level completion is denoted by
0xF. In the course of normal gameplay, completion status is not given
for Level 13 (as the boss defeats you instead). Therefore, right after
finishing Level 13, bits 4-7 of $157 are 0x0. Also, since Level 17 is
the final level, it is impossible in normal gameplay for the higher 4
bits of $159 to have the value 0xF. If these levels are set to 0xF, they
won't be destroyed (as there aren't graphics for this in the game) and
they will be impossible to enter. In summary,
0x0 - Special or boss room (except for Levels 8,14,15,16)
0x1 - Floor 1
0x2 - Floor 2
0x3 - Floor 3
.
.
.
0xA - Floor 10
0xF - Level completed (except for Levels 13 and 17)
$0150 contains the information for what floors are cleared in the Grandpa's
Tree training levels. It is done so in the same way as in $0151-$0159. The
password does not save this information, hence why it's not listed up above.
+-----------------------+
| 3.2. Reading the Data |
+-----------------------+
In order to read the data needed for the password, the game makes use of a
80 byte table at values at $9A29-$9A79, which is provided below (values
are in hex).
The bytes in the table are in sequences of four, i.e. (01 51 06 03),
(01 51 02 03), (01 52 07 04), etc. where each sequence corresponds
to an information entry that the password stores.
The first 2 bytes are the address of the memory from which information for
password generation is received (the information that's stored in the
password). These 2 bytes are ordered with the higher order byte first. Thus,
the first 2 bytes in the table give the address $0151. Recall that
$0151-$0159 are level addresses and that only bits 4-7 of $0159 are used (for
Level 17). Also, recall that bits 0-4 of $014F correspond to location data and
that bits 0 and 4 of $0052 correspond to character data.
The 3rd byte gives the number of the highest order bit (in the bit order)
used in the data stored at the address given by the first 2 bytes.
The 4th byte gives how many bits are used to store the information. So, for
level data, levels with 5 floors need 3 bits and levels with 10 floors need
4 bits. The location data needs 5 bits and each set of character data needs
1 bit.
+---------------------------+
| 3.3. Compressing the Data |
+---------------------------+
Right now, the information that's needed for the password is somewhat sparse,
meaning that not all the bits in each byte have useful information. For
example, character data only needs 2 bits, but it's currently being stored
with 2 sets of 4 bits (a byte). It would be nice to compress this data so
that only the useful bits are stored, and that's exactly what the game does.
The game does this by sequentially loading the required information into an
8-byte shift register, which is located at $DF-$E6. The data is loaded into
bit 7 of $E6 and shifted left until the shift register holds all of it. In
the process of compression, the game refers to the table starting at $9A29
(Table 3.1). Given by the table, address $0151 is loaded first, followed by
$0152-$0159, and then finally $015F and $52.
The game then stores the requested data, the byte given by each address in
the table, into the accumulator (an 8-bit register on the CPU, denoted by A
in the code examples). Here, the data only occupies the lower order bits and
needs to be shifted all the way to the left so that it is in position to be
loaded bit by bit into the shift register. The 3rd byte in each 4-byte
sequence in the table gives the position of the highest order bit of the data
to be loaded. Thus, the number of times the data needs to be shifted in the
accumulator is given by subtracting this bit position from 7 (since the
accumulator is an 8-bit register). Thus, the number of times needed to shift
the data is determined by the 3rd byte in each 4-byte sequence in the table
(hence, why data stored on the lower 4 bits of a byte have a value that is 4
higher than the data stored on the higher 4 bits).
The number of times to shift the data through the shift register is given by
the 4th byte in the 4-byte sequence, which stores how many bits the
information takes up.
Hence, this subroutines compresses the data by storing only useful
information in the shift register.
The above is summarized by the following code.
Code 3.1 - compression subroutine
$E6 = 0x00;
for(x=0x9A29; x<=0x9A79; x+=4) { // run through data in table
y1 = $x & 0xFF00; // upper byte of address
y2 = $(x+1) & 0x00FF; // lower byte of address
A = $(y1+y2); // addresses for password information
ns = $(x+2);
ns = 7 - ns ; // number of times to left shift the accumulator
nr = $(x+3); // number of times to left shift through $DF-$E6
A = (A << ns) & 0xFF; // shift data into loading position
for(i=0; i<nr; i++) {
carry[0xE7] = (A & 0x80) >> 7; // carry from A into $E6
A = (A << 1) & 0xFF;
for(y=0xE6; y>=0xE0; y--) { // shift data through $DF-$E6
carry[y] = ($y & 0x80) >> 7; // carry from $y into $(y-1)
$y = ($y << 1) & 0xFF;
$y += carry[y+1];
}
$DF = ($DF << 1) & 0xFF;
$DF += carry[$E0];
}
}
+-------------------------------+
| 3.4. Calculating the Checksum |
+-------------------------------+
Once the compression is finished, a checksum calculation subroutine
is entered. The lowest byte of the sum of the bytes $D9-$E6 is stored in
$E7. That is,
+----------------------------------+
| 3.5. The Random Number Generator |
+----------------------------------+
$E8 is the next value that needs to be computed. $E8 is given by a
pseudorandom number generator (RNG). The RNG is in the form of a three-tap
linear feedback shift register (LFSR).
If you are creating your own password, you can skip this step, as the
value it affects can be anything without affecting the validity of the
password. This is just how the game actually generates passwords and it's
only included for completeness.
The game uses $2D and $2C in RAM for the shift register, where $2D is of
higher order than $2C. Both addresses are initialized to an unknown value
and are updated 11 times when the player requests a password (pressing Start
on the map screen). After these 11 iterations, the value of $2C is stored in
$E8. $2C and $2D are only initialized at power-on, i.e. resetting the game
doesn't change their values. The taps are at bits 15, 1, and 0.
In binary, the RNG satisfies the reccurence relation:
It would be nice to know a few things about the RNG, such as if it
generates all the values between $0000 and $FFFF for $2C-2D. Also, since
the RNG is completely deterministic, it will have to repeat itself
eventually. How many iterations are needed for this to happen (the RNG's
period)?
Since there are an odd number of taps, if the NOT were removed, the RNG
would preserve either an even number or an odd number of set bits (equal
to 0b1) amongst $2C-$2D and the new bit that is added to the shift
register. What the NOT does is switch between an even number and an odd
number of set bits in these 17 bit locations after each iteration. We
will need this fact later in the determination of the period.
From the taps, the feedback polynomial is x^16 + x^2 + x + 1. On the
integer ring Z(mod 2), this factors into x + 1 and
x^15 + x^14 + x^13 + ... + x^4 + x^3 + x^2 + 1. Thus, the greatest common
divisor (GCD) of the feedback polynomial with another polynomial mod 2
will either be 1, x + 1, or x^15 + x^14 + x^13 + ... + x^4 + x^3 + x^2 + 1.
We will investigate the period by looking at each of these cases.
For the first case, x will be used, since GCD(x , x^16 + x^2 + x + 1) = 1.
Continuously squaring mod (x^16 + x^2 + x + 1) gives:
x x^256 = x^4 + x + 1
x^2 x^512 = x^8 + x^2 + 1
x^4 x^1024 = x^4 + x^2 + x
x^8 x^2048 = x^8 + x^4 + x^2
x^16 = x^2 + x + 1 x^4096 = x^8 + x^4 + x^2 + x + 1
x^32 = x^4 + x^2 + 1 x^8192 = x^8 + x^4 + x
x^64 = x^8 + x^4 + 1 x^16384 = x^8 + x + 1
x^128 = x^8 + x^2 + x x^32768 = x
So, after 32768 iterations, we are back at the starting point. Thus, if
the GCD of the starting polynomial and the feedback polynomial is 1, the
period is 32767. By plugging in 1 into all the polynomials, it is seen
that every polynomial in this period has an odd number of terms. So x is
a generator of these odd polynomials.
For a GCD of x + 1, we square in the same fashion and also get a period
of 32767. Here, all the polynomials in a period have an even number of
terms, and x + 1 is a generator.
For a GCD of x^15 + x^14 + x^13 + ... + x^4 + x^3 + x^2 + 1, we find
that squaring it doesn't change its value. Hence, the period is 1, and
seeding the RNG with the value corresponding to this polynomial will
produce a constant sequence. Only one polynomial mod (x^16 + x^2 + x + 1)
has this GCD, so this is the identity coresponding to an even number
of terms.
The only polynomial left mod (x^16 + x^2 + x + 1) is the identity for an
odd number of terms, which is obviously 1 itself.
Therefore, since the NOT switches between even and odd numbered terms
after each iteration, the RNG will have a period of 32767 x 2 = 65534,
unless it is seeded with two specific values that generate constant
sequences. These two values are 0x5555 and 0xAAAA, each consisting of
alternating digits in their binary representations.
Taking this into account, in a single period, $2C has a nearly uniform
distribution.
Value Probability
-----------------------------------------
0x55 255 / 65534
0xAA 255 / 65534
all other values 256 / 65534
65534 and 11 are relatively prime. Thus, $E8 has the same distribution.
The RNG algorithm can be expressed by the following code:
Code 3.3 - random number generator
r = $2D << 8 | $2C;
for(j=0; j<11; j++) {
r = (r << 1 | !((r >> 15 ^ r >> 1 ^ r) & 0x0001)) & 0xFFFF;
}
$2D = r & 0xFF00;
$2C = r & 0x00FF;
$E8 = $2C;
Below is a short table of values ($E8) that the RNG generates when
successive passwords are brought up. The table is seeded with
$2C = 0xFF and $2D = 0xFF.
+--------------------------+
| 3.6. Encrypting the Data |
+--------------------------+
Next, $DF-$E7 are encrypted by a combination of summing adjacent values,
right rotating, and XOR. The encryption is initialized by the random
value $E8 generated in the previous step. The encryption algorithm can
be more clearly seen in the figure below.
Figure 3.2 - Encryption
---+-----+-----+-----+-----+---------------+
| $E4 | $E5 | $E6 | $E7 | $E8 |*************>
---+-----+-----+-----+-----+---------------+
| | | | | | | |
v v v v v v v v
+---------------+
| $E8 |**********************
+---------------+ *
| | | | | | | | *
v v v v v v v v *
+-------------------+ *
| 7 6 5 4 3 2 1 0 | * *
| 8| +-----* *
(+) XOR | 7|-----|-----* *
| 6|-----|-----* *
*** Bus | 5|-----|-----* v
| Adder 4|-----|-----******>(+)
| 3|-----|-----* *
| 2|-----|-----* *
| 1|-----|-----* *
| 0|-----+ * *
| 7 6 5 4 3 2 1 0 | *
+-------------------+ *
^ ^ ^ ^ ^ ^ ^ ^ *
| | | | | | | | *
---+-----+-----+-----+-----+---------------+ *
| $E3 | $E4 | $E5 | $E6 | $E7 |************> *
---+-----+-----+-----+-----+---------------+ *
^ ^ ^ ^ ^ ^ ^ ^ *
| | | | | | | | *
***************** *
* *
*******************************
In the diagram above, $DF-$E8 is represented by two parallel, offset shift
registers that shift a byte at a time, where each address is mapped with
the corresponding address on the other shift register. You can picture this
by rolling the diagram into a cylinder, matching the $E7s, $E6s, $E5s, etc.
In this way, the encryption algorithm could be thought of as a helical
shift register passing through an adder inside that feeds back to the
preceding byte of the addition (a first order feedback).
+-------------------------+
| 3.7. Unpacking the Data |
+-------------------------+
Next, the data in $DF-$E8 is unpacked onto $E9-$F8. Observe that $DF-$E8
contain 80 bits of information. The password is 16 characters long, so
each byte in $E9-$F8 needs to contain 5 bits from $DF-$E8. Thus, 5 bit
chunks of data are sequentially taken off of $DF-$E8 and loaded into each
byte of $E9-$F8. The data is loaded by setting up $DF-$E8 as a shift
register so that the lowest order bits of $DF-$E8 are loaded onto $E9,
the next 5 onto $EA, the next 5 onto $EB, and so on.
This is done by the following code.
Code 3.5 - unpacking subroutine
for(z=0xE9; z<=0xF8; x++) { // run through $E9-$F8
A = 0x00; // clear accumulator
for(i=0; i<5; i++) { // load 5 bits onto a byte in $DF-$E8
carry0 = $E8 & 0x01; // carry from $E8 into A
carry[0xDF] = ($DF & 0x01) << 7; // carry from $DF into $E0
$DF >>= 1;
for(y=0xE0; y<=0xE7; y++) {
carry[y] = ($y & 0x01) << 7; // carry from $y into $(y+1)
$y >>= 1;
$y += carry[y-1];
}
A = (A << 1) & 0xFF;
A += carry0;
}
$z = A;
}
+-------------------------------+
| 3.8. Transcibing the Password |
+-------------------------------+
Now, all we need to know is the correspondence between the bytes in
$E9-$F8 and the characters used in the password. This document uses
@, $, & for heart, diamond, and triangle respectively for readability
purposes.
Here is a table that shows the correspondence:
Table 3.3 - Password Transcription Table
+------------------------------------------------------+
| Password Transcription Table |
+----------+----------+----------+---------------------+
| 0x00 - 2 | 0x08 - B | 0x10 - L | 0x18 - V |
| 0x01 - 3 | 0x09 - C | 0x11 - M | 0x19 - W |
| 0x02 - 4 | 0x0A - D | 0x12 - N | 0x1A - Y |
| 0x03 - 5 | 0x0B - F | 0x13 - P | 0x1B - Z |
| 0x04 - 6 | 0x0C - G | 0x14 - Q | 0x1C - + (cross) |
| 0x05 - 7 | 0x0D - H | 0x15 - R | 0x1D - @ (heart) |
| 0x06 - 8 | 0x0E - J | 0x16 - S | 0x1E - $ (diamond) |
| 0x07 - 9 | 0x0F - K | 0x17 - T | 0x1F - & (triangle) |
+----------+----------+----------+---------------------+
The table above does not encompass all the characters on the password entry
screen. Except for a few very special passwords (see Appendix B), characters
not used in any password are:
0 , 1 , # , (smiley) , ? , ! , * , X US version
0 , 1 , A , E , I , O , U , X Japan version
which all have the value 0xFF.
The final password is the 16 characters given by the correspondence in the
table above in the same order as the bytes in $E9-$F8.
This section will describe how the game verfies a password a user
has inputted and how it extracts the data stored in it.
The verification algorithm begins at $9BD3 in PRG-ROM. The password is
verified and read with 6 subroutines.
1. Check password ($E9-$F8) for forbidden characters (0xFF)
2. Read data in $E9-$F8, and pack into $DF-$E8
3. Decrypt the data in $DF-$E8
4. Calculate the checksum and proceed to step 4 only if it equals $E7
5. Decompress the data in $DF-$E6 and write to $0151-$0159 ,$014F, $52
6. Fix up the data in $0151-$0159, $014F, $52 (see Section 4.5 for details)
As for a less detailed, easier to remember description,
The section begins assuming the bits for the password are loaded into $E9-$F8.
+------------------------+
| 4.1. Checking the Data |
+------------------------+
First, the password, stored in $E9-$F8, is checked for any forbidden characters
(see Section 3.8). Recall that a forbidden character is represented by 0xFF. If
any are found, the game returns to the password screen for the player to input
another one. If no forbidden characters are encoutered, the game proceeds to
the next subroutine.
Code 4.1 - checking subroutine
for(z=0xE9; z<=0xF8; z++) { // run through $E9-$F8
if($z < $80) {
(proceed checking characters)
}
else {
(break out of loop and return to password screen)
}
}
+-----------------------+
| 4.2. Packing the Data |
+-----------------------+
Next, the bits in $E9-$F8 are read and packed into $DF-$E8 by reversing the
process outlined in Section 3.7. Hence, starting with $F8 and going backwards
through $E9, the lowest 5 bits on each byte get loaded sequentially onto the
lowest order bit of the shift register $DF-$E8.
Code 4.2 - packing subroutine
for(z=0xF8; z>=0xE9; z--) { // run through $F8-$E9
A = $z;
for(i=0; i<5; i++) { // load lowest 5 bits onto $DF-$E8
carry0 = $A & 0x01; // carry from A into $E8
A >>= 1;
carry[0xE8] = ($E8 & 0x80) >> 7; // carry from $E8 into $E7
$E8 = ($E8 << 1) & 0xFF
for(y=0xE7; y>=0xDF; y--) {
carry[y] = ($y & 0x80) >> 7; // carry from $y into $(y-1)
$y = ($y << 1) & 0xFF;
$y += carry[y+1];
}
}
}
+--------------------------+
| 4.3. Decrypting the Data |
+--------------------------+
Next, $DF-$E8 are decrypted by reversing the process outlined in Section 3.6,
that is, replacing the adder with a subtracter, replacing the right rotate
with a left rotate, and carrying out the steps outlined in the encryption
algorithm backwards.
+------------------------------+
| 4.4. Checksum Compaison Test |
+------------------------------+
The checksum is then calculated and stored in the accumulator. The game
compares this value to what is stored at $E7. If the values match,the password
as validated and proceeds to next step. If they don't match, the password is
invalid, and the game will ask prompt the player to enter a new one.
Code 4.4 - compare subroutine
A = ($DF + $E0 + $E1 + $E2 + $E3 + $E4 + $E5 + $E6) & 0xFF;
if (A == $E7) { // compare to checksum
(proceed to decompression subroutine)
}
else {
(return to password screen)
}
+-----------------------------+
| 4.5. Decompressing the Data |
+-----------------------------+
After a successful checksum, the data the password represents is decompressed
and read from $DF-$E6. It is stored in the addresses given by the first two
bytes of the $9A29 table (Table 3.1), that is $5A, $014D, and $0159-$0151.
Before it stores the data in these addresses, the values in these addresses
are first cleared, as well as the value in the address $0150. This value
describes what floors have been cleared in the Grandpa's Tree training levels
(which the password doesn't store - see Section 3.1 - Memory Locations).
It does this by reversing the process outlined in Section 3.3.
Code 4.5 - decompression subroutine
$014F = 0; // clear out data in $014F
$52 = 0; // clear out data in $52
for(w=0x159; w<=0x150; w--) { // clear out data in $0150-$0159
$w = 0;
}
for(x=0x9A75; x>=0x9A29; y-=4) { // run through data in table
A = 0x00; // clear accumulator
ns = $(x+2);
ns = 7 - ns; // number of times to right shift the accumulator
nr = $(x+3); // number of times to right shift the data $DF-$E6
for(i=0; i<nr; i++) {
carry[0xDF] = ($DF & 0x01) << 7; // carry from $DF into $E0
0xDF >>= 1;
for(y=0xE0; y<=0xE6; y++) {
carry[y] = ($y & 0x01) << 7; // carry from $y into $(y+1)
$y >>= 1;
$y += carry[y-1];
}
A >>= 1;
A += $E6;
}
A >>= ns;
y1 = $x & 0xFF00; // upper byte of address
y2 = $(x+1) & 0x00FF; // lower byte of address
A = A | $(y1+y2);
$(y1+y2) = A; // load data from A into the desired address
}
+-------------------------+
| 4.6. A Little Fixing Up |
+-------------------------+
You may be thinking the verification/extraction process is now done, but it's
not quite yet. Remember how the information stored for the levels with 5
floors is done so with 3 bits? This is troublesome because the value 0xF is
used to denote that the level has been beaten, and it requires 4 bits. So,
levels with 5 floors at this point have the value 0x7. Hence, some extra code
is needed to fix these to the desired 0xF. This way this is done is shown
below.
Code 4.6 - fix 0x7 to 0xF subroutine
for(x=0x9A29; x<=0x9A69; y+=4) {
y1 = $x & 0xFF00; // upper byte of address
y2 = $(x+1) & 0x00FF; // lower byte of address
if($(x+2) == 6) { // if level has 5 floors and is stored on higher 4
bits
if(($(y1+y2) & 0xF0) == 0x70) { // change 0x7 to 0xF
$(y1+y2) |= 0x80;
}
}
if($(x+2) == 2) { // if level has 5 floors and is stored on lower 4
bits
if(($(y1+y2) & 0x0F) = 0x07) { // change 0x7 to 0xF
$(y1+y2) |= 0x08;
}
}
}
Finally, the required data has been extracted from the password. The game then
uses this data to place you in the right location, to give you the right
character, and to remember which floors you have beaten.
+-----------------------------------------------------------------------------+
| 5. Example of password generation |
+-----------------------------------------------------------------------------+
I thought it would be a good idea to go step by step through the password
generation algorthim with an example. What will be produced is a working
password from a set of initial data.
+-------------------+
| 5.1. Initial Data |
+-------------------+
The password we will generate will have the following attributes.
$0151 = 0xFF Levels 1-2 completed
$0152 = 0xF1 Level 3 completed, at floor 1 on Level 4
$0153 = 0x23 At floor 2 on Level 5, floor 3 on Level 6
$0154 = 0x01 At boss on Level 7, Level 8 not started
$0155-$158 = 0x11 Levels 9-16 not started
$159 = 0x10 Level 17 not started
$014F = 0x01 Location is Grandpa's Tree 2
$52 = 0x01 Character is Lala with Lolo
The data above is in the same order as the table at $9A29 (Table 3.1) in memory
that the game uses to generate passwords, so no rearranging needs to be done.
First, we'll express these values in binary. Second, we'll mark off the bits to
be used in the algorithm by referring to the $9A29 table. These bits are marked
below by asterisks.
+-------------------------------------+
| 5.2. Example - Compressing the Data |
+-------------------------------------+
Next, compress these bits (Code 3.1) onto $DF-$E6 by writing only the
asterisked bits in the same order. Note that there are 61 asterisked bits,
so append 0b000 to the left of the bit sequence (in $DF).
Now we must find the random value $E8. For the sake of convenience,
we will just make up something instead of tediously stepping through
iterations in the RNG. Let's use 0x5C.
+------------------------------------+
| 5.4. Exmaple - Encrypting the Data |
+------------------------------------+
Next, we go into the encryption subroutine (Code 3.4) Start with $E7,
and see its value is 0x9E. Then, we add it to $E8 and take lowest order
byte to get 0xFA. The lowest order bit in 0xFA is 0b0, so we right shift
$E7 without a carry. (if it were 0b1, there would be a carry). Doing the
shifting gives 0x7D (if there was a carry, add 0x80 afterwards). Next, we
XOR this with the next higher address, $E8. XORing 0x7D with $E8 results in
0x21. $E7 gets updated with this value.
For the rest of the iterations, we just decreases the addresses in
question. So, for the next iteration, replace $E7 up above with $E6 and
replace $E8 with $E7 (the new $E7). Continuing until $DF, we get:
+-----------------------------------+
| 5.5. Example - Unpacking the Data |
+-----------------------------------+
The unpacking subrouting (Code 3.5) is next. Since the bits in $DF-$E8 are
right shifted into each of the $E9-$F8, we will first express $DF-$E8 in bits
and reverse the sequence so we can read off $E9-$F8 in a left-to-right
manner.
What is presented here is hopefully a complete and fully correct explanation
of how Adventures of Lolo 3's passwords are generated and verified; however, it
may be the case that I missed something or didn't explain something clearly. If
I'm missing something, or if something in this document 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.
+-----------------------------------------------------------------------------+
| A. Appendix A - Update History |
+-----------------------------------------------------------------------------+
v.0.98 (9/08/2005)
- added information about the game's special, built-in passwords
- corrected a counting error in the password trivia section of Appendix B
- corrected various minor errors in the document
v.0.97 (8/31/2005)
- expanded Section 3.5 - The Random Number Generator with a more thorough
discussion of its period
- expanded Section 3.6 - Encrypting the Data, adding a diagram and giving
a better explanation of the algorithm
- added Appendix B - Password List and Miscellaneous Facts
- fixed a bug in the C code's authentication routine
v.0.96 (8/28/2005)
- expanded Section 3.1 - Memory Locations
- expanded Section 3.5 - The Random Number Generator and greatly
simplified the algorithm
- cleaned up C code a bit
- corrected various minor errors in the document
v.0.95 (8/27/2005)
- added a random, authentic password generator in the C code
- fixed a bug in the password generation routine in the C code
- corrected various minor errors in the document
initial (8/26/2005)
- initial release
+-----------------------------------------------------------------------------+
| B. Appendix B - Password List and Miscellaneous Facts |
+-----------------------------------------------------------------------------+
Below is a list of passwords to every floor in the game, where for each one,
every floor before it has been completed. All passwords use 0x00 in $E8, thus
they all begin with the character '2'. The Level column is in the format of
level-floor, with floor B being the boss fight (if there is one). For
readability purposes, this document uses '+', '@', '$', and '&' for the
non-standard characters. For your convenience, this convention will be posted
multiple times on the right side of the table.
Lolo 3 contains some hidden, special passwords that have different effects on
the game's password screen. All of these passwords fail the game's verification
check, so you will hear a buzz (signifying a password failure) after the 16th
character is entered. To trigger their effects, you need to manually select
'END'.
All the sound test passwords begin with a two-digit number, followed by a
double zero, '00'. Each two-digit number (within a range) corresponds to a
different background music or sound effect.
Note: In place of the vowels A, E, I, O, and U, the US version of the game uses
the characters # , (smiley) , ? , ! , * respectively. The Japanese version
retains the vowels.
+---------------------------------------------------------+
| Special Passwords |
+---------------------------------+-----------------------+
| Effect | Password |
+---------------------------------+-----------------------+
| Background Music Test | %%00 LOLO 3BGM TEST | US version
| %% is a number between 00 and 23| %%00 LOLO 2BGM TEST | JP version
+---------------------------------+-----------------------+
| Sound Effect Test | %%00 LOLO 3FGM TEST | US version
| %% is a number between 00 and 48| %%00 LOLO 2FGM TEST | JP version
+---------------------------------------------------------+
| Character Display | |
| Lolo | LOLO LOOK PLEA SE@@ |
| Lala | LALA LOOK PLEA SE@@ |
| Snakey | @SNA KEY+ MONS TER@ |
| Leaper | @LEA PER+ MONS TER@ | + (cross)
| Skull | @SKA LWG+ MONS TER@ | @ (heart)
| Rocky | @ROC KY++ MONS TER@ | $ (diamond)
| Medusa | @MED USA+ MONS TER@ | & (triangle)
| Gol | @GOL +GOL MONS TER@ |
| Alma | @ALM ARK+ MONS TER@ |
| Don Medusa | DONM EDUS AMON STER |
| Moby | @CAP OXX+ MONS TER@ |
+---------------------------------+-----------------------+
Also, here are some miscellaneous facts about the password system:
The total number of passwords that can be entered from the password is
screen is 40^16 = 42949672960000000000000000. Out of these,
32^16 = 1208925819614629174706176 entirely consist of valid characters
(see Section 3.8 for details).
The total number of valid passwords, i.e. ones that do not have a
failed checksum (see Section 4.4), is 2^72 = 4722366482869645213696.
Thus, if you are entering in only valid characters at random, you will
have a 1/256 chance of inputting a correct password.
The total number of authentic passwords, i.e. ones that you can actually
receive from the game itself is 7512576. Thus, out of the valid passwords,
14673 / 9223372036854775808 (about 1.59 x 10^-13 percent) of them are ones
that you can actually get through the game. If you are entering passwords
(comprised of only valid characters again) at random, then you will have a
14673 / 2361183241434822606848 (about 6.21 x 10^-16 percent) chance of
entering one you can get from the game.
Below is the distribution given by the areas and locations of the game if
authentic passwords are generated in a uniform, random manner.
Area Probability
------------------------------------
Overworld (left) 88 / 4891
Overworld (right) 7805 / 14673
Underwater World 6530 / 14673
Underworld 74 / 14673
+-----------------------------------------------------------------------------+
| C. Appendix C - C code for password generator/verifier/authenticator |
+-----------------------------------------------------------------------------+
Here's some C code that will compile into a console program that generates,
verifies, and authenticates Lolo 3 passwords. The passwords can either be
generated from values the user enters or generated randomly. The passwords that
are randomly generated can either be completely random (valid, but might
produce some weird effects in the game when entered) or they can be both
random and authentic (can actually be generated by the game itself). The code
also contains an authentication subroutine which determines if a password is
authentic.
int randomval,indexval;
int data[11];
int E[10];
int F[16];
int rnd(int,int);
int rndp(int,int,int);
int test(int*,int*,int*);
int initialize(int*,int*);
int generate();
int degenerate();
int generate_authentic();
int authenticate();
/* Intialize data */
initialize(data,F);
srand((unsigned)time(NULL));
printf("\n");
printf("Generate or degenerate a password\n\n");
printf(" 0. Generate 1. Degenerate\n\n");
printf("Selection? ");
scanf("%d",&gord);
switch(gord) {
case 0:
printf("\n");
printf("Select the type of password generation:\n\n");
printf(" 0. Manual - Data needed is given by the user\n");
printf(" 1. Random - Generates a random but not necessarily ");
printf("authentic password\n");
printf(" 2. Authentic Random - Generates a random, authentic ");
printf("password\n\n");
printf("Selection? ");
scanf("%d",&sel);
switch(sel) {
case 0 :
/* Get data from user */
printf("\n");
printf("Enter which floor you are on for each level.\n\n");
printf("1-10 are floor numbers, 0 means a special or boss room,\n");
printf("15 means the level is completed.\n");
printf("If 0 is picked for a level that has no special room or\n");
printf("boss, entry to the level will be prohibited.\n\n");
for(i=0; i<9; i+=1) {
level = 2*i+1;
if(level == 3 || level == 13 || level == 17) {
floors = 10;
}
else {
floors = 5;
}
printf("Level %d (%d floors): ",level,floors);
scanf("%d",&floor);
if(i != 8) {
level = 2*i+2;
floors = 5;
printf("Level %d (%d floors): ",level,floors);
scanf("%d", &data[i]);
}
data[i] |= (floor << 4);
}
/* Code 3.1 - compression subroutine */
int compress() {
int A,ns,nr,i,j,k;
int carryE[10];
E[7] = 0x00;
for(i=0; i<60; i+=3) { /* run through data in table */
A = data[T[i]];
ns = T[i+1];
ns = 7 - ns; /* number of times to left shift the accumulator */
nr = T[i+2]; /* number of times to left shift through $DF-$E6 */
A = (A << ns) & 0xFF; /* shift data into loading position */
for(j=0; j<nr; j++) {
carryE[8] = (A & 0x80) >> 7; /* carry from A into $E6 */
A = (A << 1) & 0xFF;
for(k=7; k>=1; k--) { /* shift data through $DF-$E6 */
carryE[k] = (E[k] & 0x80) >> 7; /* carry from $y into $(y-1) */
E[k] = (E[k] << 1) & 0xFF;
E[k] += carryE[k+1];
}
E[0] = (E[0] << 1) & 0xFF;
E[0] += carryE[1];
}
}
return 0;
}
/* Code 3.2 - checksum subroutine */
int checksum() {
/* Code 4.5 - decompression subroutine */
int decompress() {
int i,j,k,A,nr,ns;
int carryE[10];
for(i=0; i<11; i++) { /* run through data in table */
data[i] = 0; /* clear out data */
}
for(i=57; i>=0; i-=3) { /* run through data in table */
A = 0x00; /* clear accumulator */
ns = T[i+1];
ns = 7 - ns; /* number of times to right shift the accumulator */
nr = T[i+2]; /* number of times to right shift the data $DF-$E6 */
for(j=0; j<nr; j++) {
carryE[0] = (E[0] & 0x01) << 7; /* carry from $DF into $E0 */
E[0] >>= 1;
for(k=1; k<8; k++) {
carryE[k] = (E[k] & 0x01) << 7; /* carry from $y into $(y+1) */
E[k] >>= 1;
E[k] += carryE[k-1];
}
A >>= 1;
A += carryE[7];
}
A >>= ns;
A = (A | data[T[i]]);
data[T[i]] = A; /* load data */
}
return 0;
}
/* Code 4.6 - fix 0x7 to 0xF subroutine */
int fix() {
int i;
for(i=0; i<=51; i+=3) {
if(T[i+1] == 6) { /* if level has 5 floors and is stored on higher 4
bits */
if((data[T[i]] & 0xF0) == 0x70) {
data[T[i]] |= 0x80;
}
}
if(T[i+1] == 2) { /* if level has 5 floors and is stored on lower 4
bits */
if((data[T[i]] & 0x0F) == 0x07) {
data[T[i]] |= 0x08;
}
}
}
