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 RadioGatun 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
 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         Can be used to reinitialize the hash object
 142         """
 143
 144         self.S = stateInit()
 145
 146         self.length = 0L
 147         self.count = 0
 148         self.input = ""
 149
 150     def _transform(self, inp):
 151         """Basic RadioGatun step transforming the digest based on the input.
 152
 153         Performs the inside of the first loop of alternating input construction
 154         of RadioGatun. The only thing that can be done every time new data is
 155         submitted to the hash object.
 156         Mangling and output mapping can only follow when all input data has
 157         been received.
 158         """
 159         T = XORstate(self.S,F_i(inp,self.wordlength))
 160         self.S = R(T,self.wordlength)
 161
 162
 163     # Down from here all methods follow the Python Standard Library
 164     # API of the md5 module.
 165
 166     def update(self, inBuf):
 167         """Add to the current message.
 168
 169         Update the radiogatun object with the string arg. Repeated calls
 170         are equivalent to a single call with the concatenation of all
 171         the arguments, i.e. m.update(a); m.update(b) is equivalent
 172         to m.update(a+b).
 173
 174         The hash is immediately calculated for all full blocks. The final
 175         calculation is made in digest(). This allows us to keep an
 176         intermediate value for the hash, so that we only need to make
 177         minimal recalculation if we call update() to add moredata to
 178         the hashed string.
 179         """
 180         # Amount of bytes given at input
 181         leninBuf = long(len(inBuf))
 182
 183         # Compute number of bytes mod 64.
 184         index = (self.count >> 3) % self.blocklength
 185
 186         # Update number of bits.
 187         self.count = self.count + (leninBuf << 3)
 188
 189         partLen = self.blocklength - index
 190
 191         # if length of input is at least the amount of bytes needed to fill a block
 192         if leninBuf >= partLen:
 193             self.input = self.input[:index] + inBuf[:partLen]
 194             self._transform(self.input)
 195             i = partLen
 196             while i + self.blocklength - 1 < leninBuf:
 197                 self._transform(inBuf[i:i+self.blocklength])
 198                 i = i + self.blocklength
 199             else:
 200                 self.input = inBuf[i:leninBuf]
 201         # if not enough bytes at input to fill a block
 202         else:
 203             i = 0
 204             self.input = self.input + inBuf
 205
 206
 207     def digest(self, length=256):
 208         """Terminate the message-digest computation and return digest.
 209
 210         length = output length of the digest in bits
 211                   any multiple of 8 with a minimum of 8
 212                   default = 256
 213
 214         Return the digest of the strings passed to the update()
 215         method so far. This is a byte string which may contain
 216         non-ASCII characters, including null bytes.
 217
 218         Calling digest() doesn't change the internal state. Adding data via
 219         update() can still continu after asking for an intermediate digest
 220         value.
 221         """
 222
 223         S = self.S
 224         inp = "" + self.input
 225         count = self.count
 226
 227         index = (self.count >> 3) % self.blocklength
 228
 229         if index < self.blocklength:
 230                 padLen = self.blocklength - index
 231         else:
 232                 padLen = 2*self.blocklength - index
 233
 234         #provide padding chars encoded as little endian
 235         padding = ['\001'] + ['\000'] * (padLen - 1)
 236         self.update(''.join(padding))
 237
 238         # Mangling = blank rounds
 239         for i in xrange(numberOfBlankIterations):
 240                 self.S = R(self.S,self.wordlength)
 241
 242         # Extraction
 243         # Store state in digest.
 244         digest = ""
 245         for i in xrange((length)/self.wordlength/2):
 246                 self.S = R(self.S,self.wordlength)
 247                 # F_o
 248                 digest += number2string_N((self.S["A"][1]),self.wordlength)[::-1] + number2string_N((self.S["A"][2]),self.wordlength)[::-1]
 249
 250         self.S = S
 251         self.input = inp
 252         self.count = count
 253
 254         return digest[:length/8]
 255
 256
 257     def hexdigest(self,length=256):
 258         """Terminate and return digest in HEX form.
 259
 260         length = output length of the digest in bits
 261                   any multiple of 8 with a minimum of 8
 262                   default = 256
 263
 264         Like digest() except the digest is returned as a string of
 265         length 'length', containing only hexadecimal digits. This may be
 266         used to exchange the value safely in email or other non-
 267         binary environments.
 268
 269         Calling hexdigest() doesn't change the internal state. Adding data via
 270         update() can still continu after asking for an intermediate digest
 271         value.
 272         """
 273
 274         return ''.join(['%02x' % ord(c) for c in self.digest(length)])
 275
 276     def copy(self):
 277         """Return a clone object.
 278
 279         Return a copy ('clone') of the radiogatun object. This can be used
 280         to efficiently compute the digests of strings that share
 281         a common initial substring.
 282         """
 283
 284         import copy
 285         return copy.deepcopy(self)
 286
 287 # ======================================================================
 288 # TOP LEVEL INTERFACE
 289 # ======================================================================
 290
 291 def new(wl=64,arg=None):
 292     """Return a new RadioGatun hash object
 293
 294     wl  = wordlength (in bits) of the RadioGatun hash method
 295               between 1 and 64 (default = 64)
 296     arg =  if present, the method call update(arg) is made
 297
 298     EXAMPLES: (testvectors from: http://radiogatun.noekeon.org/)
 299     ==========
 300     >>> import pyradiogatun
 301
 302     radiogatun[64]
 303     ---------------
 304     >>> hasher = pyradiogatun.new()
 305     >>> hasher.update('1234567890123456')
 306     >>> hasher.hexdigest()
 307     'caaec14b5b4a7960d6854709770e3071d635d60224f58aa385867e549ef4cc42'
 308
 309     >>> hasher = pyradiogatun.new()
 310     >>> hasher.update('Santa Barbara, California')
 311     >>> hasher.hexdigest()
 312     '0d08daf2354fa95aaa5b6a50f514384ecdd35940252e0631002e600e13cd285f'
 313
 314     radiogatun[32]
 315     ---------------
 316     >>> hasher = pyradiogatun.new(32)
 317     >>> hasher.update('1234567890123456')
 318     >>> hasher.hexdigest()
 319     '59612324f3f42d3096e69125d2733b86143ae668ae9ed561ad785e0eac8dba25'
 320
 321     >>> hasher = pyradiogatun.new(32)
 322     >>> hasher.update('Santa Barbara, California')
 323     >>> hasher.hexdigest()
 324     '041666388ef9655d48996a66dada1193d6646012a7b25a24fb10e6075cf0fc54'
 325     """
 326
 327     crypto = RadioGatunType(wl)
 328     if arg:
 329         crypto.update(arg)
 330
 331     return crypto
 332
 333 # ======================================================================
 334 # HELPER FUNCTIONS
 335 # ======================================================================
 336
 337 def rotateRight(x, amountToShift, totalBits):
 338     """Rotate x (consisting of 'totalBits' bits) n bits to right.
 339
 340     x             = integer input to be rotated
 341     amountToShift = the amount of bits that should be shifted
 342     totalBits     = total amount bits at the input for rotation
 343     """
 344     x = x%(2**totalBits)
 345     n_mod = ((amountToShift % totalBits) + totalBits) % totalBits
 346     return  ((x >> n_mod) | ((x << (totalBits-n_mod)))&((2**totalBits)-1))
 347
 348 def string2number(i):
 349     """ Convert a string to a number
 350
 351     Input: string (big-endian)
 352     Output: long or integer
 353     """
 354     return int(i.encode('hex'),16)
 355
 356 def number2string_N(i, N):
 357     """Convert a number to a string of fixed size
 358
 359     i: long or integer
 360     N: length of string
 361     Output: string (big-endian)
 362     """
 363     s = '%0*x' % (N*2, i)
 364     return s.decode('hex')
 365
 366 # ======================================================================
 367 # DOCTEST ENABLER
 368 # ======================================================================
 369
 370 def _test():
 371     import doctest
 372     doctest.testmod()
 373
 374 if __name__ == "__main__":
 375     print "DOCTEST running... no messages = all good"
 376     _test()