Play Dark Castle in Windows December 13th, 2007

Update: 13-Dec-2007

I’ve found an old image of Beyond Dark Castle that is compatible with the version of Mini vMac we are using below! I added it to the existing archive, DarkCastle.zip. Now you can simply drop the ROM file, BDCImage.hfv into the running emulator and be off to the races with the equally legendary sequel. Enjoy.

Dark Castle was one of my favorite games to play on the old mid-1980s Macintoshes like the Mac Plus. I spent some time last year looking for a version I could run in Windows, but with no success. A few weeks ago I discovered a tutorial for running Dark Castle via a Mac emulator. I felt it was a bit confusing and left something to be desired, so I decided to put together a one-stop shop for playing Dark Castle in Windows.

All the files you will need are in the archive DarkCastle.zip.

  1. Unzip the archive.
  2. Run the Mini vMac.exe executable. Mini vMac is is a Mac Plus emulator which is freely distributed. Mini vMac requires a ROM image from a Macintosh Plus to run, which I’ve provided as well.
  3. Once you’ve executed Mini vMac.exe, you are effectively running a Mac Plus with no operating system installed. I consolidated some of the steps in the above mentioned tutorial and created a disk image with System 6 already installed. Go to File > Open Disk Image within Mini vMac and open the file Disk603.dsk or drag the file into the vMac window.
  4. Now that System 6 is up and running, it would be useful to have a hard drive available to install software and save data to. Just like the previous step drag the included file, hfs10M.DSK into the vMac window to mount the 10M hard disk image I pre-loaded with the Dark Castle software.
  5. That’s pretty much it. Run the Dark Castle executable to start the game.

Enjoy the game! If you’re anything like me, it should be a nice trip down memory lane. Let me know if you have any questions about the game play.

Next on the list of Mac games I would like to resurrect is Lode Runner

AES Tutorial / Python Implementation June 10th, 2007

Update 2: 30-May-2016

There have been a number of comments and questions about whether this code is compliant or interoperable with other implementations. It is not. I wrote it as a non-crypto expert to teach myself more about AES. It was never intended to perform well or to be compatible with other AES implementations.

Update: 04-Apr-2009

I fixed two bugs in my AES implementation pointed out to me by Josiah Carlson. First, I was failing to pad properly files whose length was an even multiple of the block size. In those cases, bytes would be lost upon decrypting the file. Josiah also pointed out that I was using a static IV, which leaks information about messages which share common prefixes. This is a serious security bug and I was glad to have it pointed out.

Feel free to check out the changes I made or simply download the updated script.

I’ve put together a series of slides as well as a Python implementation of AES, the symmetric-key cryptosystem.

Source: pyAES.py

Sample Usage: (color added for clarity)

[brandon@zodiac pyAES]$ cat > testfile.txt
The sky was the color of television tuned to a dead channel.
[brandon@zodiac pyAES]$ ./pyAES.py -e testfile.txt -o testfile_encrypted.txt
Password:
Encrypting file: testfile.txt
Encryption complete.
[brandon@zodiac pyAES]$ ./pyAES.py -d testfile_encrypted.txt -o testfile_decrypted.txt
Password:
Decrypting file: testfile_encrypted.txt
Decryption complete.
[brandon@zodiac pyAES]$ cat testfile_decrypted.txt
The sky was the color of television tuned to a dead channel.
[brandon@zodiac pyAES]$ md5sum *
19725cef7495fd55540728759a6262c8 pyAES.py
2fffc9072a7c09f4f97862c0bceb6021 testfile_decrypted.txt
3e57070eaf1b4adf7f43b38e1c5ee631 testfile_encrypted.txt
2fffc9072a7c09f4f97862c0bceb6021 testfile.txt

Symmetric Key Cryptography

  • Identical keys used to encrypt/decrypt messages
  • Can be implemented as block ciphers or stream ciphers

Strengths:

  • Speed
  • Much less computationally intensive than public-key crypto
  • Easy to implement in hardware as well as software

Weaknesses:

  • Key Management
  • n users require n(n-1)/2 keys for all to communicate
  • secure key distribution is a challenge
  • Cannot be used (directly) for authentication or non-repudiation


AES – The Advanced Encryption Standard

  • Rijndael algorithm invented by Joan Daemen and Vincent Rijmen and selected as AES winner by NIST in 2001
  • AES uses fixed block size of 128-bits and key sizes of 128, 192 or 256 bits (though Rijndael specification allows for variable block and key sizes)
  • Most of the calculations in AES are performed within a finite field
  • There are a finite number of elements within the field and all operations on those elements result in an element also contained in the field


AES Operations

  • AES operates on a 4×4 matrix referred to as the state
  • 16 bytes == 128 bits == block size
  • All operations in a round of AES are invertible
  • AddRoundKey – each byte of the round key is combined with the corresponding byte in the state using XOR
  • SubBytes – each byte in the state is replaced with a different byte according to the S-Box lookup table
  • ShiftRows – each row in the state table is shifted by a varying number of bytes
  • MixColumns – each column in the state table is multiplied with a fixed polynomial


AES Operation – AddRoundKey

  • Each byte of the round key is XORed with the corresponding byte in the state table
  • Inverse operation is identical since XOR a second time returns the original values
# XOR each byte of the roundKey with the state table
def addRoundKey(state, roundKey):
    for i in range(len(state)):
        state[i] = state[i] ^ roundKey[i]


AES Operation – SubBytes

  • Each byte of the state table is substituted with the value in the S-Box whose index is the value of the state table byte
  • Provides non-linearity (algorithm not equal to the sum of its parts)
  • Inverse operation is performed using the inverted S-Box
# do sbox transform on each of the values in the state table
def subBytes(state):
    for i in range(len(state)):
        state[i] = sbox[state[i]]

# sbox transformations are invertible
>>> sbox[237]
85
>>> sboxInv[85]
237
>>> sbox[55]
154
>>> sbox[154]
184
>>> sboxInv[184]
154
>>> sboxInv[154]
55


AES Operation – ShiftRows

  • Each row in the state table is shifted left by the number of bytes represented by the row number
  • Inverse operation simply shifts each row to the right by the number of bytes as the row number
# returns a copy of the word shifted n bytes (chars) positive
# values for n shift bytes left, negative values shift right
def rotate(word, n):
    return word[n:]+word[0:n]

# iterate over each "virtual" row in the state table
# and shift the bytes to the LEFT by the appropriate
# offset
def shiftRows(state):
    for i in range(4):
        state[i*4:i*4+4] = rotate(state[i*4:i*4+4],i)


AES Operation – MixColumns

  • MixColumns is performed by multiplying each column (within the Galois finite field) by the following matrix:

  • The inverse operation is performed by multiplying each column by the following inverse matrix:

# Galois Multiplication
def galoisMult(a, b):
    p = 0
    hiBitSet = 0
    for i in range(8):
        if b & 1 == 1:
            p ^= a
        hiBitSet = a & 0x80
        a <<= 1
        if hiBitSet == 0x80:
            a ^= 0x1b
        b >>= 1
    return p % 256

# mixColumn does Galois multiplication on a state column
def mixColumn(column):
    temp = copy(column)
    column[0] = galoisMult(temp[0],2) ^ galoisMult(temp[3],1) ^ \
                galoisMult(temp[2],1) ^ galoisMult(temp[1],3)
    column[1] = galoisMult(temp[1],2) ^ galoisMult(temp[0],1) ^ \
                galoisMult(temp[3],1) ^ galoisMult(temp[2],3)
    column[2] = galoisMult(temp[2],2) ^ galoisMult(temp[1],1) ^ \
                galoisMult(temp[0],1) ^ galoisMult(temp[3],3)
    column[3] = galoisMult(temp[3],2) ^ galoisMult(temp[2],1) ^ \
                galoisMult(temp[1],1) ^ galoisMult(temp[0],3)


AES – Pulling It All Together

The AES Cipher operates using a varying number of rounds, based on the size of the cipher key.

  • A round of AES consists of the four operations performed in succession: AddRoundKey, SubBytes, ShiftRows, and MixColumns (MixColumns is omitted in the final round)
  • 128-bit key → rounds, 192-bit key → 12 rounds, 256-bit key → 14 rounds
  • The AES cipher key is expanded according to the Rijndael key schedule and a different part of the expanded key is used for each round of AES
  • The expanded key will be of length (block size * num rounds+1)
  • 128-bit cipher key expands to 176-byte key
  • 192-bit cipher key expands to 208-byte key
  • 256-bit cipher key expands to 240-byte key


AES – Key Expansion Operations

AES key expansion consists of several primitive operations:

  1. Rotate – takes a 4-byte word and rotates everything one byte to the left, e.g. rotate([1,2,3,4]) → [2, 3, 4, 1]
  2. SubBytes – each byte of a word is substituted with the value in the S-Box whose index is the value of the original byte
  3. Rcon – the first byte of a word is XORed with the round constant. Each value of the Rcon table is a member of the Rinjdael finite field.
# takes 4-byte word and iteration number
def keyScheduleCore(word, i):
    # rotate word 1 byte to the left
    word = rotate(word, 1)
    newWord = []
    # apply sbox substitution on all bytes of word
    for byte in word:
        newWord.append(sbox[byte])
    # XOR the output of the rcon[i] transformation with the first part
    # of the word
    newWord[0] = newWord[0]^rcon[i]
    return newWord

AES – Key Expansion Algorithm (256-bit)

Pseudo-code for AES Key Expansion:

  1. expandedKey[0:32] → cipherKey[0:32] # copy first 32 bytes of cipher key to expanded key
  2. i → 1 # Rcon iterator
  3. temp = byte[4] # 4-byte container for temp storage
  4. while size(expandedKey) < 240
    temp → last 4 bytes of expandedKey

    # every 32 bytes apply core schedule to temp
    if size(expandedKey)%32 == 0
    temp = keyScheduleCore(temp, i)
    ii + 1
    # since 256-bit key -> add an extra sbox transformation to each new byte
    for j in range(4):
    temp[j] = sbox[temp[j]]
    # XOR temp with the 4-byte block 32 bytes before the end of the current expanded key.
    # These 4 bytes become the next bytes in the expanded key
    expandedKey.append( temp XOR expandedKey[size(expandedKey)-32:size(expandedKey)-28]

Another function to note…

# returns a 16-byte round key based on an expanded key and round number
def createRoundKey(expandedKey, n):
    return expandedKey[(n*16):(n*16+16)]


AES – Encrypting a Single Block

  1. state → block of plaintext # 16 bytes of plaintext are copied into the state
  2. expandedKey = expandKey(cipherKey) # create 240-bytes of key material to be used as round keys
  3. roundNum → 0 # counter for which round number we are in
  4. roundKey → createRoundKey(expandedKey, roundNum)
  5. addRoundKey(state, roundKey) # each byte of state is XORed with the present roundKey
  6. while roundNum < 14 # 14 rounds in AES-256
    roundKey → createRoundKey(expandedKey, roundNum)
    # round of AES consists of 1. subBytes, 2. shiftRows, 3. mixColumns, and 4. addRoundKey
    aesRound(state, roundKey)
    roundNumroundNum + 1
  7. # for the last round leave out the mixColumns operation
    roundKey = createRoundKey(expandedKey, roundNum)
    subBytes(state)
    shiftRows(state)
    addRoundKey(state)
  8. return state as block of ciphertext


AES – Encrypting a Single Block (Demo)

>>> key = passwordToKey("s0m3_p@ssw0rD")
>>> key
[62, 142, 78, 2, 164, 231, 18, 196, 148, 177, 82, 186, 240, 44, 136, 242,
23, 13, 20, 169, 248, 69, 163, 79, 13, 155, 97, 200, 241, 15, 76, 15]
>>> plaintext = textToBlock("Hiro Protagonist")
>>> plaintext
[72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116]
>>> blockToText(plaintext)
'Hiro Protagonist'
>>> ciphertext = aesEncrypt(plaintext, key)

*** aesMain ***
initial state:
[72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116]
state after adding roundKey0:
[118, 231, 60, 109, 132, 183, 96, 171, 224, 208, 53, 213, 158, 69, 251, 134]

*** AES Round1 ***
state after subBytes:
[56, 148, 235, 60, 95, 169, 208, 98, 225, 112, 150, 3, 11, 110, 15, 68]
state after shiftRows:
[56, 148, 235, 60, 169, 208, 98, 95, 150, 3, 225, 112, 68, 11, 110, 15]
state after mixColumns:
[66, 80, 228, 230, 148, 33, 121, 29, 106, 95, 226, 146, 255, 98, 121, 117]
state after addRoundKey:
[85, 93, 240, 79, 108, 100, 218, 82, 103, 196, 131, 90, 14, 109, 53, 122]

<-- SNIP -->

*** AES Round 14 (final) ***
state after subBytes:
[0, 229, 171, 70, 93, 137, 135, 251, 99, 182, 88, 166, 228, 229, 251, 97]
state after shiftRows:
[0, 229, 171, 70, 137, 135, 251, 93, 88, 166, 99, 182, 97, 228, 229, 251]
state after addRoundKey:
[195, 123, 205, 183, 213, 202, 50, 223, 223, 164, 99, 86, 126, 34, 107, 142]

>>> ciphertext
[195, 123, 205, 183, 213, 202, 50, 223, 223, 164, 99, 86, 126, 34, 107, 142]

>>> blockToText(ciphertext)
'\xc3{\xcd\xb7\xd5\xca2\xdf\xdf\xa4cV~"k\x8e'
>>> cleartext = aesDecrypt(ciphertext, key)

*** aesMainInv ***
initial state:
[195, 123, 205, 183, 213, 202, 50, 223, 223, 164, 99, 86, 126, 34, 107, 142]

*** AES Round 14 ***
state after addRoundKey:
[0, 229, 171, 70, 137, 135, 251, 93, 88, 166, 99, 182, 97, 228, 229, 251]
state after shiftRowsInv:
[0, 229, 171, 70, 93, 137, 135, 251, 99, 182, 88, 166, 228, 229, 251, 97]
state after subBytesInv:
[82, 42, 14, 152, 141, 242, 234, 99, 0, 121, 94, 197, 174, 42, 99, 216]

<-- SNIP -->

*** AES Round 0 (final) ***
state after adding roundKey0:
[72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116]
>>> cleartext
[72, 105, 114, 111, 32, 80, 114, 111, 116, 97, 103, 111, 110, 105, 115, 116]
>>> blockToText(cleartext)
'Hiro Protagonist'


Programming Skills Test April 16th, 2007

This site is not of my creation but it is the type of website I’ve wished for for quite a while and have considered creating more than once. Project Euler hosts a series of math / computer programming problems that let a coder test his or her skills. As of 4/16/07, I’ve completed the first 14 problems.

Book Review: The Art of UNIX Programming March 30th, 2007

If you are a UNIX/Linux user of any kind, I highly recommend reading Eric S. Raymond’s The Art of UNIX Programming. While I was expecting his book to be fairly one-sided about the virtues of UNIX and the shortcomings of everything else, I found the entire book to be well-balanced, informative, and very readable. TAUP could easily be used as a text for a programming class, but it’s really more of a “philosophy of programming” book. This book is filled with tons of quotable material, so I will resist the urge to make a quote-fest of this book review…

Raymond begins with a solid chapter on the Philosophy behind UNIX. He provides a number of great guiding principles for developing smart, streamlined applications. Where he could be abstract and vague, he provides concrete, usable advice. One of the great things about the book is his ample use of quotations from other UNIX gurus. From Doug McIlroy‘s A Quarter Century of Unix:

This is the Unix philosophy: Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface.

He also quotes Rob Pike on his 6 rules of C programming. I found the last two to be especially poignant:

Rule 5. Data dominates. If you’ve chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.

Rule 6. There is no Rule 6.

Raymond goes on to compare and contrast the major operating systems of the past 20 years, including VMS, MacOS, OS/2, Windows, BeOS, MVS, VM/CMS, and Linux. He provides a framework and vocabulary for discussing OSes. Concepts like multitasking, process-spawning, file formats (e.g. textual vs. binary), and internal system boundaries differ greatly from OS to OS and have profound effects on the end user experience. Again, Raymond covers fairly academic material, making rigorous arguments using carefully defined terms. But he presents the material in a very novel and personal way, making the book feel less like a textbook and more like a pleasure read.

Once we understand the type of development environments various OSes can offer us, Raymond begins to describe criteria which we can use to set quality software apart from average software, like compactness and orthogonality. Compact software has the property that it can fit conceptually inside a human’s head. Orthogonal software has the property that operations are atomic and have no unexpected side effects; they change one thing without affecting others. Often, the concepts for good software design are best-illustrated by example, and Raymond provides many such examples to drive each point home. One of my favorite things about this material is that it has changed my thinking about design/architectural elements in my own programs.

Again, I’ll avoid the urge to summarize every chapter, as much as I’d like to. There is something to be said for letting the next reader get as much out of the book as I did. There are, however, a couple other sections of the book that I felt were compelling and deserve discussion.

One of the more enjoyable sections of the book for me was that on Unix Interface Design Patterns. Those of us who have taken a software engineering class may already have been exposed to some of the popular design patterns, so most of the vocabulary is familiar. Raymond describes patterns like The Filter Pattern, of which grep is a good example. Among other patterns, he also describes The Cantrip Pattern, The Sink Pattern, and The Compiler Pattern. The Cantrip Pattern is the simplest Unix design pattern as it has no inputs or outputs; its behavior is only affected by startup conditions. Classic examples of the Cantrip Pattern include rm and touch. Raymond reminds us to resist the temptation to write more interactive programs when a Cantrip will suffice because the program will lose scriptability.

In a further discussion of the software complexity idea, Raymond uses his “Tale of Five Editors” to explore the trade-offs between interface and implementation complexity. The five editors he compares and contrasts are: ed, vi, Sam, Emacs (my personal preference), and Wily, an editor I had neither used nor heard of. Raymond gives accurate, matter-of-fact descriptions of each of the editors and shows how . When ultimately arriving at the question of the Right Size for Software, Raymond leaves us with the Rule of Parsimony: “Write a big program only when it is clear by demonstration that nothing else will do.”

For every interesting part of the book that I mentioned in this review, there are 5 or 6 that are equally thought-provoking and affirming to those of us that embrace the *nix culture. I can’t recommend this book any stronger to any hacker or fan of Unix.

8 Reasons Why Python Rocks November 27th, 2006

First Things First


8 Reasons to Use Python

  1. Lists, Tuples, and Dictionaries
  2. Intuitive Looping Techniques
  3. Text Processing and String Operations
  4. Exception Handling
  5. Sockets
  6. Tons of Standard Libraries
  7. Working with Files
  8. Simple HTTP/Web Services


1. Lists, Tuples, Dictionaries

  • Lists – basically arrays (actually linked lists), can contain multiple data types, accessible by index, can be used as a stack or queue, can be sliced/concatenated
  • append, insert, remove, pop, count, sort, reverse
  • Tuple – statically defined, can be accessed by index but cannot be modified after instantiation, can be used as dictionary keys
  • Dictionary – accessed by key, value pairs, constant lookup time, unordered in memory
  • keys, items, del


2. Intuitive Looping Techniques

  • for i in range(10):
  • for name in [‘karl’, ‘lenny’, ‘barney’, ‘moe’]:
  • for i, j in enumerate(myList):
    print i, j
  • for k, v in myDictionary.iteritems():
    print k + “‘s value is”, v
  • questions = [‘who’, ‘what’, ‘when’, ‘where’]
    answers = [‘Mr. Green’, ‘revolver’, ’11:00′, ‘Lounge’]
    for q, a in zip(questions, answers):
    print q + “:”, a


3. Text Processing and String Operations

  • Strings can be indexed like C, but substrings can also be specified with slice notation
  • s[0], s[:2], s[4:], s[-3:],…
  • Standard string library provides dozens of useful functions
  • split, join, lower, upper, replace, title, isalnum, isdigit,
    whitespace, punctuation, printable, etc., etc.
  • Very easy to implement “filter-type” programs like grep
  • input = sys.stdin.readlines()
  • makes parsing formatted text files trivial, e.g. Apache log parsing


4. Exception Handling

Very easy to catch exceptions and run separate code for error handling routines

try:
something = that_could + produce_an_exception
except:
this_code = gets_run( only_if_exception_thrown )


5. Simple Sockets

  • Very simple to implement TCP/IP sockets
  • Easy to add networking support to your Python scripts
  • Inexpensive way to communicate between programs, even locally
  • Server:
  • 1. bind
  • 2. listen
  • 3. accept
  • 4. recv/send
  • Client:
  • 1. connect
  • 2. send/recv


6. Tons of Standard Libraries

  • Python ships with over 300 standard libraries for programmers to use:
  • >>> help()
    help> modules
  • Just to name a few:
  • calendar, Cookie, cookielib, datetime, distutils, htmllib,
    HTMLParser, httplib, math, md5, optparse, os, random, re,
    smtplib, socket, string, struct, sys, time, urllib, urlparse,
    xml, xmllib


7. Working with Files

  • Reading and writing files is very simple in Python
  • open(), read(), write(), close()
  • os library provides many useful function calls for filesystem access
  • chdir, chmod, execv, getcwd, listdir, mkdir, remove, rmdir,
    rename, walk


8. Simple HTTP / Web Services

  • Almost everything provided to the programmer by httplib and other HTTP/URL libraries
  • httplib.HTTPConnection
  • request
  • getresponse
  • getheaders
  • status
  • reason
  • read
  • close


Putting it all Together

  • Easy to code ⇒ rapid prototyping of new functions/programs
  • Easy to read ⇒ whitespace dependence leads to highly readable and reusable code
  • Let’s write a couple of Python scripts
  • factorial.py
  • primefactors.py
  • feedMonitor.py

I am definitely open to discussion on this topic as it’s one that’s close to my heart. If you’re a Perl advocate or would otherwise like to make a case against the use of Python, I strongly encourage you to send me an email. I am more than happy to try to defend it 🙂

East Bay Psychotherapist
Licensed Clinical Social Worker provides psychotherapy and counseling services for couples and individuals in the East Bay Area.