CubeHash: a simple hash function

Introduction to CubeHash

The inputs to CubeHash are

• a parameter i in {1,2,3,...}, the number of initialization rounds, typically 16;
• a parameter r in {1,2,3,...}, the number of rounds per message block, typically 16;
• a parameter b in {1,2,3,...,128}, the number of bytes per message block, typically 32;
• a parameter f in {1,2,3,...}, the number of finalization rounds, typically 32;
• a parameter h in {8,16,24,...,512}, the number of output bits, typically 512; and
• a message m, a string of bits between 0 bits and 2^128-1 bits.

The message is first padded to create a sequence of b-byte input blocks. Padding works as follows: append a 1 bit; then append the minimum possible number of 0 bits to reach a multiple of 8b bits. (The bits in a byte are first 128, then 64, then 32, then 16, then 8, then 4, then 2, then 1.) Implementations restricted to byte-aligned messages can simply append a 128 byte and then the minimum possible number of 0 bytes to reach a multiple of b bytes.

CubeHash maintains a 128-byte state. It xors the first b-byte input block into the first b bytes of the state, transforms the state invertibly through r identical rounds, xors the next b-byte input block into the first b bytes of the state, transforms the state invertibly through r identical rounds, xors the next b-byte input block into the first b bytes of the state, transforms the state invertibly through r identical rounds, etc.

The 128-byte state is viewed as a sequence of 32 4-byte words x[00000], x[00001], x[00010], x[00011], x[00100], ..., x[11111], each of which is interpreted in little-endian form as a 32-bit integer. A round has the following ten steps:

1. Add x[0jklm] into x[1jklm] modulo 2^32, for each (j,k,l,m).
2. Rotate x[0jklm] upwards by 7 bits, for each (j,k,l,m).
3. Swap x[00klm] with x[01klm], for each (k,l,m).
4. Xor x[1jklm] into x[0jklm], for each (j,k,l,m).
5. Swap x[1jk0m] with x[1jk1m], for each (j,k,m).
6. Add x[0jklm] into x[1jklm] modulo 2^32, for each (j,k,l,m).
7. Rotate x[0jklm] upwards by 11 bits, for each (j,k,l,m).
8. Swap x[0j0lm] with x[0j1lm], for each (j,l,m).
9. Xor x[1jklm] into x[0jklm], for each (j,k,l,m).
10. Swap x[1jkl0] with x[1jkl1], for each (j,k,l).

CubeHash produces the initial state as follows. Set the first three state words x[00000], x[00001], x[00010] to the integers h/8, b, r respectively. Set the remaining state words to 0. Then transform the state invertibly through i rounds. Of course, the implementor can eliminate these transformations at the expense of storage by precomputing the initial state for any particular h,b,r.

After all input blocks are handled, CubeHash produces the final hash as follows. Xor the integer 1 into the last state word x[11111]. Transform the state invertibly through f rounds. Finally, output the first h/8 bytes of the state.

Overall a round has 32 32-bit additions and 32 32-bit xors, so CubeHashr/b has 32r/b 32-bit additions and 32r/b 32-bit xors for each byte of the padded message; in other words, 128r/b bit additions and 128r/b bit xors for each bit of the padded message. The finalization has 32f 32-bit additions and 32f 32-bit xors, comparable cost to handling fb/r bytes of input. The initialization, if not precomputed, has 32i 32-bit additions and 32i 32-bit xors, comparable cost to handling ib/r bytes of input.

My main recommendation is CubeHash512, defined as CubeHash16+16/32+32–512. CubeHash512 uses 16 32-bit additions and 16 32-bit xors for each byte of the padded message. Finalization has comparable cost to handling 16 bytes of input. Initialization has comparable cost to handling 8 bytes of input.

Version