hlextend.py (16806B)
1# Copyright (C) 2014 by Stephen Bradshaw 2# 3# SHA1 and SHA2 generation routines from SlowSha https://code.google.com/p/slowsha/ 4# which is: Copyright (C) 2011 by Stefano Palazzo 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 Pure Python Hash Length Extension module. 26 27 Currently supports SHA1, SHA256 and SHA512, more algorithms will 28 be added in the future. 29 30 31 Create a hash by calling one of the named constuctor functions: 32 sha1(), sha256(), and sha512(), or by calling new(algorithm). 33 34 The hash objects have the following methods: 35 36 hash(message): 37 38 Feeds data into the hash function using the normal interface. 39 40 extend(appendData, knownData, secretLength, startHash, raw=False): 41 42 Performs a hash length extension attack. Returns the string to 43 use when appending data. 44 45 hexdigest(): 46 47 Returns a hexlified version of the hash output. 48 49 50 Assume you have a hash generated from an unknown secret value concatenated with 51 a known value, and you want to be able to produce a valid hash after appending 52 additional data to the known value. 53 54 If the hash algorithm used is one of the vulnerable functions implemented in 55 this module, is is possible to achieve this without knowing the secret value 56 as long as you know (or can guess, perhaps by brute force) the length of that 57 secret value. This is called a hash length extension attack. 58 59 60 Given an existing sha1 hash value '52e98441017043eee154a6d1af98c5e0efab055c', 61 known data of 'hello', an unknown secret of length 10 and data you wish 62 to append of 'file', you would do the following to perform the attack: 63 64 >>> import hlextend 65 >>> sha = hlextend.new('sha1') 66 >>> print sha.extend('file', 'hello', 10, '52e98441017043eee154a6d1af98c5e0efab055c') 67 'hello\\x80\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00 68 \\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00 69 \\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00xfile' 70 >>> print sha.hexdigest() 71 c60fa7de0860d4048a3bfb36b70299a95e6587c9 72 73 The unknown secret (of length 10), that when hashed appended with 'hello' produces 74 a SHA1 hash of '52e98441017043eee154a6d1af98c5e0efab055c', will then produce 75 a SHA1 hash of 'c60fa7de0860d4048a3bfb36b70299a95e6587c9' when appended with the output 76 from the extend function above. 77 78 If you are not sure of the exact length of the secret value, simply try the above 79 multiple times specifying different values for the length to brute force. 80 81''' 82 83 84 85from re import match 86from math import ceil 87 88 89__version__ = "0.1" 90 91 92 93class Hash(object): 94 '''Parent class for hash functions''' 95 96 97 def hash(self, message): 98 '''Normal input for data into hash function''' 99 100 length = bin(len(message) * 8)[2:].rjust(self._blockSize, "0") 101 102 while len(message) > self._blockSize: 103 self._transform(''.join([bin(ord(a))[2:].rjust(8, "0") for a in message[:self._blockSize]])) 104 message = message[self._blockSize:] 105 106 message = self.__hashBinaryPad(message, length) 107 108 109 for a in range(len(message) // self._b2): 110 self._transform(message[a * self._b2:a * self._b2 + self._b2]) 111 112 113 114 def extend(self, appendData, knownData, secretLength, startHash, raw=False): 115 '''Hash length extension input for data into hash function''' 116 117 self.__checkInput(secretLength, startHash) 118 self.__setStartingHash(startHash) 119 120 extendLength = self.__hashGetExtendLength(secretLength, knownData, appendData) 121 122 message = appendData 123 124 while len(message) > self._blockSize: 125 self._transform(''.join([bin(ord(a))[2:].rjust(8, "0") for a in message[:self._blockSize]])) 126 message = message[self._blockSize:] 127 128 message = self.__hashBinaryPad(message, extendLength) 129 130 for i in range(len(message) // self._b2): 131 self._transform(message[i * self._b2:i * self._b2 + self._b2]) 132 133 return self.__hashGetPadData(secretLength, knownData, appendData, raw=raw) 134 135 136 def hexdigest(self): 137 '''Outputs hash data in hexlified format''' 138 return ''.join( [ (('%0' + str(self._b1) + 'x') % (a)) for a in self.__digest()]) 139 140 141 def __init__(self): 142 # pre calculate some values that get used a lot 143 self._b1 = self._blockSize/8 144 self._b2 = self._blockSize*8 145 146 147 148 def __digest(self): 149 return [self.__getattribute__(a) for a in dir(self) if match('^_h\d+$', a)] 150 151 152 def __setStartingHash(self, startHash): 153 c = 0 154 hashVals = [ int(startHash[a:a+int(self._b1)],base=16) for a in range(0,len(startHash), int(self._b1)) ] 155 for hv in [ a for a in dir(self) if match('^_h\d+$', a) ]: 156 self.__setattr__(hv, hashVals[c]) 157 c+=1 158 159 160 def __checkInput(self, secretLength, startHash): 161 if not isinstance(secretLength, int): 162 raise TypeError('secretLength must be a valid integer') 163 if secretLength < 1: 164 raise ValueError('secretLength must be grater than 0') 165 if not match('^[a-fA-F0-9]{' + str(len(self.hexdigest())) + '}$', startHash): 166 raise ValueError('startHash must be a string of length ' + str(len(self.hexdigest())) + ' in hexlified format') 167 168 169 def __byter(self, byteVal): 170 '''Helper function to return usable values for hash extension append data''' 171 if byteVal < 0x20 or byteVal > 0x7e: 172 return '\\x%02x' %(byteVal) 173 else: 174 return chr(byteVal) 175 176 177 def __binToByte(self, binary): 178 '''Convert a binary string to a byte string''' 179 return ''.join([ chr(int(binary[a:a+8],base=2)) for a in range(0,len(binary),8) ]) 180 181 182 183 def __hashGetExtendLength(self, secretLength, knownData, appendData): 184 '''Length function for hash length extension attacks''' 185 # binary length (secretLength + len(knownData) + size of binarysize+1) rounded to a multiple of blockSize + length of appended data 186 originalHashLength = int(ceil((secretLength+len(knownData)+self._b1+1)/float(self._blockSize)) * self._blockSize) 187 newHashLength = originalHashLength + len(appendData) 188 return bin(newHashLength * 8)[2:].rjust(self._blockSize, "0") 189 190 191 def __hashGetPadData(self, secretLength, knownData, appendData, raw=False): 192 '''Return append value for hash extension attack''' 193 originalHashLength = bin((secretLength+len(knownData)) * 8)[2:].rjust(self._blockSize, "0") 194 padData = ''.join(bin(ord(i))[2:].rjust(8, "0") for i in knownData) + "1" 195 padData += "0" * (((self._blockSize*7) - (len(padData)+(secretLength*8)) % self._b2) % self._b2) + originalHashLength 196 if not raw: 197 return ''.join([ self.__byter(int(padData[a:a+8],base=2)) for a in range(0,len(padData),8) ]) + appendData 198 else: 199 return self.__binToByte(padData) + appendData 200 201 202 def __hashBinaryPad(self, message, length): 203 '''Pads the final blockSize block with \x80, zeros, and the length, converts to binary''' 204 message = ''.join(bin(ord(i))[2:].rjust(8, "0") for i in message) + "1" 205 message += "0" * (((self._blockSize*7) - len(message) % self._b2) % self._b2) + length 206 return message 207 208 209 210 211class SHA1 (Hash): 212 213 _h0, _h1, _h2, _h3, _h4, = ( 214 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0) 215 216 _blockSize = 64 217 218 219 def _transform(self, chunk): 220 221 lrot = lambda x, n: (x << n) | (x >> (32 - n)) 222 w = [] 223 224 for j in range(len(chunk) // 32): 225 w.append(int(chunk[j * 32:j * 32 + 32], 2)) 226 227 for i in range(16, 80): 228 w.append(lrot(w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16], 1) 229 & 0xffffffff) 230 231 a = self._h0 232 b = self._h1 233 c = self._h2 234 d = self._h3 235 e = self._h4 236 237 for i in range(80): 238 239 if i <= i <= 19: 240 f, k = d ^ (b & (c ^ d)), 0x5a827999 241 elif 20 <= i <= 39: 242 f, k = b ^ c ^ d, 0x6ed9eba1 243 elif 40 <= i <= 59: 244 f, k = (b & c) | (d & (b | c)), 0x8f1bbcdc 245 elif 60 <= i <= 79: 246 f, k = b ^ c ^ d, 0xca62c1d6 247 248 temp = lrot(a, 5) + f + e + k + w[i] & 0xffffffff 249 a, b, c, d, e = temp, a, lrot(b, 30), c, d 250 251 self._h0 = (self._h0 + a) & 0xffffffff 252 self._h1 = (self._h1 + b) & 0xffffffff 253 self._h2 = (self._h2 + c) & 0xffffffff 254 self._h3 = (self._h3 + d) & 0xffffffff 255 self._h4 = (self._h4 + e) & 0xffffffff 256 257 258 259class SHA256 (Hash): 260 261 _h0, _h1, _h2, _h3, _h4, _h5, _h6, _h7 = ( 262 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 263 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19) 264 265 _blockSize = 64 266 267 268 def _transform(self, chunk): 269 rrot = lambda x, n: (x >> n) | (x << (32 - n)) 270 w = [] 271 272 k = [ 273 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 274 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 275 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 276 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 277 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 278 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 279 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 280 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 281 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 282 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 283 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 284 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 285 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 286 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 287 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 288 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2] 289 290 for j in range(len(chunk) // 32): 291 w.append(int(chunk[j * 32:j * 32 + 32], 2)) 292 293 for i in range(16, 64): 294 s0 = rrot(w[i - 15], 7) ^ rrot(w[i - 15], 18) ^ (w[i - 15] >> 3) 295 s1 = rrot(w[i - 2], 17) ^ rrot(w[i - 2], 19) ^ (w[i - 2] >> 10) 296 w.append((w[i - 16] + s0 + w[i - 7] + s1) & 0xffffffff) 297 298 a = self._h0 299 b = self._h1 300 c = self._h2 301 d = self._h3 302 e = self._h4 303 f = self._h5 304 g = self._h6 305 h = self._h7 306 307 for i in range(64): 308 s0 = rrot(a, 2) ^ rrot(a, 13) ^ rrot(a, 22) 309 maj = (a & b) ^ (a & c) ^ (b & c) 310 t2 = s0 + maj 311 s1 = rrot(e, 6) ^ rrot(e, 11) ^ rrot(e, 25) 312 ch = (e & f) ^ ((~ e) & g) 313 t1 = h + s1 + ch + k[i] + w[i] 314 315 h = g 316 g = f 317 f = e 318 e = (d + t1) & 0xffffffff 319 d = c 320 c = b 321 b = a 322 a = (t1 + t2) & 0xffffffff 323 324 self._h0 = (self._h0 + a) & 0xffffffff 325 self._h1 = (self._h1 + b) & 0xffffffff 326 self._h2 = (self._h2 + c) & 0xffffffff 327 self._h3 = (self._h3 + d) & 0xffffffff 328 self._h4 = (self._h4 + e) & 0xffffffff 329 self._h5 = (self._h5 + f) & 0xffffffff 330 self._h6 = (self._h6 + g) & 0xffffffff 331 self._h7 = (self._h7 + h) & 0xffffffff 332 333 334 335 336class SHA512 (Hash): 337 338 _h0, _h1, _h2, _h3, _h4, _h5, _h6, _h7 = ( 339 0x6a09e667f3bcc908, 0xbb67ae8584caa73b, 0x3c6ef372fe94f82b, 340 0xa54ff53a5f1d36f1, 0x510e527fade682d1, 0x9b05688c2b3e6c1f, 341 0x1f83d9abfb41bd6b, 0x5be0cd19137e2179) 342 343 _blockSize = 128 344 345 346 def _transform(self, chunk): 347 348 rrot = lambda x, n: (x >> n) | (x << (64 - n)) 349 w = [] 350 351 k = [ 352 0x428a2f98d728ae22, 0x7137449123ef65cd, 353 0xb5c0fbcfec4d3b2f, 0xe9b5dba58189dbbc, 354 0x3956c25bf348b538, 0x59f111f1b605d019, 355 0x923f82a4af194f9b, 0xab1c5ed5da6d8118, 356 0xd807aa98a3030242, 0x12835b0145706fbe, 357 0x243185be4ee4b28c, 0x550c7dc3d5ffb4e2, 358 0x72be5d74f27b896f, 0x80deb1fe3b1696b1, 359 0x9bdc06a725c71235, 0xc19bf174cf692694, 360 0xe49b69c19ef14ad2, 0xefbe4786384f25e3, 361 0x0fc19dc68b8cd5b5, 0x240ca1cc77ac9c65, 362 0x2de92c6f592b0275, 0x4a7484aa6ea6e483, 363 0x5cb0a9dcbd41fbd4, 0x76f988da831153b5, 364 0x983e5152ee66dfab, 0xa831c66d2db43210, 365 0xb00327c898fb213f, 0xbf597fc7beef0ee4, 366 0xc6e00bf33da88fc2, 0xd5a79147930aa725, 367 0x06ca6351e003826f, 0x142929670a0e6e70, 368 0x27b70a8546d22ffc, 0x2e1b21385c26c926, 369 0x4d2c6dfc5ac42aed, 0x53380d139d95b3df, 370 0x650a73548baf63de, 0x766a0abb3c77b2a8, 371 0x81c2c92e47edaee6, 0x92722c851482353b, 372 0xa2bfe8a14cf10364, 0xa81a664bbc423001, 373 0xc24b8b70d0f89791, 0xc76c51a30654be30, 374 0xd192e819d6ef5218, 0xd69906245565a910, 375 0xf40e35855771202a, 0x106aa07032bbd1b8, 376 0x19a4c116b8d2d0c8, 0x1e376c085141ab53, 377 0x2748774cdf8eeb99, 0x34b0bcb5e19b48a8, 378 0x391c0cb3c5c95a63, 0x4ed8aa4ae3418acb, 379 0x5b9cca4f7763e373, 0x682e6ff3d6b2b8a3, 380 0x748f82ee5defb2fc, 0x78a5636f43172f60, 381 0x84c87814a1f0ab72, 0x8cc702081a6439ec, 382 0x90befffa23631e28, 0xa4506cebde82bde9, 383 0xbef9a3f7b2c67915, 0xc67178f2e372532b, 384 0xca273eceea26619c, 0xd186b8c721c0c207, 385 0xeada7dd6cde0eb1e, 0xf57d4f7fee6ed178, 386 0x06f067aa72176fba, 0x0a637dc5a2c898a6, 387 0x113f9804bef90dae, 0x1b710b35131c471b, 388 0x28db77f523047d84, 0x32caab7b40c72493, 389 0x3c9ebe0a15c9bebc, 0x431d67c49c100d4c, 390 0x4cc5d4becb3e42b6, 0x597f299cfc657e2a, 391 0x5fcb6fab3ad6faec, 0x6c44198c4a475817] 392 393 for j in range(len(chunk) // 64): 394 w.append(int(chunk[j * 64:j * 64 + 64], 2)) 395 396 for i in range(16, 80): 397 s0 = rrot(w[i - 15], 1) ^ rrot(w[i - 15], 8) ^ (w[i - 15] >> 7) 398 s1 = rrot(w[i - 2], 19) ^ rrot(w[i - 2], 61) ^ (w[i - 2] >> 6) 399 w.append((w[i - 16] + s0 + w[i - 7] + s1) & 0xffffffffffffffff) 400 401 a = self._h0 402 b = self._h1 403 c = self._h2 404 d = self._h3 405 e = self._h4 406 f = self._h5 407 g = self._h6 408 h = self._h7 409 410 for i in range(80): 411 s0 = rrot(a, 28) ^ rrot(a, 34) ^ rrot(a, 39) 412 maj = (a & b) ^ (a & c) ^ (b & c) 413 t2 = s0 + maj 414 s1 = rrot(e, 14) ^ rrot(e, 18) ^ rrot(e, 41) 415 ch = (e & f) ^ ((~ e) & g) 416 t1 = h + s1 + ch + k[i] + w[i] 417 418 h = g 419 g = f 420 f = e 421 e = (d + t1) & 0xffffffffffffffff 422 d = c 423 c = b 424 b = a 425 a = (t1 + t2) & 0xffffffffffffffff 426 427 self._h0 = (self._h0 + a) & 0xffffffffffffffff 428 self._h1 = (self._h1 + b) & 0xffffffffffffffff 429 self._h2 = (self._h2 + c) & 0xffffffffffffffff 430 self._h3 = (self._h3 + d) & 0xffffffffffffffff 431 self._h4 = (self._h4 + e) & 0xffffffffffffffff 432 self._h5 = (self._h5 + f) & 0xffffffffffffffff 433 self._h6 = (self._h6 + g) & 0xffffffffffffffff 434 self._h7 = (self._h7 + h) & 0xffffffffffffffff 435 436 437 438 439 440def new(algorithm): 441 obj = { 442 'sha1': SHA1, 443 'sha256': SHA256, 444 'sha512': SHA512, 445 }[algorithm]() 446 return obj 447 448 449 450def sha1(): 451 ''' Returns a new sha1 hash object ''' 452 return new('sha1') 453 454 455 456def sha256(): 457 ''' Returns a new sha256 hash object ''' 458 return new('sha256', ) 459 460 461 462def sha512(): 463 ''' Returns a new sha512 hash object ''' 464 return new('sha512', ) 465 466 467 468__all__ = ('sha1', 'sha256', 'sha512') 469 470