Collision and Preimage Attacks on Vortex as submitted to the SHA-3 competition
by Lars R. Knudsen and Florian Mendel and Christian Rechberger and Søren S. Thomsen
In this note we point out that collision and preimage attacks on
MDC-2 also apply to Vortex in the version submitted to the SHA-3
competition [3]. In particular, this includes a recently
discovered collision attack [2] that has a time complexity below
the birthday bound and a preimage attack that allows various
time/memory tradeoffs.
(1) One can construct a pseudo-collision for the compression
function with a complexity of about 2^{n/4} instead of 2^{n/2}
(see [1]).
(2) Preimages for Vortex can be constructed with a complexity of
about 2^{3n/4} instead of 2^n (see [1] and extension of it as in
[2]). Using Vortex-256 as an example, depending on memory
requirements this results in runtimes between 2^{192} and 2^{256}. An
even lower runtime (as low as 2^{n/2} for MDC-2 as recently
discovered [2]) seems difficult to achieve.
(3) One can find collisions for Vortex with a time complexity
slightly faster than brute force search (see [2]). Using
Vortex-256 as an example, this results in a runtime of 2^{122.5}.
Short description of Vortex (actually a sub block):
For the full description, refer to [3].
A||B = V(C_A(W_0) \oplus W_0; C_B(W_0)\oplus W_0)
A||B =V(C_A(W_1) \oplus W_1; C_B(W_1) \oplus W_1)
ad 1: Pseudo-Collision Attack:
The attack can be summarized as follows:
- Compute x = C_A(W_0) \oplus W_0 for a fixed value of W_0 and
2^{n/4} different values of A and save x in the list L_A.
- Compute Y = C_B(W_0) \oplus W_0 for the same value of W_0 and
2^{n/4} different values of B and save y in the list L_B.
- Choose another W_0
- Compute x and y for arbitrary values of A (and B) and check for
a match in list L_A (and L_B). Note that due to the birthday
paradox we expect to find a match in L_A (and L_B) after testing
2^{n/4} candidates for x (and y).
Hence, we can construct a pseudo-collision (or semi-free-start
collision) for Vortex with complexity 2^{n/4}
ad 2: Preimage and Second Preimage Attack
The transformation V is not invertible (which contrasts MDC-2),
nevertheless the same attack applies in a straight-forward way:
Assume we have given the final hash value h=A'||B' then the attack
can be summarized as follows:
- Invert the function V to get x and y (again x = C_A(W_0) + W_0
and y = C_B(W_0) + W_0). This has a complexity of about 2^{n/2}
and can be summarized as follows:
* Let A'=A_1||A_0, B'=B_1||B_0, x=x_1||x_0 and y=y_1||y_0.
* Choose a random values for B_1 and A_0. This determines I_0 = x_0
\oplus A_0, I_1 = B_1 - y_1 and O = O_1||O_0 = x_0 * y_1. Note
that by fixing O_1 and O_0 also the values of y_0 and x_1 are
determined.
* Once, we have determines y_0 and x_1, we have to check if also I =
I_1||I_0 = y_0 * x_1 is correct. This holds with a probability of
2^{-n/2}. Hence, by repeating the attack 2^n/2 times we can invert V.
- Choose a random value for A and compute x = C_A(W_0) + W_0.
After testing all 2^{n/2} values for A we expect to find the
correct value.
- Choose a random value for B and compute y = C_B(W_0) + W_0.
After testing all 2^{n/2} values for B we expect to find the
correct value. Hence, we can invert the compression function of
Vortex with a complexity of 2^{n/2}.
By using a meet-in-the-middle attack we can turn the preimage
attack on the compression function into a preimage attack on the
hash function. This has a complexity of about 2^{3n/4}. For
details of the attack we refer to [1]. In constrast to MDC-2, further
reducing the runtime to 2^{n/2} as done in [2] seems difficult.
ad 3: Collision Attack
The collision attack on Vortex (or MDC-2 in general) makes use of
multicollisions. It can be summarized as follows:
- Given A and B, find an r-collision in A with A||B = V(C_A(W_0)
\oplus W_0; C_B(W_0) \oplus W_0). Let the messages producing the
r-collision be W_0^1,...,W_0^k and let the r (random) values of A
be A_01,...,A_0^k.
- Choose the message block W_1 arbitrarily, and evaluate
x^i=C_{A^i}(W_1) \oplus W_1 for i=0,...,k. If x_t = x^j for t <> j
then a collision has been found for Vortex.
The attack has a complexity of about 2^{122.5} compression function
evaluations for Vortex-256 and 2^{249.7} for Vortex-512. For the
details of the attack we refer to [2]
[1] X. Lai and J. L. Massey. Hash Functions Based on Block
Ciphers. In R. A. Rueppel, editor, Advances in Cryptology -
EUROCRYPT '92, Proceedings, volume 658 of Lecture Notes in
Computer Science, pages 55-70. Springer, 1993.
[2] Lars R. Knudsen and Florian Mendel and Christian Rechberger
and Søren S. Thomsen. Cryptanalysis of MDC-2. Submitted to Eurocrypt
2009.
[3] Michael Kounavis and Shay Gueron. Vortex: A New Family of One
Way Hash Functions based on Rijndael Rounds and Carry-less
Multiplication, Cryptology ePrint Archive, Report 2008/464.