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 beltWidth = 3
  32 beltLength = 13
  33 millSize = 2*beltWidth + beltLength
  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 XOR_F_i(state,inp,wl):
  42         """Input mapping
  43
  44         mapping input blocks to a state variable + XOR step of the alternating-
  45         input construction
  46
  47         input = 1 blocklength string
  48         wl    = wordlength of the RadioGatun hash object
  49         """
  50         for i in xrange(beltWidth):
  51                 # reverse endianness of byte ordering and convert the input
  52                 #  block to integer
  53                 p_i = string2number(inp[i*wl:(i+1)*wl][::-1])
  54                 state["B"][0][i] ^= p_i
  55                 state["A"][i+millSize-beltWidth] ^= p_i
  56         return state
  57
  58 def R(state,wl):
  59         """Round function R
  60
  61         state = the RadioGatun status
  62         wl    = wordlength of the RadioGatun hash object
  63         """
  64         out = stateInit()
  65         # Belt function: simple rotation
  66         out["B"] = state["B"][-1:]+state["B"][:-1]
  67         # Mill to belt feedforward
  68         for i in xrange(beltLength - 1):
  69                 out["B"][i+1][i%beltWidth] ^= state["A"][i+1]
  70         # Run the mill
  71         out["A"] = Mill(state["A"],wl)
  72         # Belt to mill feedforward
  73         for i in xrange(beltWidth):
  74                 out["A"][i+beltLength] ^= state["B"][-1][i]
  75         return out
  76
  77 def Mill(a,wl):
  78         """The Mill function
  79
  80         a  = Mill variable of the RadioGatun status
  81         wl = wordlength of the RadioGatun hash object
  82         """
  83         A = [0]*millSize
  84         # Gamma: Non-linearity
  85         for i in xrange(millSize):
  86                 A[i] = a[i] ^ ~((~a[(i+1)%millSize]) & (a[(i+2)%millSize]) )
  87                 # Alternative:
  88                 #  A[i] = a[i] ^ ((a[(i+1)%millSize]) | (~(a[(i+2)%millSize])&((2**(wl*8))-1)) )
  89         # Pi: Intra-word and inter-word dispersion
  90         for i in xrange(millSize):
  91                 a[i] = rotateRight(A[(7*i)%millSize],i*(i+1)/2,wl*8)
  92         # Theta: Diffusion
  93         for i in xrange(millSize):
  94                 A[i] = a[i] ^ a[(i+1)%millSize] ^ a[(i+4)%millSize]
  95         # Iota: Asymmetry
  96         A[0] = A[0] ^ 1
  97         return A
  98
  99 class RadioGatunType:
 100     "An implementation of the RadioGatun hash function in pure Python."
 101
 102     def __init__(self,wl):
 103         """Initialisation.
 104
 105         wl = wordlength (in bits) of the RadioGatun hash method
 106               between 8 and 64 (default = 64)
 107         """
 108
 109         if not ( 8 <= wl <= 64) or not (wl%8 == 0 ):
 110                 raise ValueError,"Wordlength should be a multiple of 8 between 8 and 64"
 111
 112         # word & block length in bytes
 113         self.wordlength = wl/8
 114         self.blocklength = self.wordlength*beltWidth
 115
 116         # Initial message length in bits(!).
 117         self.length = 0
 118         self.count = 0
 119
 120         # Initial empty message as a sequence of bytes (8 bit characters).
 121         self.input = ""
 122
 123         # Call a separate init function, that can be used repeatedly
 124         # to start from scratch on the same object.
 125         self.init()
 126
 127
 128     def init(self):
 129         """Initialize the message-digest and set all fields to zero.
 130
 131         Can be used to reinitialize the hash object
 132         """
 133
 134         self.S = stateInit()
 135
 136         self.length = 0
 137         self.count = 0
 138         self.input = ""
 139
 140     def _transform(self, inp):
 141         """Basic RadioGatun step transforming the digest based on the input.
 142
 143         Performs the inside of the first loop of alternating input construction
 144         of RadioGatun. The only thing that can be done every time new data is
 145         submitted to the hash object.
 146         Mangling and output mapping can only follow when all input data has
 147         been received.
 148         """
 149         T = XOR_F_i(self.S,inp,self.wordlength)
 150         self.S = R(T,self.wordlength)
 151
 152
 153     # Down from here all methods follow the Python Standard Library
 154     # API of the md5 module.
 155
 156     def update(self, inBuf):
 157         """Add to the current message.
 158
 159         Update the radiogatun object with the string arg. Repeated calls
 160         are equivalent to a single call with the concatenation of all
 161         the arguments, i.e. m.update(a); m.update(b) is equivalent
 162         to m.update(a+b).
 163
 164         The hash is immediately calculated for all full blocks. The final
 165         calculation is made in digest(). This allows us to keep an
 166         intermediate value for the hash, so that we only need to make
 167         minimal recalculation if we call update() to add moredata to
 168         the hashed string.
 169         """
 170         # Amount of bytes given at input
 171         leninBuf = long(len(inBuf))
 172
 173         # Compute number of bytes mod 64.
 174         index = (self.count >> 3) % self.blocklength
 175
 176         # Update number of bits.
 177         self.count = self.count + (leninBuf << 3)
 178
 179         partLen = self.blocklength - index
 180
 181         # if length of input is at least the amount of bytes needed to fill a block
 182         if leninBuf >= partLen:
 183             self.input = self.input[:index] + inBuf[:partLen]
 184             self._transform(self.input)
 185             i = partLen
 186             while i + self.blocklength - 1 < leninBuf:
 187                 self._transform(inBuf[i:i+self.blocklength])
 188                 i = i + self.blocklength
 189             else:
 190                 self.input = inBuf[i:leninBuf]
 191         # if not enough bytes at input to fill a block
 192         else:
 193             i = 0
 194             self.input = self.input + inBuf
 195
 196
 197     def digest(self, length=256):
 198         """Terminate the message-digest computation and return digest.
 199
 200         length = output length of the digest in bits
 201                   any multiple of 8 with a minimum of 8
 202                   default = 256
 203
 204         Return the digest of the strings passed to the update()
 205         method so far. This is a byte string which may contain
 206         non-ASCII characters, including null bytes.
 207
 208         Calling digest() doesn't change the internal state. Adding data via
 209         update() can still continu after asking for an intermediate digest
 210         value.
 211         """
 212
 213         S = self.S
 214         inp = "" + self.input
 215         count = self.count
 216
 217         index = (self.count >> 3) % self.blocklength
 218
 219         padLen = self.blocklength - index
 220
 221         padding = ['\001'] + ['\000'] * (padLen - 1)
 222         self.update(''.join(padding))
 223
 224         # Mangling = blank rounds
 225         for i in xrange(numberOfBlankIterations):
 226                 self.S = R(self.S,self.wordlength)
 227
 228         # Extraction
 229         # Store state in digest.
 230         digest = ""
 231         for i in xrange((length)/self.wordlength/2):
 232                 self.S = R(self.S,self.wordlength)
 233                 # F_o
 234                 digest += number2string_N((self.S["A"][1]),self.wordlength)[::-1] + number2string_N((self.S["A"][2]),self.wordlength)[::-1]
 235
 236         self.S = S
 237         self.input = inp
 238         self.count = count
 239
 240         return digest[:length/8]
 241
 242
 243     def hexdigest(self,length=256):
 244         """Terminate and return digest in HEX form.
 245
 246         length = output length of the digest in bits
 247                   any multiple of 8 with a minimum of 8
 248                   default = 256
 249
 250         Like digest() except the digest is returned as a string of
 251         length 'length', containing only hexadecimal digits. This may be
 252         used to exchange the value safely in email or other non-
 253         binary environments.
 254
 255         Calling hexdigest() doesn't change the internal state. Adding data via
 256         update() can still continu after asking for an intermediate digest
 257         value.
 258         """
 259
 260         return ''.join(['%02x' % ord(c) for c in self.digest(length)])
 261
 262     def copy(self):
 263         """Return a clone object.
 264
 265         Return a copy ('clone') of the radiogatun object. This can be used
 266         to efficiently compute the digests of strings that share
 267         a common initial substring.
 268         """
 269
 270         import copy
 271         return copy.deepcopy(self)
 272
 273 # ======================================================================
 274 # TOP LEVEL INTERFACE
 275 # ======================================================================
 276
 277 def new(arg=None,wl=64,):
 278     """Return a new RadioGatun hash object
 279
 280     wl  = wordlength (in bits) of the RadioGatun hash method
 281               between 1 and 64 (default = 64)
 282     arg =  if present, the method call update(arg) is made
 283
 284     EXAMPLES: (testvectors from: http://radiogatun.noekeon.org/)
 285     ==========
 286     >>> import pyradiogatun
 287
 288     radiogatun[64]
 289     ---------------
 290     >>> hasher = pyradiogatun.new()
 291     >>> hasher.update('1234567890123456')
 292     >>> hasher.hexdigest()
 293     'caaec14b5b4a7960d6854709770e3071d635d60224f58aa385867e549ef4cc42'
 294
 295     >>> hasher = pyradiogatun.new()
 296     >>> hasher.update('Santa Barbara, California')
 297     >>> hasher.hexdigest(480)
 298     '0d08daf2354fa95aaa5b6a50f514384ecdd35940252e0631002e600e13cd285f74adb0c0a666adeb1f2d20b1f2489e3d973dae4efc1f2cc5aaa13f2b'
 299
 300     radiogatun[32]
 301     ---------------
 302     >>> hasher = pyradiogatun.new(wl=32)
 303     >>> hasher.update('1234567890123456')
 304     >>> hasher.hexdigest()
 305     '59612324f3f42d3096e69125d2733b86143ae668ae9ed561ad785e0eac8dba25'
 306
 307     >>> hasher = pyradiogatun.new(wl=32)
 308     >>> hasher.update('Santa Barbara, California')
 309     >>> hasher.hexdigest(512)
 310     '041666388ef9655d48996a66dada1193d6646012a7b25a24fb10e6075cf0fc54a162949f4022531dbb6f66b64c3579df49f0f3af5951df9d68af310f2703b06d'
 311
 312     radiogatun[16]
 313     ---------------
 314     >>> hasher = pyradiogatun.new(wl=16)
 315     >>> hasher.update('Santa Barbara, California')
 316     >>> hasher.hexdigest()
 317     'ab2203a8c3de943309b685513a29060339c001acce5900dcd6427a02c1fb8011'
 318
 319     radiogatun[8]
 320     --------------
 321     >>> hasher = pyradiogatun.new(wl=8)
 322     >>> hasher.update('Santa Barbara, California')
 323     >>> hasher.hexdigest()
 324     'e08f5cdbbfd8f5f3c479464a60ac186963e741d28f654e2c961d2f9bebc7de31'
 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()