CubeHash

Last updated

CubeHash [1] is a cryptographic hash function submitted to the NIST hash function competition by Daniel J. Bernstein. CubeHash has a 128 byte state, uses wide pipe construction, and is ARX based. Message blocks are XORed into the initial bits of a 128-byte state, which then goes through an r-round bijective transformation between blocks. The initial NIST proposal ("Cubehash8/1") required about 200 cycles per byte. [2] After 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]

Contents

CubeHash advanced to the second round of the competition, but was not chosen as one of the 5 finalists. Bernstein has since tuned the parameters further and his main recommendation is CubeHash512, defined as CubeHash16+16/32+32–512. [4]

Operation

This description refers to the latest specification, and not the NIST submission. [4]

CubeHash has 5 parameters, a certain instance is denoted by CubeHashi+r/b+f-h.

In the original NIST submission, i and f was fixed to 10r. The obsolete notation CubeHashr/b-h indicates i and f being implicitly 10r.

The internal state is defined as a five-dimensional array of words (four-byte integers), 0-1 in both dimensions. The words are referred to with their coordinates [00000] to [11111]. The words are treated as little-endian.

The internal state is initialized by setting the first three words ([00000], [00001], [00010]) to h/8, b, and r respectively, all other words to zero. The state is then run through i rounds, and the initialization stage is complete. The state is now the Initialization Vector (IV). The IV can be saved and reused for a given combination of h, b, r.

The message is padded and split to b-byte blocks. The padding appends a 1 bit, followed by as many 0 bits as necessary to make a complete block.

Each block is inputted by XORing to the first b bytes of the state, and then performing r rounds of transformation.

Finally, 1 is XORed to the state word [11111], and then f rounds of transformation are performed.

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

Round function

The ten steps of the mixing function. Two of the five dimensions are unrolled. CubeHash Mixing Function.svg
The ten steps of the mixing function. Two of the five dimensions are unrolled.

CubeHash round function consists of the following ten steps:

  1. Add x[0jklm] into x[1jklm] modulo 232, 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 232, 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).

Example hashes

This example uses CubeHash80+8/1+80-512. The initialization vector is the same for all 80+8/1+f-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 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 parameters. The messages are all in ASCII.

message: ""  (the zero-length string) CubeHash160+16/32+160-512: 4a1d00bbcfcb5a9562fb981e7f7db3350fe2658639d948b9d57452c22328bb32\                            f468b072208450bad5ee178271408be0b16e5633ac8a1e3cf9864cfbfc8e043a  CubeHash80+8/1+80-512: 90bc3f2948f7374065a811f1e47a208a53b1a2f3be1c0072759ed49c9c6c7f28\                        f26eb30d5b0658c563077d599da23f97df0c2c0ac6cce734ffe87b2e76ff7294  CubeHash10+1/1+10-512: 3f917707df9acd9b94244681b3812880e267d204f1fdf795d398799b584fa8f1\                        f4a0b2dbd52fd1c4b6c5e020dc7a96192397dd1bce9b6d16484049f85bb71f2f  CubeHash160+16/32+160-256: 44c6de3ac6c73c391bf0906cb7482600ec06b216c7c54a2a8688a6a42676577d  CubeHash80+8/1+80-256: 38d1e8a22d7baac6fd5262d83de89cacf784a02caa866335299987722aeabc59  CubeHash10+1/1+10-256: 80f72e07d04ddadb44a78823e0af2ea9f72ef3bf366fd773aa1fa33fc030e5cb 
message: "Hello" CubeHash160+16/32+160-512: dcc0503aae279a3c8c95fa1181d37c418783204e2e3048a081392fd61bace883\                            a1f7c4c96b16b4060c42104f1ce45a622f1a9abaeb994beb107fed53a78f588c  CubeHash80+8/1+80-512: 7ce309a25e2e1603ca0fc369267b4d43f0b1b744ac45d6213ca08e7567566444\                        8e2f62fdbf7bbd637ce40fc293286d75b9d09e8dda31bd029113e02ecccfd39b  CubeHash10+1/1+10-512: 13cf99c1a71e40b135f5535bee02e151eb4897e4de410b9cb6d7179c677074eb\                        6ef1ae9a9e685ef2d2807509541f484d39559525179d53838eda95eb3f6a401d  CubeHash160+16/32+160-256: e712139e3b892f2f5fe52d0f30d78a0cb16b51b217da0e4acb103dd0856f2db0  CubeHash80+8/1+80-256: 692638db57760867326f851bd2376533f37b640bd47a0ddc607a9456b692f70f  CubeHash10+1/1+10-256: f63041a946aa98bd47f3175e6009dcb2ccf597b2718617ba46d56f27ffe35d49 
message: "The quick brown fox jumps over the lazy dog" CubeHash160+16/32+160-512: bdba44a28cd16b774bdf3c9511def1a2baf39d4ef98b92c27cf5e37beb8990b7\                            cdb6575dae1a548330780810618b8a5c351c1368904db7ebdf8857d596083a86  CubeHash80+8/1+80-512: ca942b088ed9103726af1fa87b4deb59e50cf3b5c6dcfbcebf5bba22fb39a6be\                        9936c87bfdd7c52fc5e71700993958fa4e7b5e6e2a3672122475c40f9ec816ba  CubeHash10+1/1+10-512: eb7f5f80706e8668c61186c3c710ce57f9094fbfa1dbdc7554842cdbb4d10ce4\                        2fce72736d10b152f6216f23fc648bce810a7af4d58e571ec1b852fa514a0a8e  CubeHash160+16/32+160-256: 5151e251e348cbbfee46538651c06b138b10eeb71cf6ea6054d7ca5fec82eb79  CubeHash80+8/1+80-256: 94e0c958d85cdfaf554919980f0f50b945b88ad08413e0762d6ff0219aff3e55  CubeHash10+1/1+10-256: 217a4876f2b24cec489c9171f85d53395cc979156ea0254938c4c2c59dfdf8a4

The Initialization Vectors for the four variants shown are all different as well. For example, the Initialization Vector for CubeHash80+8/1+80-512 can be seen above, and the IV for CubeHash80+8/1+80-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.

Related Research Articles

<span class="mw-page-title-main">HMAC</span> Computer communications hash algorithm

In cryptography, an HMAC is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and authenticity of a message.

The MD5 message-digest algorithm is a widely used hash function producing a 128-bit hash value. MD5 was designed by Ronald Rivest in 1991 to replace an earlier hash function MD4, and was specified in 1992 as RFC 1321.

<span class="mw-page-title-main">RIPEMD</span> Cryptographic hash function

RIPEMD is a family of cryptographic hash functions developed in 1992 and 1996. There are five functions in the family: RIPEMD, RIPEMD-128, RIPEMD-160, RIPEMD-256, and RIPEMD-320, of which RIPEMD-160 is the most common.

In cryptography, SHA-1 is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard. The algorithm has been cryptographically broken but is still widely used.

In cryptography, Tiger is a cryptographic hash function designed by Ross Anderson and Eli Biham in 1995 for efficiency on 64-bit platforms. The size of a Tiger hash value is 192 bits. Truncated versions can be used for compatibility with protocols assuming a particular hash size. Unlike the SHA-2 family, no distinguishing initialization values are defined; they are simply prefixes of the full Tiger/192 hash value.

HAVAL is a cryptographic hash function. Unlike MD5, but like most modern cryptographic hash functions, HAVAL can produce hashes of different lengths – 128 bits, 160 bits, 192 bits, 224 bits, and 256 bits. HAVAL also allows users to specify the number of rounds to be used to generate the hash. HAVAL was broken in 2004.

The MD2 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1989. The algorithm is optimized for 8-bit computers. MD2 is specified in IETF RFC 1319. The "MD" in MD2 stands for "Message Digest".

SHA-2 is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression function itself built using the Davies–Meyer structure from a specialized block cipher.

The GOST hash function, defined in the standards GOST R 34.11-94 and GOST 34.311-95 is a 256-bit cryptographic hash function. It was initially defined in the Russian national standard GOST R 34.11-94 Information Technology – Cryptographic Information Security – Hash Function. The equivalent standard used by other member-states of the CIS is GOST 34.311-95.

<span class="mw-page-title-main">Merkle–Damgård construction</span> Method of building collision-resistant cryptographic hash functions

In cryptography, the Merkle–Damgård construction or Merkle–Damgård hash function is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. This construction was used in the design of many popular hash algorithms such as MD5, SHA-1 and SHA-2.

<span class="mw-page-title-main">Skein (hash function)</span> Cryptographic hash function

Skein is a cryptographic hash function and one of five finalists in the NIST hash function competition. Entered as a candidate to become the SHA-3 standard, the successor of SHA-1 and SHA-2, it ultimately lost to NIST hash candidate Keccak.

SHA-3 is the latest member of the Secure Hash Algorithm family of standards, released by NIST on August 5, 2015. Although part of the same series of standards, SHA-3 is internally different from the MD5-like structure of SHA-1 and SHA-2.

Grøstl is a cryptographic hash function submitted to the NIST hash function competition by Praveen Gauravaram, Lars Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, and Søren S. Thomsen. Grøstl was chosen as one of the five finalists of the competition. It uses the same S-box as AES in a custom construction. The authors claim speeds of up to 21.4 cycles per byte on an Intel Core 2 Duo, and 9.6 cycles/byte on an Intel i7 with AES-NI.

JH is a cryptographic hash function submitted to the NIST hash function competition by Hongjun Wu. Though chosen as one of the five finalists of the competition, in 2012 JH ultimately lost to NIST hash candidate Keccak. JH has a 1024-bit state, and works on 512-bit input blocks. Processing an input block consists of three steps:

  1. XOR the input block into the left half of the state.
  2. Apply a 42-round unkeyed permutation (encryption function) to the state. This consists of 42 repetitions of:
    1. Break the input into 256 4-bit blocks, and map each through one of two 4-bit S-boxes, the choice being made by a 256-bit round-dependent key schedule. Equivalently, combine each input block with a key bit, and map the result through a 5→4 bit S-box.
    2. Mix adjacent 4-bit blocks using a maximum distance separable code over GF(24).
    3. Permute 4-bit blocks so that they will be adjacent to different blocks in following rounds.
  3. XOR the input block into the right half of the state.

The following tables compare general and technical information for a number of cryptographic hash functions. See the individual functions' articles for further information. This article is not all-inclusive or necessarily up-to-date. An overview of hash function security/cryptanalysis can be found at hash function security summary.

BLAKE is a cryptographic hash function based on Daniel J. Bernstein's ChaCha stream cipher, but a permuted copy of the input block, XORed with round constants, is added before each ChaCha round. Like SHA-2, there are two variants differing in the word size. ChaCha operates on a 4×4 array of words. BLAKE repeatedly combines an 8-word hash value with 16 message words, truncating the ChaCha result to obtain the next hash value. BLAKE-256 and BLAKE-224 use 32-bit words and produce digest sizes of 256 bits and 224 bits, respectively, while BLAKE-512 and BLAKE-384 use 64-bit words and produce digest sizes of 512 bits and 384 bits, respectively.

Streebog is a cryptographic hash function defined in the Russian national standard GOST R 34.11-2012 Information Technology – Cryptographic Information Security – Hash Function. It was created to replace an obsolete GOST hash function defined in the old standard GOST R 34.11-94, and as an asymmetric reply to SHA-3 competition by the US National Institute of Standards and Technology. The function is also described in RFC 6986 and one out of hash functions in ISO/IEC 10118-3:2018.

Kupyna is a cryptographic hash function defined in the Ukrainian national standard DSTU 7564:2014. It was created to replace an obsolete GOST hash function defined in the old standard GOST 34.11-95, similar to Streebog hash function standardized in Russia.

<span class="mw-page-title-main">OpenTimestamps</span>

OpenTimestamps (OTS) is an open-source project that aims to provide a standard format for blockchain timestamping. With the advent of systems like Bitcoin, it is possible to create and verify proofs of existence of documents (timestamps) without relying on a trusted third party; this represents an enhancement in term of security, since it excludes the possibility of a malicious trusted third party to compromise the timestamp.

LSH is a cryptographic hash function designed in 2014 by South Korea to provide integrity in general-purpose software environments such as PCs and smart devices. LSH is one of the cryptographic algorithms approved by the Korean Cryptographic Module Validation Program (KCMVP). And it is the national standard of South Korea.

References

  1. ↑ Daniel J. Bernstein (2009-09-14). "CubeHash specification (2.B.1)" (PDF).
  2. ↑ Daniel J. Bernstein (2008-10-28). "CubeHash efficiency estimates (2.B.2)" (PDF).
  3. ↑ Daniel J. Bernstein (2009-07-15). "CubeHash parameter tweak: 16 times faster" (PDF).
  4. 1 2 Daniel J. Bernstein. "Introduction to CubeHash".
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.