python_sha3.py
1 #! /usr/bin/env python 2 # coding: utf-8 3 4 # The Keccak sponge function was designed by Guido Bertoni, Joan Daemen, 5 # Michaël Peeters and Gilles Van Assche. For more information, feedback or 6 # questions, please refer to their website: http://keccak.noekeon.org/ 7 # 8 # Based on the implementation by Renaud Bauvin, 9 # from http://keccak.noekeon.org/KeccakInPython-3.0.zip 10 # 11 # Modified by Moshe Kaplan to be hashlib-compliant 12 # 13 # To the extent possible under law, the implementer has waived all copyright 14 # and related or neighboring rights to the source code in this file. 15 # http://creativecommons.org/publicdomain/zero/1.0/ 16 17 18 import math 19 20 21 def sha3_224(data=None): 22 return Keccak(c=448, r=1152, n=224, data=data) 23 24 25 def sha3_256(data=None): 26 return Keccak(c=512, r=1088, n=256, data=data) 27 28 29 def sha3_384(data=None): 30 return Keccak(c=768, r=832, n=384, data=data) 31 32 33 def sha3_512(data=None): 34 return Keccak(c=1024, r=576, n=512, data=data) 35 36 37 class KeccakError(Exception): 38 """Custom error Class used in the Keccak implementation""" 39 40 def __init__(self, value): 41 self.value = value 42 43 def __str__(self): 44 return repr(self.value) 45 46 47 class Keccak: 48 def __init__(self, r, c, n, data=None): 49 # Initialize the constants used throughout Keccak 50 # bitrate 51 self.r = r 52 # capacity 53 self.c = c 54 # output size 55 self.n = n 56 57 self.b = r + c 58 # b = 25*w 59 self.w = self.b // 25 60 # 2**l = w 61 self.l = int(math.log(self.w, 2)) 62 63 self.n_r = 12 + 2 * self.l 64 65 self.block_size = r 66 self.digest_size = n 67 68 # Initialize the state of the sponge 69 # The state is made up of 25 words, each word being w bits. 70 self.S = [[0, 0, 0, 0, 0], 71 [0, 0, 0, 0, 0], 72 [0, 0, 0, 0, 0], 73 [0, 0, 0, 0, 0], 74 [0, 0, 0, 0, 0]] 75 76 # A string of hexchars, where each char represents 4 bits. 77 self.buffered_data = "" 78 79 # Store the calculated digest. 80 # We'll only apply padding and recalculate the hash if it's modified. 81 self.last_digest = None 82 83 if data: 84 self.update(data) 85 86 # Constants 87 88 ## Round constants 89 RC = [0x0000000000000001, 90 0x0000000000008082, 91 0x800000000000808A, 92 0x8000000080008000, 93 0x000000000000808B, 94 0x0000000080000001, 95 0x8000000080008081, 96 0x8000000000008009, 97 0x000000000000008A, 98 0x0000000000000088, 99 0x0000000080008009, 100 0x000000008000000A, 101 0x000000008000808B, 102 0x800000000000008B, 103 0x8000000000008089, 104 0x8000000000008003, 105 0x8000000000008002, 106 0x8000000000000080, 107 0x000000000000800A, 108 0x800000008000000A, 109 0x8000000080008081, 110 0x8000000000008080, 111 0x0000000080000001, 112 0x8000000080008008] 113 114 ## Rotation offsets 115 r = [[0, 36, 3, 41, 18], 116 [1, 44, 10, 45, 2], 117 [62, 6, 43, 15, 61], 118 [28, 55, 25, 21, 56], 119 [27, 20, 39, 8, 14]] 120 121 @staticmethod 122 def Round(A, RCfixed, w): 123 """Perform one round of computation as defined in the Keccak-f permutation 124 125 A: current state (5x5 matrix) 126 RCfixed: value of round constant to use (integer) 127 """ 128 129 #Initialization of temporary variables 130 B = [[0, 0, 0, 0, 0], 131 [0, 0, 0, 0, 0], 132 [0, 0, 0, 0, 0], 133 [0, 0, 0, 0, 0], 134 [0, 0, 0, 0, 0]] 135 C = [0, 0, 0, 0, 0] 136 D = [0, 0, 0, 0, 0] 137 138 #Theta step 139 for x in range(5): 140 C[x] = A[x][0] ^ A[x][1] ^ A[x][2] ^ A[x][3] ^ A[x][4] 141 142 for x in range(5): 143 D[x] = C[(x - 1) % 5] ^ _rot(C[(x + 1) % 5], 1, w) 144 145 for x in range(5): 146 for y in range(5): 147 A[x][y] = A[x][y] ^ D[x] 148 149 #Rho and Pi steps 150 for x in range(5): 151 for y in range(5): 152 B[y][(2 * x + 3 * y) % 5] = _rot(A[x][y], Keccak.r[x][y], w) 153 154 #Chi step 155 for x in range(5): 156 for y in range(5): 157 A[x][y] = B[x][y] ^ ((~B[(x + 1) % 5][y]) & B[(x + 2) % 5][y]) 158 159 #Iota step 160 A[0][0] = A[0][0] ^ RCfixed 161 162 return A 163 164 @staticmethod 165 def KeccakF(A, n_r, w): 166 """Perform Keccak-f function on the state A 167 168 A: 5x5 matrix containing the state, where each entry is a string of hexchars that is 'w' bits long 169 n_r: number of rounds 170 w: word size 171 """ 172 173 for i in xrange(n_r): 174 A = Keccak.Round(A, Keccak.RC[i] % (1 << w), w) 175 176 return A 177 178 ### Padding rule 179 # This is a disgusting piece of code. Clean it. 180 @staticmethod 181 def pad10star1(M, n): 182 """Pad M with the pad10*1 padding rule to reach a length multiple of r bits 183 184 M: message pair (length in bits, string of hex characters ('9AFC...') 185 n: length in bits (must be a multiple of 8) 186 Example: pad10star1([60, 'BA594E0FB9EBBD30'],8) returns 'BA594E0FB9EBBD93' 187 """ 188 189 [my_string_length, my_string] = M 190 191 # Check the parameter n 192 if n % 8 != 0: 193 raise KeccakError.KeccakError("n must be a multiple of 8") 194 195 # Check the length of the provided string 196 if len(my_string) % 2 != 0: 197 #Pad with one '0' to reach correct length (don't know test 198 #vectors coding) 199 my_string += '0' 200 if my_string_length > (len(my_string) // 2 * 8): 201 raise KeccakError.KeccakError("the string is too short to contain the number of bits announced") 202 203 nr_bytes_filled = my_string_length // 8 204 nbr_bits_filled = my_string_length % 8 205 l = my_string_length % n 206 if ((n - 8) <= l <= (n - 2)): 207 if (nbr_bits_filled == 0): 208 my_byte = 0 209 else: 210 my_byte = int(my_string[nr_bytes_filled * 2:nr_bytes_filled * 2 + 2], 16) 211 my_byte = (my_byte >> (8 - nbr_bits_filled)) 212 my_byte = my_byte + 2 ** (nbr_bits_filled) + 2 ** 7 213 my_byte = "%02X" % my_byte 214 my_string = my_string[0:nr_bytes_filled * 2] + my_byte 215 else: 216 if (nbr_bits_filled == 0): 217 my_byte = 0 218 else: 219 my_byte = int(my_string[nr_bytes_filled * 2:nr_bytes_filled * 2 + 2], 16) 220 my_byte = (my_byte >> (8 - nbr_bits_filled)) 221 my_byte = my_byte + 2 ** (nbr_bits_filled) 222 my_byte = "%02X" % my_byte 223 my_string = my_string[0:nr_bytes_filled * 2] + my_byte 224 while((8 * len(my_string) // 2) % n < (n - 8)): 225 my_string = my_string + '00' 226 my_string = my_string + '80' 227 228 return my_string 229 230 def update(self, arg): 231 # Update the hash object with the string arg. Repeated calls are equivalent to a single call with the concatenation of all the arguments: m.update(a); m.update(b) is equivalent to m.update(a+b). arg is a normal bytestring. 232 233 self.last_digest = None 234 # Convert the data into a workable format, and add it to the buffer 235 self.buffered_data += arg.encode('hex') 236 237 # Absorb any blocks we can: 238 if len(self.buffered_data) * 4 >= self.r: 239 extra_bits = len(self.buffered_data) * 4 % self.r 240 241 # An exact fit! 242 if extra_bits == 0: 243 P = self.buffered_data 244 self.buffered_data = "" 245 else: 246 # Slice it up into the first r*a bits, for some constant a>=1, and the remaining total-r*a bits. 247 P = self.buffered_data[:-extra_bits // 4] 248 self.buffered_data = self.buffered_data[-extra_bits // 4:] 249 250 #Absorbing phase 251 for i in xrange((len(P) * 8 // 2) // self.r): 252 to_convert = P[i * (2 * self.r // 8):(i + 1) * (2 * self.r // 8)] + '00' * (self.c // 8) 253 P_i = _convertStrToTable(to_convert, self.w, self.b) 254 255 # First apply the XOR to the state + block 256 for y in xrange(5): 257 for x in xrange(5): 258 self.S[x][y] = self.S[x][y] ^ P_i[x][y] 259 # Then apply the block permutation, Keccak-F 260 self.S = Keccak.KeccakF(self.S, self.n_r, self.w) 261 262 def digest(self): 263 """Return the digest of the strings passed to the update() method so far. 264 265 This is a string of digest_size bytes which may contain non-ASCII 266 characters, including null bytes.""" 267 268 if self.last_digest: 269 return self.last_digest 270 271 # UGLY WARNING 272 # Handle bytestring/hexstring conversions 273 M = _build_message_pair(self.buffered_data.decode('hex')) 274 275 # First finish the padding and force the final update: 276 self.buffered_data = Keccak.pad10star1(M, self.r) 277 self.update('') 278 # UGLY WARNING over 279 280 assert len(self.buffered_data) == 0, "Why is there data left in the buffer? %s with length %d" % (self.buffered_data, len(self.buffered_data) * 4) 281 282 # Squeezing time! 283 Z = '' 284 outputLength = self.n 285 while outputLength > 0: 286 string = _convertTableToStr(self.S, self.w) 287 # Read the first 'r' bits of the state 288 Z = Z + string[:self.r * 2 // 8] 289 outputLength -= self.r 290 if outputLength > 0: 291 S = KeccakF(S, verbose) 292 293 self.last_digest = Z[:2 * self.n // 8].decode('hex') 294 return self.last_digest 295 296 def hexdigest(self): 297 """Like digest() except the digest is returned as a string of hex digits 298 299 This may be used to exchange the value safely in email or other 300 non-binary environments.""" 301 return self.digest().encode('hex') 302 303 def copy(self): 304 # First initialize whatever can be done normally 305 duplicate = Keccak(c=self.c, r=self.r, n=self.n) 306 # Then copy over the state. 307 for i in xrange(5): 308 for j in xrange(5): 309 duplicate.S[i][j] = self.S[i][j] 310 # and any other stored data 311 duplicate.buffered_data = self.buffered_data 312 duplicate.last_digest = self.last_digest 313 return duplicate 314 315 316 ## Generic utility functions 317 318 def _build_message_pair(data): 319 hex_data = data.encode('hex') 320 size = len(hex_data) * 4 321 return (size, hex_data) 322 323 324 def _rot(x, shift_amount, length): 325 """Rotate x shift_amount bits to the left, considering the \ 326 string of bits is length bits long""" 327 328 shift_amount = shift_amount % length 329 return ((x >> (length - shift_amount)) + (x << shift_amount)) % (1 << length) 330 331 ### Conversion functions String <-> Table (and vice-versa) 332 333 334 def _fromHexStringToLane(string): 335 """Convert a string of bytes written in hexadecimal to a lane value""" 336 337 #Check that the string has an even number of characters i.e. whole number of bytes 338 if len(string) % 2 != 0: 339 raise KeccakError.KeccakError("The provided string does not end with a full byte") 340 341 #Perform the conversion 342 temp = '' 343 nrBytes = len(string) // 2 344 for i in xrange(nrBytes): 345 offset = (nrBytes - i - 1) * 2 346 temp += string[offset:offset + 2] 347 return int(temp, 16) 348 349 350 def _fromLaneToHexString(lane, w): 351 """Convert a lane value to a string of bytes written in hexadecimal""" 352 353 laneHexBE = (("%%0%dX" % (w // 4)) % lane) 354 #Perform the conversion 355 temp = '' 356 nrBytes = len(laneHexBE) // 2 357 for i in xrange(nrBytes): 358 offset = (nrBytes - i - 1) * 2 359 temp += laneHexBE[offset:offset + 2] 360 return temp.upper() 361 362 363 def _convertStrToTable(string, w, b): 364 """Convert a string of hex-chars to its 5x5 matrix representation 365 366 string: string of bytes of hex-coded bytes (e.g. '9A2C...')""" 367 368 # Check that the input paramaters are expected 369 if w % 8 != 0: 370 raise KeccakError("w is not a multiple of 8") 371 372 # Each character in the string represents 4 bits. 373 # The string should have exactly 'b' bits. 374 if len(string) * 4 != b: 375 raise KeccakError.KeccakError("string can't be divided in 25 blocks of w bits\ 376 i.e. string must have exactly b bits") 377 378 #Convert 379 output = [[0, 0, 0, 0, 0], 380 [0, 0, 0, 0, 0], 381 [0, 0, 0, 0, 0], 382 [0, 0, 0, 0, 0], 383 [0, 0, 0, 0, 0]] 384 385 bits_per_char = 2 * w // 8 386 for x in xrange(5): 387 for y in xrange(5): 388 # Each entry will have b/25=w bits. 389 offset = (5 * y + x) * bits_per_char 390 # Store the data into the associated word. 391 hexstring = string[offset:offset + bits_per_char] 392 output[x][y] = _fromHexStringToLane(hexstring) 393 return output 394 395 396 def _convertTableToStr(table, w): 397 """Convert a 5x5 matrix representation to its string representation""" 398 399 #Check input format 400 if w % 8 != 0: 401 raise KeccakError.KeccakError("w is not a multiple of 8") 402 if (len(table) != 5) or any(len(row) != 5 for row in table): 403 raise KeccakError.KeccakError("table must be 5x5") 404 405 #Convert 406 output = [''] * 25 407 for x in xrange(5): 408 for y in xrange(5): 409 output[5 * y + x] = _fromLaneToHexString(table[x][y], w) 410 output = ''.join(output).upper() 411 return output