#!/usr/bin/env python # _*_ coding: latin1 _*_ from __future__ import print_function # needed by Python2 intro = """ blake.py version 3 BLAKE is a SHA3 round-3 finalist designed and submitted by Jean-Philippe Aumasson et al. At the core of BLAKE is a ChaCha-like mixer, very similar to that found in the stream cipher, ChaCha8. Besides being a very good mixer, ChaCha is fast. One test on a 2.0GHz Core 2 Duo of 10,000 iterations of BLAKE-256 on a short message produced a time of 5.7 seconds. Not bad, but if raw speed is what you want, look to the the C version. It is 40x faster and did the same thing in 0.13 seconds. This implementation assumes all data is in increments of whole bytes. (The formal definition of BLAKE allows for hashing individual bits.) Note too that this implementation does include the round-3 tweaks where the number of rounds was increased to 14/16 from 10/14. This version appears to work for Python 2.6.x and up, including 3.2. References: http://www.131002.net/blake/ http://csrc.nist.gov/groups/ST/hash/sha-3/index.html http://en.wikipedia.org/wiki/BLAKE_(hash_function) Copyright (c) 2009-2011 by Larry Bugbee, Kent, WA ALL RIGHTS RESERVED. blake.py IS EXPERIMENTAL SOFTWARE FOR EDUCATIONAL PURPOSES ONLY. IT IS MADE AVAILABLE "AS-IS" WITHOUT WARRANTY OR GUARANTEE OF ANY KIND. USE SIGNIFIES ACCEPTANCE OF ALL RISK. To make your learning and experimentation less cumbersome, blake.py is free for any use. FWIW, comparative times for different versions of Python: 64-bit: 2.6 6.284s 2.7 6.343s 3.2 7.620s pypy (2.7) 2.080s 32-bit: 2.5 (32) 15.389s (with psyco) 2.7-32 13.645s 3.2-32 12.574s Enjoy, Larry Bugbee March 2011 rev May 2011 - fixed Python version check (tx JP) rev May 2011 - ported to Python3 """ import struct from binascii import hexlify, unhexlify try: import psyco have_psyco = True print('psyco enabled') except: have_psyco = False #--------------------------------------------------------------- class BLAKE(object): # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - # initial values, constants and padding # IVx for BLAKE-x IV64 = [ 0x6A09E667F3BCC908, 0xBB67AE8584CAA73B, 0x3C6EF372FE94F82B, 0xA54FF53A5F1D36F1, 0x510E527FADE682D1, 0x9B05688C2B3E6C1F, 0x1F83D9ABFB41BD6B, 0x5BE0CD19137E2179, ] IV48 = [ 0xCBBB9D5DC1059ED8, 0x629A292A367CD507, 0x9159015A3070DD17, 0x152FECD8F70E5939, 0x67332667FFC00B31, 0x8EB44A8768581511, 0xDB0C2E0D64F98FA7, 0x47B5481DBEFA4FA4, ] # note: the values here are the same as the high-order # half-words of IV64 IV32 = [ 0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A, 0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19, ] # note: the values here are the same as the low-order # half-words of IV48 IV28 = [ 0xC1059ED8, 0x367CD507, 0x3070DD17, 0xF70E5939, 0xFFC00B31, 0x68581511, 0x64F98FA7, 0xBEFA4FA4, ] # constants for BLAKE-64 and BLAKE-48 C64 = [ 0x243F6A8885A308D3, 0x13198A2E03707344, 0xA4093822299F31D0, 0x082EFA98EC4E6C89, 0x452821E638D01377, 0xBE5466CF34E90C6C, 0xC0AC29B7C97C50DD, 0x3F84D5B5B5470917, 0x9216D5D98979FB1B, 0xD1310BA698DFB5AC, 0x2FFD72DBD01ADFB7, 0xB8E1AFED6A267E96, 0xBA7C9045F12C7F99, 0x24A19947B3916CF7, 0x0801F2E2858EFC16, 0x636920D871574E69, ] # constants for BLAKE-32 and BLAKE-28 # note: concatenate and the values are the same as the values # for the 1st half of C64 C32 = [ 0x243F6A88, 0x85A308D3, 0x13198A2E, 0x03707344, 0xA4093822, 0x299F31D0, 0x082EFA98, 0xEC4E6C89, 0x452821E6, 0x38D01377, 0xBE5466CF, 0x34E90C6C, 0xC0AC29B7, 0xC97C50DD, 0x3F84D5B5, 0xB5470917, ] # the 10 permutations of:0,...15} SIGMA = [ [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15], [14,10, 4, 8, 9,15,13, 6, 1,12, 0, 2,11, 7, 5, 3], [11, 8,12, 0, 5, 2,15,13,10,14, 3, 6, 7, 1, 9, 4], [ 7, 9, 3, 1,13,12,11,14, 2, 6, 5,10, 4, 0,15, 8], [ 9, 0, 5, 7, 2, 4,10,15,14, 1,11,12, 6, 8, 3,13], [ 2,12, 6,10, 0,11, 8, 3, 4,13, 7, 5,15,14, 1, 9], [12, 5, 1,15,14,13, 4,10, 0, 7, 6, 3, 9, 2, 8,11], [13,11, 7,14,12, 1, 3, 9, 5, 0,15, 4, 8, 6, 2,10], [ 6,15,14, 9,11, 3, 0, 8,12, 2,13, 7, 1, 4,10, 5], [10, 2, 8, 4, 7, 6, 1, 5,15,11, 9,14, 3,12,13, 0], [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15], [14,10, 4, 8, 9,15,13, 6, 1,12, 0, 2,11, 7, 5, 3], [11, 8,12, 0, 5, 2,15,13,10,14, 3, 6, 7, 1, 9, 4], [ 7, 9, 3, 1,13,12,11,14, 2, 6, 5,10, 4, 0,15, 8], [ 9, 0, 5, 7, 2, 4,10,15,14, 1,11,12, 6, 8, 3,13], [ 2,12, 6,10, 0,11, 8, 3, 4,13, 7, 5,15,14, 1, 9], [12, 5, 1,15,14,13, 4,10, 0, 7, 6, 3, 9, 2, 8,11], [13,11, 7,14,12, 1, 3, 9, 5, 0,15, 4, 8, 6, 2,10], [ 6,15,14, 9,11, 3, 0, 8,12, 2,13, 7, 1, 4,10, 5], [10, 2, 8, 4, 7, 6, 1, 5,15,11, 9,14, 3,12,13, 0], ] MASK32BITS = 0xFFFFFFFF MASK64BITS = 0xFFFFFFFFFFFFFFFF # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - def __init__(self, hashbitlen): """ load the hashSate structure (copy hashbitlen...) hashbitlen: length of the hash output """ if hashbitlen not in [224, 256, 384, 512]: raise Exception('hash length not 224, 256, 384 or 512') self.hashbitlen = hashbitlen self.h = [0]*8 # current chain value (initialized to the IV) self.t = 0 # number of *BITS* hashed so far self.cache = b'' # cached leftover data not yet compressed self.salt = [0]*4 # salt (null by default) self.init = 1 # set to 2 by update and 3 by final self.nullt = 0 # Boolean value for special case \ell_i=0 # The algorithm is the same for both the 32- and 64- versions # of BLAKE. The difference is in word size (4 vs 8 bytes), # blocksize (64 vs 128 bytes), number of rounds (14 vs 16) # and a few very specific constants. if (hashbitlen == 224) or (hashbitlen == 256): # setup for 32-bit words and 64-bit block self.byte2int = self._fourByte2int self.int2byte = self._int2fourByte self.MASK = self.MASK32BITS self.WORDBYTES = 4 self.WORDBITS = 32 self.BLKBYTES = 64 self.BLKBITS = 512 self.ROUNDS = 14 # was 10 before round 3 self.cxx = self.C32 self.rot1 = 16 # num bits to shift in G self.rot2 = 12 # num bits to shift in G self.rot3 = 8 # num bits to shift in G self.rot4 = 7 # num bits to shift in G self.mul = 0 # for 32-bit words, 32<>1 is the same as i/2 but faster) v[12] = v[12] ^ (self.t & MASK) v[13] = v[13] ^ (self.t & MASK) v[14] = v[14] ^ (self.t >> self.WORDBITS) v[15] = v[15] ^ (self.t >> self.WORDBITS) # - - - - - - - - - - - - - - - - - # ready? let's ChaCha!!! def G(a, b, c, d, i): va = v[a] # it's faster to deref and reref later vb = v[b] vc = v[c] vd = v[d] sri = SIGMA[round][i] sri1 = SIGMA[round][i+1] va = ((va + vb) + (m[sri] ^ cxx[sri1]) ) & MASK x = vd ^ va vd = (x >> rot1) | ((x << (WORDBITS-rot1)) & MASK) vc = (vc + vd) & MASK x = vb ^ vc vb = (x >> rot2) | ((x << (WORDBITS-rot2)) & MASK) va = ((va + vb) + (m[sri1] ^ cxx[sri]) ) & MASK x = vd ^ va vd = (x >> rot3) | ((x << (WORDBITS-rot3)) & MASK) vc = (vc + vd) & MASK x = vb ^ vc vb = (x >> rot4) | ((x << (WORDBITS-rot4)) & MASK) v[a] = va v[b] = vb v[c] = vc v[d] = vd for round in range(self.ROUNDS): # column step G( 0, 4, 8,12, 0) G( 1, 5, 9,13, 2) G( 2, 6,10,14, 4) G( 3, 7,11,15, 6) # diagonal step G( 0, 5,10,15, 8) G( 1, 6,11,12,10) G( 2, 7, 8,13,12) G( 3, 4, 9,14,14) # - - - - - - - - - - - - - - - - - # save current hash value (use i&0x3 to get 0,1,2,3,0,1,2,3) self.h = [self.h[i]^v[i]^v[i+8]^self.salt[i&0x3] for i in range(8)] # print('self.h', [num2hex(h) for h in self.h]) # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - def addsalt(self, salt): """ adds a salt to the hash function (OPTIONAL) should be called AFTER Init, and BEFORE update salt: a bytestring, length determined by hashbitlen. if not of sufficient length, the bytestring will be assumed to be a big endian number and prefixed with an appropriate number of null bytes, and if too large, only the low order bytes will be used. if hashbitlen=224 or 256, then salt will be 16 bytes if hashbitlen=384 or 512, then salt will be 32 bytes """ # fail if addsalt() was not called at the right time if self.init != 1: raise Exception('addsalt() not called after init() and before update()') # salt size is to be 4x word size saltsize = self.WORDBYTES * 4 # if too short, prefix with null bytes. if too long, # truncate high order bytes if len(salt) < saltsize: salt = (chr(0)*(saltsize-len(salt)) + salt) else: salt = salt[-saltsize:] # prep the salt array self.salt[0] = self.byte2int(salt[ : 4<= fill: self.cache = self.cache + data[:fill] self.t += BLKBITS # update counter self._compress(self.cache) self.cache = b'' data = data[fill:] datalen -= fill # compress new data until not enough for a full block while datalen >= BLKBYTES: self.t += BLKBITS # update counter self._compress(data[:BLKBYTES]) data = data[BLKBYTES:] datalen -= BLKBYTES # cache all leftover bytes until next call to update() if datalen > 0: self.cache = self.cache + data[:datalen] # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - def final(self, data=b''): """ finalize the hash -- pad and hash remaining data returns hashval, the digest """ ZZ = b'\x00' ZO = b'\x01' OZ = b'\x80' OO = b'\x81' PADDING = OZ + ZZ*128 # pre-formatted padding data if data: self.update(data) # copy nb. bits hash in total as a 64-bit BE word # copy nb. bits hash in total as a 128-bit BE word tt = self.t + (len(self.cache) << 3) if self.BLKBYTES == 64: msglen = self._int2eightByte(tt) else: low = tt & self.MASK high = tt >> self.WORDBITS msglen = self._int2eightByte(high) + self._int2eightByte(low) # size of block without the words at the end that count # the number of bits, 55 or 111. # Note: (((self.WORDBITS/8)*2)+1) equals ((self.WORDBITS>>2)+1) sizewithout = self.BLKBYTES - ((self.WORDBITS>>2)+1) if len(self.cache) == sizewithout: # special case of one padding byte self.t -= 8 if self.hashbitlen in [224, 384]: self.update(OZ) else: self.update(OO) else: if len(self.cache) < sizewithout: # enough space to fill the block self.t -= (sizewithout - len(self.cache)) << 3 self.update(PADDING[:sizewithout - len(self.cache)]) # use t=0 if no remaining data if len(self.cache) == 0: self.nullt=1 else: # NOT enough space, need 2 compressions # ...add marker, pad with nulls and compress self.t -= (self.BLKBYTES - len(self.cache)) << 3 self.update(PADDING[:self.BLKBYTES - len(self.cache)]) # ...now pad w/nulls leaving space for marker & bit count self.t -= (sizewithout+1) << 3 self.update(PADDING[1:sizewithout+1]) # pad with zeroes self.nullt = 1 # raise flag to set t=0 at the next _compress # append a marker byte if self.hashbitlen in [224, 384]: self.update(ZZ) else: self.update(ZO) self.t -= 8 # append the number of bits (long long) self.t -= self.BLKBYTES self.update(msglen) hashval = [] if self.BLKBYTES == 64: for h in self.h: hashval.append(self._int2fourByte(h)) else: for h in self.h: hashval.append(self._int2eightByte(h)) return b''.join(hashval)[:self.hashbitlen >> 3] digest = final # may use digest() as a synonym for final() # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - def hash(self, data): """ all-in-one function data data to be hashed (bytestring) returns digest value (bytestring) """ return self.digest(data) # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - # utility functions def _fourByte2int(self, bytestr): # see also long2byt() below """ convert a 4-byte string to an int (long) """ return struct.unpack('!L', bytestr)[0] def _eightByte2int(self, bytestr): """ convert a 8-byte string to an int (long long) """ return struct.unpack('!Q', bytestr)[0] def _int2fourByte(self, x): # see also long2byt() below """ convert a number to a 4-byte string, high order truncation possible (in Python x could be a BIGNUM) """ return struct.pack('!L', x) def _int2eightByte(self, x): """ convert a number to a 8-byte string, high order truncation possible (in Python x could be a BIGNUM) """ return struct.pack('!Q', x) # - - - - - - - - - - - - - - - - - - - - - - - - - - - - - if have_psyco: _compress = psyco.proxy(_compress) #--------------------------------------------------------------- #--------------------------------------------------------------- # test vectors def main(): import sys if sys.version_info[0] < 3: print('\n *** this version intended for Python 3.x *** \n') if 0: print(intro) def test_BLAKE(hashlen, msg, expect): print(' BLAKE-%d: msg = "%s" length = %d' % (hashlen, msg.decode(), len(msg))) digest = BLAKE(hashlen).hash(msg) print(' %s %s' % ( 'valid ' if digest == unhexlify(expect) else 'ERROR >>>', hexlify(digest).decode()) ) if 1: print('') print('single null-byte message:') msg = b'\x00' hashlen = 256 expect = ('0ce8d4ef4dd7cd8d62dfded9d4edb0a7' + '74ae6a41929a74da23109e8f11139c87' ).encode('latin1') test_BLAKE(hashlen, msg, expect) hashlen = 224 expect = ('4504cb0314fb2a4f7a692e696e487912' + 'fe3f2468fe312c73a5278ec5' ).encode('latin1') test_BLAKE(hashlen, msg, expect) hashlen = 512 expect = ('97961587f6d970faba6d2478045de6d1' + 'fabd09b61ae50932054d52bc29d31be4' + 'ff9102b9f69e2bbdb83be13d4b9c0609' + '1e5fa0b48bd081b634058be0ec49beb3' ).encode('latin1') test_BLAKE(hashlen, msg, expect) hashlen = 384 expect = ('10281f67e135e90ae8e882251a355510' + 'a719367ad70227b137343e1bc122015c' + '29391e8545b5272d13a7c2879da3d807' ).encode('latin1') test_BLAKE(hashlen, msg, expect) if 1: print('') print('72 null-bytes message:') msg = b'\x00'*72 hashlen = 256 expect = ('d419bad32d504fb7d44d460c42c5593f' + 'e544fa4c135dec31e21bd9abdcc22d41' ).encode('latin1') test_BLAKE(hashlen, msg, expect) hashlen = 224 expect = ('f5aa00dd1cb847e3140372af7b5c46b4' + '888d82c8c0a917913cfb5d04' ).encode('latin1') test_BLAKE(hashlen, msg, expect) print('') print('144 null-bytes message:') msg = b'\x00'*144 hashlen = 512 expect = ('313717d608e9cf758dcb1eb0f0c3cf9f' + 'c150b2d500fb33f51c52afc99d358a2f' + '1374b8a38bba7974e7f6ef79cab16f22' + 'ce1e649d6e01ad9589c213045d545dde' ).encode('latin1') test_BLAKE(hashlen, msg, expect) hashlen = 384 expect = ('0b9845dd429566cdab772ba195d271ef' + 'fe2d0211f16991d766ba749447c5cde5' + '69780b2daa66c4b224a2ec2e5d09174c' ).encode('latin1') test_BLAKE(hashlen, msg, expect) if 1: print('') print('more:') if 1: msg = b'Kilroy was here!' hashlen = 256 expect = ('b25c02ccfa1f664d25a15d999b56a4be' + '1ad84a029a96be5d654387a2def99916' ).encode('latin1') test_BLAKE(hashlen, msg, expect) msg = b'The quick brown fox jumps over the lazy dog' hashlen = 512 expect = ('1F7E26F63B6AD25A0896FD978FD050A1' + '766391D2FD0471A77AFB975E5034B7AD' + '2D9CCF8DFB47ABBBE656E1B82FBC634B' + 'A42CE186E8DC5E1CE09A885D41F43451' ).encode('latin1') test_BLAKE(hashlen, msg, expect) if 0: msg = b'\x00'*55 hashlen = 256 expect = ('dc980544f4181cc43505318e317cdfd4' + '334dab81ae035a28818308867ce23060' ).encode('latin1') test_BLAKE(hashlen, msg, expect) msg = b'\x00'*56 hashlen = 256 expect = ('26ae7c289ebb79c9f3af2285023ab103' + '7a9a6db63f0d6b6c6bbd199ab1627508' ).encode('latin1') test_BLAKE(hashlen, msg, expect) msg = b'\x00'*111 hashlen = 512 expect = ('125695c5cc01de48d8b107c101778fc4' + '47a55ad3440a17dc153c6c652faecdbf' + '017aed68f4f48826b9dfc413ef8f14ae' + '7dfd8b74a0afcf47b61ce7dcb1058976' ).encode('latin1') test_BLAKE(hashlen, msg, expect) msg = b'\x00'*112 hashlen = 512 expect = ('aa42836448c9db34e0e45a49f916b54c' + '25c9eefe3f9f65db0c13654bcbd9a938' + 'c24251f3bedb7105fa4ea54292ce9ebf' + '5adea15ce530fb71cdf409387a78c6ff' ).encode('latin1') test_BLAKE(hashlen, msg, expect) if 1: import time print('') print('simple timimg test:') def time_it(hashsize, iter): t0 = time.time() for i in range(iter): digest = BLAKE(hashsize).hash(b'\x00') # hash a single null byte t1 = time.time() template = '%8d iterations of single-block BLAKE-%d took %6.3f seconds' print(template % (iter, hashsize, (t1-t0))) iterations = [10, 100, 1000, 10000] hashsize = 256 for iter in iterations: time_it(hashsize, iter) #--------------------------------------------------------------- if __name__ == '__main__': main() print('') #--------------------------------------------------------------- #--------------------------------------------------------------- #---------------------------------------------------------------