src/CryptoPlus/Cipher/blockcipher.py

   1 # =============================================================================
   2 # Copyright (c) 2008 Christophe Oosterlynck (christophe.oosterlynck@gmail.com)
   3 #                    Philippe Teuwen (philippe.teuwen@nxp.com)
   4 #
   5 # Permission is hereby granted, free of charge, to any person obtaining a copy
   6 # of this software and associated documentation files (the "Software"), to deal
   7 # in the Software without restriction, including without limitation the rights
   8 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   9 # copies of the Software, and to permit persons to whom the Software is
  10 # furnished to do so, subject to the following conditions:
  11 #
  12 # The above copyright notice and this permission notice shall be included in
  13 # all copies or substantial portions of the Software.
  14 #
  15 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20 # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  21 # THE SOFTWARE.
  22 # =============================================================================
  23 from ..Util import util
  24 from array import array
  25 from ..Util import padding
  26
  27 MODE_ECB = 1
  28 MODE_CBC = 2
  29 MODE_CFB = 3
  30 MODE_OFB = 5
  31 MODE_CTR = 6
  32 MODE_XTS = 7
  33 MODE_CMAC = 8
  34
  35 class BlockCipher():
  36     """ Base class for all blockciphers
  37     """
  38
  39     key_error_message = "Wrong key size" #should be overwritten in child classes
  40
  41     def __init__(self,key,mode,IV,counter,cipher_module,args={}):
  42         # Cipher classes inheriting from this one take care of:
  43         #   self.blocksize
  44         #   self.cipher
  45         self.key = key
  46         self.mode = mode
  47         self.cache = ''
  48         self.ed = None
  49
  50         if 'keylen_valid' in dir(self): #wrappers for pycrypto functions don't have this function
  51          if not self.keylen_valid(key) and type(key) is not tuple:
  52                 raise ValueError(self.key_error_message)
  53
  54         if mode <> MODE_XTS:
  55             self.cipher = cipher_module(self.key,**args)
  56         if mode == MODE_ECB:
  57             self.chain = ECB(self.cipher, self.blocksize)
  58         elif mode == MODE_CBC:
  59             if IV == None:
  60                 raise Exception,"Provide an IV!"
  61             if len(IV) <> self.blocksize:
  62                 raise Exception,"the IV length should be %i bytes"%self.blocksize
  63             self.chain = CBC(self.cipher, self.blocksize,IV)
  64         elif mode == MODE_CFB:
  65             if IV == None:
  66                 raise Exception,"Provide an IV!"
  67             if len(IV) <> self.blocksize:
  68                 raise Exception,"the IV length should be %i bytes"%self.blocksize
  69             self.chain = CFB(self.cipher, self.blocksize,IV)
  70         elif mode == MODE_OFB:
  71             if IV == None:
  72                 raise Exception,"Provide an IV!"
  73             if len(IV) <> self.blocksize:
  74                 raise ValueError("the IV length should be %i bytes"%self.blocksize)
  75             self.chain = OFB(self.cipher, self.blocksize,IV)
  76         elif mode == MODE_CTR:
  77             if (counter == None) or  not callable(counter):
  78                 raise Exception,"Supply a valid counter object for the CTR mode"
  79             self.chain = CTR(self.cipher,self.blocksize,counter)
  80         elif mode == MODE_XTS:
  81             if self.blocksize <> 16:
  82                 raise Exception,'XTS only works with blockcipher that have a 128-bit blocksize'
  83             if not(type(key) == tuple and len(key) == 2):
  84                 raise Exception,'Supply two keys as a tuple when using XTS'
  85             if 'keylen_valid' in dir(self): #wrappers for pycrypto functions don't have this function
  86              if not self.keylen_valid(key[0]) or  not self.keylen_valid(key[1]):
  87                 raise ValueError(self.key_error_message)
  88             self.cipher = cipher_module(self.key[0],**args)
  89             self.cipher2 = cipher_module(self.key[1],**args)
  90             self.chain = XTS(self.cipher, self.cipher2)
  91         elif mode == MODE_CMAC:
  92             if self.blocksize not in (8,16):
  93                 raise Exception,'CMAC only works with blockcipher that have a 64 or 128-bit blocksize'
  94             self.chain = CMAC(self.cipher,self.blocksize)
  95         else:
  96                 raise Exception,"Unknown chaining mode!"
  97
  98     def encrypt(self,plaintext,n=''):
  99         """Encrypt some plaintext
 100
 101             plaintext   = a string of binary data
 102             n           = the 'tweak' value when the chaining mode is XTS
 103
 104         The encrypt function will encrypt the supplied plaintext.
 105         The behavior varies slightly depending on the chaining mode.
 106
 107         ECB, CBC:
 108         ---------
 109         When the supplied plaintext is not a multiple of the blocksize
 110           of the cipher, then the remaining plaintext will be cached.
 111         The next time the encrypt function is called with some plaintext,
 112           the new plaintext will be concatenated to the cache and then
 113           cache+plaintext will be encrypted.
 114
 115         CFB, OFB, CTR:
 116         --------------
 117         When the chaining mode allows the cipher to act as a stream cipher,
 118           the encrypt function will always encrypt all of the supplied
 119           plaintext immediately. No cache will be kept.
 120
 121         XTS:
 122         ----
 123         Because the handling of the last two blocks is linked,
 124           it needs the whole block of plaintext to be supplied at once.
 125         Every encrypt function called on a XTS cipher will output
 126           an encrypted block based on the current supplied plaintext block.
 127
 128         CMAC:
 129         -----
 130         Everytime the function is called, the hash from the input data is calculated.
 131         No finalizing needed.
 132         The hashlength is equal to block size of the used block cipher.
 133         """
 134         #self.ed = 'e' if chain is encrypting, 'd' if decrypting,
 135         # None if nothing happened with the chain yet
 136         #assert self.ed in ('e',None)
 137         # makes sure you don't encrypt with a cipher that has started decrypting
 138         self.ed = 'e'
 139         if self.mode == MODE_XTS:
 140             # data sequence number (or 'tweak') has to be provided when in XTS mode
 141             return self.chain.update(plaintext,'e',n)
 142         else:
 143             return self.chain.update(plaintext,'e')
 144
 145     def decrypt(self,ciphertext,n=''):
 146         """Decrypt some ciphertext
 147
 148             ciphertext  = a string of binary data
 149             n           = the 'tweak' value when the chaining mode is XTS
 150
 151         The decrypt function will decrypt the supplied ciphertext.
 152         The behavior varies slightly depending on the chaining mode.
 153
 154         ECB, CBC:
 155         ---------
 156         When the supplied ciphertext is not a multiple of the blocksize
 157           of the cipher, then the remaining ciphertext will be cached.
 158         The next time the decrypt function is called with some ciphertext,
 159           the new ciphertext will be concatenated to the cache and then
 160           cache+ciphertext will be decrypted.
 161
 162         CFB, OFB, CTR:
 163         --------------
 164         When the chaining mode allows the cipher to act as a stream cipher,
 165           the decrypt function will always decrypt all of the supplied
 166           ciphertext immediately. No cache will be kept.
 167
 168         XTS:
 169         ----
 170         Because the handling of the last two blocks is linked,
 171           it needs the whole block of ciphertext to be supplied at once.
 172         Every decrypt function called on a XTS cipher will output
 173           a decrypted block based on the current supplied ciphertext block.
 174
 175         CMAC:
 176         -----
 177         Mode not supported for decryption as this does not make sense.
 178         """
 179         #self.ed = 'e' if chain is encrypting, 'd' if decrypting,
 180         # None if nothing happened with the chain yet
 181         #assert self.ed in ('d',None)
 182         # makes sure you don't decrypt with a cipher that has started encrypting
 183         self.ed = 'd'
 184         if self.mode == MODE_XTS:
 185             # data sequence number (or 'tweak') has to be provided when in XTS mode
 186             return self.chain.update(ciphertext,'d',n)
 187         else:
 188             return self.chain.update(ciphertext,'d')
 189
 190     def final(self,padfct=padding.PKCS7):
 191         # TODO: after calling final, reset the IV? so the cipher is as good as new?
 192         """Finalizes the encryption by padding the cache
 193
 194             padding = padding function
 195                       import from CryptoPlus.Util.padding
 196
 197         While a cipher object is in encryption mode, the final function will pad the remaining cache and encrypt it.
 198         If the cipher has been used for decryption, the final function won't do antyhing. You have to manually unpad if necessary or
 199         construct a Padder yourself en use its unpad function.
 200
 201         After finalization, the chain can still be used but the IV, counter etc aren't reset but just continu as they were after the last step (finalization step).
 202         """
 203         assert self.mode not in (MODE_XTS, MODE_CMAC) # finalizing (=padding) doesn't make sense when in XTS or CMAC mode
 204         if self.ed == 'e':
 205             # when the chain is in encryption mode, finalizing will pad the cache and encrypt this last block
 206             if self.mode in (MODE_OFB,MODE_CFB,MODE_CTR):
 207                 dummy = '0'*(self.blocksize - self.chain.keystream.buffer_info()[1]) # a dummy string that will be used to get a valid padding
 208             else: #ECB, CBC
 209                 dummy = self.chain.cache
 210             return self.chain.update(padfct(dummy,padding.PAD,self.blocksize)[len(dummy):],'e') # pad the cache and then only supply the padding to the update function
 211         else:
 212             # final function doesn't make sense when decrypting => padding should be removed manually
 213             pass
 214
 215 class ECB:
 216     """ECB chaining mode
 217     """
 218     def __init__(self, codebook, blocksize):
 219         self.cache = ''
 220         self.codebook = codebook
 221         self.blocksize = blocksize
 222
 223     def update(self, data, ed):
 224         """Processes the given ciphertext/plaintext
 225
 226         Inputs:
 227             data: raw string of any length
 228             ed:   'e' for encryption, 'd' for decryption
 229         Output:
 230             processed raw string block(s), if any
 231
 232         When the supplied data is not a multiple of the blocksize
 233           of the cipher, then the remaining input data will be cached.
 234         The next time the update function is called with some data,
 235           the new data will be concatenated to the cache and then
 236           cache+data will be processed and full blocks will be outputted.
 237         """
 238         output_blocks = []
 239         self.cache += data
 240         if len(self.cache) < self.blocksize:
 241             return ''
 242         for i in xrange(0, len(self.cache)-self.blocksize+1, self.blocksize):
 243             #the only difference between encryption/decryption in the chain is the cipher block
 244             if ed == 'e':
 245                 output_blocks.append(self.codebook.encrypt( self.cache[i:i + self.blocksize] ))
 246             else:
 247                 output_blocks.append(self.codebook.decrypt( self.cache[i:i + self.blocksize] ))
 248         self.cache = self.cache[i+self.blocksize:]
 249         return ''.join(output_blocks)
 250
 251 class CBC:
 252     """CBC chaining mode
 253     """
 254     def __init__(self, codebook, blocksize, IV):
 255         self.IV = IV
 256         self.cache = ''
 257         self.codebook = codebook
 258         self.blocksize = blocksize
 259
 260     def update(self, data, ed):
 261         """Processes the given ciphertext/plaintext
 262
 263         Inputs:
 264             data: raw string of any length
 265             ed:   'e' for encryption, 'd' for decryption
 266         Output:
 267             processed raw string block(s), if any
 268
 269         When the supplied data is not a multiple of the blocksize
 270           of the cipher, then the remaining input data will be cached.
 271         The next time the update function is called with some data,
 272           the new data will be concatenated to the cache and then
 273           cache+data will be processed and full blocks will be outputted.
 274         """
 275         if ed == 'e':
 276             encrypted_blocks = ''
 277             self.cache += data
 278             if len(self.cache) < self.blocksize:
 279                 return ''
 280             for i in xrange(0, len(self.cache)-self.blocksize+1, self.blocksize):
 281                 self.IV = self.codebook.encrypt(util.xorstring(self.cache[i:i+self.blocksize],self.IV))
 282                 encrypted_blocks += self.IV
 283             self.cache = self.cache[i+self.blocksize:]
 284             return encrypted_blocks
 285         else:
 286             decrypted_blocks = ''
 287             self.cache += data
 288             if len(self.cache) < self.blocksize:
 289                 return ''
 290             for i in xrange(0, len(self.cache)-self.blocksize+1, self.blocksize):
 291                 plaintext = util.xorstring(self.IV,self.codebook.decrypt(self.cache[i:i + self.blocksize]))
 292                 self.IV = self.cache[i:i + self.blocksize]
 293                 decrypted_blocks+=plaintext
 294             self.cache = self.cache[i+self.blocksize:]
 295             return decrypted_blocks
 296
 297 class CFB:
 298     """CFB Chaining Mode
 299
 300     Can be accessed as a stream cipher.
 301     """
 302
 303     def __init__(self, codebook, blocksize, IV):
 304         self.codebook = codebook
 305         self.IV = IV
 306         self.blocksize = blocksize
 307         self.keystream = []
 308     def update(self, data, ed):
 309         """Processes the given ciphertext/plaintext
 310
 311         Inputs:
 312             data: raw string of any multiple of bytes
 313             ed:   'e' for encryption, 'd' for decryption
 314         Output:
 315             processed raw string
 316
 317         The encrypt/decrypt functions will always process all of the supplied
 318           input data immediately. No cache will be kept.
 319         """
 320         output = list(data)
 321
 322         for i in xrange(len(data)):
 323             if ed =='e':
 324                 if len(self.keystream) == 0:
 325                     block = self.codebook.encrypt(self.IV)
 326                     self.keystream = list(block)
 327                     self.IV = ''
 328                 output[i] = chr(ord(output[i]) ^ ord(self.keystream.pop(0)))
 329                 self.IV += output[i] # the IV for the next block in the chain is being built byte per byte as the ciphertext flows in
 330             else:
 331                 if len(self.keystream) == 0:
 332                     block = self.codebook.encrypt(self.IV)
 333                     self.keystream = list(block)
 334                     self.IV = ''
 335                 self.IV += output[i]
 336                 output[i] = chr(ord(output[i]) ^ ord(self.keystream.pop(0)))
 337         return ''.join(output)
 338
 339 class OFB:
 340     """OFB Chaining Mode
 341
 342     Can be accessed as a stream cipher.
 343     """
 344     def __init__(self, codebook, blocksize, IV):
 345         self.codebook = codebook
 346         self.IV = IV
 347         self.blocksize = blocksize
 348         self.keystream = []
 349     def update(self, data, ed):
 350         """Processes the given ciphertext/plaintext
 351
 352         Inputs:
 353             data: raw string of any multiple of bytes
 354             ed:   'e' for encryption, 'd' for decryption
 355         Output:
 356             processed raw string
 357
 358         The encrypt/decrypt functions will always process all of the supplied
 359           input data immediately. No cache will be kept.
 360         """
 361         #no difference between encryption and decryption mode
 362         n = len(data)
 363         blocksize = self.blocksize
 364         output = list(data)
 365
 366         for i in xrange(n):
 367             if len(self.keystream) == 0: #encrypt a new counter block when the current keystream is fully used
 368                 self.IV = self.codebook.encrypt(self.IV)
 369                 self.keystream = list(self.IV)
 370             output[i] = chr(ord(output[i]) ^ ord(self.keystream.pop(0))) #as long as an encrypted counter value is available, the output is just "input XOR keystream"
 371         return ''.join(output)
 372
 373 class CTR:
 374     """CTR Chaining Mode
 375
 376     Can be accessed as a stream cipher.
 377     """
 378     # initial counter value can be choosen, decryption always starts from beginning
 379     #   -> you can start from anywhere yourself: just feed the cipher encoded blocks and feed a counter with the corresponding value
 380     def __init__(self, codebook, blocksize, counter):
 381         self.codebook = codebook
 382         self.counter = counter
 383         self.blocksize = blocksize
 384         self.keystream = [] #holds the output of the current encrypted counter value
 385
 386     def update(self, data, ed):
 387         """Processes the given ciphertext/plaintext
 388
 389         Inputs:
 390             data: raw string of any multiple of bytes
 391             ed:   'e' for encryption, 'd' for decryption
 392         Output:
 393             processed raw string
 394
 395         The encrypt/decrypt functions will always process all of the supplied
 396           input data immediately. No cache will be kept.
 397         """
 398         # no need for the encryption/decryption distinction: both are the same
 399         n = len(data)
 400         blocksize = self.blocksize
 401
 402         output = list(data)
 403         for i in xrange(n):
 404             if len(self.keystream) == 0: #encrypt a new counter block when the current keystream is fully used
 405                 block = self.codebook.encrypt(self.counter())
 406                 self.keystream = list(block)
 407             output[i] = chr(ord(output[i])^ord(self.keystream.pop(0))) #as long as an encrypted counter value is available, the output is just "input XOR keystream"
 408         return ''.join(output)
 409
 410 class XTS:
 411     """XTS Chaining Mode
 412     """
 413     # TODO: allow other blocksizes besides 16bytes?
 414     def __init__(self,codebook1, codebook2):
 415         self.cache = ''
 416         self.codebook1 = codebook1
 417         self.codebook2 = codebook2
 418
 419     def update(self, data, ed,tweak=''):
 420         # supply n as a raw string
 421         # tweak = data sequence number
 422         """Perform a XTS encrypt/decrypt operation.
 423
 424         Because the handling of the last two blocks is linked,
 425           it needs the whole block of ciphertext to be supplied at once.
 426         Every decrypt function called on a XTS cipher will output
 427           a decrypted block based on the current supplied ciphertext block.
 428         """
 429         output = ''
 430         assert len(data) > 15, "At least one block of 128 bits needs to be supplied"
 431         assert len(data) < 128*pow(2,20)
 432
 433         # initializing T
 434         # e_k2_n = E_K2(tweak)
 435         e_k2_n = self.codebook2.encrypt(tweak+ '\x00' * (16-len(tweak)))[::-1]
 436         self.T = util.string2number(e_k2_n)
 437
 438         i=0
 439         while i < ((len(data) // 16)-1): #Decrypt all the blocks but one last full block and opt one last partial block
 440             # C = E_K1(P xor T) xor T
 441             output += self.__xts_step(ed,data[i*16:(i+1)*16],self.T)
 442             # T = E_K2(n) mul (a pow i)
 443             self.__T_update()
 444             i+=1
 445
 446         # Check if the data supplied is a multiple of 16 bytes -> one last full block and we're done
 447         if len(data[i*16:]) == 16:
 448             # C = E_K1(P xor T) xor T
 449             output += self.__xts_step(ed,data[i*16:(i+1)*16],self.T)
 450             # T = E_K2(n) mul (a pow i)
 451             self.__T_update()
 452         else:
 453             T_temp = [self.T]
 454             self.__T_update()
 455             T_temp.append(self.T)
 456             if ed=='d':
 457                 # Permutation of the last two indexes
 458                 T_temp.reverse()
 459             # Decrypt/Encrypt the last two blocks when data is not a multiple of 16 bytes
 460             Cm1 = data[i*16:(i+1)*16]
 461             Cm = data[(i+1)*16:]
 462             PP = self.__xts_step(ed,Cm1,T_temp[0])
 463             Cp = PP[len(Cm):]
 464             Pm = PP[:len(Cm)]
 465             CC = Cm+Cp
 466             Pm1 = self.__xts_step(ed,CC,T_temp[1])
 467             output += Pm1 + Pm
 468         return output
 469
 470     def __xts_step(self,ed,tocrypt,T):
 471         T_string = util.number2string_N(T,16)[::-1]
 472         # C = E_K1(P xor T) xor T
 473         if ed == 'd':
 474             return util.xorstring(T_string, self.codebook1.decrypt(util.xorstring(T_string, tocrypt)))
 475         else:
 476             return util.xorstring(T_string, self.codebook1.encrypt(util.xorstring(T_string, tocrypt)))
 477
 478     def __T_update(self):
 479         # Used for calculating T for a certain step using the T value from the previous step
 480         self.T = self.T << 1
 481         # if (Cout)
 482         if self.T >> (8*16):
 483             #T[0] ^= GF_128_FDBK;
 484             self.T = self.T ^ 0x100000000000000000000000000000087L
 485
 486
 487 class CMAC:
 488     """CMAC chaining mode
 489
 490     Supports every cipher with a blocksize available
 491       in the list CMAC.supported_blocksizes.
 492     The hashlength is equal to block size of the used block cipher.
 493     """
 494     # TODO: move to hash module?
 495     # TODO: change update behaviour to .update() and .digest() as for all hash modules?
 496     #       -> other hash functions in pycrypto: calling update, concatenates current input with previous input and hashes everything
 497     __Rb_dictionary = {64:0x000000000000001b,128:0x00000000000000000000000000000087}
 498     supported_blocksizes = __Rb_dictionary.keys()
 499     def __init__(self,codebook,blocksize):
 500         # Purpose of init: calculate Lu & Lu2
 501         #blocksize (in bytes): to select the Rb constant in the dictionary
 502         #Rb as a dictionary: adding support for other blocksizes is easy
 503         self.cache=''
 504         self.blocksize = blocksize
 505         self.codebook = codebook
 506
 507         #Rb_dictionary: holds values for Rb for different blocksizes
 508         # values for 64 and 128 bits found here: http://www.nuee.nagoya-u.ac.jp/labs/tiwata/omac/omac.html
 509         # explanation from: http://csrc.nist.gov/publications/nistpubs/800-38B/SP_800-38B.pdf
 510         #             Rb is a representation of a certain irreducible binary polynomial of degree b, namely,
 511         #             the lexicographically first among all such polynomials with the minimum possible number of
 512         #             nonzero terms. If this polynomial is expressed as ub+cb-1ub-1+...+c2u2+c1u+c0, where the
 513         #             coefficients cb-1, cb-2, ..., c2, c1, c0 are either 0 or 1, then Rb is the bit string cb-1cb-2...c2c1c0.
 514
 515         self.Rb = self.__Rb_dictionary[blocksize*8]
 516
 517         mask1 = int(('\xff'*blocksize).encode('hex'),16)
 518         mask2 = int(('\x80' + '\x00'*(blocksize-1) ).encode('hex'),16)
 519
 520         L = int(self.codebook.encrypt('\x00'*blocksize).encode('hex'),16)
 521
 522         if L & mask2:
 523             Lu = ((L << 1) & mask1) ^ self.Rb
 524         else:
 525             Lu = L << 1
 526             Lu = Lu & mask1
 527
 528         if Lu & mask2:
 529             Lu2 = ((Lu << 1) & mask1)^ self.Rb
 530         else:
 531             Lu2 = Lu << 1
 532             Lu2 = Lu2 & mask1
 533
 534         self.Lu =util.number2string_N(Lu,self.blocksize)
 535         self.Lu2=util.number2string_N(Lu2,self.blocksize)
 536
 537     def update(self, data, ed):
 538         """Processes the given ciphertext/plaintext
 539
 540         Inputs:
 541             data: raw string of any length
 542             ed:   'e' for encryption, 'd' for decryption
 543         Output:
 544             hashed data as raw string
 545
 546         This is not really an update function:
 547         Everytime the function is called, the hash from the input data is calculated.
 548         No finalizing needed.
 549         """
 550         assert ed == 'e'
 551         blocksize = self.blocksize
 552
 553         m = (len(data)+blocksize-1)/blocksize #m = amount of datablocks
 554         y = '\x00'*blocksize
 555         i=0
 556         for i in range(1,m):
 557             y = self.codebook.encrypt( util.xorstring(data[(i-1)*blocksize:(i)*blocksize],y) )
 558
 559         if len(data[(i)*blocksize:])==blocksize:
 560             X = util.xorstring(util.xorstring(data[(i)*blocksize:],y),self.Lu)
 561         else:
 562             tmp = data[(i)*blocksize:] + '\x80' + '\x00'*(blocksize - len(data[(i)*blocksize:])-1)
 563             X = util.xorstring(util.xorstring(tmp,y),self.Lu2)
 564
 565         T = self.codebook.encrypt(X)
 566         return T
 567