Cubehash

The operation of CubeHash r / bh is based on three parameters: r , b and h .

• r - the number of rounds (not less than 1)
• b - block size in bytes (from 1 to 128)
• h - hash size in bits (may be 8, 16, 24, 32, ..., 512)

The algorithm has 5 main steps:

• initialization of a 128 byte state as a function of ( h , b , r )
• splitting an incoming message into parts. Each part includes one or more b- byte blocks
• for each b- byte block of the message part: an exclusive “OR” operation is performed on the block and the first b bytes of status and then converts it by r identical rounds
• state completion
• output first h / 8 status bytes

Initialization. A 128-byte state is considered a sequence of 32 four-byte words x ₀₀₀₀₀ , x ₀₀₀₀₁ , x ₀₀₀₁₀ , ..., x ₁₁₁₁₁ , each of which is represented in a little-endian form of 32-bit integers. The first three words x ₀₀₀₀₀ , x ₀₀₀₀₁ , x _{00010 are} set to h / 8, b , r, respectively. The remaining words are zero. Then, the state is transformed by 10 r identical rounds.

Filling. 1 bit is added to the incoming message, then it is supplemented with the minimum possible number of zero bits so that the number of bits is a multiple of 8 b .

It should be noted that filling does not require separation of the storage length of the message, the block for processing and the rest. An implementation can simply store a single number between 0 and 8 b to record the number of bits currently processed in the current block.

Completion. Modulo two is added to the last state of the word x ₁₁₁₁₁ modulo two. Next, the state is converted by 10 r identical rounds.

Each round includes 10 steps:

• add x _{0 jklm} to x _{1 jklm} modulo 2 ³² for each ( j, k, l, m )
• 7-bit left shift in a circle x _{0 jklm} for each ( j, k, l, m )
• exchange x _{00 klm} cx _{01 klm} for each ( k, l, m )
• modulo 2 adding the numbers x _{1 jklm} to x _{0 jklm} for each ( j, k, l, m )
• exchange x _{1 jk 0 m} with x _{1 jk 1 m} for each ( j, k, m )
• add x _{0 jklm} to x _{1 jklm} modulo 2 ³² for each ( j, k, l, m )
• left shift in a circle by 11 bits of the word x _{0 jklm} for each ( j, k, l, m )
• exchange x _{0 j 0 lm} with x _{0 j 1 lm} for each ( j, l, m )
• modulo 2 adding the numbers x _{1 jklm} to x _{0 jklm} for each ( j, k, l, m )
• exchange x _{1 jkl 0} with x _{1 jkl 1} for each ( j, k, l )

The CubeHash algorithm does not include blocks of counters, blocks using random numbers, and the like blocks. Without these blocks, it is easier to find the state in which the collision occurs, but this argument does not work when the size of the state is quite large. A typical attack on CubeHash should make 2 ^ 400 attempts to find a collision of the 1024 bit state for CubeHash. There is also no need to break any symmetry that is used in the rounds .

The initializing state of CubeHash is not symmetrical; if parameter b is not very large, then the attacker does not have enough computing power to calculate a symmetric state or a pair of states.

The main operations used in CubeHash are:

• adding 32 bit number,
• performing an exclusive OR operation on 32 bit numbers and
• fixed shift left or right.

These operations are performed in constant time on typical processors. Most implementations will avoid leaks from various software levels. For example, for most software implementations using AES , key leakage through the cache is possible. This fact forced Intel to add the time constant associated with AES.

At the SHA- 3 competition, NIST tested the proposed functions, one of them was CubeHash with parameters 16/32. Testing was conducted on two Intel Core 2 Duo 6f6 (katana) and Intel Core 2 Duo E8400 1067a (brick) processors:

• 11.47 cycles / byte: CubeHash16 / 32, brick, AMD64 architecture.

• 12.60 cycles / byte: SHA-512, brick, AMD64 architecture.

• 12.60 cycles / byte: SHA-512, katana, AMD64 architecture.

• 12.66 cycles / byte: CubeHash16 / 32, katana, AMD64 architecture.

• 12.74 cycles / byte: CubeHash16 / 32, brick, x86 architecture.

• 14.07 cycles / byte: CubeHash16 / 32, katana, x86 architecture.

• 15.43 cycles / byte: SHA-256, brick, x86 architecture.

• 15.53 cycles / byte: SHA-256, brick, amd64 architecture.

• 15.56 cycles / byte: SHA-256, katana, AMD64 architecture.

• 17.76 cycles / byte: SHA-512, brick, x86 architecture.

• 20.00 cycles / byte: SHA-512, katana, x86 architecture.

• 22.76 cycles / byte: SHA-256, katana, x86 architecture.

It is worth noting that CubeHash is not inferior in speed to its opponents.

This example uses CubeHash 8 / 1-512.

The initializing vector is the same for all 8 / 1-512 hashes and looks like:

  6998f35dfb0930c760948910e626160f36077cf3b58b0d0c57cf193d3341e7b8 \
 a334805b2089f9ef31ffc4142aef3850fe121839e940a4527d5293a27045ca12 \
 9358096e81bf70349a90a44a93c33edb14c3e9844a87dbd0bc451df25212b3ac \
 6aabe51c5df0f63bddbb8ae8fad3cf0fd52582fbad2e2446094025a521a23d5c

Hashing the ASCII Hello message (hex: 0x48, 0x65, 0x6c, 0x6c, 0x6f) uses 6 blocks. The first 5 blocks come (since in this case each letter is one byte) from the message and one more block to fill.

The value of the 512-bit hash is:

  7ce309a25e2e1603ca0fc369267b4d43f0b1b744ac45d6213ca08e7567566444 \
 8e2f62fdbf7bbd637ce40fc293286d75b9d09e8dda31bd029113e02ecccfd39b

A small change in the message (for example, a change in one bit) leads to a significant change in the hash (the so-called avalanche effect ).

For example, take the “hello” message, which differs from “Hello” in just one bit. The hash of this message is:

  01ee7f4eb0e0ebfdb8bf77460f64993faf13afce01b55b0d3d2a63690d25010f \
 7127109455a7c143ef12254183e762b15575e0fcc49c79a0471a970ba8a66638

Change Settings

CubeHash r / bh accepts many different parameters used to determine the hash. This gives flexibility to the algorithm with respect to the end user, who himself determines the best parameters for use. Below are some examples of hashes of various messages using different algorithm parameters. All messages are recorded in ASCII. Three parameters used in hash generation are presented in r / bh format.

  Message: "" (empty string, zero long 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

The stability of this algorithm increases with decreasing b to 1, and with increasing r .
Therefore, CubeHash 8 / 1-512 is more stable (safer) than CubeHash 1 / 1-512, and CubeHash 1 / 1-512 is more stable than CubeHash 1 / 2-512. The weakest possible version of this algorithm is CubeHash 1/128- h . However, safety depends on time. A safer option would be to calculate the hash value longer.

Attacks using a hash function structure are usually the most successful of all kinds of attacks. Such attacks can find collisions, prototypes and second prototypes. However, the distinguishing feature of such attacks is that they are almost always designed for a specific hash function, because such attacks use a specific implementation of state calculation ^[9] .

Single Block Attack

Since the round of calculations in CubeHash is reversible, the initial state can be calculated by performing inverse operations on the final state. A single block attack is based on this circumstance.

Consider the algorithm of this attack.

Take the hash H of a message, b bytes of the second inverse image of the message are calculated using CubeHashr / bh .

1. Set the first h / 8 bytes of the final state using the H hash, and the remaining 128-h / 8 bytes using the trial value T , we get state 6. The method for choosing the trial value will be described later.
2. Applying 10r inverse rounds to state 6, we obtain state 5. Inverse rounds of the function can be obtained by taking the steps of the algorithm in the reverse order, that is, replacing the displacements in a circle to the left by the displacements in a circle to the right and adding by subtracting modulo 2 ³² .
3. We apply the exclusive operation to either 1 and the last word of state 5, so we get state 4
4. Having made r reverse rounds with state 4, we obtain state 3.
5. Let us apply the exclusive operation either to message 0x80 and the first byte of state 4, resulting in state 3.
6. Having made r reverse rounds with state 2, we obtain state 1.
7. If the last 128 - b bytes of state 1 do not match the 128-b bytes of the initialization vector (state 0), then the test message was unsuccessfully selected.
8. Otherwise, the test message was selected successfully. The second inverse image is calculated using either the exclusive state over the first b bytes of state 1 and the first b bytes of the state of the initializing vector.

Repeating the procedure described above with different values ​​of T , a second prototype will ultimately be generated. The method of choosing the value of T is not critical. For example, a sequence of numbers following one after another can be used.

Assuming that CubeHash (in a direct or reverse message) behaves like a random mapping for an arbitrary trial value of T, then the probability that the last 128-b bytes of state 1 will be equal to the corresponding bytes of the initializing vector is 2 ^{−8 (128-b)} . Thus, the number of test messages before success is 2 ^{8 (128-b)} . If 2 ^{8 (128-b)} <2 ^h then an attack based on one block will find the second prototype in fewer attempts, compared to exhaustive search. In other words, an attack based on one block is more effective than exhaustive search for the following values h = 224 and b> 100 , for h = 256 and b> 96 , for h = 384 and b> 80 , for h = 512 and b> 64 .

However, the expected number of attempts necessary to achieve success does not depend on the number of rounds r. Of course, the time needed to carry out an attack increases linearly from r, and not as an exponential function. It should also be noted that for b = 128, any value of T will immediately be the second prototype.

Consider an algorithm to improve the attack of finding the first prototype.

1. Based on the values ​​of ( h , b , r ), we calculate the initialization vector (state 0).
2. For h bits and 1024-h , perform 10r inverse rounds and the exclusive operation or to get the state f .
3. We find two n block sequences that map state 0 and state f to two states that have the same last 1024-h bits.

There are 2 ^nb possible input n blocks and one of them will collide. The number of attempts needed to find a conflict is estimated as

2 * (521 / b - 4) * 2 ^{512 - 4b} = 2 * 522 - 4b - logb

In addition, we take into account that each round requires 2 ¹¹ bit operations, then the formula will change to ^{2,533-4b-logb + logr} bit operations. The acceleration of this attack can be achieved due to the fact that we will search for collisions not only after calculating the nth block, but also in each different state that we have reached (we will use intermediate states). Thus, we will get rid of the multiplier (512 / b-4) . Then the number of attempts necessary to find the collision will be estimated as 2 ^513-4b bit operations. Consider CubeHash-512 with the parameters h, b, r equal to 512, 1, 8, respectively. For an improved algorithm, the number of attempts required to find a collision is ^2,523 compared to the standard attack algorithm with attempts to find a collision of ^2,532 . If r = 8 , for an improved algorithm it is necessary that b> 3 so that the number of attempts is less than 2 ⁵¹² , for a conventional algorithm, conditions b> 5 must be fulfilled.

Symmetry Attack

As mentioned above, the CubeHash algorithm is very symmetrical and does not use any constants. Therefore, there are many classes of symmetry with respect to permutations. The most effective way to attack is to use a symmetry class for which a message extension can generate symmetric messages. For example, we can use a symmetry class called C2. For this class, a state is called symmetric if x _ijkl0 = x _ijkl1 for any i, j, k, l.

When parameter b is 32, that is, CubeHash is normal, message injection gives control over x _00klm for any k, l, m.

Therefore, in order to achieve a symmetric state, you just need to reach a state that satisfies the following 384-bit equation

x _01kl0 = x _01kl1

x _10kl0 = x _10kl1

x _11kl0 = x _11kl1

for any k, l.

And then message injection can be used to achieve a completely symmetrical state. The expected difficulty is ^2,384 .

This can be used to attack the prototype. The algorithm can be written as follows

1. Find message A that will be symmetric with the initializing vector
2. Find a message D that is symmetric in the reverse order with the given one.
3. Form 2 ¹⁹² symmetric messages B _j . Then calculate the state obtained after the operation or on A and B _j
4. Form 2 ¹⁹² symmetric messages With _j . Then calculate the state obtained after performing the operation or over the execution of C _j and D.
5. There is a high probability that there will be a pair of values ​​satisfying

b _01kl0 = c _01kl0

b _10kl0 = c _10kl0

b _11kl0 = c _11kl0

then the following equalities follow from symmetry

b _01kl1 = c _01kl1

b _10kl1 = c _10kl1

b _11kl1 = c _11kl1

satisfied for any k, l.

Then use block X to match the first 256 bits. This gives a prototype - we perform an operation or on A, B _{i 0} , X, C _{i 0} , D.

The complexity of steps 1 and 2 is 2 ³⁸⁴ , and the complexity of steps 3 and 4 is 2 ¹⁹² . It should be noted that it can be implemented without high memory costs. This attack has the same complexity as a power based attack when B is a power of two, but it becomes more effective when b is not a power of two.

The most time-consuming part of an attack based on symmetry is the calculations needed to calculate the symmetric state. Nevertheless, it turns out that this problem is easily solved using the Grover algorithm on a quantum computer. In fact, finding a state that satisfies the equation described above is equivalent to finding a preimage of zero for a hash function that will iterate over the rounds of the CubeHash function, and the output of which will be presented

x ₀₁₀₀₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₀₁₀₀₁

x ₀₁₀₁₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₀₁₀₁₁

x ₀₁₁₀₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₀₁₁₀₁

x ₀₁₁₁₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₀₁₁₁₁

x ₁₀₀₀₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₁₀₀₀₁

x ₁₀₀₁₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₁₀₀₁₁

x ₁₀₁₀₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₁₀₁₀₁

x ₁₀₁₁₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₁₀₁₁₁

x ₁₁₀₀₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₁₁₀₀₁

x ₁₁₀₁₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₁₁₀₁₁

x ₁₁₁₀₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₁₁₁₀₁

x ₁₁₁₁₀${\displaystyle {<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\oplus </span></span>}_{\mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">2</span></span>}}}$ {\ displaystyle \ oplus _ {2}}   x ₁₁₁₁₁

For the 384-bit function, the Grover algorithm has a complexity of 2 ¹⁹² operations. Then an attack using symmetry will require ^2,192 operations, provided that quantum computers are available.

• Eric Brier and Thomas Peyrin. Cryptanalysis of CubeHash // Applied Cryptography and Network Security, 7th International Conference, ACNS 2009. - Springer-Verlag Berlin Heidelberg, 2009. - S. 354-368. - 535 s. - ISBN 978-3-642-01956-2 .

• Algorithm Official Website