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:
- 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]
- SubBytes – each byte of a word is substituted with the value in the S-Box whose index is the value of the original byte
- 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:
- expandedKey[0:32] → cipherKey[0:32] # copy first 32 bytes of cipher key to expanded key
- i → 1 # Rcon iterator
- temp = byte[4] # 4-byte container for temp storage
- 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)
i → i + 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
- state → block of plaintext # 16 bytes of plaintext are copied into the state
- expandedKey = expandKey(cipherKey) # create 240-bytes of key material to be used as round keys
- roundNum → 0 # counter for which round number we are in
- roundKey → createRoundKey(expandedKey, roundNum)
- addRoundKey(state, roundKey) # each byte of state is XORed with the present roundKey
- 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)
roundNum → roundNum + 1 - # for the last round leave out the mixColumns operation
roundKey = createRoundKey(expandedKey, roundNum)
subBytes(state)
shiftRows(state)
addRoundKey(state) - 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'
Hi mate. I’m interested in the source code of Python AES implementation. Maybe you can upload again the file, because the link seems to be broken. Thanks!
Thanks for pointing that out. The broken link is fixed now.
Thank you very much.
Jan.
A small bug: in line 360 of the script, change “filename” to “outputfile”.
@thanassis,
Good catch, thank you. The bug is fixed now.
Question: suppose AES is used being used a stream cipher and the attacker knows the actual contents of the initial blocks (which is not difficult because, for example, most XMLs begin with DOCTYPE header). Can the attacker get the cipher text and derive the key from the known plaintext from the header?
gud lecturer ..Have worked with Equivalent Inverse Cipher???????
I need code for it in C
Interesting, you have separate encrypt and decrypt functions, but they both invoke aesEncrypt. In fact in this implementation, since you are simply XORing plaintext with a key, the encryption is very malleable … I could easily change the ciphertext of “Help him” to “kill him” even if I can never decrypt it. I know it is not supposed to provide authentication, but still.
So I’m wondering why you chose to implement it like this. Usually people would implement it using one of the standard block cipher modes (http://en.wikipedia.org/wiki/Cipher_modes) to provide non-malleability.
Hi Samee,
Thanks for the comments, though I think you rushed through the reading of my code. First, the encrypt and decrypt functions do call separate methods, so I’m not sure where that comment came from or why it’s relevant. Your example of malleability is extremely contrived. Almost no crypto is going to withstand an attack if you have known plaintext and known ciphertexts, so I don’t think that’s an indictment of my code in particular. I would love to see an example of an 8 byte encrypted message, in plaintext and ciphertext, that can withstand this type of tampering. As far as your comment about not “XORing plaintext with a key”, I have not seen very many cryptosystems that don’t follow this pattern. All of the block cipher modes operate by generating blocks of key material and XORing those with blocks of plaintext to produce blocks of ciphertext. I don’t quite see how to avoid this pattern. Finally, my code does implement AES in Output Feedback Mode, so I am aware of block cipher modes, but I still don’t think these solve your example above. Maybe you can clarify your comments.
Thanks,
Brandon
You know what, you are right. I think I was confused by something else
Hello. Can you please fix the link to the pyAES.py file, since it is broken.
Thanks, Josh. Link is fixed now.
1) thanks for tutorial, great work π
2) images in section mixColumns do not exist anymore.. :/
G’day mate,
I’ve downloaded and tried yor code, and I get this error (using python 3.3) Python# time ./pyAES.py -e testfile.txt -o testfile_enc.txt
File “./pyAES.py”, line 352
print “pyAES: unable to open input file -“, myInput
^
SyntaxError: invalid syntax
Error in sys.excepthook:
Traceback (most recent call last):
File “/usr/lib/python3/dist-packages/apport_python_hook.py”, line 63, in apport_excepthook
from apport.fileutils import likely_packaged, get_recent_crashes
File “/usr/lib/python3/dist-packages/apport/__init__.py”, line 5, in
from apport.report import Report
File “/usr/lib/python3/dist-packages/apport/report.py”, line 30, in
import apport.fileutils
File “/usr/lib/python3/dist-packages/apport/fileutils.py”, line 23, in
from apport.packaging_impl import impl as packaging
File “/usr/lib/python3/dist-packages/apport/packaging_impl.py”, line 20, in
import apt
File “/usr/lib/python3/dist-packages/apt/__init__.py”, line 23, in
import apt_pkg
ImportError: No module named ‘apt_pkg’
Original exception was:
File “./pyAES.py”, line 352
print “pyAES: unable to open input file -“, myInput
^
SyntaxError: invalid syntax
but when I use python 2 (like the original code) everything works fine.
My question as I’m newby in python and basically I’m testing some ciphers is, Do you know why this error ocurr and why is linked to the version, obiusly python3 is doing something different that i dont know and/or i cant tell.
I’ll be nice if you can give me a hand about it.
Thanks a lot and your code is really nice π
take care
cya
In Python 3
print
is no longer a statement and has been changed to a proper function. It needs to be called as such, e.g.print("hello")
. This code is not valid Python 3.Have you tried testing your variant with an AES implementation from a crypto library?
That is because when you call the function shiftRows you are actually shifting the state columns. When you call the mixColumns function you mix the rows.
Here are the correct definitions for shiftRows and mixColumns (and for their inverses): http://ideone.com/di7GBN
The rest should be kept the same.
I’ve been trying to validate your script against OpenSSL output using various permutations of options, but have been unable to create ciphertext that this script can decode (or vice versa) – particularly the -aes-256-ofb, -nosalt, and -iv 00 options (the latter involved hardcoding the IV in your code to all zeroes, for the purpose of testing).
I’m curious then: what AES implementation did you use to validate your script against? While I doubt I’m hitting a bug, it’s not out of the question and being able to compare this to a known implementation would be valuable.
I implemented your algorithm and discovered that in the encrypt and decrypt methods you only call aesEncrypt. aesDecrypt never seems to be called as far as I can tell. My implementation seems to be working fine and I am a bit puzzled about why the aesDecrypt method was included but not used. Thanks!
Hi,
I like your code, especially because that aren’t many implementations of AES primitives in Python. We find mostly Python interfaces that call C or C++ libraries directly.
Because individual pages get reorganized over time, I usually cannot find back a web page that I previously referenced to inspire my own code because it has moved somewhere else.
Can you migrate your code to a github repository or even better, create a dedicated repository π ?
Can you also change your shebang to “#!/usr/bin/env python”, because some of us have installed python in /usr/local/bin/ (MacosX) or even elsewhere ?
I see that your sbox, sboxInv and rcon lists are hardcoded, I have found an implementation to generate them at https://gist.github.com/jeetsukumaran/1291836 in case you’re interested, the disadvantage is that this developer only used 4 or 5 functions therefore his code is not easy to read but it seems efficient to generate these ‘boxes’.
Can you add a function ‘initAES’ (for instance) that generates them ?
I do know that’s a lot to ask, but please let me know once you have done the first part (migrating your code to github).
Cheers π
I agree with Richard Bagdazian comment. “discovered that in the encrypt and decrypt methods you only call aesEncrypt. aesDecrypt never seems to be called as far as I can tell. ” sboxInv table is never used. The code seems to work anyhow but i dont understand why it works without calling aesDecrypt from decrypt method