# Category: Programming

## Hacked my DEF CON 18 badgeJuly 30th, 2010

I was only able to stay for part of the first day of DEF CON this year, but I’m glad I did. One of the things they’ve done for the last five years or so is put microcontrollers in the badges, and put in little Easter eggs for people to search for. This year’s had a Ninja Party mode which was locked by default, but you could unlock it by placing a series of 15 tumblers in the correct position.

They published the source code for the badges on the CD they gave out at registration (so perhaps I’m stupid for loading the CD on my laptop rather than smart for reverse engineering the badge). I opened up DC18_Badge.c and, searching for “Ninja” (the code was commented nicely), quickly found the following two C functions:

```/*************************************/
/* NINJA ROUTINES
/*************************************/

int dc18_ninja_validate(uint32_t val)
{
uint16_t a, b;

a = (uint16_t)(val & 0xfff);
b = (uint16_t)(val >> 12);

if((a ^ b) == 0x916)
{
return 1;
}
return 0;
}

// encode tumbler states into
// 24-bit value
uint32_t
dc18_encode_tumblers(tumbler_state_type
*tumblers)
{
uint32_t x = 0, j = 1;
uint16_t i;

for (i = 0; i < TUMBLERS_PER_IMAGE;
i++)
{
x += tumblers[i] * j;
j *= 3;
}

return x;
}
```

So the trick was to find the number that made `(a ^ b) == 0x916` and then figure out the tumbler positions to represent that number. I wrote two small Python functions to automate those tasks. To find the number that would unlock Ninja Mode, I wrote this loop. I added a print statement to show how far into the search we were, thinking it might take some time to find it, but it popped out 6423 in no time at all:

```while 1:
a = i & 0xfff
b = i >> 12
if i % 10000 == 0:
print "# a: %d, b: %d, i: %d" % \
(a, b, i)
if a ^ b == 0x916:
print "DONE: %d" % (i)
break
i += 1

DONE: 6423```

Now all that was left was to figure out the tumbler positions to represent 6423. Clearly, `dc18_encode_tumblers` tells us how to do that. I whipped up this little function to convert the tumbler positions to a decimal number:

```def enc_tumblers(tum):
x = 0; j = 1;
for i in range(15):
x += tum[i] * j
j *= 3
return x

>>> enc_tumblers([1,1,1,1,1,2,2,2,
0,0,0,0,0,0,0])
6439
```

I was going to write another loop to increment the tumbler array I was passing to `enc_tumblers`, but my first guess was so close that I just manually entered the settings until I found the winning configuration:

```>>> enc_tumblers([0,2,2,0,1,2,2,2,
0,0,0,0,0,0,0])
6423
```

Once I had the configuration, I put the tumblers in the appropriate positions: 0 - up, 1 - middle, 2 - down. After that, well, I guess I'm a ninja now:

Sometimes I make a tool that I use for a while and then wonder if it’s something others will find useful too. Here’s one of them…

For a while I was sharing links on my home page by linking to the feed of stories I’ve upvoted on Reddit, but that has become less satisfying as Reddit dumbs itself down each day (the same thing that happened to Digg a few years earlier). I decided to make my own link-sharing program that I could use by just clicking a bookmarklet whenever I was on a page I wanted to share.

It is a very simple program that stores the links in a flat text file and uses CORS to allow the bookmarklet to POST data to it from across domains. You can put the files in a directory on your server and use this simple bookmarklet to share links:

You can check out the server code or the bookmarklet source, or you can download the zip archive and extract the files on your server.

When you fetch the server script with GET you get back a JSON or RSS feed depending on the `format` parameter you pass.

Make sure the password in the bookmarklet stays synced with the password in the server file and change them to something secure.

## A-Star (A*) Algorithm in Python – UpdateJanuary 25th, 2010

Since there have been many requests over the years for the source code referenced in my A-Star (A*) Algorithm post, I decided to share it. I did a bit of refactoring too, as I have learned some neat things about Python in the years since I wrote that post, like list comprehensions.

A cautionary note to undergrad CS students (who I can only assume are the requestors): CS professors are pretty good at catching cheaters, so learn from others’ code, but write your own.

Source: astar.py

## Python AES Implementation – UpdateApril 4th, 2009

I fixed two bugs in my AES implementation. The first was a padding bug which resulted in the loss of up to a block of data when decrypting certain ciphertexts. The second bug was a more serious security problem caused by the use of a static initialization vector.

## Python CIDR Block ConverterDecember 14th, 2007

I wrote a Python script that converts a CIDR Block into a list of individual IP addresses, one-per-line. I found that I needed to repeat some network-related tasks across an entire subnet, and this script provides an easy way to automate these kinds of tasks in a shell environment. The source code and sample usage for the script follow:

Source Code: cidr.py

Sample Usage:

```brandon@zodiac ~ \$ cidr 192.168.1.5/30
192.168.1.4
192.168.1.5
192.168.1.6
192.168.1.7```

One item to note is a key difference between the way this program computes a CIDR block and others I have seen. The lazy way to convert a CIDR block to a list of IPs is to calculate the number of IP addresses in the subnet, (2^(32 – \$subnetSize)), and simply increment the base IP address that number of times. This method is deficient because, as in the example usage above, the base IP address that is specified may fall somewhere in the middle of the range of IP addresses (not necessarily at the beginning).

In my script, I calculate the CIDR block members the correct way. I am converting the base IP address to its binary form, zeroing-out the number of least significant bits as specified in the subnet size, and starting the enumeration of IP addresses at the bottom of that range.

## AES Tutorial / Python ImplementationJune 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.

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
Encrypting file: testfile.txt
Encryption complete.
[brandon@zodiac pyAES]\$ ./pyAES.py -d testfile_encrypted.txt -o testfile_decrypted.txt
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
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

• 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
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)
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]
[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]
[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]
[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 ***
[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) ***