src/CryptoPlus/Hash/pyradiogatun.py

   1 # =============================================================================
   2 # Copyright (c) 2008 Christophe Oosterlynck (christophe.oosterlynck_AT_gmail.com)
   3 #                    Philippe Teuwen (philippe.teuwen_AT_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
  24 """RadioGatun pure python implementation
  25
  26 Code based on the standard found here: http://radiogatun.noekeon.org/
  27 Api and code interface is based on the MD5 implementation of pypy
  28  http://codespeak.net/pypy/dist/pypy/doc/home.html
  29 """
  30
  31 millSize = 19
  32 beltWidth = 3
  33 beltLength = 13
  34 numberOfBlankIterations = 16
  35
  36 def stateInit():
  37         """construct an empty state variable
  38         """
  39         return {"A":[0]*millSize,"B":[[0]*beltWidth for x in range(beltLength)]}
  40
  41 def XORstate(state1,state2):
  42         """XOR the vectors of the status of a RadioGatun object
  43         """
  44         out = stateInit()
  45         for i in xrange(millSize):
  46                 out["A"][i] = state1["A"][i] ^ state2["A"][i]
  47         for i in xrange(beltLength):
  48                 for j in xrange(beltWidth):
  49                         out["B"][i][j] = state1["B"][i][j] ^ state2["B"][i][j]
  50         return out
  51
  52 def F_i(inp,wl):
  53         """Input mapping
  54
  55         input = 1 blocklength string
  56         wl    = wordlength of the RadioGatun hash object
  57         """
  58         mapped = stateInit()
  59         for i in xrange(beltWidth):
  60                 # reverse endianness of byte ordering and convert the input
  61                 #  block to integer
  62                 p_i = string2number(inp[i*wl:(i+1)*wl][::-1])
  63                 mapped["B"][0][i] = p_i
  64                 mapped["A"][i+16] = p_i
  65         return mapped
  66
  67 def R(state,wl):
  68         """Round function R
  69
  70         state = the RadioGatun status
  71         wl    = wordlength of the RadioGatun hash object
  72         """
  73         out = stateInit()
  74         # Belt function: simple rotation
  75         for i in xrange(beltLength):
  76                 out["B"][i] = state["B"][(i - 1)%beltLength]
  77         # Mill to belt feedforward
  78         for i in xrange(12):
  79                 out["B"][i+1][i%beltWidth] ^= state["A"][i+1]
  80         # Run the mill
  81         out["A"] = Mill(state["A"],wl)
  82         # Belt to mill feedforward
  83         for i in xrange(beltWidth):
  84                 out["A"][i+13] ^= state["B"][12][i]
  85         return out
  86
  87 def Mill(a,wl):
  88         """The Mill function
  89
  90         a  = Mill variable of the RadioGatun status
  91         wl = wordlength of the RadioGatun hash object
  92         """
  93         A = [0]*millSize
  94         # Gamma: Non-linearity
  95         for i in xrange(millSize):
  96                 #A[i] = a[i] ^ ~((~a[(i+1)%millSize]) & (a[(i+2)%millSize]) )
  97                 A[i] = a[i] ^ ((a[(i+1)%millSize]) | (~(a[(i+2)%millSize])&((2**(wl*8))-1)) )
  98         # Pi: Intra-word and inter-word dispersion
  99         for i in xrange(millSize):
 100                 #TODO: don't hardcode wordlength in ror64
 101                 a[i] = rotateRight(A[(7*i)%millSize],i*(i+1)/2,wl*8)
 102         # Theta: Diffusion
 103         for i in xrange(millSize):
 104                 A[i] = a[i] ^ a[(i+1)%millSize] ^ a[(i+4)%millSize]
 105         # Iota: Asymmetry
 106         A[0] = A[0] ^ 1
 107         return A
 108
 109 class RadioGatunType:
 110     "An implementation of the MD5 hash function in pure Python."
 111
 112     def __init__(self,wl):
 113         """Initialisation.
 114
 115         wl = wordlength (in bits) of the RadioGatun hash method
 116               between 1 and 64 (default = 64)
 117         """
 118
 119         if not ( 1 <= wl <= 64) or not (wl%8 == 0 ):
 120                 raise ValueError,"Wordlength should be a multiple of 8 between 1 and 64"
 121
 122         # word & block length in bytes
 123         self.wordlength = wl/8
 124         self.blocklength = self.wordlength*3
 125
 126         # Initial message length in bits(!).
 127         self.length = 0L
 128         self.count = [0, 0]
 129
 130         # Initial empty message as a sequence of bytes (8 bit characters).
 131         self.input = ""
 132
 133         # Call a separate init function, that can be used repeatedly
 134         # to start from scratch on the same object.
 135         self.init()
 136
 137
 138     def init(self):
 139         """Initialize the message-digest and set all fields to zero.
 140         """
 141
 142         self.S = stateInit()
 143
 144         self.length = 0L
 145         self.count = [0, 0]
 146         self.input = ""
 147
 148     def _transform(self, inp):
 149         """Basic RadioGatun step transforming the digest based on the input.
 150
 151         Performs the inside of the first loop of alternating input construction
 152         of RadioGatun. The only thing that can be done every time new data is
 153         submitted to the hash object.
 154         Mangling and output mapping can only follow when all input data has
 155         been received.
 156         """
 157         T = XORstate(self.S,F_i(inp,self.wordlength))
 158         self.S = R(T,self.wordlength)
 159
 160
 161     # Down from here all methods follow the Python Standard Library
 162     # API of the md5 module.
 163
 164     def update(self, inBuf):
 165         """Add to the current message.
 166
 167         Update the radiogatun object with the string arg. Repeated calls
 168         are equivalent to a single call with the concatenation of all
 169         the arguments, i.e. m.update(a); m.update(b) is equivalent
 170         to m.update(a+b).
 171
 172         The hash is immediately calculated for all full blocks. The final
 173         calculation is made in digest(). This allows us to keep an
 174         intermediate value for the hash, so that we only need to make
 175         minimal recalculation if we call update() to add moredata to
 176         the hashed string.
 177         """
 178         # Amount of bytes given at input
 179         leninBuf = long(len(inBuf))
 180
 181         # Compute number of bytes mod 64.
 182         index = (self.count[0] >> 3) % self.blocklength
 183
 184         # Update number of bits.
 185         self.count[0] = self.count[0] + (leninBuf << 3)
 186
 187         partLen = self.blocklength - index
 188
 189         # if length of input is at least the amount of bytes needed to fill a block
 190         if leninBuf >= partLen:
 191             self.input = self.input[:index] + inBuf[:partLen]
 192             self._transform(self.input)
 193             i = partLen
 194             while i + self.blocklength - 1 < leninBuf:
 195                 self._transform(inBuf[i:i+self.blocklength])
 196                 i = i + self.blocklength
 197             else:
 198                 self.input = inBuf[i:leninBuf]
 199         # if not enough bytes at input to fill a block
 200         else:
 201             i = 0
 202             self.input = self.input + inBuf
 203
 204
 205     def digest(self, length=256):
 206         """Terminate the message-digest computation and return digest.
 207
 208         length = output length of the digest in bits
 209                   any multiple of 8 with a minimum of 8
 210                   default = 256
 211
 212         Return the digest of the strings passed to the update()
 213         method so far. This is a byte string which may contain
 214         non-ASCII characters, including null bytes.
 215
 216         Calling digest() doesn't change the internal state. Adding data via
 217         update() can still continu after asking for an intermediate digest
 218         value.
 219         """
 220
 221         S = self.S
 222         inp = "" + self.input
 223         count = [] + self.count
 224
 225         index = (self.count[0] >> 3) % self.blocklength
 226
 227         if index < self.blocklength:
 228                 padLen = self.blocklength - index
 229         else:
 230             padLen = 2*self.blocklength - index
 231
 232         #provide padding chars encoded as little endian
 233         padding = ['\001'] + ['\000'] * (padLen - 1)
 234         self.update(''.join(padding))
 235
 236         # Mangling = blank rounds
 237         for i in xrange(numberOfBlankIterations):
 238                 self.S = R(self.S,self.wordlength)
 239
 240         # Extraction
 241         # Store state in digest.
 242         digest = ""
 243         for i in xrange((length)/self.wordlength/2):
 244                 self.S = R(self.S,self.wordlength)
 245                 # F_o
 246                 digest += number2string_N((self.S["A"][1]),self.wordlength)[::-1] + number2string_N((self.S["A"][2]),self.wordlength)[::-1]
 247
 248         self.S = S
 249         self.input = inp
 250         self.count = count
 251
 252         return digest[:length/8]
 253
 254
 255     def hexdigest(self,length=256):
 256         """Terminate and return digest in HEX form.
 257
 258         length = output length of the digest in bits
 259                   any multiple of 8 with a minimum of 8
 260                   default = 256
 261
 262         Like digest() except the digest is returned as a string of
 263         length 'length', containing only hexadecimal digits. This may be
 264         used to exchange the value safely in email or other non-
 265         binary environments.
 266
 267         Calling hexdigest() doesn't change the internal state. Adding data via
 268         update() can still continu after asking for an intermediate digest
 269         value.
 270         """
 271
 272         return ''.join(['%02x' % ord(c) for c in self.digest(length)])
 273
 274     def copy(self):
 275         """Return a clone object.
 276
 277         Return a copy ('clone') of the radiogatun object. This can be used
 278         to efficiently compute the digests of strings that share
 279         a common initial substring.
 280         """
 281
 282         import copy
 283         return copy.deepcopy(self)
 284
 285 # ======================================================================
 286 # TOP LEVEL INTERFACE
 287 # ======================================================================
 288
 289 def new(wl=64,arg=None):
 290     """Return a new RadioGatun hash object
 291
 292     wl  = wordlength (in bits) of the RadioGatun hash method
 293               between 1 and 64 (default = 64)
 294     arg =  if present, the method call update(arg) is made
 295
 296     EXAMPLES: (testvectors from: http://radiogatun.noekeon.org/)
 297     ==========
 298     >>> import pyradiogatun
 299
 300     radiogatun[64]
 301     ---------------
 302     >>> hasher = pyradiogatun.new()
 303     >>> hasher.update('1234567890123456')
 304     >>> hasher.hexdigest()
 305     'caaec14b5b4a7960d6854709770e3071d635d60224f58aa385867e549ef4cc42'
 306
 307     >>> hasher = pyradiogatun.new()
 308     >>> hasher.update('Santa Barbara, California')
 309     >>> hasher.hexdigest()
 310     '0d08daf2354fa95aaa5b6a50f514384ecdd35940252e0631002e600e13cd285f'
 311
 312     radiogatun[32]
 313     ---------------
 314     >>> hasher = pyradiogatun.new(32)
 315     >>> hasher.update('1234567890123456')
 316     >>> hasher.hexdigest()
 317     '59612324f3f42d3096e69125d2733b86143ae668ae9ed561ad785e0eac8dba25'
 318
 319     >>> hasher = pyradiogatun.new(32)
 320     >>> hasher.update('Santa Barbara, California')
 321     >>> hasher.hexdigest()
 322     '041666388ef9655d48996a66dada1193d6646012a7b25a24fb10e6075cf0fc54'
 323     """
 324
 325     crypto = RadioGatunType(wl)
 326     if arg:
 327         crypto.update(arg)
 328
 329     return crypto
 330
 331 # ======================================================================
 332 # HELPER FUNCTIONS
 333 # ======================================================================
 334
 335 def rotateRight(x, amountToShift, totalBits):
 336     """Rotate x (consisting of 'totalBits' bits) n bits to right.
 337
 338     x             = integer input to be rotated
 339     amountToShift = the amount of bits that should be shifted
 340     totalBits     = total amount bits at the input for rotation
 341     """
 342     x = x%(2**totalBits)
 343     n_mod = ((amountToShift % totalBits) + totalBits) % totalBits
 344     return  ((x >> n_mod) | ((x << (totalBits-n_mod)))&((2**totalBits)-1))
 345
 346 def string2number(i):
 347     """ Convert a string to a number
 348
 349     Input: string (big-endian)
 350     Output: long or integer
 351     """
 352     return int(i.encode('hex'),16)
 353
 354 def number2string_N(i, N):
 355     """Convert a number to a string of fixed size
 356
 357     i: long or integer
 358     N: length of string
 359     Output: string (big-endian)
 360     """
 361     s = '%0*x' % (N*2, i)
 362     return s.decode('hex')
 363
 364 # ======================================================================
 365 # DOCTEST ENABLER
 366 # ======================================================================
 367
 368 def _test():
 369     import doctest
 370     doctest.testmod()
 371
 372 if __name__ == "__main__":
 373     print "DOCTEST running... no messages = all good"
 374     _test()