PUBLIC

Copyright Google Inc, 2018.

PSHA2 is a cryptographic hash function specialized for the needs of the google3 build system and source system. It is derived from SHA-256 by a tree construction, with 0-4 intermediate levels depending on message size.

Define SHA256x16(s):

The input message s is divided into 4-byte chunks striped over 16 "lanes", each of which is hashed with SHA256. Chunk number i starting at byte offset i * 4 is part of lane i % 16. Partial chunks are not padded.

For example, given len(s) = 137, the lane hashes are

• h[0] = SHA256(s[0:4] + s[64:68] + s[128:132])
• h[1] = SHA256(s[4:8] + s[68:72] + s[132:136])
• h[2] = SHA256(s[8:12] + s[72:76] + s[136])
• h[3] = SHA256(s[12:16] + s[76:80])
• ...
• h[15] = SHA256(s[60:64] + s[124:128])

The binary lane hashes are concatenated with the original length of the input (big-endian) and a type suffix to form a summary, which is hashed again.

The value of SHA256x16(s) is SHA256(h[0] + h[1] + ... + h[15] + BE64(len(s)) + "/J16").

(This construction permits accelerated implementations in terms of vector instructions.)

NOTE: The "/J16" suffix (mnemonic: J-lanes=16) serves two purposes:

• prevent the summary from colliding with any short message hashed by CHUNK_HASH below
• ease any future migration where we want to define a new hash function but avoid colliding with SHA256x16

Define CHUNK_HASH(s):

if len(s) < 1024: SHA256(s + "/")

if len(s) >= 1024: SHA256x16(s)

For example, CHUNK_HASH("hello") = b2f361b1385fd06bb7807a4d7d26064911b1a7efe6746378ffe63a7a1c234ce3

and CHUNK_HASH(`seq 300`) = cde9c9596fd8e050be0545c6fbb42c5a96796452a17b3adef41c0252e0547125

(Plain SHA256 is faster than accelerated SHA256x16 for very short messages.)

Define CHUNK_LIST(s):

The input is divided into 2 MiB chunks, each of which is hashed with CHUNK_HASH.

For example, given len(s) = 6283185, the chunk hashes are

• h[0] = CHUNK_HASH(s[0:2097152])
• h[1] = CHUNK_HASH(s[2097152:4194304])
• h[2] = CHUNK_HASH(s[4194304:6283185])

The binary chunk hashes are concatenated with the original length of the input and a type suffix.

The value of CHUNK_LIST(s) is h[0] + ... + h[n] + BE64(len(s)) + "/T21".

For example, CHUNK_LIST(`seq 913470`) =

009c35809036580c90709b1e246d9ee814eab713386626565342ab64e3778b9f 2595560c0292d3dbdc182eb1f34cfde0dee72b2fb0784b7ae5f752f8f2274e79 8a8c87368972ef766c8f91a2bdbf0675b2012a165c8435bc45314019eaf4f3bc 00000000005fdfb12f543231

(We wish to use multiple CPUs to hash long messages.)

NOTE: The "/T21" suffix (mnemonic: Tree at 221 bytes) is primarily a debugging aid, to make it obvious when a message might be acting as a chunk list. It is not required for correctness, since there is never ambiguity between a chunk list and the other suffixed messages above.

Combining all the above, define PSHA2(s):

if                  len(s) == 0             : "\x00"

if  0             < len(s) <= 2**21         : "\x01" + BE24(len(s)) + CHUNK_HASH(s)

if  2**21         < len(s) <= 2**37 - 2**21 : "\x02" + BE40(len(s)) + CHUNK_HASH(CHUNK_LIST(s))

if  2**37 - 2**21 < len(s) <= 2**52         : "\x03" + BE56(len(s)) + CHUNK_HASH(CHUNK_LIST(CHUNK_LIST(s)))

if  2**52         < len(s)                  : undefined

For example, PSHA2(`seq 300`) = 01000444cde9c9596fd8e050be0545c6fbb42c5a96796452a17b3adef41c0252e0547125

and PSHA2(`seq 913470`) = 0200005fdfb1ad5ab7fdae86f18fc023daffea11eac2d644c6d3df9c0f0afc6630cb7dc43f58

Note that PSHA2 values include the exact length of the input. The leading tag byte and length have little entropy, so use as rowkeys etc may require permutation.

One can compute PSHA2(CHUNK_LIST(s)) from PSHA2(s), which allows uniform treatment of CHUNK_LIST values and user messages. Inputs shorter than 128GB result in a chunk list which fits in a single chunk; beyond that, additional indirection may be required.

The leading byte ('\x00' .. '\x03') makes PSHA2 a prefix code, and allows unambiguous use in a field which may also hold a hex-encoded MD5, common in existing protocols. However, for ease of debugging, a printable representation of PSHA2 is recommended in situations where size and speed are not critical (e.g. an RPC payload containing a single digest field).

The choice of big-endian encoding in PSHA2 leaves fewer occupied bit prefixes if we need to further carve the space later.