# HMAC-SHA-256 implementation in Python 3

A hash-based message authentication code (HMAC) is an algorithm for generating a message authentication code (MAC), which can be used to verify both the integrity and the authentication of a given message. Although both constructs, HMAC and MAC, are based on a cryptographic hash function (such as SHA-1, Whirlpool or RIPEMD-160), the former requires a key (shared between the sender and the receiver of the message) while the latter doesn’t. The HMAC concept was proposed by Bellare, Canetti, and Krawczyk in 1996 and is described in RFC 2104.

As seen from its name, HMAC-SHA-256 uses as its engine the SHA-256 cryptographic hash function, which produces message digests of 256 bits in length. Like the other members of the SHA-2 family (and also MD-5 and SHA-1), SHA-256 is an iterative hash function (based on the Merkle–Damgård scheme) that works by breaking up the input message into blocks of a fixed size (512 bits for SHA-256) and iterating over them with a compression function.

```#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: HMAC-SHA256 implementation in Python 3
#
# Date: 2013-06-10
#
#          (CC BY-NC-SA 3.0)
#================================================================

from functools import reduce
from math import log,ceil

def intToList2(number,length):
"""Convert a number into a byte list
with specified length"""
return [(number >> i) & 0xff
for i in reversed(range(0,length*8,8))]

def intToList(number):
"""Converts an integer of any length into an integer list"""
L1 = log(number,256)
L2 = ceil(L1)
if L1 == L2:
L2 += 1
return [(number&(0xff<<8*i))>>8*i for i in reversed(range(L2))]

def listToInt(lst):
"""Convert a byte list into a number"""
return reduce(lambda x,y:(x<<8)+y,lst)

def bitList32ToList4(lst):
"""Convert a 32-bit list into a 4-byte list"""
def bitListToInt(lst):
return reduce(lambda x,y:(x<<1)+y,lst)

lst2 = []
for i in range(0,len(lst),8):
lst2.append(bitListToInt(lst[i:i+8]))
return list([0]*(4-len(lst2)))+lst2

def list4ToBitList32(lst):
"""Convert a 4-byte list into a 32-bit list"""
def intToBitList2(number,length):
"""Convert an integer into a bit list
with specified length"""
return [(number>>n) & 1
for n in reversed(range(length))]

lst2 = []
for e in lst:
lst2 += intToBitList2(e,8)
return list([0]*(32-len(lst2)))+lst2

"""Add up to five 32-bit numbers"""
p2,q2 = listToInt(p), listToInt(q)
if t is None:
if s is None:
if r is None:
else:
r2 = listToInt(r)
else:
r2,s2 = listToInt(r),listToInt(s)
else:
r2,s2,t2 = listToInt(r),listToInt(s),listToInt(t)

def xor(x,y,z=None):
"""Evaluate the XOR on two or three operands"""
if z is None:
return list(i^j for i,j in zip(x,y))
else:
return list(i^j^k for i,j,k in zip(x,y,z))

def sha256(m):
"""Return the SHA-256 digest of input"""
"""Pad message according to SHA-256 rules"""
def bitListToList(lst):
"""Convert a bit list into a byte list"""
lst2 = [0]*((8-len(lst)%8)%8)+lst
return [reduce(lambda x,y:(x<<1)+y,lst2[i*8:i*8+8])
for i in range(len(lst2)//8)]

def intToBitList(number):
"""Convert an integer into a bit list"""
return list(map(int,list(bin(number)[2:])))

if type(m) is int:
m1 = intToBitList(m)
L = len(m1)
k = (447-L)%512
return bitListToList(m1+[1]+list([0]*k))+intToList2(L,8)
else:
m1 = m
if type(m) is str:
m1 = list(map(ord,m))
if not(type(m) is list):
raise TypeError
L = len(m1)*8
k = (447-L)%512
return m1+bitListToList([1]+list([0]*k))+intToList2(L,8)

def compress(m):
"""Evaluates SHA-256 compression function to input"""
def Ch(x,y,z):
return list([(i&j)^((i^0xff)&k) for i,j,k in zip(x,y,z)])

def Maj(x,y,z):
return list([(i&j)^(i&k)^(j&k) for i,j,k in zip(x,y,z)])

def rotRight(p,n):
"""Rotate 32-bit word right by n bits"""
p2 = list4ToBitList32(p)
return bitList32ToList4(p2[-n:]+p2[:-n])

def shiftRight(p,n):
"""Shift 32-bit right by n bits"""
p2 = list4ToBitList32(p)
return bitList32ToList4(list(bytes(n))+p2[:-n])

def Sigma0(p):
"""SHA-256 function"""
return xor(rotRight(p,2),rotRight(p,13),rotRight(p,22))

def Sigma1(p):
"""SHA-256 function"""
return xor(rotRight(p,6),rotRight(p,11),rotRight(p,25))

def sigma0(p):
"""SHA-256 function"""
return xor(rotRight(p,7),rotRight(p,18),shiftRight(p,3))

def sigma1(p):
"""SHA-256 function"""
return xor(rotRight(p,17),rotRight(p,19),shiftRight(p,10))

nonlocal H
[a,b,c,d,e,f,g,h] = H
K = [0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2]
W = [None]*64
for t in range(16):
W[t] = m[t*4:t*4+4]
for t in range(16,64):
for t in range(64):
h = g; g = f; f = e; e = add32(d,T1)
d = c; c = b; b = a; a = add32(T1,T2)
H = [add32(x,y) for x,y in zip([a,b,c,d,e,f,g,h],H)]

H0 = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19]
H = list(map(lambda x:intToList2(x,4),H0))
for i in range(0,len(mp),64):
compress(mp[i:i+64])
return listToInt([s2 for s1 in H for s2 in s1])

def hmac_sha256(k,m):
"""Return the HMAC-SHA-256 of the input
if type(k) is int:
k1 = intToList(k)
L = len(k1)
if L > 64:
K = intToList2(sha256(k),32)+list([0]*32)
else:
K = k1+list([0]*(64-L))
else:
k1 = list(map(ord,k))
L = len(k1)
if L > 64:
K = intToList(sha256(k1))
else:
K = k1+list([0]*(64-L))
if type(m) is int:
M = intToList(m)
else:
M = list(map(ord,m))
return sha256(arg1+intToList(sha256(arg2+M)))

if __name__ == '__main__':

# Wikipedia's test case #1

# Wikipedia's test case #2
assert hmac_sha256("key", "The quick brown fox jumps over the lazy dog") == \
0xf7bc83f430538424b13298e6aa6fb143ef4d59a14946175997479dbc2d1a3cd8

# RFC 4231 - Identifiers and Test Vectors for HMAC-SHA-224, HMAC-SHA-256,
# HMAC-SHA-384, and HMAC-SHA-512

# RFC 4231 Test case 1
Key1 = 0x0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
Data1 = 0x4869205468657265
HMAC1 = 0xb0344c61d8db38535ca8afceaf0bf12b881dc200c9833da726e9376c2e32cff7
assert hmac_sha256(Key1,Data1) == HMAC1

# RFC 4231 Test case 2
Key2 = 0x4a656665
Data2 = 0x7768617420646f2079612077616e7420666f72206e6f7468696e673f
HMAC2 = 0x5bdcc146bf60754e6a042426089575c75a003f089d2739839dec58b964ec3843
assert hmac_sha256(Key2,Data2) == HMAC2

# RFC 4231 Test case 3
Key3 = 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Data3 = 0xdddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
HMAC3 = 0x773ea91e36800e46854db8ebd09181a72959098b3ef8c122d9635514ced565fe
assert hmac_sha256(Key3,Data3) == HMAC3

# RFC 4231 Test case 4
Key4 = 0x0102030405060708090a0b0c0d0e0f10111213141516171819
Data4 = 0xcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcdcd
HMAC4 = 0x82558a389a443c0ea4cc819899f2083a85f0faa3e578f8077a2e3ff46729665b
assert hmac_sha256(Key4,Data4) == HMAC4

# RFC 4231 Test case 5
Key5 = 0x0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c0c
Data5 = 0x546573742057697468205472756e636174696f6e
HMAC5 = 0xa3b6167473100ee06e0c796c2955552b
assert hmac_sha256(Key5,Data5)>>128 == HMAC5

# RFC 4231 Test case 6
Key6 = 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Data6 = 0x54657374205573696e67204c6172676572205468616e20426c6f636b2d53697a65204b6579202d2048617368204b6579204669727374
HMAC6 = 0x60e431591ee0b67f0d8a26aacbf5b77f8e0bc6213728c5140546040f0ee37f54
assert hmac_sha256(Key6,Data6) == HMAC6

# RFC 4231 Test case 7
Key7 = 0xaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Data7 = 0x5468697320697320612074657374207573696e672061206c6172676572207468616e20626c6f636b2d73697a65206b657920616e642061206c6172676572207468616e20626c6f636b2d73697a6520646174612e20546865206b6579206e6565647320746f20626520686173686564206265666f7265206265696e6720757365642062792074686520484d414320616c676f726974686d2e
HMAC7 = 0x9b09ffa71b942fcb27635fbcd5b0e944bfdc63644f0713938a7f51535c3a35e2
assert hmac_sha256(Key7,Data7) == HMAC7

print("Ok!")
```

# Validation of an AES-CFB implementation in Python 3

A symmetric block cipher such as AES (or Triple DES) operates on blocks of fixed size (128 bits for AES and 64 bits for TDES). It is possible, however, to convert a block cipher into a stream cipher using one of the three following modes: cipher feedback (CFB), output feedback (OFB), and counter (CTR). A stream cipher eliminates the need to pad a message to be an integral number of blocks and, for this reason, can operate in real time, making it the natural choice for encrypting streaming data (e.g. voice).

The Python code shown below implements the encryption and decryption operations for CFB-8 and CFB-128 modes. These functions rely on the “basic” AES mode (ECB) services provided by sundAES, an AES implementation in Python presented in a previous blog.

```#!/usr/bin/python3

import sys
from functools import reduce
import sundAES

# Auxiliary functions

def xor(x,y):
"""Returns the xor between two lists"""
return bytes(i^j for i,j in zip(x,y))

def bytesToInt(b):
"""Converts a bytes string into an integer"""
return listToInt(list(b))

def listToInt(lst):
"""Convert a byte list into a number"""
return reduce(lambda x,y:(x<<8)+y,lst)

def intToList(number):
"""Converts an integer into an integer list"""
if number == 0:
return [0]
lst = []
while number:
lst += [number&0xff]
number >>= 8
return lst[::-1]

def intToBytes(number):
"""Converts an integer into a bytes list"""
return bytes(intToList(number))

def intToList2(number,length=None):
"""Converts an integer into an integer list with
16, 24 or 32 elements"""
lst = []
while number:
lst.append(number&0xff)
number >>= 8
L = len(lst)
if length:
pZero = length-L
assert pZero >= 0
else:
if L <= 16:
pZero = 16-L
elif L <= 24:
pZero = 24-L
elif L <= 32:
pZero = 32-L
else:
raise ValueError
return list(bytes(pZero)) + lst[::-1]

def intToBytes2(number,length=None):
"""Converts an integer into a bytes list with
16, 24 or 32 elements"""
return bytes(intToList2(number,length))

# Real crypto stuff starts here...

def encryptCFB8(keysize,key,iv,input):
"""Encrypts single bytes of input block (CFB8 mode)"""
inputBuffer = intToBytes2(iv)
if type(input) is int:
ptext = intToBytes(input)
else:
ptext = bytes(map(ord,input))
obj = sundAES.AES("MODE_ECB")
obj.setKey(keysize,key,iv)
ctext = bytes()
for i in range(0,len(ptext),1):
AESoutput = obj.encrypt(inputBuffer)
cbyte = bytes([AESoutput[0] ^ ptext[i]])
inputBuffer = inputBuffer[1:] + cbyte
ctext += cbyte
if type(input) is int:
ctext = bytesToInt(ctext)
else:
ctext = list(ctext)
return ctext

def decryptCFB8(keysize,key,iv,input):
"""Decrypts single bytes of input block (CFB8 mode)"""
inputBuffer = intToBytes2(iv)
if type(input) is int:
ctext = intToBytes(input)
else:
ctext = bytes(map(ord,input))
obj = sundAES.AES("MODE_ECB")
obj.setKey(keysize,key,iv)
ptext = bytes()
for i in range(0,len(ctext),1):
AESoutput = obj.encrypt(inputBuffer)
pbyte = bytes([AESoutput[0] ^ ctext[i]])
inputBuffer = inputBuffer[1:] + bytes(ctext[i])
ptext += pbyte
if type(input) is int:
ptext = bytesToInt(ptext)
else:
ptext = "".join(chr(e) for e in ptext)
return ptext

# ... and goes on here

def encryptCFB128(keysize,key,iv,input):
"""Encrypts a 16-byte input block (CFB128 mode)"""
inputBuffer = intToBytes2(iv)
if type(input) is int:
ptext = intToList2(input)
else:
ptext = list(map(ord,input))
L = 16-len(ptext)
ptext = list(bytes(L)) + ptext
obj = sundAES.AES("MODE_ECB")
obj.setKey(keysize,key,iv)
ctext = bytes()
L3 = len(ptext)
for i in range(0,L3,16):
AESoutput = obj.encrypt(inputBuffer)
inputBuffer = xor(AESoutput,ptext[i:min(L3,i+16)])
ctext += bytes(inputBuffer)
if type(input) is int:
ctext = bytesToInt(ctext)
else:
ctext = list(ctext)
return ctext

def decryptCFB128(keysize,key,iv,input):
"""Decrypts a 16-byte input block (CFB128 mode)"""
inputBuffer = intToBytes2(iv)
if type(input) is int:
ctext = intToList2(input)
else:
ctext = list(map(ord,input))
L = 16-len(ctext)
ctext = list(bytes(L)) + ctext
obj = sundAES.AES("MODE_ECB")
obj.setKey(keysize,key,iv)
ptext = bytes()
L3 = len(ctext)
for i in range(0,L3,16):
AESoutput = obj.encrypt(inputBuffer)
inputBuffer = ctext[i:min(L3,i+16)]
ptextBlock = xor(AESoutput,inputBuffer)
ptext += ptextBlock
if type(input) is int:
ptext = bytesToInt(ptext)
else:
ptext = "".join(chr(e) for e in ptext)
return ptext
```

CFB8 encrypts (or decrypts) a single byte while CFB128 operates on a 16-byte block. Like the other stream modes (OFB and CTR), and differently from Electronic codebook (ECB) and Cipher block chaining (CBC) “block modes”, CFB dispenses padding and uses only the ECB encryption operation. This latter feature is very convenient for AES, since AES encryption and decryption operations are somewhat different.

The US National Institute of Standards and Technology (NIST) defines four types of Known Answer Test (KAT): GFSbox, KeySbox, Variable Key and Variable Text. The contents of file `CFB8GFSbox128.rsp` (see below) describe the GFSbox encryption and decryption tests cases for CFB8 using 128-bits AES keys.

```# CAVS 11.1
# Config info for aes_values
# AESVS GFSbox test data for CFB8
# State : Encrypt and Decrypt
# Key Length : 128
# Generated on Fri Apr 22 15:11:46 2011

[ENCRYPT]

COUNT = 0
KEY = 00000000000000000000000000000000
IV = f34481ec3cc627bacd5dc3fb08f273e6
PLAINTEXT = 00
CIPHERTEXT = 03

... 5 test cases omitted

[DECRYPT]

COUNT = 0
KEY = 00000000000000000000000000000000
IV = f34481ec3cc627bacd5dc3fb08f273e6
CIPHERTEXT = 03
PLAINTEXT = 00

... 5 test cases omitted
```

As a second example, the contents of file `CFB128VarKey192.rsp` file that follow describe the Variable Key encryption and decryption tests cases for the CFB128 mode using 192-bits AES keys.

```# CAVS 11.1
# Config info for aes_values
# AESVS VarKey test data for CFB128
# State : Encrypt and Decrypt
# Key Length : 192
# Generated on Fri Apr 22 15:11:55 2011

[ENCRYPT]

COUNT = 0
KEY = 800000000000000000000000000000000000000000000000
IV = 00000000000000000000000000000000
PLAINTEXT = 00000000000000000000000000000000
CIPHERTEXT = de885dc87f5a92594082d02cc1e1b42c

... 190 test cases omitted

[DECRYPT]

COUNT = 0
KEY = 800000000000000000000000000000000000000000000000
IV = 00000000000000000000000000000000
CIPHERTEXT = de885dc87f5a92594082d02cc1e1b42c
PLAINTEXT = 00000000000000000000000000000000

... 190 test cases omitted
```

Next is presented the Python program that extracts data from the files contained in the KAT_AES directory which names start with “CFB8” or “CFB128”, then builds the test cases and finally executes them.

```#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: Validation of AES-CFB8 and AES-CFB128
#              implementations in Python
#
# Date: 2013-06-05
#
#          (CC BY-NC-SA 3.0)
#===========================================================

import os,sys,re
from functools import reduce
from glob import glob
import AES_CFB

# Global counters
noFilesTested = noFilesSkipped = 0
counterOK = counterNOK = 0

class AEStester:
def buildTestCases(self,filename):
"""Build test cases described in a given file"""
global noFilesTested,noFilesSkipped

self.basename = os.path.basename(filename)
if self.basename.startswith('CFB'):
if self.basename.startswith('CFB8'):
self.mode = "MODE_CFB8"
result = re.search("CFB8(\D{6,})\d{3}",self.basename)
self.typeTest = result.group(1)
elif self.basename.startswith('CFB128'):
self.mode = "MODE_CFB128"
result = re.search("CFB128(\D{6,})\d{3}",self.basename)
self.typeTest = result.group(1)
else: # CFB1 files not considered
noFilesSkipped += 1
return
else: # not CFB files
noFilesSkipped += 1
return

noFilesTested += 1
digits = re.search("(\d{3})\.",self.basename)
self.keysize = 'SIZE_' + digits.group(1)
self.iv = None
for line in open(filename):
line = line.strip()
if (line == "") or line.startswith('#'):
continue
elif line == '[ENCRYPT]':
self.operation = 'encrypt'
continue
elif line == '[DECRYPT]':
self.operation = 'decrypt'
continue
param,_,value = line.split(' ',2)
if param == "COUNT":
self.count = int(value)
continue
else:
self.__setattr__(param.lower(),int(value,16))
if (self.operation == 'encrypt') and (param == "CIPHERTEXT") or \
(self.operation == 'decrypt' and param == "PLAINTEXT"):
self.runTestCase()

def runTestCase(self):
"""Execute test case and report result"""
global counterOK,counterNOK

def printTestCase(result):
print("Type={0:s} Mode={1:s} Keysize={2:s} Function={3:s} Count={4:03d} {5:s}"\
.format(self.typeTest,self.mode[5:],\
self.keysize[5:],self.operation.upper(),\
self.count,result))
if self.operation == 'encrypt':
if self.mode == "MODE_CFB8":
CIPHERTEXT = AES_CFB5.encryptCFB8(self.keysize,self.key,self.iv,self.plaintext)
else:
CIPHERTEXT = AES_CFB5.encryptCFB128(self.keysize,self.key,self.iv,self.plaintext)
try:
assert self.ciphertext == CIPHERTEXT
counterOK += 1
printTestCase("OK")
except AssertionError:
counterNOK +=1
print(self.basename,end=" ")
printTestCase("failed")
print("Expected ciphertext={0:0x}".format(self.ciphertext))
print("Returned ciphertext={0:0x}".format(CIPHERTEXT))
else:
if self.mode == "MODE_CFB8":
PLAINTEXT = AES_CFB5.decryptCFB8(self.keysize,self.key,self.iv,self.ciphertext)
else:
PLAINTEXT = AES_CFB5.decryptCFB128(self.keysize,self.key,self.iv,self.ciphertext)
try:
assert self.plaintext == PLAINTEXT
counterOK += 1
printTestCase("OK")
except AssertionError:
counterNOK +=1
print(self.basename,end=" ")
printTestCase("failed")
print("Expected plaintext={0:0x}".format(self.plaintext))
print("Returned plaintext={0:0x}".format(PLAINTEXT))

if __name__ == '__main__':
path = os.path.dirname(__file__)
files = sys.argv[1:]
if not files:
files = glob(os.path.join(path,'KAT_AES','*.rsp'))
files.sort()
for file in files:
AEStester().buildTestCases(file)
print("Files tested={0:d}".format(noFilesTested))
print("Files skipped={0:d}".format(noFilesSkipped))
print("Test cases OK={0:d}".format(counterOK))
print("Test cases NOK={0:d}".format(counterNOK))
```

This program, when executed without arguments, will generate the following report:

```Type=GFSbox Mode=CFB128 Keysize=128 Function=ENCRYPT Count=000 OK
Type=GFSbox Mode=CFB128 Keysize=128 Function=ENCRYPT Count=001 OK
Type=GFSbox Mode=CFB128 Keysize=128 Function=ENCRYPT Count=002 OK
Type=GFSbox Mode=CFB128 Keysize=128 Function=ENCRYPT Count=003 OK
Type=GFSbox Mode=CFB128 Keysize=128 Function=ENCRYPT Count=004 OK

... 4,146 test cases omitted

Type=VarTxt Mode=CFB8 Keysize=256 Function=DECRYPT Count=123 OK
Type=VarTxt Mode=CFB8 Keysize=256 Function=DECRYPT Count=124 OK
Type=VarTxt Mode=CFB8 Keysize=256 Function=DECRYPT Count=125 OK
Type=VarTxt Mode=CFB8 Keysize=256 Function=DECRYPT Count=126 OK
Type=VarTxt Mode=CFB8 Keysize=256 Function=DECRYPT Count=127 OK
Files tested=24
Files skipped=48
Test cases OK=4156
Test cases NOK=0
```

# Validation of an AES implementation in Python 3

The Cryptographic Algorithm Validation Program (CAVP) defines validation testing for cryptographic algorithms approved by the US National Institute of Standards and Technology (NIST). All of the tests under CAVP, established by NIST and its Canadian counterpart (CSEC) in 1995, are handled by accredited third-party laboratories.

To assist prospective vendors in checking their implementations, NIST provides electronic versions of the vectors for the Known Answer Test (KAT) for the three NIST-approved symmetric cryptographic algorithms: AES, Triple-DES, and Skipjack. Also available are sample values for the Monte Carlo (MCT) test and the Multiblock Message (MMT) test for the same algorithms, thus completing the set of tests a cryptographic implementation (dubbed “Implementation Under Test”) will face during a formal validation. A detailed account of the procedures involved in validating AES implementations can be found in the NIST document The Advanced Encryption Standard Algorithm Validation Suite (AESAVS).

The NIST KAT validation suite for AES contains 72 files describing test vectors for different AES modes of operation: ECB (Electronic Codebook), CBC (Cipher Block Chaining), CFB (Cipher Feedback) and OFB (Output Feedback). Besides this partition, there are also separated tests for AES encryption and decryption, exemplified by the abridged contents of the file `ECBKeySbox128.rsp` (see below).

```# CAVS 11.1
# Config info for aes_values
# AESVS KeySbox test data for ECB
# State : Encrypt and Decrypt
# Key Length : 128
# Generated on Fri Apr 22 15:11:26 2011

[ENCRYPT]

COUNT = 0
KEY = 10a58869d74be5a374cf867cfb473859
PLAINTEXT = 00000000000000000000000000000000
CIPHERTEXT = 6d251e6944b051e04eaa6fb4dbf78465

COUNT = 1
KEY = caea65cdbb75e9169ecd22ebe6e54675
PLAINTEXT = 00000000000000000000000000000000
CIPHERTEXT = 6e29201190152df4ee058139def610bb

... (18 test cases omitted)

[DECRYPT]

COUNT = 0
KEY = 10a58869d74be5a374cf867cfb473859
CIPHERTEXT = 6d251e6944b051e04eaa6fb4dbf78465
PLAINTEXT = 00000000000000000000000000000000

COUNT = 1
KEY = caea65cdbb75e9169ecd22ebe6e54675
CIPHERTEXT = 6e29201190152df4ee058139def610bb
PLAINTEXT = 00000000000000000000000000000000

... (18 test cases omitted)
```

These vectors can be used to informally verify the correctness of an AES implementation, such as the one presented below, which successfully passed all 4,156 KAT tests involving ECB and CBC modes. This Python code differs from the one already presented in a previous blog only with respect to the input/output types accepted: if the input plaintext (ciphertext) is of integer type, so will be the correspondent ciphertext (plaintext) output. This feature simplifies validation testing, since the integer plaintexts and ciphertexts usually employed in those scenarios can be deal with directly without any type conversion.

```#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: AES implementation in Python 3
#              (sundAES)
#
# Date: 2013-06-02 (version 1.1)
#       2012-01-16 (version 1.0)
#
#          (CC BY-NC-SA 3.0)
#===========================================================
import sys
from itertools import repeat
from functools import reduce
from copy import copy

__all__ = ["setKey","encrypt","decrypt"]

def memoize(func):
"""Memoization function"""
memo = {}
def helper(x):
if x not in memo:
memo[x] = func(x)
return memo[x]
return helper

def mult(p1,p2):
"""Multiply two polynomials in GF(2^8)/x^8+x^4+x^3+x+1"""
p = 0
while p2:
if p2&0x01:
p ^= p1
p1 <<= 1
if p1&0x100:
p1 ^= 0x1b
p2 >>= 1
return p&0xff

# Auxiliary one-parameter functions defined for memoization
# (to speed up multiplication in GF(2^8))

@memoize
def x2(y):
"""Multiplication by 2"""
return mult(2,y)

@memoize
def x3(y):
"""Multiplication by 3"""
return mult(3,y)

@memoize
def x9(y):
"""Multiplication by 9"""
return mult(9,y)

@memoize
def x11(y):
"""Multiplication by 11"""
return mult(11,y)

@memoize
def x13(y):
"""Multiplication by 13"""
return mult(13,y)

@memoize
def x14(y):
"""Multiplication by 14"""
return mult(14,y)

class AES:
"""Class definition for AES objects"""
keySizeTable = {"SIZE_128":16,
"SIZE_192":24,
"SIZE_256":32}
wordSizeTable = {"SIZE_128":44,
"SIZE_192":52,
"SIZE_256":60}
numberOfRoundsTable = {"SIZE_128":10,
"SIZE_192":12,
"SIZE_256":14}
cipherModeTable = {"MODE_ECB":1,
"MODE_CBC":2}
# S-Box
sBox = (0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,
0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,
0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,
0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,
0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,
0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,
0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,
0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,
0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,
0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,
0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,
0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,
0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,
0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,
0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,
0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,
0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,
0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,
0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,
0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,
0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,
0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,
0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,
0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,
0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16)
# Inverse S-Box
invSBox = (0x52,0x09,0x6a,0xd5,0x30,0x36,0xa5,0x38,
0xbf,0x40,0xa3,0x9e,0x81,0xf3,0xd7,0xfb,
0x7c,0xe3,0x39,0x82,0x9b,0x2f,0xff,0x87,
0x34,0x8e,0x43,0x44,0xc4,0xde,0xe9,0xcb,
0x54,0x7b,0x94,0x32,0xa6,0xc2,0x23,0x3d,
0xee,0x4c,0x95,0x0b,0x42,0xfa,0xc3,0x4e,
0x08,0x2e,0xa1,0x66,0x28,0xd9,0x24,0xb2,
0x76,0x5b,0xa2,0x49,0x6d,0x8b,0xd1,0x25,
0x72,0xf8,0xf6,0x64,0x86,0x68,0x98,0x16,
0xd4,0xa4,0x5c,0xcc,0x5d,0x65,0xb6,0x92,
0x6c,0x70,0x48,0x50,0xfd,0xed,0xb9,0xda,
0x5e,0x15,0x46,0x57,0xa7,0x8d,0x9d,0x84,
0x90,0xd8,0xab,0x00,0x8c,0xbc,0xd3,0x0a,
0xf7,0xe4,0x58,0x05,0xb8,0xb3,0x45,0x06,
0xd0,0x2c,0x1e,0x8f,0xca,0x3f,0x0f,0x02,
0xc1,0xaf,0xbd,0x03,0x01,0x13,0x8a,0x6b,
0x3a,0x91,0x11,0x41,0x4f,0x67,0xdc,0xea,
0x97,0xf2,0xcf,0xce,0xf0,0xb4,0xe6,0x73,
0xe2,0xf9,0x37,0xe8,0x1c,0x75,0xdf,0x6e,
0x47,0xf1,0x1a,0x71,0x1d,0x29,0xc5,0x89,
0x6f,0xb7,0x62,0x0e,0xaa,0x18,0xbe,0x1b,
0xfc,0x56,0x3e,0x4b,0xc6,0xd2,0x79,0x20,
0x9a,0xdb,0xc0,0xfe,0x78,0xcd,0x5a,0xf4,
0x1f,0xdd,0xa8,0x33,0x88,0x07,0xc7,0x31,
0xb1,0x12,0x10,0x59,0x27,0x80,0xec,0x5f,
0x60,0x51,0x7f,0xa9,0x19,0xb5,0x4a,0x0d,
0x2d,0xe5,0x7a,0x9f,0x93,0xc9,0x9c,0xef,
0xa0,0xe0,0x3b,0x4d,0xae,0x2a,0xf5,0xb0,
0xc8,0xeb,0xbb,0x3c,0x83,0x53,0x99,0x61,
0x17,0x2b,0x04,0x7e,0xba,0x77,0xd6,0x26,
0xe1,0x69,0x14,0x63,0x55,0x21,0x0c,0x7d)

# Instance variables
wordSize = None
w = [None]*60 # Round subkeys list
keyDefined = None # Key definition flag
numberOfRounds = None
cipherMode = None
ivEncrypt = None # Initialization
ivDecrypt = None #  vectors

"""Create a new instance of an AES object"""
try:
assert mode in AES.cipherModeTable
except AssertionError:
print("Cipher mode not supported:",mode)
sys.exit("ValueError")
self.cipherMode = mode
try:
except AssertionError:
sys.exit(ValueError)
self.keyDefined = False

def intToList(self,number):
"""Convert an 16-byte number into a 16-element list"""
return [(number>>i)&0xff for i in reversed(range(0,128,8))]

def intToList2(self,number):
"""Converts an integer into one (or more) 16-element list"""
lst = []
while number:
lst.append(number&0xff)
number >>= 8
m = len(lst)%16
if m == 0 and len(lst) != 0:
return lst[::-1]
else:
return list(bytes(16-m)) + lst[::-1]

def listToInt(self,lst):
"""Convert a list into a number"""
return reduce(lambda x,y:(x<<8)+y,lst)

def wordToState(self,wordList):
"""Convert list of 4 words into a 16-element state list"""
return [(wordList[i]>>j)&0xff
for j in reversed(range(0,32,8)) for i in range(4)]

def listToState(self,list):
"""Convert a 16-element list into a 16-element state list"""
return [list[i+j] for j in range(4) for i in range(0,16,4)]

stateToList = listToState # this function is an involution

def subBytes(self,state):
"""SubBytes transformation"""
return [AES.sBox[e] for e in state]

def invSubBytes(self,state):
"""Inverse SubBytes transformation"""
return [AES.invSBox[e] for e in state]

def shiftRows(self,s):
"""ShiftRows transformation"""
return s[:4]+s[5:8]+s[4:5]+s[10:12]+s[8:10]+s[15:]+s[12:15]

def invShiftRows(self,s):
"""Inverse ShiftRows transformation"""
return s[:4]+s[7:8]+s[4:7]+s[10:12]+s[8:10]+s[13:]+s[12:13]

def mixColumns(self,s):
"""MixColumns transformation"""
return [x2(s[i])^x3(s[i+4])^   s[i+8] ^   s[i+12]  for i in range(4)]+ \
[   s[i] ^x2(s[i+4])^x3(s[i+8])^   s[i+12]  for i in range(4)]+ \
[   s[i] ^   s[i+4] ^x2(s[i+8])^x3(s[i+12]) for i in range(4)]+ \
[x3(s[i])^   s[i+4] ^   s[i+8] ^x2(s[i+12]) for i in range(4)]

def invMixColumns(self,s):
"""Inverse MixColumns transformation"""
return [x14(s[i])^x11(s[i+4])^x13(s[i+8])^ x9(s[i+12]) for i in range(4)]+ \
[ x9(s[i])^x14(s[i+4])^x11(s[i+8])^x13(s[i+12]) for i in range(4)]+ \
[x13(s[i])^ x9(s[i+4])^x14(s[i+8])^x11(s[i+12]) for i in range(4)]+ \
[x11(s[i])^x13(s[i+4])^ x9(s[i+8])^x14(s[i+12]) for i in range(4)]

return [i^j for i,j in zip(subkey,state)]

def rotWord(self,number):
"""Rotate subkey left"""
return (((number&0xff000000)>>24) +
((number&0xff0000)<<8) +
((number&0xff00)<<8) +
((number&0xff)<<8))

def subWord(self,key):
"""Substitute subkeys bytes using S-box"""
return ((AES.sBox[(key>>24)&0xff]<<24) +
(AES.sBox[(key>>16)&0xff]<<16) +
(AES.sBox[(key>>8)&0xff]<<8) +
AES.sBox[key&0xff])

def setKey(self,keySize,key,iv = None):
"""KeyExpansion transformation"""
rcon = (0x00,0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x1B,0x36)
try:
assert keySize in AES.keySizeTable
except AssertionError:
print("Key size identifier not valid")
sys.exit("ValueError")
try:
assert isinstance(key,int)
except AssertionError:
print("Invalid key")
sys.exit("ValueError")
klen = len("{:02x}".format(key))//2
try:
assert klen <= AES.keySizeTable[keySize]
except AssertionError:
print("Key size mismatch")
sys.exit("ValueError")
try:
assert ((self.cipherMode == "MODE_CBC" and isinstance(iv,int)) or
self.cipherMode == "MODE_ECB")
except AssertionError:
print("IV is mandatory for CBC mode")
sys.exit(ValueError)

if self.cipherMode == "MODE_CBC":
temp = self.intToList(iv)
self.ivEncrypt = copy(temp)
self.ivDecrypt = copy(temp)
nr = AES.numberOfRoundsTable[keySize]
self.numberOfRounds = nr
self.wordSize = AES.wordSizeTable[keySize]
if nr == 10:
nk = 4
keyList = self.intToList(key)
elif nr == 12:
nk = 6
keyList =  self.intToList(key>>64) + \
(self.intToList(key&int("ff"*32,16)))[8:]
else:
nk = 8
keyList =  self.intToList(key>>128) + \
self.intToList(key&int("ff"*64,16))
for index in range(nk):
self.w[index] =  (keyList[4*index]<<24) + \
(keyList[4*index+1]<<16) + \
(keyList[4*index+2]<<8) +\
keyList[4*index+3]
for index in range(nk,self.wordSize):
temp = self.w[index - 1]
if index % nk == 0:
temp = (self.subWord(self.rotWord(temp)) ^
rcon[index//nk]<<24)
elif self.numberOfRounds == 14 and index%nk == 4:
temp = self.subWord(temp)
self.w[index] = self.w[index-nk]^temp
self.keyDefined = True
return

def getKey(self,operation):
"""Return next round subkey for encryption or decryption"""
if operation == "encryption":
for i in range(0,self.wordSize,4):
yield self.wordToState(self.w[i:i+4])
else: # operation = "decryption":
for i in reversed(range(0,self.wordSize,4)):
yield self.wordToState(self.w[i:i+4])

def encryptBlock(self,plaintextBlock):
"""Encrypt a 16-byte block with key already defined"""
key = self.getKey("encryption")
state = self.listToState(plaintextBlock)
for _ in repeat(None,self.numberOfRounds - 1):
state = self.subBytes(state)
state = self.shiftRows(state)
state = self.mixColumns(state)
state = self.subBytes(state)
state = self.shiftRows(state)
return self.stateToList(state)

def decryptBlock(self,ciphertextBlock):
"""Decrypt a 16-byte block with key already defined"""
key = self.getKey("decryption")
state = self.listToState(ciphertextBlock)
for _ in repeat(None,self.numberOfRounds - 1):
state = self.invShiftRows(state)
state = self.invSubBytes(state)
state = self.invMixColumns(state)
state = self.invShiftRows(state)
state = self.invSubBytes(state)
return self.stateToList(state)

if type(data) is bytes:
else:

"""Remove PKCS7 padding (if present) from plaintext"""
return "".join(chr(e) for e in byteList[:-byteList[-1]])
else:
return "".join(chr(e) for e in byteList)

def encrypt(self,input):
"""Encrypt plaintext passed as a string or as an integer"""
try:
assert self.keyDefined
except AssertionError:
print("Key not defined")
sys.exit("ValueError")

if type(input) is int:
inList = self.intToList2(input)
else:
outList = []
if self.cipherMode == "MODE_CBC":
outBlock = self.ivEncrypt
for i in range(0,len(inList),16):
auxList = self.xorLists(outBlock,inList[i:i+16])
outBlock = self.encryptBlock(auxList)
outList += outBlock
self.ivEncrypt = outBlock
else:
for i in range(0,len(inList),16):
outList += self.encryptBlock(inList[i:i+16])
if type(input) is int:
return self.listToInt(outList)
else:
return outList

def decrypt(self,input):
"""Decrypt ciphertext passed as a string or as an integer"""
try:
assert self.keyDefined
except AssertionError:
print("Key not defined")
sys.exit("ValueError")
if type(input) is int:
inList = self.intToList2(input)
else:
inList = input
outList = []
if self.cipherMode == "MODE_CBC":
oldInBlock = self.ivDecrypt
for i in range(0,len(inList),16):
newInBlock = inList[i:i+16]
auxList = self.decryptBlock(newInBlock)
outList += self.xorLists(oldInBlock,auxList)
oldInBlock = newInBlock
self.ivDecrypt = oldInBlock
else:
for i in range(0,len(inList),16):
outList += self.decryptBlock(inList[i:i+16])
if type(input) is int:
return self.listToInt(outList)
else:
```

The Python program below extracts data from the files contained in the KAT_AES directory, then builds the test cases and finally executes them. Only the files applicable to ECB and CBC operation modes (the modes supported by this AES implementation) are considered.

```#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: Validation of an AES implementation in Python
#
# Date: 2013-06-02
#
#          (CC BY-NC-SA 3.0)
#===========================================================

import os,sys,re
from functools import reduce
from glob import glob
import sundAES

# Global counters
noFilesTested = noFilesSkipped = 0
counterOK = counterNOK = 0

class AEStester:
""""""
def buildTestCases(self,filename):
"""Build test cases described in a given file"""
global noFilesTested,noFilesSkipped

self.basename = os.path.basename(filename)
if self.basename.startswith('ECB'):
self.mode = "MODE_ECB"
noFilesTested += 1
elif self.basename.startswith('CBC'):
self.mode = "MODE_CBC"
noFilesTested += 1
else:
noFilesSkipped += 1
return

digits = re.search("\d{3}",self.basename)
self.keysize = 'SIZE_' + digits.group()
result = re.search("CFB\d*(\D{6,})\d{3}",self.basename)
if result != None:
self.typeTest = result.group(1)
self.typeTest = re.search("\w{3}(\D{6,})\d{3}",self.basename).group(1)
self.iv = None
for line in open(filename):
line = line.strip()
if (line == "") or line.startswith('#'):
continue
elif line == '[ENCRYPT]':
self.operation = 'encrypt'
continue
elif line == '[DECRYPT]':
self.operation = 'decrypt'
continue
param,_,value = line.split(' ',2)
if param == "COUNT":
self.count = int(value)
continue
else:
self.__setattr__(param.lower(),int(value,16))
if (self.operation == 'encrypt') and (param == "CIPHERTEXT") or \
(self.operation == 'decrypt' and param == "PLAINTEXT"):
self.runTestCase()

def runTestCase(self):
"""Execute test case and report result"""
global counterOK,counterNOK

def printTestCase(result):
print("Type={0:s} Mode={1:s} Keysize={2:s} Function={3:s} Count={4:03d} {5:s}"\
.format(self.typeTest,self.mode[5:],\
self.keysize[5:],self.operation.upper(),\
self.count,result))

obj = sundAES3.AES(self.mode)
obj.setKey(self.keysize,self.key,self.iv)
if self.operation == 'encrypt':
CIPHERTEXT = obj.encrypt(self.plaintext)
try:
assert self.ciphertext == CIPHERTEXT
counterOK += 1
printTestCase("OK")
except AssertionError:
counterNOK +=1
print(self.basename)
printTestCase("failed")
print("Expected ciphertext={0:0x}".format(self.ciphertext))
print("Returned ciphertext={0:0x}".format(CIPHERTEXT))
else:
PLAINTEXT = obj.decrypt(self.ciphertext)
try:
assert self.plaintext == PLAINTEXT
counterOK += 1
printTestCase("OK")
except AssertionError:
counterNOK +=1
print(self.basename)
printTestCase("failed")
print("Expected plaintext={0:0x}".format(self.plaintext))
print("Returned plaintext={0:0x}".format(PLAINTEXT))

# Main program
path = os.path.dirname(__file__)
files = sys.argv[1:]
if not files:
files = glob(os.path.join(path,'KAT_AES','*.rsp'))
files.sort()
for file in files:
AEStester().buildTestCases(file)
print("Files tested={0:d}".format(noFilesTested))
print("Files skipped={0:d}".format(noFilesSkipped))
print("Test cases OK={0:d}".format(counterOK))
print("Test cases NOK={0:d}".format(counterNOK))
```

Executed without arguments, this program will apply all ECB and CBC tests described in the files against the AES implementation, producing the following output:

```Type=GFSbox Mode=CBC Keysize=128 Function=ENCRYPT Count=000 OK
Type=GFSbox Mode=CBC Keysize=128 Function=ENCRYPT Count=001 OK
Type=GFSbox Mode=CBC Keysize=128 Function=ENCRYPT Count=002 OK
Type=GFSbox Mode=CBC Keysize=128 Function=ENCRYPT Count=003 OK
Type=GFSbox Mode=CBC Keysize=128 Function=ENCRYPT Count=004 OK

... (4,147 lines omitted)

Type=VarTxt Mode=ECB Keysize=256 Function=DECRYPT Count=124 OK
Type=VarTxt Mode=ECB Keysize=256 Function=DECRYPT Count=125 OK
Type=VarTxt Mode=ECB Keysize=256 Function=DECRYPT Count=126 OK
Type=VarTxt Mode=ECB Keysize=256 Function=DECRYPT Count=127 OK
Files tested=24
Files skipped=48
Test cases OK=4156
Test cases NOK=0
```

If, however, this program is run with one or more files in the KAT_AES directory as argument(s), it will instead build and execute the tests contained in the indicated file(s).