src/CryptoPlus/Hash/pyradiogatun.py

   1 # =============================================================================
   2 # Copyright (c) 2008
   3 #     Christophe Oosterlynck (christophe.oosterlynck_AT_gmail.com)
   4 #     Philippe Teuwen (philippe.teuwen_AT_nxp.com)
   5 #
   6 # Permission is hereby granted, free of charge, to any person obtaining a copy
   7 # of this software and associated documentation files (the "Software"), to deal
   8 # in the Software without restriction, including without limitation the rights
   9 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10 # copies of the Software, and to permit persons to whom the Software is
  11 # furnished to do so, subject to the following conditions:
  12 #
  13 # The above copyright notice and this permission notice shall be included in
  14 # all copies or substantial portions of the Software.
  15 #
  16 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21 # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  22 # THE SOFTWARE.
  23 # =============================================================================
  24
  25 """RadioGatun pure python implementation
  26
  27 Code based on the standard found here: http://radiogatun.noekeon.org/
  28 Api and code interface is based on the MD5 implementation of pypy
  29  http://codespeak.net/pypy/dist/pypy/doc/home.html
  30 """
  31
  32 BELT_WIDTH = 3
  33 BELT_LENGTH = 13
  34 MILL_SIZE = 2*BELT_WIDTH + BELT_LENGTH
  35 NUMBER_OF_BLANK_ITERATIONS = 16
  36
  37 def state_init():
  38     """construct an empty state variable
  39     """
  40     return {"A":[0]*MILL_SIZE, "B":[[0]*BELT_WIDTH for x in range(BELT_LENGTH)]}
  41
  42 def XOR_F_i(state, inp, wl):
  43     """Input mapping
  44
  45     mapping input blocks to a state variable + XOR step of the alternating-
  46     input construction
  47
  48     input = 1 blocklength string
  49     wl    = wordlength of the RadioGatun hash object
  50     """
  51     for i in xrange(BELT_WIDTH):
  52         # reverse endianness of byte ordering and convert the input
  53         #  block to integer
  54         p_i = string2number(inp[i*wl:(i+1)*wl][::-1])
  55         state["B"][0][i] ^= p_i
  56         state["A"][i+MILL_SIZE-BELT_WIDTH] ^= p_i
  57     return state
  58
  59 def R(state, wl):
  60     """Round function R
  61
  62     state = the RadioGatun status
  63     wl    = wordlength of the RadioGatun hash object
  64     """
  65     out = state_init()
  66     # Belt function: simple rotation
  67     out["B"] = state["B"][-1:]+state["B"][:-1]
  68     # Mill to belt feedforward
  69     for i in xrange(BELT_LENGTH - 1):
  70         out["B"][i+1][i%BELT_WIDTH] ^= state["A"][i+1]
  71     # Run the mill
  72     out["A"] = Mill(state["A"], wl)
  73     # Belt to mill feedforward
  74     for i in xrange(BELT_WIDTH):
  75         out["A"][i+BELT_LENGTH] ^= state["B"][-1][i]
  76     return out
  77
  78 def Mill(a, wl):
  79     """The Mill function
  80
  81     a  = Mill variable of the RadioGatun status
  82     wl = wordlength of the RadioGatun hash object
  83     """
  84     A = [0]*MILL_SIZE
  85     # Gamma: Non-linearity
  86     for i in xrange(MILL_SIZE):
  87         A[i] = a[i] ^ ~((~a[(i+1)%MILL_SIZE]) & (a[(i+2)%MILL_SIZE]) )
  88     # Pi: Intra-word and inter-word dispersion
  89     for i in xrange(MILL_SIZE):
  90         a[i] = rotateRight(A[(7*i)%MILL_SIZE], i*(i+1)/2, wl*8)
  91     # Theta: Diffusion
  92     for i in xrange(MILL_SIZE):
  93         A[i] = a[i] ^ a[(i+1)%MILL_SIZE] ^ a[(i+4)%MILL_SIZE]
  94     # Iota: Asymmetry
  95     A[0] = A[0] ^ 1
  96     return A
  97
  98 class RadioGatunType:
  99     "An implementation of the RadioGatun hash function in pure Python."
 100
 101     def __init__(self, wl):
 102         """Initialisation.
 103
 104         wl = wordlength (in bits) of the RadioGatun hash method
 105               between 8 and 64 (default = 64)
 106         """
 107
 108         if not ( 8 <= wl <= 64) or not (wl%8 == 0 ):
 109             raise ValueError, "Wordlength should be a multiple of 8" +\
 110                               " between 8 and 64"
 111
 112         # word & block length in bytes
 113         self.wordlength = wl/8
 114         self.blocklength = self.wordlength*BELT_WIDTH
 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 = state_init()
 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
 182         # the amount of bytes needed to fill a block
 183         if leninBuf >= partLen:
 184             self.input = self.input[:index] + inBuf[:partLen]
 185             self._transform(self.input)
 186             i = partLen
 187             while i + self.blocklength - 1 < leninBuf:
 188                 self._transform(inBuf[i:i+self.blocklength])
 189                 i = i + self.blocklength
 190             else:
 191                 self.input = inBuf[i:leninBuf]
 192         # if not enough bytes at input to fill a block
 193         else:
 194             i = 0
 195             self.input = self.input + inBuf
 196
 197
 198     def digest(self, length=256):
 199         """Terminate the message-digest computation and return digest.
 200
 201         length = output length of the digest in bits
 202                   any multiple of 8 with a minimum of 8
 203                   default = 256
 204
 205         Return the digest of the strings passed to the update()
 206         method so far. This is a byte string which may contain
 207         non-ASCII characters, including null bytes.
 208
 209         Calling digest() doesn't change the internal state. Adding data via
 210         update() can still continu after asking for an intermediate digest
 211         value.
 212         """
 213
 214         S = self.S
 215         inp = "" + self.input
 216         count = self.count
 217
 218         index = (self.count >> 3) % self.blocklength
 219
 220         padLen = self.blocklength - index
 221
 222         padding = ['\001'] + ['\000'] * (padLen - 1)
 223         self.update(''.join(padding))
 224
 225         # Mangling = blank rounds
 226         for i in xrange(NUMBER_OF_BLANK_ITERATIONS):
 227             self.S = R(self.S, self.wordlength)
 228
 229         # Extraction
 230         # Store state in digest.
 231         digest = ""
 232         for i in xrange((length)/self.wordlength/2):
 233             self.S = R(self.S, self.wordlength)
 234             # F_o
 235             digest += \
 236                 number2string_N((self.S["A"][1]), self.wordlength)[::-1] +\
 237                 number2string_N((self.S["A"][2]), self.wordlength)[::-1]
 238
 239         self.S = S
 240         self.input = inp
 241         self.count = count
 242
 243         return digest[:length/8]
 244
 245
 246     def hexdigest(self, length=256):
 247         """Terminate and return digest in HEX form.
 248
 249         length = output length of the digest in bits
 250                   any multiple of 8 with a minimum of 8
 251                   default = 256
 252
 253         Like digest() except the digest is returned as a string of
 254         length 'length', containing only hexadecimal digits. This may be
 255         used to exchange the value safely in email or other non-
 256         binary environments.
 257
 258         Calling hexdigest() doesn't change the internal state. Adding data via
 259         update() can still continu after asking for an intermediate digest
 260         value.
 261         """
 262
 263         return ''.join(['%02x' % ord(c) for c in self.digest(length)])
 264
 265     def copy(self):
 266         """Return a clone object.
 267
 268         Return a copy ('clone') of the radiogatun object. This can be used
 269         to efficiently compute the digests of strings that share
 270         a common initial substring.
 271         """
 272
 273         import copy
 274         return copy.deepcopy(self)
 275
 276 # ======================================================================
 277 # TOP LEVEL INTERFACE
 278 # ======================================================================
 279
 280 def new(arg=None, wl=64):
 281     """Return a new RadioGatun hash object
 282
 283     wl  = wordlength (in bits) of the RadioGatun hash method
 284               between 1 and 64 (default = 64)
 285     arg =  if present, the method call update(arg) is made
 286
 287     EXAMPLES: (testvectors from: http://radiogatun.noekeon.org/)
 288     ==========
 289     >>> import pyradiogatun
 290
 291     radiogatun[64]
 292     ---------------
 293     >>> hasher = pyradiogatun.new()
 294     >>> hasher.update('1234567890123456')
 295     >>> hasher.hexdigest()
 296     'caaec14b5b4a7960d6854709770e3071d635d60224f58aa385867e549ef4cc42'
 297
 298     >>> hasher = pyradiogatun.new()
 299     >>> hasher.update('Santa Barbara, California')
 300     >>> hasher.hexdigest(480)
 301     '0d08daf2354fa95aaa5b6a50f514384ecdd35940252e0631002e600e13cd285f74adb0c0a666adeb1f2d20b1f2489e3d973dae4efc1f2cc5aaa13f2b'
 302
 303     radiogatun[32]
 304     ---------------
 305     >>> hasher = pyradiogatun.new(wl=32)
 306     >>> hasher.update('1234567890123456')
 307     >>> hasher.hexdigest()
 308     '59612324f3f42d3096e69125d2733b86143ae668ae9ed561ad785e0eac8dba25'
 309
 310     >>> hasher = pyradiogatun.new(wl=32)
 311     >>> hasher.update('Santa Barbara, California')
 312     >>> hasher.hexdigest(512)
 313     '041666388ef9655d48996a66dada1193d6646012a7b25a24fb10e6075cf0fc54a162949f4022531dbb6f66b64c3579df49f0f3af5951df9d68af310f2703b06d'
 314
 315     radiogatun[16]
 316     ---------------
 317     >>> hasher = pyradiogatun.new(wl=16)
 318     >>> hasher.update('Santa Barbara, California')
 319     >>> hasher.hexdigest()
 320     'ab2203a8c3de943309b685513a29060339c001acce5900dcd6427a02c1fb8011'
 321
 322     radiogatun[8]
 323     --------------
 324     >>> hasher = pyradiogatun.new(wl=8)
 325     >>> hasher.update('Santa Barbara, California')
 326     >>> hasher.hexdigest()
 327     'e08f5cdbbfd8f5f3c479464a60ac186963e741d28f654e2c961d2f9bebc7de31'
 328     """
 329
 330     crypto = RadioGatunType(wl)
 331     if arg:
 332         crypto.update(arg)
 333
 334     return crypto
 335
 336 # ======================================================================
 337 # HELPER FUNCTIONS
 338 # ======================================================================
 339
 340 def rotateRight(x, amountToShift, totalBits):
 341     """Rotate x (consisting of 'totalBits' bits) n bits to right.
 342
 343     x             = integer input to be rotated
 344     amountToShift = the amount of bits that should be shifted
 345     totalBits     = total amount bits at the input for rotation
 346     """
 347     x = x%(2**totalBits)
 348     n_mod = ((amountToShift % totalBits) + totalBits) % totalBits
 349     return  ((x >> n_mod) | ((x << (totalBits-n_mod)))&((2**totalBits)-1))
 350
 351 def string2number(i):
 352     """ Convert a string to a number
 353
 354     Input: string (big-endian)
 355     Output: long or integer
 356     """
 357     return int(i.encode('hex'), 16)
 358
 359 def number2string_N(i, N):
 360     """Convert a number to a string of fixed size
 361
 362     i: long or integer
 363     N: length of string
 364     Output: string (big-endian)
 365     """
 366     s = '%0*x' % (N*2, i)
 367     return s.decode('hex')
 368
 369 # ======================================================================
 370 # DOCTEST ENABLER
 371 # ======================================================================
 372
 373 def _test():
 374     import doctest
 375     doctest.testmod()
 376
 377 if __name__ == "__main__":
 378     print "DOCTEST running... no messages = all good"
 379     _test()