February 05, 2012

Might and Magic - The Encrypted Files

Back in 1986/1987, I owned a Commodore 64 computer.  I love to play the video games of the day, especially the dungeons/adventure based games of the era.  One of these games was Might and Magic.  The game came in 4 disks, which you loaded in depending on where you were in the world.  The game was loaded from Disk 1, and once the game got going, you might switch to another disk when asked.  As you might imagine, that meant there was a relatively large amount of content for the day.  

After playing the game for a while I bored of following the game - as it was a very long adventure and became sort of repetitive.  However, I wanted to see later aspects of the game, and get the feeling of power that larger and better weapons and armor might give me over the challenges within the game.  It was at this point that the aspect of the game changed for me.  No longer was it a role-playing game based in the middle ages; now it was a computer-based game - me against the original programmers.  I wanted to edit my character files on the disk to see if I could change the items in my inventory to something a bit more favorable.

I started up a disk editor.  On the Commodore 64, diskettes were broken into track and sector, and the file system was serial in nature.  Starting at track 18 (from what I recall) and sector 00, the first two bytes of the track and sector pointed to the next track and sector in the sequence.  Starting up and looking at this first track, everything seemed normal, and I began analyzing the disk contents.  When I followed the link to the next sector, however, I got a bit of a surprise.  There was a word that had begun on the last few bytes of the sector I had just left, but the word did not continue on in this sector.

I started looking around the disk for plain text content, and I couldn't find any except on that first sector!  The whole disk was encrypted!  I checked the other three disks and they too were encrypted. Well, this was a new challenge for me - I'd never seen a program that encrypted the disk contents as a method of protection.  I had wanted to edit my game characters, but I wasn't goingg to be able to do that if I couldn't read the contents in the first place. Luckily for me, I had done many cryptograms when I was younger, so I was familiar with both the Caesar shift cipher as well as replacement alphabets.  

I made the assumption that the computer would have to use some type of formula to easily translate the disk contents, and I had some known plaintext to work with due to the string content that bled from one sector to the next.  One of my character names had ended mid-word at the first sector, so I made the assumption that it must continue into the second sector. Having some math background and being obsessed with the new challenge, I quickly got to work, figuring out what the shift would need to be for my name to continue uninterrupted.  I came up with a value fairly quickly, and went about testing it on the new sector's contents.  

Plaintext quickly became apparent throughout the sector's encrypted bytes!  I had done it - I'd figured out the proper byte shift with just one incomplete word of known plaintext.  Pleased with myself, I continued on to the third sector....but alas, it wasn't going to be so simple.  The shift value was no longer presenting me with any known text.   While most of the file contents were gobbledy-gook, on sector 2 of the file, I had at least been able to make out some plain words (names of my party characters).  Lucky for me, I had another plaintext that had only partially translated at the end of sector 2, so I figured out the shift value that would get me the plaintext continuation into sector 3.  It worked!

So, now I had two different shift values for two different sectors.  I continued on to the fourth sector and accomplished the same, but I ran out of luck when it came to the fifth (IIRC).  No more known plain text bordered the two sectors.  I'd either have to guess at 255 values for shift and try them all, or come up with another way.  At this point, I figured that the shift values had to follow some kind of pattern for the computer to be able to figure out what the next shift value would be.  

I got out some more graph paper.  It occured to me that the value would have to have some constraints, to be able to have values between 1 and 255 - and I had just finished a trigonometry class, so the sin() wave was looking like a good bet to me.  I plotted the 3 shift values I had, and plotted 0 for the first track and sector.  I used the sector value itself for the x variable and set about plotting a formula that would give me the known values. I tested the formula on subsequent sectors and sat up for hours working on it.

Into the next day (after little sleep) I had cracked at least part of the puzzle.  I don't recall what happened that led me to use more than sin() waves.  I do know that in the end, there were three parts to the formula, and that the equation used track, sector and disk number to determine the shift offset.  I had decrypted the disk and determined the encryption algorithm, based on sin(), tan() and a constant based on one of those values.  

I modified a disk editor program to decrypt the disk as it edited it, and re-encrypt when writing the modified values back to the disk.  I manually edit my character's inventory to have item numbers that I did not already possess, and started up the game.  Success!!!!

I never played Might and Magic again after that weekend.  The game had become boring - especially compared to the game I had just played - battling not the trolls and wizards of lore, but battling the developers who relied upon in-house encryption to protect their secrets.  I will never forget that weekend and the dozens of pieces of graph paper that littered my floor amongst the empty bags of chips and soda cans.