CubeHash
Encyclopedia
CubeHash 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
. 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".
CubeHash advanced to the second round of the competition, but was not chosen as one of the 5 finalists.
CubeHash r/b-h works based on the three parameters r, b, and h.
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.
The initialization vector is the same for all 8/1-512 hashes, and is as follows:
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:
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:
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:
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.
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
submitted to the NIST hash function competition
NIST hash function competition
The NIST hash function competition is an open competition held by the US National Institute of Standards and Technology for a new SHA-3 function to replace the older SHA-1 and SHA-2, which was formally announced in the Federal Register on November 2, 2007...
by Daniel J. Bernstein
Daniel J. Bernstein
Daniel Julius Bernstein is a mathematician, cryptologist, programmer, and professor of mathematics at the University of Illinois at Chicago...
. Message blocks are XORed into the initial bits of a 128-byte state, which goes through an r-round bijective
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
transformation between blocks. The initial NIST proposal ("Cubehash8/1") required about 200 cycles per byte
Cycles per byte
Cycles per byte is a unit of measurement which indicates the number of clock cycles a microprocessor will perform per byte of data processed in an algorithm. It is commonly used as a partial indicator of real-world performance in cryptographic functions....
. 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".
CubeHash advanced to the second round of the competition, but was not chosen as one of the 5 finalists.
How it works
- 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
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
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
Avalanche effect
In cryptography, the avalanche effect refers to a desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions. The avalanche effect is evident if, when an input is changed slightly the output changes significantly...
.
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.