It is currently Wed Apr 25, 2018 9:40 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 12 posts ] 
Author Message
PostPosted: Fri Dec 22, 2017 2:00 pm 
Offline
User avatar

Joined: Fri Dec 22, 2017 1:37 pm
Posts: 6
Location: Wisconsin
Greetings Friends,

I'm not exactly new since I've be skulking about in the shadows for sometime now but only recently have I tried to post anything. I did recently put together a piece about the password system used by the homebrew game The Legends of Owlia (recently re-released as a free ROM) which I thought I was pretty good and would be interesting to the right audience.

I tried tweeting it but nobody cared. Then I thought that it might be appropriate to post in the general section here and that the more technical audience might appreciate it more anyway. (A shameless plug; I know. Sorry. :oops:)

https://bacteriamage.wordpress.com/2017/12/22/an-analysis-of-the-legends-of-owlia-password-system/

Cheers!

_________________
https://bacteriamage.wordpress.com/


Top
 Profile  
 
PostPosted: Sat Dec 23, 2017 1:04 am 
Offline
User avatar

Joined: Fri Feb 27, 2009 2:35 pm
Posts: 242
Location: Fort Wayne, Indiana
I haven't developed any games that would have called for passwords myself, so I never really looked into them much, and it was interesting to build on what I knew a little. Owlia's password reminds me of tepples's suggestion for an RPG password with its "chapter" and "event flags for chapter" bits.

I had no idea that it was common for games to include decoy password characters.


Top
 Profile  
 
PostPosted: Sat Dec 23, 2017 3:41 am 
Offline

Joined: Sun Mar 03, 2013 1:52 am
Posts: 105
Location: Texas, USA
Thanks for sharing your investigation into Owlia's password system. When I saw Owlia's password, I noticed the total number of possible passwords didn't match up to a whole number of bits and wondered how the conversion dealt with that. The decoy characters makes it much simpler!

Did you use FCEUX's debugger during your work? In the two password systems I have analyzed, I did lots of analysis myself first, but eventually used the debugger to help me figure things out.

Here's my encoder and decoder for Ufouria's passwords. It uses a method to scramble the password that I didn't completely understand, I just copied the algorithm I saw the code was doing. Also, I remember having problems getting the table of data that it uses for the scrambling method because the right bank wasn't switched in.

I figured out how the password system in the Lizard demo works, but didn't write up the details. (I still have the files from when I worked on it, maybe I'll write up some notes sometime.) I remember I had assumed the checksum would be at the end of the password, but it was actually in the middle! Sneaky.


Top
 Profile  
 
PostPosted: Sat Dec 23, 2017 3:02 pm 
Online

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19950
Location: NE Indiana, USA (NTSC)
I too recognized parallels between the algorithm in Owlia and what I had suggested, but I didn't want to be so quick to shill my own posts after having taken heat for mentioning Pently too much in the FamiTracker users' Discord server.

What I would have done differently:

  1. Run a diffusion algorithm on the whole password. This would obscure the relationship between an individual character and an individual part of the state, and it would make invalid money values behave as a stronger checksum.
  2. Use vowels as the decoys, if only so that a valid password can never include well-known obscenities (such as an infamous Metroid password that begins ENGAGE RIDLEY MOTHER).


Top
 Profile  
 
PostPosted: Sat Dec 23, 2017 3:53 pm 
Offline
User avatar

Joined: Fri Dec 22, 2017 1:37 pm
Posts: 6
Location: Wisconsin
NovaSquirrel wrote:
Owlia's password reminds me of tepples's suggestion for an RPG password with its "chapter" and "event flags for chapter" bits.


Yeah, that looks like good advice to me too. I think the really great thing about this is that a lot of different programmers have independently approached this problem over the years and come up with similar solutions. When I first looked into this about 10 years ago there didn't seem to be much information about it at all which is one of the reasons I ended up digging in myself.

I didn't know that homebrewers would eventually pick up the mantle. I wonder how much NES programmers back in the day collaborated?

NovaSquirrel wrote:
I had no idea that it was common for games to include decoy password characters.


I can only speak to what I've seen personally but yes I've seen this in multiple games. One is the GI Joe NES game which lets you select from a larger set but only uses 16 of the total characters and it changes which subset it uses based on the checksum.

Bavi_H wrote:
I noticed the total number of possible passwords didn't match up to a whole number of bits and wondered how the conversion dealt with that. The decoy characters makes it much simpler!


Yeah, I can only think of one other way to deal with the fractional bits by grouping digits but I've never seen anything that does anything other than just use a subset that is an even number of bits.

Bavi_H wrote:
Did you use FCEUX's debugger during your work? In the two password systems I have analyzed, I did lots of analysis myself first, but eventually used the debugger to help me figure things out.


When I first started I always used the debugger. With experience I am now able to break the simpler systems without examining the code. Owlia didn't try hard to hide the encoding or the key so it was easy to decipher by hand. I couldn't have done it if I haven't already worked with other systems before though.

Bavi_H wrote:
Here's my encoder and decoder for Ufouria's passwords. It uses a method to scramble the password that I didn't completely understand, I just copied the algorithm I saw the code was doing. Also, I remember having problems getting the table of data that it uses for the scrambling method because the right bank wasn't switched in.


Wow, that's a big one! I've seen programs like that for games like Metroid but I've only worked with games that use short single line strings usually 5 to 12 characters. I have a spreadsheet that I use and just keep writing Excel macros to encode and decode as a reverse new games.

Bavi_H wrote:
I figured out how the password system in the Lizard demo works, but didn't write up the details. (I still have the files from when I worked on it, maybe I'll write up some notes sometime.) I remember I had assumed the checksum would be at the end of the password, but it was actually in the middle! Sneaky.


Awesome, post it! From Brad's screenshots looks like he's changed the system in the final version. His kickstarter was before I knew about homebrew so I hope I can snag a copy once he ships.

I don't think there's any particular pattern on this. Gargoyle's Quest for the GameBoy splits the checksum between the front and end. I think it does that so the those characters of the password change more so it creates more apparent randomness to the player.

tepples wrote:
Run a diffusion algorithm on the whole password. This would obscure the relationship between an individual character and an individual part of the state, and it would make invalid money values behave as a stronger checksum.


Yeah, I've wondered about using more modern cryptographic techniques but everything seems to just use simple classical encryption like substitution or transposition. Modern cryptography might be overkill for this application and probably more code on the NES in 6502 assembly. Most of the math for real modern encryption is a little above my head.

tepples wrote:
Use vowels as the decoys, if only so that a valid password can never include well-known obscenities (such as an infamous Metroid password that begins ENGAGE RIDLEY MOTHER.


I didn't know about that. I did know about the one password that works that is somebody's name. I've always thought about that if I ever make a game I'd design the password encoding so that my name would be some super-powered password.

_________________
https://bacteriamage.wordpress.com/


Last edited by BacteriaMage on Sat Dec 23, 2017 8:59 pm, edited 1 time in total.

Top
 Profile  
 
PostPosted: Sat Dec 23, 2017 4:12 pm 
Offline
User avatar

Joined: Sun Jan 22, 2012 12:03 pm
Posts: 6223
Location: Canada
Lizard's final password system is essentially the same implementation concept as in the alpha demo, but I think it had 3 bits of parity before and I had to cut it down to 2 bits to accommodate >256 rooms. Also it uses the numbers 1-8 instead of letters now, which I thought would be easier to understand, and not so subject to accidentally offensive words.

The basics of it:
  • 1. Each digit of the password encodes 3 bits as an number 1-8.
  • 2. Each piece of information is interleaved across the digits, trying to stick each bit in a different digit. The goal is that changes won't be easily localized/isolated in a single digit.
  • 3. Unused bits are used to store some XOR parity of a set of the other bits, with 2 bits this makes 3/4 "random" passwords invalid.
  • 4. After encoding a few chosen bits are flipped with XOR, basically so if all the incoming info is 0 it doesn't still come out as an obvious 00000 password.
  • 5. Since everything is binary encoded, information that isn't power-of-two in size leaves means there's some invalid possible values for each decoded piece of info, which again invalidates many passwords.
  • 6. Unless using a cheat, passwords only work at a checkpoint, which means normally like 99.6% of passwords are invalid by not going to a checkpoint. (It's very useful for debugging that every room has a valid cheat password though, and I don't mind it as an accessible cheat method.)

My only real goal here was to make it so that there's no "obvious" way to generate passwords. Like I didn't want people to just be able to change XXXX2 to XXXX3 and see their lizard change, etc. Obviously anyone motivated can crack it (and I'm going to open source it later anyway) but really all I wanted was to prevent being able to edit/guess passwords without doing some real analysis.

My more general goals:
  • Make sure a large percentage of passwords are invalid to discourage guessing.
  • Try to make sure valid passwords aren't distributed close to each other, i.e. changing a valid password single digit by 1 shouldn't produce another valid password.
  • Try to make a single change in the input information produce more than one digit of change in the password.
  • Try not to make the value of inputs obvious, e.g. "0" shouldn't look like "0" in the password.
  • Do not let any possible password produce an invalid/corrupt game state.

I think for larger passwords I might like to try some kind of variation of autokey encryption, maybe generating a CRC for the start of the password and then using that to seed something that chaotically-but-deterministically (PRNG) swizzles or flips bits in the rest of the password.


Top
 Profile  
 
PostPosted: Sat Dec 23, 2017 9:01 pm 
Online

Joined: Sun Apr 13, 2008 11:12 am
Posts: 7027
Location: Seattle
I've been really tempted to write a BCH-21,31 (a forward-error correction system) encoder/decoder to the NES specifically for passwords. On the down side, it does inflate your passwords by 150%, but on the plus side you can intentionally encode errors (that will be corrected out) into your password and only accept a password with the correct number of errors.


Top
 Profile  
 
PostPosted: Sat Dec 23, 2017 9:36 pm 
Offline
User avatar

Joined: Fri Dec 22, 2017 1:37 pm
Posts: 6
Location: Wisconsin
rainwarrior wrote:
Each digit of the password encodes 3 bits as an number 1-8


Just my personal feeling with no good factual basis but as a child I felt like games that used only numbers in the password were somehow less advanced. Guess, I'm number-biased? :P

Might be the fact that the set of digits is smaller than the set of letters.

rainwarrior wrote:
I think for larger passwords I might like to try some kind of variation of autokey encryption, maybe generating a CRC for the start of the password and then using that to seed something that chaotically-but-deterministically (PRNG) swizzles or flips bits in the rest of the password.


That's an interesting idea. I really agree on the wanting to create the high-degree of randomness and protect from causal and accidental modification as a design goal.

After having reversed a number of these systems and been thinking about it for a while the method I'd like to use someday would be to include a 2 or 3-bit counter plus some portion of the checksum in the first character. The counter would just increment each time a password was issued to ensure that the first character always changes. The character values would be pre-assigned at random and then when encoding, the current character value would be offset by the value of the previous character. I think that would result in even small changes giving completely different passwords that appeared heavily random and you'd get a kind of cascading effect.

Gargoyle's Quest on the Game Boy did something similar which is where I drew some inspiration on this. It has a 3 bit field which is just used to pick a different XOR key used to scramble the rest of the password. Obviously, these bits get set after the rest are scrambled since they'd otherwise scramble themselves.

This results in very different passwords being generated for all of the different possible values of this field. What's a little odd though is that the value of this field is just randomly assigned each time the password is issued. Since this an RPG like game where the passwords are issued by NPCs in towns you can just keep talking to the NPC and he'll give you a different but equivalent one most times from the set of possible 8 variations.

As a child playing this I noticed how the passwords were usually very different but then sometimes pretty similar. I noticed that if I kept talking to the NPC in the next town he'd eventually give me a password that was very close to the original one. This always struck me as odd but it would still be more than a decade before I eventually discovered why.

The way I think this should have worked was to increment the value each time so that all the possible variations were cycled through. That way once you circled around hopefully the data had changed enough that the two passwords using the same key were now different enough to no longer appear very similar. The other important thing would be to only increment the counter if something actually changed since the last issuing so that you can't just talk to the same NPC over and over again and immediately cycle through the set.

_________________
https://bacteriamage.wordpress.com/


Top
 Profile  
 
PostPosted: Sat Dec 23, 2017 9:40 pm 
Online

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19950
Location: NE Indiana, USA (NTSC)
lidnariq wrote:
I've been really tempted to write a BCH-21,31 (a forward-error correction system) encoder/decoder to the NES specifically for passwords.

If you do, I'd like to use it to display a 2D barcode for Internet ranking, seeing as I can't seem to figure out the math behind QR code ECC myself.


Top
 Profile  
 
PostPosted: Sun Dec 24, 2017 3:50 am 
Offline
User avatar

Joined: Fri Feb 27, 2009 2:35 pm
Posts: 242
Location: Fort Wayne, Indiana
Over on the far end of trying to make passwords difficult to figure out, you've got Animal Crossing for GameCube, using the RSA encryption algorithm on top of substitution ciphers and shuffling bits and bytes around multiple times, in ways that vary based on the input. Kind of makes me wonder what sort of stuff is going on for, say, PlayStation 1 games that provide both a memory card and password option since they easily have the CPU power to do something strong.

I think in Owlia, or really any homebrew game, barely obfuscating the password is fine since cheaters are going to find a way no matter what. Passwords are really just a convenience to the player, and I would probably focus on making them pleasant to use (catching incorrectly typed passwords, not having similarly looking characters, short, etc.).


Top
 Profile  
 
PostPosted: Sun Dec 24, 2017 7:22 am 
Online

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19950
Location: NE Indiana, USA (NTSC)
Previously on Security Stack Exchange: Which block cipher for a very short (40-bit) message?

In that question, tepples wrote:
I'm worried about online attacks and pencil-and-paper attacks by bored gamers, as have been posted in the "Classified Information" section of Nintendo Power magazine. But I'm not quite as concerned about automated attacks by someone reading the algorithm and symmetric key out of the game's code and using this information to put a password generator on a website, as this would take conscious effort on a player's part to cheat at the game.

Suggestions in answers include the Thorp shuffle, Swap or Not, and ciphers with a 32-bit block size. My previous demo ended up using a homemade cipher with a structure inspired by XXTEA.

The complexity of the Animal Crossing example probably has something to do with wanting to avoid modification of the recipient name and town for potentially valuable items, where playground children may be trading pocket change for item codes. There's a bit more incentive to cheat at something like that.


Top
 Profile  
 
PostPosted: Sun Dec 24, 2017 4:52 pm 
Offline

Joined: Sun Mar 03, 2013 1:52 am
Posts: 105
Location: Texas, USA
Bavi_H wrote:
I figured out how the password system in the Lizard demo works, but didn't write up the details. (I still have the files from when I worked on it, maybe I'll write up some notes sometime.)
BacteriaMage wrote:
Awesome, post it!
rainwarrior wrote:
Lizard's final password system is essentially the same implementation concept as in the alpha demo [...].
The basics of it: [...]

I posted my additional notes about Lizard Demo's password system in the Lizard thread.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: freem, TmEE and 9 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group