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) # # License: Attribution-NonCommercial-ShareAlike 3.0 Unported # (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} paddingTable = {"NoPadding":0, "PKCS7Padding":1} # 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, 0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0, 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, 0x96,0xac,0x74,0x22,0xe7,0xad,0x35,0x85, 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 padding = None # Padding scheme ivEncrypt = None # Initialization ivDecrypt = None # vectors def __init__(self,mode,padding = "NoPadding"): """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: assert padding in AES.paddingTable except AssertionError: print("Padding scheme not supported:",padding) sys.exit(ValueError) self.padding = padding 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)] def addRoundKey (self,subkey,state): """AddRoundKey transformation""" return [i^j for i,j in zip(subkey,state)] xorLists = addRoundKey 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) state = self.addRoundKey(next(key),state) for _ in repeat(None,self.numberOfRounds - 1): state = self.subBytes(state) state = self.shiftRows(state) state = self.mixColumns(state) state = self.addRoundKey(next(key),state) state = self.subBytes(state) state = self.shiftRows(state) state = self.addRoundKey(next(key),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) state = self.addRoundKey(next(key),state) for _ in repeat(None,self.numberOfRounds - 1): state = self.invShiftRows(state) state = self.invSubBytes(state) state = self.addRoundKey(next(key),state) state = self.invMixColumns(state) state = self.invShiftRows(state) state = self.invSubBytes(state) state = self.addRoundKey(next(key),state) return self.stateToList(state) def padData(self,data): """Add PKCS7 padding to plaintext (or just add bytes to fill a block)""" paddingLength = 16-(len(data)%16) if self.padding == "NoPadding": paddingLength %= 16 if type(data) is bytes: return data+bytes(list([paddingLength]*paddingLength)) else: return [ord(s) for s in data]+[paddingLength]*paddingLength def unpadData(self,byteList): """Remove PKCS7 padding (if present) from plaintext""" if self.padding == "PKCS7Padding": 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: inList = self.padData(input) 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: return self.unpadData(outList)
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 # # License: Attribution-NonCommercial-ShareAlike 3.0 Unported # (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).