Before 1992, before I ever touched a computer, I played a lot of games on the NES.
And in NES games, one of the most fascinating things to me
was the password generators.
I am Bisqwit, and in this series we explore how old games generated their passwords.
Today we study the passwords of Bubble Bobble.
Bubble Bobble is one of the 29 games
that will be re-released in November this year
on the Nintendo Classic Mini.
to begin off, we generate a blank password by feeding the cute little dragon to the…
whatever those are.
And we get the password for level 1: BBAAB.
Now, on cursory glance it might look like these passwords are
hardcoded into the game, like in Gremlins 2,
but learning two things will change your mind.
First is that you can modify the password,
and nearly everything you try will produce a new valid password.
Secondly, if you look at walkthroughs for this game, you learn that there are
over a hundred levels in this game.
It just is not feasible for game developers to waste expensive ROM estate
for huge password tables.
And foremost, it would hurt the pride of the developers to use a table of passwords.
So it stands to reason that there is an actual algorithm behind here.
Now, in my youth, I was never able to discover
the logic behind the passwords.
But now, that I am in the future,
I can take a look at the game ROM and learn what the game actually does.
Using the ROMHacking.net RAM map for this game,
I learned that game stores password letters in RAM addresses $0502 through $0506.
I disassembled the game ROM, and searched for code that
deals with these RAM addresses in particular.
After a couple of hours,
I had a pretty good understanding of what the code does.
Here it is.
You can pause the video here if you want.
The first part of the code deals with generating the password,
and the second part deals with decoding and verifying one.
Let's walk through the whole thing.
First things first.
The passwords are actually five-digit numbers.
The letters that you enter and read on the password screens, are actually numbers.
And not only that, it is a substitution cipher
where each letter corresponds to some particular digit.
Here are examples of some known passwords, and how they actually are in numeric form.
Now it is very important to keep in mind that the password
is comprised of five digits.
That is, five numbers that are treated individually.
This is an important distinction to keep in mind, because from now on,
we are going to operate on the individual digits,
or letters, of the password, in binary form.
The next layer of protection is exclusive–or convolution.
It is a reversible operation that mixes up bits in the letters.
We will get back to this later.
Here is an example of how a password is decomposed
into the five digits by undoing both the substitution cipher
and the XOR convolution.
The next step is the most interesting part.
This is the final part of the password decoding process,
and the first part of the password encoding process.
Here, each letter is decomposed into bit fields.
The level number is split into three bit fields,
which are stored in the first three letters.
The flag that indicates whether this is a Super Bubble Bobble game
is stored in the next letter.
The same letter also stores Something.
Something is a two-bit variable of unknown purpose.
I do not know what the game uses it for.
Finally, there is a checksum that is split into two fields.
The low-order three bits are stored in the final letter,
and the remaining two bits are stored in the center letter.
The checksum is simply calculated by adding all the letters together,
exclusing the checksum itself.
Let's try in practice how this works.
Let's say, we want a level 77 password for regular Bobble Bobble,
where Something is three.
First we convert these numbers into binary,
and then we start inserting the bits from those numbers into the letters.
The bits from LevelNumber go into letters 0, 1 and 2.
The SuperFlag goes into letter 3, and so does Something.
When we add these numbers together, we get 14.
The checksum is also converted into binary, and inserted into letters 2 and 4.
Now that we know all the digits of the password,
next we have to do the XOR convolution, and finally the substitution cipher.
The password is JIAIJ.
Here is another example.
Level 1 of Super Bubble Bobble, where Something is three.
The password becomes BBFJJ.
Now.
Let's take a step backwards.
Remember when I said that each letter in the password is a 4-bit number?
So far the game has been dealing with three-bit numbers,
but they are actually four-bit.
We have been playing nice so far.
Going by the rules of the game.
Now it is time to break out.
The actual formula, used by the password decoder, looks like this.
In the bitmask format we can make a few observations.
Let's skip the level number for now.
The SuperFlag is now a two-bit number.
Zero SuperFlag means regular Bobble Bobble.
SuperFlags 1—3 mean Super Bubble Bobble.
In other words, the game only cares of whether it is zero or nonzero.
Too bad.
Now, about Something.
I have found exactly one use for Something.
If you go to level 100 and Something is zero, the final boss battle will trigger.
If Something is nonzero, the boss battle will not trigger.
In any case, if you go to level 113 or higher,
the final boss battle always trigger.
I do not know for sure, but I theorize that Something is an indicator
for which ending you are going to get.
I have not played this game much, and whatever little I know of the actual gameplay comes
from playing it as a child and from some walkthroughs I read just now.
Now, about the level numbers.
Even though range of valid level numbers in this game is 1 through 113,
it is actually possible to craft passwords where the level number is in range 0 to 159.
But this cannot be used to break the game.
The game automatically turns level 0 into level 1,
and starts the final boss battle on any level number higher than 112.
Finally, some of these bits overlap.
This means in some cases,
multiple different passwords may produce the identical outcome.
Again, I created a little program.
This PHP program will walk through all the 100000 different passwords,
trying to decode them like the game would,
and if the decoding succeeds, lists those passwords.
In other words, it lists all valid passwords recognized by the game.
The number of those passwords is 2868, way too much to list in this video,
but here is a sample of the program's output.
I am (inaudible).
In the next episode we will have another game to study.
It may contain trace amounts of dinosaurs.
Then again, it may not.
Không có nhận xét nào:
Đăng nhận xét