Topic: CVIII Password Revisited

[TheouAegis]

CV3's password algorithm is at the end of this post.

A long while back, I shared a password generator for Castlevania III and a little insight about how it was created. I wasn't happy with the original code, so I thought I'd go back to it and try to understand what was actually going on and revise it. If you had seen the original code, you'd be flabbergasted by how long and ungainly it was. Parts of this post were covered in the original topic, so I apologize for repeating myself.

Boring informative stuff

(click to show/hide)

There were 18 stages in Castlevania III, thus there were a minimum of 18 passwords. Each stage could be played on either Normal or Hard, increasing the number of passwords to 36. Each level could be played either as Trevor solo or with one of three allies; there were 4 allied states per level, which were denoted in the passwords; the number of passwords increased from 36 to 144 passwords. Things get only more complicated (and convoluted) from there.

To make it harder for people to just use passwords from friends or strategy guides (such as Nintendo Power), the player's name determined what password was given as well. There are 173,059,286,400 permutations of names in the name entry screen in CVIII. Each character (A-Z, !, ?, _) has a value which is added to each slot, which are themselves valued like so:

7 3 1 6 2 4 5 0

However, only the lowest three bits were accounted for, limiting the value of any name to no more than 7, increasing the number of passwords to 1152.

To add insult to injury and to fuck with young gamers' heads, Konami randomized the password generation, thus further increasing the number of passwords to a whopping 2304. (18 * 2 * 4 * 8 * 2) Good luck writing them all out!

So how was the password actually generated?

The password generator takes into account the player's name, the stage, Trevor's ally, and the difficulty.

As mentioned earlier, it starts with the player's name. By default, a name of _ _ _ _ _ _ _ _ (all blank) has a value of 28. Each character had a value that was added to the value of each slot. Then the lowest 3 bits were taken from the sum (NAME & 7).

The name, ally and difficulty are arranged in a single byte:

AAAXYBBC         AAA  Name         X  Parity         Y  Random         BB  Ally         C  Difficulty

Bit X was reserved for the parity of the stage, not the stage itself. The reason for this is the stage took up 5 bits, whereas the password was restricted to 8 bits and only 2 were available for use. The benefit of this was it made the password harder to crack. Interestingly, the parity is essentially saved twice, as can be seen by the decryption code.

As for bit Y, that was for the randomizer (0 or 1).

The upper and lower nybbles (every 4 bits) are added together. After that, the password generator did some stuff for reasons I cannot figure out yet, although I have been trying to wrack my brain over it. However, what is important is that at this point the stage was worked into the password formula.

The two generated variables were then analyzed on a bit-by-bit basis, with the bits of the first variable given higher weight (i.e., they were shifted left 1 place). This was the actual heart of the password - each icon was a representation of these values.

The stage was handled inappropriately, although Konami may have decided it would be better to use the decryption hash in reverse for the encryption. Basically they took the stage value, halved it, hashed it twice through a transformation and then compared the result. Since the result was based on just one variable, it was a needless process.

The results from the previous step were used to further hash the password. The outcome determined where each icon would be placed, calculated via a look-up table. What this means for you is that's one more aspect of the program that can be customized.


When the player entered a password, each modified cell in the password screen had a value of 4n, where n was the index in the cell array. Each icon had a value from 0 (blank) to 3 (heart). The value of the icon was added to the value of the cell. The program basically then just worked backwards, running all the values through the hasher and comparing the results, extracting each of the bits, then assigning them to their appropriate variables. The whole process - even after reworking my own interpretation of the code - was twice as long as the encryption phase. mostly because it handled decryption by comparing every single hashed value.

Also, due to how the stage is encrypted, cells 0, 6 and 13 are the only three cells where the stage is stored.

Anyhoo, here's the encryption/decryption code in Game Maker format. Even if you don't know Game Maker's language, you can figure out the code for use in C++ or Unity or whatever pretty easily.


PASS_ENCRYPT

(click to show/hide)

var A,X,Y,R;

A[4] = 0;


//Randomize the password
R = choose(0,1);


//Encrypt player's NAME
A[0] = name_set(1);


/*
    This combines the difficulty, ally, and name code, as well
    as whether the stage is odd-valued and a random value
        Difficulty: 1 bit
        Ally: 2 bits
        Randomizer: 1 bit
        Odd Stage: 1 bit
        Name Code: 3 bits
*/
X = ( ( (A[0]<<1 | (STAGE & 1) )<<1 | R )<<2 | ALLY )<<1 | QUEST;


/*
    "If you can figure out how this next part works,
    please enlighten me." -Theou Aegis
*/
A[4] = $50 << R;
A[2] = X & $F0;    //name & parity
A[3] = X << 4 & $F0;    //randomizer, ally, and difficulty
A[1] = A[3] + A[2] & $FF;
A[0] = A[4] ^ A[2];
Y = ( ((A[4] ^ A[3]) + A[0])>> 4 | A[1] ) + STAGE;


/*
    The password itself is simply a comparison of each
    bit of the two variables calculated above. A value
    of 1 means only A[1] set that bit, a value of 2
    means only A[0] set that bit, and a value of 3 means
    the bit is set in both variables.

    This is just a bit-fetching routine.
*/
A[0] = X;
A[1] = Y;
for(X=8; X > -1; X-=1)
    R[X] = 0;
for (X=0; X<8; X+=1)
{
    R[X] |= A[0] & 1;    //LSR A[0]
    A[0] = A[0] >> 1;    //ROL R[X]
    R[X] = R[X] << 1 | (A[1] & 1);    //LSR A[1]
    A[1] = A[1] >> 1;    //ROL R[X]
}


/*
    This part can be simplified with a switch since the
    calculated values have no bearing on the result. However,
    cryptos[1] holds the pass code itself for STAGE, meaning
    it may be desirable to edit the values. This part was
    retained for the sake of flexibility. If you wish to speed
    things up and retain cryptos[1], here is the switch:
   
        switch STAGE>>1
        {
            case 0:
            case 2:
            case 5: Y = $01; break;
            case 1:
            case 4:
            case 7: Y = $0A; break;
            case 3:
            case 6:
            case 8: Y = $13; break;
        }
*/
Y = STAGE>>1;
X = 2;
while X > -1
{
    A[0] = (cryptos(1,Y) & $C) >> 2;
    if (cryptos(1,Y) & $30) | A[0] != cryptos(2,X)
        X -= 1;
    else
    {
        Y = 9*X;
        break;
    }
}


//Encode sprite info into the pass hash
for(X=0; X<9; X+=1)
{
    A[1] = cryptos(3,Y+1) & $30;
    PASS[X+1] = (cryptos(3,Y+1) & 3)<<2 | A[1] | R[X];
    Y += 1;
}
PASS[0] = cryptos(1,STAGE>>1);


//Place the icons
for (X=0; X<9; X+=1)
{
    Y = (PASS[X] & $3C)>>1;
    R = instance_create(cryptos(6,Y+1),cryptos(6,Y),obj_icon);
    switch PASS[X] & 3
    {
        case 0: R.sprite_index = -1; break;
        case 1: R.sprite_index = spr_passwhip; break;
        case 2: R.sprite_index = spr_passcross; break;
        case 3: R.sprite_index = spr_passheart; break;
    }
}


name_set(0);

PASS_DECRYPT

(click to show/hide)

var A,X,Y,R,REAL,FAIL;

A[9] = 0;


/*
    This variable gets adjusted whenever there is an error.
    Different bits are set along the way to ease debugging.
*/
FAIL = 0;


//Encrypt NAME (will be checked later)
A[7] = name_set(1);


A[1] = 0;
A[0] = 2;
while A[0] > -1
{
    /*
        If you leave cryptos[1] intact, you can
        replace the next two lines with a switch
        to slightly speed up the code:
       
            switch A[0]
            {
                case 0: Y = 0; break;
                case 1: Y = 6; break;
                case 2: Y = 13; break;
            }
    */
    R = cryptos(2,A[0]);
    Y = (R & $30) >> 2 | (R & $03);
   
    if PASS[Y] & 3
    {
        A[2] = A[0];
        A[1] += 1;
        for (X=0; X<9; X+=1)
        {
            if PASS[Y] == cryptos(1,X)
                break;
        }   
        STAGE = X << 1;
    }
    A[0] -= 1;
}
if A[1] != 1
    FAIL |= $1;

   
A[0] = A[2] * 9;


//De-hash all set cells
for( A[1]=$F; A[1] > -1; A[1]-=1)
{
    if PASS[A[1]] & 3
    {
        A[2] = A[0];
        for(A[3]=9; A[3]>0; A[3] -= 1)
        {
            R = cryptos(3,A[2]);
            Y = ((R & $30) >> 2) | (R & $03);
            if Y != A[1]
                A[2] += 1;
            else break;
        }
        if !A[3]
            FAIL |= $2;
    }
}


//Retrieve real pass from the input pass
for (X=0; X<9 ; X+=1)
{
    R = cryptos(3,A[0]);
    Y = (R & $30) >> 2 | (R & $03);
    REAL[X] = PASS[Y];
    A[0] += 1;
}
for (X=0; X<8; X+=1)
    REAL[X] = REAL[X+1];

   
//Reduce password back down to two variables
A[0] = 0;
A[1] = 0;
for(X=0; X<8; X+=1)
{
    A[1] = A[1] >> 1;
    A[1] |= (REAL[X] & 1)<<7;
    REAL[X] = REAL[X]>>1;
    A[0] = A[0] >> 1;
    A[0] |= (REAL[X] & 1)<<7;
    REAL[X] = REAL[X]>>1;
}
A[9] = A[1];
A[8] = A[0];


//Adjust parity of STAGE
STAGE |= (A[0] & $10) >> 4;


//If a NAME cheat is used, skip this next part
if !(A[8] & 1)
{
    if STAGE > $11
        FAIL |= $4;
    else
    if STAGE < $10
    {
        A[0] = A[8] & 6;
        if A[0]
        {
            Y = (STAGE & >>3 | A[0];
            X = STAGE & 7;
            if cryptos(5,Y) & cryptos(5,X + == 0
                FAIL |= $4;
        }
    }
}


//Set QUEST and ALLY
QUEST = A[8] & 1;
ALLY = A[8] >> 1 & 3;


//Adjust parity of STAGE (again)
if A[8] & $10
    STAGE |= 1;
   
   
//Check NAME and set PATH if STAGE branches
A[5] = A[8] >> 5;
if A[5] != A[7]
    FAIL |= $8;
else
if STAGE == 2 || STAGE == 4
    PATH = 1;


A[4] = $50 << (A[8] & 8 > 0);
A[3] = A[8] << 4;
A[2] = A[8] & $F0;
A[1] = A[3] + A[2] & $FF;
A[0] = ( ( (A[4] ^ A[2]) + (A[4] ^ A[3]) & $FF ) >> 4 | A[1] ) + STAGE;
if A[0] != A[9]
    FAIL |= $10;

name_set(0);

//Returns 1 if the password is correct
return !FAIL;

name_set

(click to show/hide)

/*
    Modifies the values saved in the name[v] array. In initial demos, each
    key is the corresponding image_index in the sprite font; to work with
    the password generator, values need to match the original in CV3.
   
    The second part of this script can be excluded if name[v] is automatically
    set correctly or if values will be changed for the sake of customization.
*/

//Set values to be encrypted
if argument0
{
    for (name_slot=0;name_slot<8;name_slot+=1)
        if name[name_slot]>0
            name[name_slot]+=$2F;
           
    for ({var X,Y; X=0; Y=0;} X<8; X+=1)
        Y += name[X] + cryptos(0,X);
       
    return Y & 7;
}

//Set values to be drawn
else
    for (name_slot=0;name_slot<8;name_slot+=1)
        if name[name_slot]>0
            name[name_slot]-=$2F;

cryptos

(click to show/hide)

/*
    Castlevania III's password algorithm used various
    hash tables and look-up tables. Some of these were
    included in the initial transcription and later
    deemed redundant or unnecessary and removed.

    The values retained herein can be edited in order
    to customize the algorithm for your own games.
    The safest changes are simply reordering the cases.
    Changing actual values (except in #6) may have
    undesireable results, so do so at your discretion.
*/

switch argument0
{

/*
    These are the values to scramble NAME[n].
    It is safe to change the ordering, but
    change the values at your own risk.
*/
case 0: switch argument1
   {
   case 0: return $07; break;
   case 1: return $03; break;
   case 2: return $01; break;
   case 3: return $06; break;
   case 4: return $02; break;
   case 5: return $04; break;
   case 6: return $05; break;
   case 7: return $00; break;
   } break;
   
   
/*
    The values here encrypt STAGE>>1
    and as such may be re-ordered. They
    are used in tandem with #2 below, so
    edit the values at your discretion.
*/
case 1:switch argument1
   {
   case 0: return $01; break;
   case 1: return $1B; break;
   case 2: return $02; break;
   case 3: return $35; break;
   case 4: return $19; break;
   case 5: return $03; break;
   case 6: return $37; break;
   case 7: return $1A; break;
   case 8: return $36; break;
   } break;
   
   
/*
    The values here are used with #1 above
    in an algorithm in PASS_ENCRYPT(); do
    not edit or re-order these values without
    understanding how the algorithm works.
*/
case 2:switch argument1
   {
   case 0: return $0; break;
   case 1: return $12; break;
   case 2: return $31; break;
   } break;
   
   
/*
    The values here encrypt the pass code
    and specify which position to place the
    icons. Only change the ordering, not the
    values, as #6 below is based on them.
*/
case 3:switch argument1
   {
   case 0: return $00; break;
   case 1: return $33; break;
   case 2: return $20; break;
   case 3: return $13; break;
   case 4: return $22; break;
   case 5: return $01; break;
   case 6: return $11; break;
   case 7: return $03; break;
   case 8: return $32; break;
   case 9: return $12; break;
   case 10: return $10; break;
   case 11: return $02; break;
   case 12: return $32; break;
   case 13: return $23; break;
   case 14: return $13; break;
   case 15: return $30; break;
   case 16: return $21; break;
   case 17: return $01; break;
   case 18: return $31; break;
   case 19: return $13; break;
   case 20: return $01; break;
   case 21: return $22; break;
   case 22: return $10; break;
   case 23: return $30; break;
   case 24: return $33; break;
   case 25: return $03; break;
   case 26: return $21; break;
   } break;
   

/*
    These values are based on STAGE and
    used for the algorithm in PASS_DECRYPT();
    don't mess with them until you figure
    out what their purpose is. Changing
    #1 or #2 above may require augmentation.
*/
case 5:switch argument1
    {
    case 0: return $B7; break;
    case 1: return $60; break;
    case 2: return $07; break;
    case 3: return $03; break;
    case 4: return $2F; break;
    case 5: return $FF; break;
    case 6: return $00; break;
    case 7: return $3D; break;
    case 8: return $80; break;
    case 9: return $40; break;
    case 10: return $20; break;
    case 11: return $10; break;
    case 12: return $08; break;
    case 13: return $04; break;
    case 14: return $02; break;
    case 15: return $01; break;
    } break;
   
   
/*
    These are the coordinate pairs of the icons.
    The default values are based on CVIII's pass
    screen and would need to be changed if your
    pass screen has a different layout. The first
    four values are x-coordinates; the lower four
    values are y-coordinates.
   
    There is no need to change the ordering, as
    the values here are based on #3 above.
*/
case 6:switch argument1
    {
    case 0:
    case 2:
    case 4:
    case 6: return $7A; break;
    case 8:
    case 10:
    case 12:
    case 14: return $92; break;
    case 16:
    case 18:
    case 20:
    case 22: return $AA; break;
    case 24:
    case 26:
    case 28:
    case 30: return $C2; break;
    case 1:
    case 9:
    case 17:
    case 25: return $5D; break;
    case 3:
    case 11:
    case 19:
    case 27: return $75; break;
    case 5:
    case 13:
    case 21:
    case 29: return $8D; break;
    case 7:
    case 15:
    case 23:
    case 31: return $A5; break;
   
   
    case 32:
    case 34:
    case 36: //Y-coordinate for entry icons
             return $50; break;
             
    case 33: //X-coordinate for Whip
             return $70; break;
             
    case 35: //X-coordinate for Cross
             return $90; break;
             
    case 37: //X-coordinate for Heart
             return $B0; break;
    } break;
}

As you can see by reading through the notes in cryptos(), you can customize the algorithm for your own games with some minor corrections. Change values at your own discretion and always thoroughly verify and re-verify your passwords work. The following code was used at the end of PASS_ENCRYPT() to verify any password generated could be decrypted with PASS_DECRYPT().

(click to show/hide)

text = "";
for(X=0; X<9; X+=1)
    A[X] = PASS[X];
STAGE=0;ALLY=0;QUEST=0;
for(Y=0; Y<16; Y+=1)
{
    PASS[Y]=0;
    for(X=0; X<9; X+=1)
    {
        R = (A[X] & $3C)>>2;
        if R == Y
        {
            switch A[X] & 3
            {
                case 1: PASS[Y] |= 1; break;
                case 2: PASS[Y] |= 2; break;
                case 3: PASS[Y] |= 3; break;
            }
            if A[X] & 3
                PASS[Y] |= R<<2;
        }
    }
    text += string(PASS[Y])+",";
}
show_debug_message(text);
PASS_DECRYPT();

[X]

LOL! Glad to see you having fun with this. I can't make heads or tails out of it, oh god... *dizzy*

[SabinFigaro]

I assume that the hard difficulty you're talking about is when you restart the game after beating it once? Otherwise.....yes, complete mindfuck lol!

[TheouAegis]

Yes, when you beat the game and play again, or if you use certain names like OKUDA (I think), a difficulty variable is flagged and that is included in the password.

Here's the original password generator:
http://www.mediafire.com/download/5im4cq9zrcym156/cv3pwgen.exe
My original code for that is on the forums in the murky past.


The point of this thread was so anyone wanting to incorporate a password system like the one in CV3 into their game, all the necessary code is here. You just copy the four scripts into your program, edit the name_set and cryptos scripts, then you're good to roll.

I also did it for anyone interested in various ways password generators were made. Like, I never would have considered some of the things they did in this code. I had a lot of "How did they come up with this?!" moments while working on this.

[BLOOD MONKEY]

Noice. Now i can play as grant from the start.

[TheouAegis]

If you knew what bytes to edit, you could make Alucard or even Grant freeze enemies (give them Sypha's abilities). Of course the pallet entries will be all wrong, but still fun. (No, you can't give Sypha the ability to turn into a bat unless you hack the ROM data itself. Sorry.)

[BLOOD MONKEY]

If you knew what bytes to edit, you could make Alucard or even Grant freeze enemies (give them Sypha's abilities). Of course the pallet entries will be all wrong, but still fun. (No, you can't give Sypha the ability to turn into a bat unless you hack the ROM data itself. Sorry.)

I know. I used to make Alucard use a whip and Grant use fireballs with all my fancy rom stuff.

[TheouAegis]

Sorry for necroing this, but I spent a few hours this week trying to actually understand the algorithm better, analyzing what each process is intended to do. I am aware that my original code is sloppy and hard to follow, and it even has some glaring errata. Regardless, here are my notes on it. I'm fairly confident now I would be able to quite easily modify the algorithm for use in even dissimilar games. For example, I think the CV3 password would actually work well if you wanted to add passwords to a Ghost & Goblins game.

https://gmvania.blogspot.com/2020/12/castlevania-iii-password-once-more-from.html