CubeHash

CubeHash^[1] is a cryptographic hash function submitted to the NIST hash function competition by Daniel J. Bernstein. Message blocks are XORed into the initial bits of a 128-byte state, which goes through an r-round bijective transformation between blocks. The initial NIST proposal ("Cubehash8/1") required about 200 cycles per byte^[2]. After some clarifications from NIST, the author changed the proposal to Cubehash16/32, which "is approximately 16 times faster than CubeHash8/1, easily catching up to both SHA-256 and SHA-512 on the reference platform" while still maintaining a "comfortable security margin"^[3].

CubeHash advanced to the second round of the competition, but was not chosen as one of the 5 finalists.

How it works

Figure 1. Diagram of how CubeHash works

CubeHash r/b-h works based on the three parameters r, b, and h.

• r is the number of rounds to use, defined for {1, 2, 3, ... }
• b is the block size in bytes, defined for {1, 2, 3, ... 128}
• h is the size of the hash output in bits, defined for {8, 16, 24, 32, ... 512}

The internal state is maintained as an array of 32 four-byte integers (referred to as words).

The internal state is initialized by setting the first three words to h/8, b, and r, respectively, all other words to zero. The state is then run through 10r rounds, and the initialization stage is complete. The state is now the Initialization Vector.

The message is split into however many b-byte blocks are necessary to hold all of the information. Message padding occurs only once at the end of every message. The padding appends a 1 bit, followed by the minimum number of 0 bits necessary to make a complete block.

State updates are performed by XORing each b-byte message block into the first b bytes of the currently permuted state, and then performing r rounds of transformation. This continues until all b-byte blocks have been mixed into the state.

At this point, the state is ready to finalize, and a 1 is XORed into the last state word, and then 10r rounds of transformation are performed on the state.

The output hash is now contained in the first h/8 bytes of this final state.

Example Hashes

This example uses CubeHash 8/1-512.
The initialization vector is the same for all 8/1-512 hashes, and is as follows:

6998f35dfb0930c760948910e626160f36077cf3b58b0d0c57cf193d3341e7b8\
a334805b2089f9ef31ffc4142aef3850fe121839e940a4527d5293a27045ca12\
9358096e81bf70349a90a44a93c33edb14c3e9844a87dbd0bc451df25212b3ac\
6aabe51c5df0f63bddbb8ae8fad3cf0fd52582fbad2e2446094025a521a23d5c

Hashing the ASCII message "Hello" (hex: 0x48, 0x65, 0x6c, 0x6c, 0x6f) uses 6 message blocks. There are 5 blocks from the message, and since this is a byte-aligned input, there is 1 block for padding.
The 512 bit hash value is:

7ce309a25e2e1603ca0fc369267b4d43f0b1b744ac45d6213ca08e7567566444\
8e2f62fdbf7bbd637ce40fc293286d75b9d09e8dda31bd029113e02ecccfd39b

A small change in the message, such as flipping a single bit, will wildly change the hash output, due to the avalanche effect.
Hashing the message "hello" (which only differs from "Hello" in 1 bit position) gives the following hash value:

01ee7f4eb0e0ebfdb8bf77460f64993faf13afce01b55b0d3d2a63690d25010f\
7127109455a7c143ef12254183e762b15575e0fcc49c79a0471a970ba8a66638

Parameter Changes

CubeHash r/b-h allows for many different parameters to be used to determine the hash output. It is up to the user to decide which parameters they wish to use. Here are several example hashes of different messages, using different CubeHash algorithm parameters. The messages are all in ASCII. The three parameters used to generate the hash are in r/b-h format.

message: ""  (the zero-length string)
CubeHash 16/32-512: 4a1d00bbcfcb5a9562fb981e7f7db3350fe2658639d948b9d57452c22328bb32\
                    f468b072208450bad5ee178271408be0b16e5633ac8a1e3cf9864cfbfc8e043a

CubeHash 8/1-512: 90bc3f2948f7374065a811f1e47a208a53b1a2f3be1c0072759ed49c9c6c7f28\
                  f26eb30d5b0658c563077d599da23f97df0c2c0ac6cce734ffe87b2e76ff7294

CubeHash 1/1-512: 3f917707df9acd9b94244681b3812880e267d204f1fdf795d398799b584fa8f1\
                  f4a0b2dbd52fd1c4b6c5e020dc7a96192397dd1bce9b6d16484049f85bb71f2f

CubeHash 16/32-256: 44c6de3ac6c73c391bf0906cb7482600ec06b216c7c54a2a8688a6a42676577d

CubeHash 8/1-256: 38d1e8a22d7baac6fd5262d83de89cacf784a02caa866335299987722aeabc59

CubeHash 1/1-256: 80f72e07d04ddadb44a78823e0af2ea9f72ef3bf366fd773aa1fa33fc030e5cb

message: "Hello"
CubeHash 16/32-512: dcc0503aae279a3c8c95fa1181d37c418783204e2e3048a081392fd61bace883\
                    a1f7c4c96b16b4060c42104f1ce45a622f1a9abaeb994beb107fed53a78f588c

CubeHash 8/1-512: 7ce309a25e2e1603ca0fc369267b4d43f0b1b744ac45d6213ca08e7567566444\
                  8e2f62fdbf7bbd637ce40fc293286d75b9d09e8dda31bd029113e02ecccfd39b

CubeHash 1/1-512: 13cf99c1a71e40b135f5535bee02e151eb4897e4de410b9cb6d7179c677074eb\
                  6ef1ae9a9e685ef2d2807509541f484d39559525179d53838eda95eb3f6a401d

CubeHash 16/32-256: e712139e3b892f2f5fe52d0f30d78a0cb16b51b217da0e4acb103dd0856f2db0

CubeHash 8/1-256: 692638db57760867326f851bd2376533f37b640bd47a0ddc607a9456b692f70f

CubeHash 1/1-256: f63041a946aa98bd47f3175e6009dcb2ccf597b2718617ba46d56f27ffe35d49

message: "The quick brown fox jumps over the lazy dog"
CubeHash 16/32-512: bdba44a28cd16b774bdf3c9511def1a2baf39d4ef98b92c27cf5e37beb8990b7\
                    cdb6575dae1a548330780810618b8a5c351c1368904db7ebdf8857d596083a86

CubeHash 8/1-512: ca942b088ed9103726af1fa87b4deb59e50cf3b5c6dcfbcebf5bba22fb39a6be\
                  9936c87bfdd7c52fc5e71700993958fa4e7b5e6e2a3672122475c40f9ec816ba

CubeHash 1/1-512: eb7f5f80706e8668c61186c3c710ce57f9094fbfa1dbdc7554842cdbb4d10ce4\
                  2fce72736d10b152f6216f23fc648bce810a7af4d58e571ec1b852fa514a0a8e

CubeHash 16/32-256: 5151e251e348cbbfee46538651c06b138b10eeb71cf6ea6054d7ca5fec82eb79

CubeHash 8/1-256: 94e0c958d85cdfaf554919980f0f50b945b88ad08413e0762d6ff0219aff3e55

CubeHash 1/1-256: 217a4876f2b24cec489c9171f85d53395cc979156ea0254938c4c2c59dfdf8a4

The Initialization Vectors for the four variants shown are all different as well.
For example, the Initialization Vector for CubeHash 8/1-512 can be seen above, and the IV for CubeHash 8/1-256 is:

830b2bd5273d616fd785876a4a500218a5388963eeb702fb47547842459f8d89\
8727a1c8ba40bd48cef47fe82543c2735c033052ae9fcd632d4541bde6b6cb0d\
cb8a9cdf579f5b67b2ae00968180af6e51ebdf0ca597cd2bf91f981f7ab29a62\
01ad72d946e6c075c6d1337e0a293d6f90c438ac38be153f32aa288ffc5eca8a

Security

The strength of this function increases as b decreases towards 1, and as r increases.
So CubeHash 8/1-512 is stronger (more secure) than CubeHash 1/1-512, and CubeHash 1/1-512 is stronger than CubeHash 1/2-512. The weakest possible version of this algorithm is CubeHash 1/128-h.
However, there is a security versus time tradeoff. A more secure version will take longer to compute a hash value than a weakened version.

References

1. ^ Daniel J. Bernstein (2009-09-14) (PDF). CubeHash specification (2.B.1). http://cubehash.cr.yp.to/submission2/spec.pdf. 
2. ^ Daniel J. Bernstein (2008-10-28) (PDF). CubeHash efficiency estimates (2.B.2). http://cubehash.cr.yp.to/submission/estimates.pdf. 
3. ^ Daniel J. Bernstein (2009-07-15) (PDF). CubeHash parameter tweak: 16 times faster. http://cubehash.cr.yp.to/submission/tweak.pdf. 

External links

• The CubeHash web site