# Collision Attacks against the Knudsen-Preneel Compression Functions

 Collision Attacks against the Knudsen-Preneel Compression Functions Authors Onur O ̈zen[@: 1] and Martijn Stam[@: 2] Published 2010 г. Web site International Association for Cryptologic Research Download оригинал

Abstract. Knudsen and Preneel (Asiacrypt’96 and Crypto’97) intro- duced a hash function design in which a linear error-correcting code is used to build a wide-pipe compression function from underlying block- ciphers operating in Davies-Meyer mode. Their main design goal was to deliver compression functions with collision resistance up to, and even beyond, the block size of the underlying blockciphers. In this paper, we present new collision-finding attacks against these compression functions using the ideas of an unpublished work of Watanabe and the preimage attackofO ̈zen,Shrimpton,andStam(FSE’10).Inbrief,ourbestattack has a time complexity strictly smaller than the block-size for all but two of the parameter sets. Consequently, the time complexity lower bound proven by Knudsen and Preneel is incorrect and the compression func- tions do not achieve the security level they were designed for.
Keywords: Collision attack, coding theory, compression function.

## Introduction

Hash functions are currently at the centre of the cryptographic community’s attention. While most of this attention is geared directly towards the SHA- 3 competition (by analysing its remaining candidates), other, arguably more fundamental questions regarding hash function design should not be forgotten. After all, the study of the underlying principles of hash function design are potentially beneficial for the SHA-3 decision process.

The two most revered principles in hash function design are (i) the Merkle-Damgard iterative construction, or more generally the principle of designing a secure compression function and (ii) the Davies-Meyer construction, or more generally the principle of using a blockcipher as underlying primitive. Indeed, the currently standardized hash functions from the SHA family follow this approach (as did their predecessor MD5) as well as several of the SHA-3 candidates.

It was already recognized early on that the output sizes of traditional block-ciphers are insufficient to yield a secure compression function[1].. This still holds true today: for all the (optimally secure) PGV blockcipher-based compression functions[2], [3], [4] based on an 𝑛-bit blockcipher, the (time) complexity of collision- and preimage-finding attacks is at most ${\displaystyle 2^{n/2}}$ resp. ${\displaystyle 2^{n}}$; when 𝑛 = 128 (e.g. AES) the resulting bounds are mostly unacceptable for current practice (in particular for collision resistance).

To achieve acceptable security (based on small block sizes) it is necessary to output a multiple of the block-length. In the 1990s many constructions were proposed for this goal, mostly outputting 2𝑛 bits with the explicit collision re- sistance target of 2𝑛 (see[5],[6] for an overview). The standard goal for these constructions has been optimal collision-resistance: a target output size is fixed and the compression function should be collision resistant up to the birthday bound for that digest size. In three papers[7],[8],[9], Knudsen and Preneel adopted a different approach, namely to fix a particular security target and let the output size (and relatedly the number of blockcipher calls) vary as needed in order to guarantee a particular security target without imposing optimal security.

Specifically, given 𝑟 independent ideal compression functions ${\displaystyle f_{1}...f_{r}}$ each mapping ${\displaystyle cn}$ to ${\displaystyle n}$ bits, they create a new ‘bigger’ compression function out- putting 𝑟𝑛 bits. Following principles (i) and (ii) already mentioned, they then propose to instantiate the underlying ideal compression functions with a blockci- pher run in Davies-Meyer mode and to iterate the compression function to obtain a full blockcipher-based hash function. However, they derive their security from the compression function, so that is where we will focus our attention.

The ${\displaystyle f_{1}...f_{r}}$ are run in parallel where each of their inputs is some lin- ear combination of the blocks of message and chaining variable that are to be processed; the ${\displaystyle rn}$-bit output of their construction is the concatenation of the out- puts of these parallel calls. The elegance of the KP construction is in how the inputs to ${\displaystyle f_{1}...f_{r}}$ are computed. They use the generator matrix of an ${\displaystyle [g,k,d]}$ error-correcting code over ${\displaystyle F_{2}}$ to determine how the ${\displaystyle ck}$ input blocks of the ‘big’ compression function are xor’ed together to form the inputs to the underlying ${\displaystyle r}$ functions. (In a generalization they consider the ${\displaystyle f_{i}}$ as mapping from ${\displaystyle bcn'}$ to ${\displaystyle bn'}$ bits instead and use a code over ${\displaystyle F_{2^{bc}}}$ .)

The (deliberate) effect of this design is that when two inputs to the ‘big’ compression function differ, the corresponding inputs for the underlying func- tions will differ for at least 𝑑 functions. In particular, when using a systematic generator, a change in the systematic part of the input results in at least ${\displaystyle d-1}$ so-called active functions in the non-systematic part. Intuitively this means that one has to find a preimage, resp. a collision for the ${\displaystyle d-1}$ active functions in parallel. Based on this observation, Knudsen and Preneel claim that (under an assumption) any collision attack needs time at least ${\displaystyle 2^{(d-1)n/2}}$ (and as many 𝑓𝑖 evaluations) and they conjecture that a preimage attack will require time at least ${\displaystyle 2^{(d-1)n}}$. Additionally, they give preimage and collision attacks (sometimes matching their lower bounds).

Table 1. A summary of collision attacks on the Knudsen-Preneel compression functions, with constant and polynomial factors (in 𝑛) ignored. Non-MDS pa- rameters are in italic, for ${\displaystyle e/in\{2,4\}}$ the underlying primitive ${\displaystyle f_{i}:\{0,1\}^{2n}\rightarrow {0,1}^{n}}$, and for ${\displaystyle e=3}$ ${\displaystyle f_{i}:\{0,1\}^{3n}\rightarrow \{0,1\}^{n}}$

Watanabe[10] already pointed out a collision attack beating the one given by Knudsen and Preneel for many of the parameter sets. In particular, his dif- ferential attack works whenever ${\displaystyle r<2k}$ and has a query and time complexity of essentially ${\displaystyle k2^{n}}$. Thus he demonstrated that the proven collision resistance lower bound given by Knudsen and Preneel is incorrect whenever ${\displaystyle r<2k}$ and ${\displaystyle d>3}$. For a code with minimum distance ${\displaystyle d=3}$ he matches the Knudsen-Preneel ${\displaystyle 2^{n}}$ collision-resistance lower bound, but does not violate it; the two codes proposed by Knudsen and Preneel with ${\displaystyle r\geq 2k}$ (namely ${\displaystyle [4,2,3]_{8}}$ and ${\displaystyle [5,2,4]_{8}}$) seem beyond reproach. Yet this was the first indication that something is amiss with the claim by Knudsen and Preneel. A second indication arrived at FSE’10, when O ̈zen, Shrimpton, and Stam [7] demonstrated a remarkably efficient preimage attack that, for 9 out of 16 cases, runs in time ${\displaystyle 2^{rn/k}}$ which was shown optimal. More- over, using a yield-based argument, they showed that an information-theoretic adversary in principle should be able to find collisions after only ${\displaystyle 2^{rn/2k}}$ queries.

Our contribution. In this paper we deal what we believe will be the final blow against the Knudsen-Preneel compression functions. Our contribution is four- fold, with a summary provided in Table 1. For completeness, we have also investigated the time complexity that one would obtain by straightforward adaptation of the ideas and query complexities of OSS; we refer to the full version of this paper[11]. for the details.

The mise en place in Section 4 provides a detailed mathematical character- ization of the Knudsen-Preneel compression function’s preprocessing. As a first simple result, this allows us in Section 5.1 to revise the attack of Watanabe in a way that slightly reduces the time requirements, yet significantly increases the number of collisions it can produce. More precisely, after an initial effort of ${\displaystyle d2^{n}}$, we can generate (up to) ${\displaystyle 2^{(k-d)n}}$ collisions in constant time (for ${\displaystyle k>d}$).

In our revised version of Watanabe’s attack, we fix a pure tensor to create a differential. By adaptively looking for an arbitrary tensor and using the same type of queries as Ozen,Shrimpton,and Stam we arrive in Section5.2 at a new, symbiotic collision-finding attack with time complexity ${\displaystyle d2^{dn/(d+1)}}$. The attack works whenever ${\displaystyle d\leq k}$ (as in Watanabe’s case). Even more amazing is that if the inequality is strict, that is if ${\displaystyle d, the adversary can create further collisions (like our revised attack) in constant time (up to ${\displaystyle 2^{(k-d)n}}$ collisions).

Thirdly, in Section 6.1 we introduce a parametrized information-theoretic collision attack. It turns out that the new symbiotic attack and the old OSS information-theoretic collision attack are both on opposite ends of the spectrum of this parametrized attack, yet optimality is typically achieved somewhere in the middle—with ${\displaystyle KP([5,2,4]_{8})}$ and ${\displaystyle KP([4,2,3]_{8})}$) again as exceptions—yielding query complexity ${\displaystyle 2^{kn/(3k-r)}}$.

Our final contribution is a reduced-time variant of our optimized attack above. For this we use the same ideas as O ̈SS, but with a crucial twist: where they used the dual code to look for preimages efficiently, we will use the dual shortened code to search for collisions efficiently. As a result, for 12 out of 16 suggested parameters we can mount a collision attack whose time complexity matches its query complexity (ignoring constants and logarithmic factors). Even better, only for ${\displaystyle KP([5,2,4]_{8})}$ we are unable to beat the time-complexity of any prior attack we are aware of, for the rest we set new records.

## Preliminaries.

With some minor modifications, we will adhere to the notation also used by Ozen, Shrimpton, and Stam.

Linear error correcting codes. ${\displaystyle [r,k,d]_{2^{e}}}$ linear error correcting code 𝒞 is the set of elements (codewords) in a 𝑘-dimensional subspace of${\displaystyle F_{2^{e}}^{r}}$ (for ${\displaystyle r\geq k}$), where the minimum distance 𝑑 is defined as the minimum Hamming weight (taken over all nonzero codewords in 𝒞). The dual code ${\displaystyle [r,r-k,d^{\perp }]_{2^{e}}}$ is the set of all elements in ${\displaystyle (r-k)}$-dimensional subspace orthogonal to 𝒞 (with respect to the usual inner product), and its minimum distance is denoted ${\displaystyle d^{\perp }}$. The Singleton bound puts a limit on the minimum distance:${\displaystyle d. Codes matching the Singleton bound are called maximum distance separable (MDS). An important property of an MDS code is that its dua is MDS as well,so ${\displaystyle d^{\perp }=k+1}$.

An ${\displaystyle [r,k,d]_{2^{e}}}$ code 𝒞 can be generated by a matrix ${\displaystyle G\in F_{2^{e}}^{k}\times r}$, C=${\displaystyle \{x\cdot G|x\in F_{2^{e}}^{k}\}}$ (using row vectors throughout). A generator matrix 𝐺 is 𝑘×(𝑟−𝑘) called systematic if it has the form ${\displaystyle G=[I_{k}|P]}$ for ${\displaystyle P\in F_{2^{e}}^{k}\times (r-k)}$ and ${\displaystyle I_{k}}$ the identitu matrix in ${\displaystyle F_{2^{e}}^{k}\times k}$. Furthermore, 𝐺 is the generator matrix of an MDS code if any 𝑘 columns are linearly independent. For an index set ${\displaystyle \chi \subseteq \{1,..r\}}$ we define ${\displaystyle G\in F_{2^{e}}^{k}\times r}$as the restriction of 𝐺 to those columns indexed by ${\displaystyle X}$. For a code and any index set ${\displaystyle \chi \subseteq \{1,..r\}}$, we want to define ${\displaystyle {\bar {\chi }}\subseteq \{1,..r\}}$ such that ${\displaystyle G_{\bar {\chi }}}$ is invertible and ${\displaystyle {\bar {\chi }}\subseteq \chi }$ or ${\displaystyle \chi \supseteq {\bar {\chi }}}$ . For MDS codes, the existence of such an ${\displaystyle {\bar {\chi }}}$ can be shown easily (and we can impose uniqueness e.g. by virtue of an ordering). For non-MDS codes there exist some ${\displaystyle \chi }$ for which such an ${\displaystyle {\bar {\chi }}}$ does not exist (for example the ${\displaystyle \chi \in \{1,..r\}}$), however for any target cardinality it is possible to find an ${\displaystyle \chi }$ (of that cardinality) that does have an ${\displaystyle \chi }$ (e.g. by first going through the systematic columns); we call such an ${\displaystyle \chi }$ admissible.

A given ${\displaystyle [r,k,d]_{2^{e}}}$ code 𝒞 can be shortened to obtain a new, derived code 𝒞′. Let ${\displaystyle i\in \{1,..r\}}$, then consider the set of all codewords in 𝒞 that are 0 on position 𝑖. The new code 𝒞′ consists of these codewords with position 𝑖 dropped, however we sometimes ‘quasi-shorten’ and keep the superfluous zeroes present (we always keep the original indexing). It is easy to see that 𝒞′ is an ${\displaystyle [r-1,k-1,d]_{2^{e}}}$ code unless all codewords in 𝒞 had a 0 on position 𝑖 or ${\displaystyle k=1}$ (in the latter case the shortening might result in the trivial one-codeword code. The shortening of an MDS code is an MDS code itself. By repeated application one can shorten by any index set ${\displaystyle \chi _{0}\in \{1,..r\}}$, for which ${\displaystyle \theta =|\chi _{0}| to obtain a derived MDS code 𝒞′. If 𝐺 is systematic and ${\displaystyle \chi _{0}\in \{1,..\theta \}}$we can generate the shortened code by dropping the first ${\displaystyle \theta }$ rows ${\displaystyle G_{\chi }}$, where ${\displaystyle \chi _{0}=\{1,..r\}\backslash \chi _{0}=\{\theta +1,...,r\}}$. (For the four non-MDS codes used by Knudsen and Preneel we will perform a separate analysis on repeated shortening.)

Линейно-блочные функции сжатия. A compression function is a mapping ${\displaystyle H:\left\{0,1\right\}^{tn}\rightarrow \left\{0,1\right\}^{sn}}$ for some blocksize ${\displaystyle n>0}$ and integer parameters ${\displaystyle t>s>0}$. For positive integers 𝑐 and 𝑛, we let Func(𝑐𝑛,𝑛) denote the set of all functions mapping ${\displaystyle \left\{0,1\right\}^{cn}}$ into ${\displaystyle \left\{0,1\right\}^{n}}$. A compression function is Public Random Function (PuRF)-based if its mapping is computed by a program with oracle access to a finite number of specified oracles ${\displaystyle f_{1},...,f_{r}}$, where ${\displaystyle f_{1},...,f_{r}{\overset {\}{\leftarrow }}Func(cn,n)}$. When a PuRF-based compression function operates on input 𝑊 , we write ${\displaystyle H^{f_{1},...,f_{r}}(W)}$ for the resulting value. Of primary interest for us will be single-layer PuRF-based compression functions without feedforward. These call all oracles in parallel and compute the output based only on the results of these calls; in particular, input to the compression function is not considered.

Most PuRF-based (and blockcipher-based) compression functions are of a special type. Instead of arbitrary pre- and postprocessing, one finds only func- tions that are blockwise linear. The Knudsen-Preneel construction is also block- wise linear, so let us recall from [7] what is a blockwise-linear scheme.

Definition 1 (Blockwise-linear scheme).

Let 𝑟,𝑐,𝑏,𝑡,𝑠 be positive integers and let matrices ${\displaystyle C^{PRE}\in F_{2}^{rcb\times tb},C^{POST}\in F_{2}^{sb\times rb}}$ be given. We define ${\displaystyle H=BL^{b}\left(C^{PRE},C^{POST}\right)}$ o be a family of single-layer PuRF-based compression functions ${\displaystyle H_{n}:\left\{0,1\right\}^{tn}\rightarrow \left\{0,1\right\}^{sn}}$, for all positive integers 𝑛 with${\displaystyle b|n}$. Specifically, let ${\displaystyle n'b=n}$ and ${\displaystyle f_{1},...,f_{r}\in Func(cn,n)}$. Then on input ${\displaystyle W\in \left\{0,1\right\}^{tn}}$ (interpreted as column vector), ${\displaystyle H_{n}^{f_{1},...,f_{r}}}$ computes the digest ${\displaystyle Z\in \left\{0,1\right\}^{sn}}$ as follows:

1. Compute ${\displaystyle X\leftarrow (C^{PRE}\bigotimes I_{{n}'})\cdot W}$

2. Parse ${\displaystyle X=(x_{i})_{i=1...r}}$ and for ${\displaystyle i=1...r}$ compute ${\displaystyle y_{i}=f_{i}(x_{i})}$

3. Parse ${\displaystyle (y_{i})_{i=1...r}=Y}$ and output ${\displaystyle Z=(C^{POST}\bigotimes I_{{n}'})\cdot Y}$

where ${\displaystyle \bigotimes }$ denotes the Kronecker product and ${\displaystyle I_{{n}'}}$ the identity matrix in ${\displaystyle F_{2}^{{n}'\times {n}'}}$.

In the definition above we silently identified ${\displaystyle \left\{0,1\right\}^{n}}$ with the vector space ${\displaystyle F_{2}^{n}}$. The map corresponding to ${\displaystyle \left(C^{PRE}\bigotimes I_{n'}\right)}$ will occasionally be denoted ${\displaystyle C^{PRE}}$ and its image ${\displaystyle \varpi (C^{PRE})\subseteq \left\{0,1\right\}^{rcn}}$. It will be convenient for us to write the codomain of ${\displaystyle C^{PRE}}$ as a direct sum, so we identify ${\displaystyle \left\{0,1\right\}^{rcn}}$ with ${\displaystyle \bigoplus _{i=1}^{r}V_{i}}$ where ${\displaystyle V_{i}=F_{2}^{cn}}$ for ${\displaystyle i=1,...,r}$. If ${\displaystyle x_{1}\in V_{1}}$ and ${\displaystyle x_{2}\in V_{2}}$, then consequently ${\displaystyle x_{1}+x_{2}}$ will be in ${\displaystyle V_{1}\bigoplus V_{2}}$. (This extends naturally to ${\displaystyle L_{1}+L_{2}}$, when ${\displaystyle L_{1}\subset V_{1},L_{2}\subset V_{2}}$)

Knudsen-Preneel compression functions. Knudsen and Preneel[7],[8] introduced a family of hash functions employing error correcting codes. (We use the journal version[9] as our frame of reference). Although their work was ostensibly targeted at blockcipher-based designs, the main technical thread of their work develops a transform that extends the range of an ‘ideal’ compression function (blockcipher-based, or not) in a manner that delivers some target level of security. As is nowadays typical, we understand an ideal compression function to be a PuRF. In fact, the KP transform is a special instance of a blockwise-linear scheme (Definition 1), in which the inputs to the PuRFs are determined by a linear code over a binary field with extension degree ${\displaystyle e>1}$, and with ${\displaystyle C^{POST}}$ being the identity matrix over ${\displaystyle F_{2}^{rb\times rb}}$. The extension field itself is represented as a subring of the matrix ring (of dimension equalling the extension degree) over the base field. We formalize this by an injective ring homomorphism ${\displaystyle \mu :F_{2^{e}}\rightarrow F_{2^{e\times e}}}$ and let ${\displaystyle {\overline {\mu }}:F_{2^{e}}^{r\times k}\rightarrow F_{2^{e}}^{re\times ke}}$ be the component-wise application of ${\displaystyle \mu }$ and subsequent identification of ${\displaystyle \left(F_{2}^{e\times e}\right)^{r\times k}}$ with ${\displaystyle F_{2^{e}}^{re\times ke}}$ (we will use ${\displaystyle {\overline {\mu }}}$ for matrices over ${\displaystyle F_{2^{e}}}$ of arbitrary dimensions). For completeness, there is also a group homomorphism ${\displaystyle \psi :F_{2^{e}}\rightarrow F_{2}^{e}}$ such that for all ${\displaystyle g,h\in F_{2^{e}}:\psi (gh)=\mu (g)*\psi (h)}$.

Definition 2 (Knudsen-Preneel transform).

Let ${\displaystyle \left[r,k,d\right]}$ be a linear code over ${\displaystyle F_{2^{e}}}$ with generator matrix ${\displaystyle G\in F_{k\times r}^{2^{e}}}$. Let ${\displaystyle \varphi :F_{2^{e}}\rightarrow F_{e\times e}^{2^{e}}}$ - be an injec- tive ring homomorphism and let ${\displaystyle b}$ be positive divisor of ${\displaystyle e}$ such cthat ${\displaystyle ek>rb}$. Then the Knudsen-Preneel compression function${\displaystyle H=KP^{b}\left(\left[r,k,d\right]_{2^{e}}\right)}$ equals ${\displaystyle H=BL^{b}(C^{PRE},C^{POST})}$ with ${\displaystyle C^{PRE}={\overline {\varphi }}(G^{T})}$ and ${\displaystyle C^{POST}=I_{rb}}$.

If ${\displaystyle H=KP^{b}\left(\left[r,k,d\right]_{2^{e}}\right)}$, then ${\displaystyle H_{n}:\left\{0,1\right\}^{kcn}\rightarrow \left\{0,1\right\}^{rn}}$ with ${\displaystyle c=e/b}$ is defined for al ${\displaystyle n}$, for which ${\displaystyle b}$ - divides ${\displaystyle n}$. Moreover, ${\displaystyle H_{n}}$ is based on r PuRF in ${\displaystyle Func(cn,n)}$. For use of 𝐻 in an iterated hash function, note that per invocation (of 𝐻) one can compress ${\displaystyle ck-r}$ message blocks (hence the requirement ${\displaystyle ek>rb}$ ensures actually compression is taking place), and the rate of the compression function ${\displaystyle ck/r-1}$. We will concentrate on the case ${\displaystyle (b,e)\in \left\{(1,2),(2,4),(1,3)\right\}}$ and then in particular on the 16 parameter sets given by Knudsen and Preneel.1 Since ${\displaystyle b}$ is uniquely determined given ${\displaystyle e}$ (and ${\displaystyle c}$), we will often omit it.

Security notions. A collision-finding adversary is an algorithm whose goal is to find two distinct inputs 𝑊, 𝑊 ′ that hash to the same value, so ${\displaystyle H(W)=H(W')}$. We will consider adversaries in two scenarios: the information-theoretic one and a more realistic concrete setting. For information-theoretic adversaries the only resource of interest is the number of queries made to their oracles. Otherwise, these adversaries are considered (computationally) unbounded. In the concrete setting, on the other hand, we are interested in the actual runtime of the algorithm and, to a lesser extent, its memory consumption (and code-size).

## Prior Art on the Knudsen-Preneel Hash Functions

Knudsen and Preneel’s security claims. Knudsen and Preneel concentrate on the collision resistance of their compression function in the complexity theo- retic model. Under a fairly generous (but plausible) assumption, they essentially show that if ${\displaystyle H=KP^{b}([r,k,d]_{2^{e}})}$, then finding collisions in ${\displaystyle H_{n}}$ takes time at least ${\displaystyle 2^{(d-1)n/2}}$. For preimage resistance Knudsen and Preneel do not give a cor- responding theorem and assumption, yet they do conjecture it to be essentially the square of the collision resistance.

Knudsen and Preneel also present two attacks, one for finding preimages [[9], Proposition 3] and one for finding collisions [[9], Proposition 4] (see results in Table 1). Both attacks revolve around finding multi-preimages for the systematic part of the construction in sufficient numbers to make it likely that completion to the non-systematic part will yield a full preimage respectively a full collision.

Watanabe’s collision-finding attack. Knudsen and Preneel left a consider- able gap between the actual complexity of attacks and their lower bounds in the case of collision resistance. Watanabe[10] has pointed out a collision attack that runs in time ${\displaystyle k2^{n}}$ (and as many PuRF evaluations). Thus, for many of the parameter sets, it beats the one given by Knudsen and Preneel. More interestingly, his attack serves as proof that the lower bound given by Knudsen and Preneel is incorrect for a large class of parameters: whenever ${\displaystyle r<2k}$ and ${\displaystyle d>3}$, which involves 6 out of 16 parameter sets. (See also Table 1.)

Assume that the code’s generator matrix is systematic, that is ${\displaystyle G=(I_{k}|P)}$ with ${\displaystyle P\in F_{2^{e}}^{k\times (r-k))}}$. Then the goal is to generate, for each ${\displaystyle i\in \left\{1,...,k\right\}}$a colliding pair of inputs ${\displaystyle x_{i}\neq x_{i}'}$ (and ${\displaystyle f_{i}(x_{i})=f_{i}(x_{i}')}$) in such a way that their completion to full ‘codewords’ satisfies ${\displaystyle x_{i}=x_{i}'}$ for ${\displaystyle i\in \left\{k+1,...,r\right\}}$. This is done by ensuring that ${\displaystyle x_{i}\bigoplus x_{i}'=\Delta _{i}}$, where ${\displaystyle \Delta =\sum _{i=1}^{k}\Delta _{i}\in F_{2}^{ken'}\backslash \left\{0\right\}}$ is in the kernel of ${\displaystyle {\overline {\varphi }}(P^{T})\bigotimes I_{n'}}$ (since ${\displaystyle r-k,the kernel is guaranteed to contain a non- trivial element). Mutual independence of the inputs to the PuRFs corresponding to the code’s systematic part allow the initial collision searches to be mounted independently. Unfortunately, since the collisions need to be rather special (due to fixed ${\displaystyle \Delta _{i}}$, the birthday paradox does not apply and a collision search costs about ${\displaystyle 2^{n}}$. queries and time (per PuRF). On the plus side, the attack is trivially memoryless and parallellizable.

Ozen-Shrimpton-Stam preimage-finding attack.An extensive security analysis for the preimage resistance of KP-constructions, falsifying the designers’ conjectured lower bound, has been provided by O ̈zen, Shrimpton, and Stam [12].. Additionally, they also provided a related collision-finding attack with a surpris- ingly low query complexity: ${\displaystyle 2^{rn/(2k)}}$ (but no analysis of its time complexity).

At the core of the Ozen-Shrimpton-Stam attacks is the simple observation that ${\displaystyle (0^{a}||x_{1})\bigoplus (0^{a}||x_{2})}$ yields a string of the form ${\displaystyle (0^{a}||X)}$. More generally, any linear combination of strings with the same pattern of fixed zero bits will yield a string with the same form. By restricting PuRF queries to strings with the same (blockwise) pattern one can optimize the yield of these queries (i.e. the maximum number of KP compression function evaluations an adversary can compute for a given number of queries). Matching the yield with the size of the codomain (resp. its square root) gives rise to an information-theoric preimage (resp. collision) attack.

A second observation is that, in the case of a preimage attack, the dual code can be used to find the preimage far more efficiently than a naive method. Direct application of this method however is disappointing (see Table 1). The resulting time complexities are typically much higher than the corresponding query complexities and the attack is seldom competitive with that of Knudsen and Preneel, let alone with that of Watanabe.

## Decoding the Knudsen-Preneel Preprocessing

An important property that is exploited by both Watanabe and OSS is linearity ${\displaystyle C^{PRE}}$. Indeed, the image ${\displaystyle \varpi (C^{PRE})}$ itself can be regarded as an 𝑒𝑘𝑛′-dimensional subspace of ${\displaystyle F_{2}^{ern'}}$ or equivalently as an ${\displaystyle \left[ern',ekn',d'\right]_{2}}$ code ${\displaystyle C^{\bigotimes }}$ (where the minimum distance d' is largely irrelevant; it satisfies ${\displaystyle d\leq d'\leq de}$). This has the consequence that if ${\displaystyle X=C^{PRE}(W)}$ and ${\displaystyle X'=C^{PRE}(W')}$, collide, it is guaranteed that ${\displaystyle \Delta =X\bigoplus X'\in \varpi (C^{PRE})}$, i.e. the difference ${\displaystyle \Delta }$ itself is a (nonzero) codeword in ${\displaystyle C^{\bigotimes }}$. Below we will give a more detailed mathematical characterization of ${\displaystyle \varpi (C^{PRE})}$,with a special eye towards the improved collision-finding algorithms we will give later on. Most of the results below are mathematically rather straightforward (and the proofs are left to the full version); the machinery is mainly needed to ensure that, when using canonical bases for the various vector spaces, everything lines up correctly and consistently with the actual Knudsen-Preneel compression function. Recall that we are given an injective ring homomorphism ${\displaystyle \varphi :F_{2^{e}}\rightarrow F_{2}^{e\times e}}$ and a group isomorphism ${\displaystyle \psi :F_{2^{e}}\rightarrow F_{2}^{e}}$, that satisfy ${\displaystyle \varphi (g)\psi (h)=\psi (gh))}$ for all ${\displaystyle g,h\in F_{2^{e}}}$. Let ${\displaystyle \left[r,k,d\right]_{2^{e}}}$ - be a linear code with generator matrix ${\displaystyle G\in F_{2^{e}}^{k\times r}}$, let ${\displaystyle b}$ - be a positive divisor of ${\displaystyle e}$, such that ${\displaystyle ek>rb}$ and finally let ${\displaystyle n=nb'}$. Then the input processing ${\displaystyle C^{PRE}:\left\{0,1\right\}^{ekn'}\rightarrow \left\{0,1\right\}^{ern'}}$ of the Knudsen- Preneel compression function is defined by ${\displaystyle C^{PRE}(W)={\bar {\varphi }}(G^{T})\bigotimes I_{n'})W}$ (and note that ${\displaystyle ern'=rcn}$).

Characterization of ${\displaystyle \varpi (C^{PRE})}$ as a sum. We have already written the codomain of ${\displaystyle C^{PRE}}$as a direct sum of PuRF inputs by identifying ${\displaystyle \left\{0,1\right\}^{ren'}}$ with ${\displaystyle \bigoplus _{i=1}^{r}V_{i}}$ where ${\displaystyle V_{i}=F_{2}^{en'}}$ for ${\displaystyle i=1,...,r}$. Here we will use a second interpretation that emphasizes the code. We will consider ${\displaystyle \bigoplus _{j=1}^{n'}U_{j}}$ where ${\displaystyle U_{j}=F_{2^{e}}^{r}}$ for ${\displaystyle j=1,...,n'}$. Since ${\displaystyle F_{2^{e}}^{r}}$ and, by extension ${\displaystyle \bigoplus _{j=1}^{n'}U_{j}}$ is a vector space over ${\displaystyle F_{2^{e}}}$, we cannot find a vector space isomorphism (as for the earlier direct sum). Nonetheless we can find a suitable group isomorphism from ${\displaystyle \bigoplus _{j=1}^{n'}U_{j}}$ to ${\displaystyle \left\{0,1\right\}^{ren'}}$.

To define the group isomorphism we exploit that, luckily, the underlying ${\displaystyle F_{2^{e}}}$, arithmetic is essentially preserved by ${\displaystyle C^{PRE}:\left\{0,1\right\}^{ken'}\rightarrow \left\{0,1\right\}^{ern'}}$, even though the '${\displaystyle \bigotimes I_{n'}}$' in ${\displaystyle C^{PRE}(W)={\bar {\varphi }}(G^{T})\bigotimes I_{n'})W}$ garbles things up. To formalize this, let ${\displaystyle \rho :F_{2^{e}}^{n'}\rightarrow F_{2^{e}}^{en'}}$ - be the group isomorphism such that ${\displaystyle \rho (g\delta )=(\varphi (g)\bigotimes I_{n'})\rho (\delta )}$for all ${\displaystyle \delta \in F_{2^{e}}^{n'}}$ and ${\displaystyle g\in F_{2^{e}}}$.

Lemma 1

Let ${\displaystyle X_{0}\subset \left\{1,...,r\right\}}$, let ${\displaystyle C'}$ be the (quasi) shortening of ${\displaystyle C}$ on ${\displaystyle X_{0}}$ and let ${\displaystyle C'_{j}=C'\subseteq U_{j}}$ for ${\displaystyle j=1,...,n'}$. Then ${\displaystyle X=\sum _{i=1}^{r}x_{i}\varpi (C^{PRE})}$ with ${\displaystyle x_{i}=0}$ for all ${\displaystyle i\in X_{0}}$ if ${\displaystyle \exists !\forall _{j=1,...,n'}g_{j}=\sum _{i=1}^{r}x_{i}\in C_{j}}$ such that ${\displaystyle x_{i}=\rho (\sum _{j=1}^{n'}g_{ji})}$.

The following proposition develops the key idea on how to recognize that a given ${\displaystyle X\in F_{2}^{ern'}}$ is an element of ${\displaystyle \varpi (C^{PRE}}$. This result is exploited in [12] to efficiently find preimages for Knudsen-Preneel compression functions.

Proposition 1

Let ${\displaystyle H=KP^{b}([r,k,d]_{2^{e}})}$, ${\displaystyle M\in F_{2}^{e\times re/b}}$ and a nonzero ${\displaystyle X\in F_{2}^{ern'}}$ be given. Suppose that ${\displaystyle M={\overline {\varphi }}(h^{T})}$ for some ${\displaystyle h\in C^{\perp }}$, then ${\displaystyle X\in \varpi (C^{PRE})}$ iff for all positive integers 𝑛′ it holds that ${\displaystyle n'}$ ${\displaystyle (M\bigotimes I_{n'})X=0}$.

Since ${\displaystyle F_{2^{e}}^{n'r}}$ is isomorphic ${\displaystyle F_{2^{e}}^{r}\bigotimes F_{2^{e}}^{n'}}$, this leads in a natural way to a function from ${\displaystyle F_{2^{e}}^{r}\times F_{2^{e}}^{n'}}$ to ${\displaystyle \left\{0,1\right\}^{ren}}$, where ${\displaystyle g\bigotimes \delta }$ with ${\displaystyle g\in F_{2^{e}}^{r}}$ and ${\displaystyle \delta \in F_{2^{e}}^{n'}}$. Note that we do not discriminate between different representatives, that is for nonzero ${\displaystyle \beta \in F_{2^{e}}}$ we have that ${\displaystyle g\bigotimes \delta =(\beta g)\bigotimes (\beta ^{-1}\delta )}$.

Lemma 2

If ${\displaystyle g\in F_{2^{e}}^{r}}$ and ${\displaystyle \delta \in F_{2^{e}}^{n'}}$, then ${\displaystyle {\overline {p}}(g\bigotimes \delta )\in \varpi (C^{PRE})}$ if ${\displaystyle g\in C}$ or ${\displaystyle \delta =0}$.

The following lemma states that invertibility of ${\displaystyle G_{x}}$ suffices to invert C^{PRE}.

Lemma 3

Let G - be a generator matrix for an ${\displaystyle [r,k,d]_{2^{e}})}$ code. Let ${\displaystyle {\overline {X}}\subset \left\{1,..,r\right\}}$ be such that ${\displaystyle G_{\overline {X}}}$ is invertible, with transposed inverse ${\displaystyle G_{\overline {X}}^{-T}}$. Let ${\displaystyle n'}$ be an integer and, for ${\displaystyle i=1,..,r}$ let ${\displaystyle V_{i}=F_{2}^{en'}}$ be a direct-sum-decomposition of ${\displaystyle F_{2}^{ern'}}$. If given ${\displaystyle x_{i}\in V_{i}}$, for ${\displaystyle i\in {\overline {X}}}$, or equivalently ${\displaystyle {\widetilde {X}}=\sum _{i\in {\overline {X}}}x_{i}}$ then ${\displaystyle W=({\overline {\varphi }}(G_{\overline {X}}^{-T})\bigotimes I_{n'}){\widetilde {X}}}$ is the unique element for which ${\displaystyle X'=C^{PRE}(W)}$ satisfies ${\displaystyle x'_{i}=x_{i}}$ for ${\displaystyle i\in {\overline {X}}}$.

## A New Symbiotic Collision-Finding Attack

### Revising Watanabe’s Attack

Watanabe’s attack has complexity ${\displaystyle k2^{n}}$, requires ${\displaystyle k>r-k}$ and essentially finds a single collision. Below we give a revised and improved version of his algorithm. It only has complexity ${\displaystyle d2^{n}}$, requires ${\displaystyle k\geq d}$ and it potentially results in many, many collisions. More precisely, if ${\displaystyle k>d}$, then after the initial effort (of ${\displaystyle d2^{n}}$) we can find a new collision in constant time, for up to a whopping ${\displaystyle 2^{(k-d)n}}$ collisions.

we can find a new collision in constant time, for up to a whopping ${\displaystyle \Delta }$ was computed as some non-trivial kernel element, we will compute it based on a codeword ${\displaystyle g\in C}$ of sufficiently low weight and an arbitrary (nonzero) ‘block multiplier’ ${\displaystyle \delta }$. In particular, we will set, ${\displaystyle \Delta ={\overline {\rho }}(g\bigotimes \delta )}$. By using a minimal weight codeword the attack performs best.

Algorithm 1 (Revised Watanabe Collision Attack)

For the revised attack to work, we need one further ingredient. Watanabe assumes a systematic code and exploits that, when ${\displaystyle k there exists a nonzero codeword ${\displaystyle g\in C}$ for which ${\displaystyle \chi (g)\subseteq \left\{1,...,k\right\}}$. This allows easy completion of a partial collision to a full collision. Our revised version allows an arbitrary (nonzero) codeword ${\displaystyle g}$ of weight at most ${\displaystyle k}$ (existence of which requires ${\displaystyle d\leq k}$). Thus ${\displaystyle \chi (g)}$ might no longer map to the systematic part of the code. Luckily, Lemma 3 provides completion to a full collision, provided ${\displaystyle X=\chi (g)}$ is admissable; for the four non-MDS codes proposed by Knudsen and Preneel it can be verified that the minimum distance codewords are admissible.

Theorem 1(Revised Watanabe attack.)
Let ${\displaystyle H=KP^{b}([r,k,d]_{2^{e}})}$ be given with${\displaystyle k\geq d}$. Consider ${\displaystyle H_{n}}$ (with ${\displaystyle b|n}$). Then Algorithm 1 using a minimum-weight codeword ${\displaystyle g}$ (and an arbitrary nonzero ${\displaystyle \delta }$) finds collisions for ${\displaystyle H_{n}}$ in expected time ${\displaystyle d2^{n}}$ (using as many PuRF evaluations)
Proof
W/o proof.

Algorithm 2 (New Symbiotic Collision Attack)

### A New Symbiotic attack

Our revised version of Watanabe’s attack clearly shows that an attacker poten- tially has a lot of freedom. Below we transform some of this freedom into a faster attack. More to the point, as in the revised Watanabe attack we still look for a collision with differential ${\displaystyle \Delta ={\overline {\rho }}(g\bigotimes \delta )}$ and fix the codeword ${\displaystyle g\in C}$ but we do not fix the multiplier ${\displaystyle \delta }$ up front. Instead we determine it based on the outcomes of the queries we make. To increase our success probability, we restrict to the same kind of queries as O ̈zen, Shrimpton, and Stam did.

Theorem 2(New symbiotic attack)
Let ${\displaystyle H=KP^{b}([r,k,d]_{2^{e}})}$ be given with ${\displaystyle k\geq d}$. Consider ${\displaystyle H_{n}}$${\displaystyle b|n}$). Then Algorithm 2 finds collisions for ${\displaystyle H_{n}}$ in ${\displaystyle d2^{dn/(d+1)}}$ time (using as many PuRF evaluations) and memory (expressed in 𝑛-bit blocks).
Proof

Proof (Sketch). We will leave showing the correctness of Algorithm 2 to the full version of this paper [8] and only prove here that a collision is expected and that the query and time complexities are as claimed.

Since ${\displaystyle |/chi|=2^{\alpha n}}$, by construction, the attack has the stated query complexity (per PuRF) for ${\displaystyle \alpha =d/(d+1)}$, since all queries are made during the Query Phase. Using a naive approach, Local Collision Detection step can be performed in roughly ${\displaystyle 2^{dn/(d+1)}}$ (грубо) comparisons resulting in partial collision lists of expected cardinality ${\displaystyle \left|L_{i}\right|\approx 2^{(2\alpha -1)n}}$ for ${\displaystyle i\in X}$.

For Global Collision Detection, we just enumerate one partial collision list and check for membership against the others. Assuming constant time mem- ory access, the time complexity of this step is at most${\displaystyle (d-1)max_{i\in X}\left|L_{i}\right|}$. Since ${\displaystyle \alpha >1}$, it follows that ${\displaystyle 2\alpha -1<\alpha }$, making the Query Phase dominant with its time complexity of ${\displaystyle 2^{\alpha n}}$.

Since we have 𝑑 active PuRFs in total, the probability of finding a common element among 𝑑 such lists is then ${\displaystyle (\prod _{i}|L_{i}|)/|\chi |^{d-1}}$ или ${\displaystyle 2^{((2\alpha -1)d-\alpha (d-1))}}$. To ensure an expected number of collisions of one, we need the second exponent to be at least zero, and indeed, solving for zero gives the desired${\displaystyle \alpha =d/(d+1)}$

## A Parametrized Collision-Finding Attack.

### Optimizing the Query Complexity.

Algorithm 3 (Parameterized Collision Attack).

The symbiotic attack and the information-theoretic attack by Ozen, Shrimpton, and Stam have completely different query complexities and which one is the best seems very parameter dependent. However, it turns out that both attacks are the extreme cases of a more general parametrized attack, as given by Algorithm 3.

Theorem 3
Let ${\displaystyle H=KP^{b}([r,k,d]_{2^{e}})}$ be given. Consider ${\displaystyle H_{n}}$ (with ${\displaystyle b|n}$). Then collisions for ${\displaystyle H_{n}}$ can be found with Alg. 3 using ${\displaystyle 2^{\alpha n}}$ queries (per PuRF) where

${\displaystyle \alpha =\left\{{\begin{matrix}(r-\theta /(2k-\theta ),for:0\leq \theta \leq (r-d,r-k)\\(r-\theta )(r+k-2\theta ),for:(r-k)\leq \theta \leq r-d\end{matrix}}\right.}$

Proof

That the attack has the stated query complexity follows readily from the usual observation that ${\displaystyle |\chi |=2^{\alpha n}}$ combined with the computation of ${\displaystyle \alpha }$. exactly matching the theorem statement. What remains to show is that collisions are indeed output and expected with good probability.

For correctness, let ${\displaystyle (W,W')}$ be output by the algorithm and consider ${\displaystyle X=C^{PRE}(W)}$, and ${\displaystyle X'=C^{PRE}(W')}$. First, notice that Lemma 3 implies that projecting ${\displaystyle (X\bigoplus X',X,X')}$ onto ${\displaystyle \bigoplus _{i\in {\overline {X}}}V_{i}}$ is in ${\displaystyle L_{\widetilde {X}}}$. Now, either of the steps Degrees of Freedom, Filtering or Skip ensures that ${\displaystyle ({\widetilde {\Delta }},{\widetilde {X}},{\widetilde {X'}})\in L_{x}}$. Finallys, since ${\displaystyle L_{x}\subseteq {\widetilde {L_{x}}}}$, it follows that ${\displaystyle (x_{i},x'_{i})\in L_{i}}$ for ${\displaystyle i\in X}$ and hence by construction (Local Collision Detection) we have ${\displaystyle f_{i}(x_{i})=f_{i}(x'_{i})}$.

Moreover Collision Pruning guarantees that ${\displaystyle \Delta +0\in \varpi (C^{PRE})}$ and De- grees of Freedom ensures that the projections of ${\displaystyle \Delta +0}$ and ${\displaystyle X\bigoplus X'}$ onto ${\displaystyle \bigoplus _{i\in {\overline {X}}}V_{i}}$ are equal. Hence, ${\displaystyle x_{i}=x'_{i}}$ for all ${\displaystyle i\in X_{0}}$.

Let us move on to the number of expected collisions output. Since ${\displaystyle |\chi |=2^{\alpha n}}$, the expected number of local collisions found per active PuRF for ${\displaystyle i\in X}$ is ${\displaystyle |L_{i}|\approx |\chi |^{2}/2n=2^{2\alpha -1}n}$. Using that ${\displaystyle |X|=r-\theta }$, we arrive at a total number of potential collisions of ${\displaystyle |{\widetilde {L_{x]}}}|\approx 2^{(2\alpha -1)(r-\theta )n}}$. For a true collision to occur, we need to find a tuple ${\displaystyle (x_{i},x'_{i})_{i\in {\widetilde {X}}}}$ such that both ${\displaystyle \sum _{i\in {\widetilde {X}}}x_{i}}$, and ${\displaystyle \sum _{i\in {\widetilde {X}}}x'_{i}}$ can be completed to codewords subject to the constraint that ${\displaystyle (X,X')}$, then ${\displaystyle \Delta =X\bigoplus X'}$ is a codeword as well and the above implies that ${\displaystyle {\widetilde {\Delta }}=\sum _{i\in X}\Delta _{i}}$. The restriction ${\displaystyle \theta =r-d}$ ensures nontriviality of the shortened code (shortening any further and the shortened code would consist of the zero codeword only resulting in ${\displaystyle W=W'}$, so no collision). In case of MDS codes, the shortened code has parameters ${\displaystyle [r-\theta ,k-\theta ,d']_{2^{e}}}$, in particular it has dimension ${\displaystyle k-\theta }$. (For non-MDS codes it is possible that a higher dimension is achieved.)

As a result, a fraction ${\displaystyle 2^{(k-r)\alpha n}}$ of the differentials will be satisfactory, leading to an expected number of ${\displaystyle |L_{x}|=2^{((2\alpha -1)(r-\theta )-\alpha (r-k))n}}$. If ${\displaystyle X\subseteq {\widetilde {X}}}$ or equivalently ${\displaystyle r-\theta \leq k}$ we are done whenever ${\displaystyle |L_{x}|\geq 1}$. Since ${\displaystyle r-\theta \leq k}$ can be rewritten to ${\displaystyle \theta \geq r-k}$, we are in the second case, with ${\displaystyle \alpha =(r-\theta )/(r+k-2\theta )}$. Writing ${\displaystyle F=(lg|L_{x}|)/n}$ and substitution lead to ${\displaystyle F\approx (2\alpha -1)(r-\theta )-\alpha (r-k)=\alpha (2r-2\theta -r+k)-(r-\theta )=0}$ or ${\displaystyle |L_{x}|\approx 1}$ as desired.

If on the other hand, ${\displaystyle X'\subset X}$, further filtering is needed. In particular, given a potential ‘half’ of a collision ${\displaystyle X}$ we need to check if it can correspond to a codeword. Since ${\displaystyle X'\subset X}$, we can uniquely complete ${\displaystyle X}$ to a codeword given ${\displaystyle k}$ of its elements. The remaining ${\displaystyle |X|-k}$coordinates need to be in sync. Per remaining element, this occurs with probability ${\displaystyle 2^{-\alpha n}}$, leading to ${\displaystyle |{\widetilde {L_{x}}}|\approx |L_{x}|2^{-\alpha n(r-\theta -k)}}$. Now we are in the first case since ${\displaystyle 0\leq \theta \leq r-k}$. Writing ${\displaystyle F=(lg{\widetilde {L_{\widetilde {x}}}})/n}$, we obtain ${\displaystyle F\approx (2\alpha -1)(r-\theta )-\alpha (r-k-\theta )=\alpha (k-\theta )-(r-\theta )}$. Since we aim for ${\displaystyle F=0}$, ${\displaystyle \alpha =(r-\theta )/(2k-\theta )}$ as desired.

Collolary 1
Assuming , substitution of ${\displaystyle \theta =r-k}$ in Theorem 3 gives ${\displaystyle \alpha =k/(3k-r)}$. This is optimal (for Algorithm 3) whenever .
Proof

That the substition does what it says can be readily verified, so we restrict ourselves to prove the optimality here. Let ${\displaystyle f_{1}(\theta )=(r-\theta )/(2k-\theta )}$ and ${\displaystyle f_{2}(\theta )=(r-\theta )/(r+k-2\theta )}$ - 2 be two real valued functions defined over closed intervals ${\displaystyle 0\leq \theta \leq r-k}$ and ${\displaystyle r-k\leq \theta \leq r-d}$ respectively. Note that both and are continuous in their respective domains (since their respective poles fall outside the domains). So both and attain their maximum and minimum in the closed intervals ${\displaystyle |0,r-k|}$ и ${\displaystyle |r-k,r-d|}$.Since ${\displaystyle f'_{1}(\theta )=(r-2k)/(2k-\theta )^{2}\leq 0}$ and ${\displaystyle f'_{2}(\theta )=(r-2k)/(r+k-2\theta )^{2}\geq 0}$, we can conclude that ${\displaystyle f_{1}(\theta )}$ is decreasing и ${\displaystyle f_{2}(\theta )}$ is increasing. Therefore, they both attain their minimum at their shared boundary ${\displaystyle \theta =r-k}$.

Remark 1 The only two parameter sets proposed by Knudsen and Preneel not satisfying the conditions of the corollary above are ${\displaystyle [4,2,3]_{8}}$ and ${\displaystyle [5,2,4]_{8}}$. n both cases ${\displaystyle d>k}$ and only ${\displaystyle f_{1}(\theta )}$ is applicable. For ${\displaystyle [5,2,4]_{8}}$ можно проверить ${\displaystyle 2k и ${\displaystyle f'_{1}(\theta )\geq 0}$.one can check that ${\displaystyle \alpha }$ is attained at ${\displaystyle 0}$. For ${\displaystyle [4,2,3]_{8}}$ it holds that ${\displaystyle 2k=r}$, so that - is in fact a constant function and both ${\displaystyle f_{1}(\theta )}$ and ${\displaystyle \theta =0}$ lead to the same ${\displaystyle \theta =1}$.

Remark 2. Substitution of ${\displaystyle \theta =0}$ in Theorem 3 gives ${\displaystyle \alpha =r/2k}$ and the resulting query complexity coincides with that reported by O ̈zen, Shrimpton, and Stam. On the other extreme, substitution of${\displaystyle \theta =r-d}$ gives ${\displaystyle \alpha =d/(2d-r+k)}$ (assuming ${\displaystyle d\leq k}$). For MDS codes this simplifies to ${\displaystyle \alpha =d/(d+1)}$, coinciding with our symbiotic attack. For non-MDS codes there seems to be a slight mismatch. The reason is that if a non-MDS code is maximally shortened, the shortened code has dimension 1, whereas in the derivation of Theorem 3 we pessimistically assumed${\displaystyle k-\theta =0}$ (at least for the KP non-MDS codes that satisfy ${\displaystyle r-d=k}$). Correcting for this looseness would result in a match with the symbiotic attack.

### Generic Collision Attack against MDS Constructions

Algorithm 4 (Collision Attack against MDS-based schemes).

If we want to run Algorithm 3 (with fixed ${\displaystyle \theta =r-k}$ и ${\displaystyle \alpha =k/(3k-r)}$ as obtained in Corollary 1) we ideally want a time complexity almost coinciding with the targeted query complexity. For ${\displaystyle \theta =r-k}$ it holds that ${\displaystyle X={\widetilde {X}}}$,obviating the need for the steps Filtering and Degrees of Freedom. We have already seen that Local Collision Detection costs at most a small logarithmic factor, which leaves only the Merge Phase and Collision Pruning to worry about. Together, these two steps are designed to produce ${\displaystyle L_{x}}$. A naive approach would enumerate all elements in the much larger ${\displaystyle L_{\widetilde {x}}}$, which is wasteful. Our task is therefore, given the lists of partial collisions ${\displaystyle L_{i}}$ for ${\displaystyle i\in X}$, to create ${\displaystyle L_{x}}$ more efficiently.

In the sequel, we will follow in the footsteps of O ̈zen, Shrimpton, and Stam who used the dual code in a similar problem related to their preimage-finding attack. An important innovation for the collision-finding attack stems from the realization that ${\displaystyle \delta }$ can be regarded as belonging to the (quasi) shortened code. This allows the use of the dual of the shortened code to speed up the search. As the minimum distance of the dual code is an important parameter in determining the overall time-complexity and shortening a code reduces the minimum distance of its dual accordingly, we make a significant efficiency gain this way

Road map. We present our collision attack against Knudsen-Prennel compression functions whose ${\displaystyle C^{PRE}}$ is based on MDS codes in Alg. 4, whereas its analysis is given in Thm. 4. We leave the generalization of our attack to (KP-suggested) non-MDS parameters together with the proof of Thm. 4 to the full version of this work where we also investigate a more space efficient version of Alg. 4.

Reducing the Time Complexity. Since ${\displaystyle X={\widetilde {X}}}$ and ${\displaystyle \theta =r-k}$, we know from Algorithm 3 that it is enough to find a nonzero ${\displaystyle \Delta \in \varpi (C'^{PRE})}$ of the form ${\displaystyle \Delta =\Delta '+0}$ for ${\displaystyle \Delta '=\sum _{i\in {\widetilde {X}}}\Delta _{i}}$ to complete the collision. Now notice that ${\displaystyle \Delta '}$ is lying in a smaller space ${\displaystyle \varpi (C'^{PRE})}$, identified by ${\displaystyle C'}$, that is the ${\displaystyle [r-\theta ,k-\theta ,d']}$ shortened code obtained from ${\displaystyle C}$ (by dropping the zeroes of the codewords from all the positions appearing in${\displaystyle X_{0}}$). This observation allows us to guarantee that ${\displaystyle \Delta \in \varpi (C^{PRE})}$, once we determine that a candidate ${\displaystyle \Delta '}$ is in${\displaystyle \varpi (C'^{PRE})}$. Hence, it is enough for our purposes to limit ourselves to ${\displaystyle \varpi (C'^{PRE})}$, rather than looking for membership in the larger space${\displaystyle \varpi (C^{PRE})}$.

To this end, we first identify an index set ${\displaystyle X_{h'}\subseteq \left\{1,...,r\right\}}$ (the role of ${\displaystyle h'}$ will be explained momentarily) defining a subspace ${\displaystyle \bigoplus _{i\in X_{h'}}V_{i}}$, for which ${\displaystyle \varpi (C'^{PRE})}$ when restricted to this subspace, is not surjective. As a consequence, we will be able to prune significantly the total collection of candidate ${\displaystyle \Delta '}$, которые допустимы ${\displaystyle \varpi (C'^{PRE})}$ (restricted to ${\displaystyle \bigoplus _{i\in X_{h'}}V_{i}}$). In the sequel, we will show how to efficiently find an index set ${\displaystyle X_{h'}}$ and how to efficiently prune.

An important parameter determining the runtime of our collision attack is ${\displaystyle d'^{\perp }}$, the minimum distance of the dual shortened code. Let ${\displaystyle \chi }$ be function that maps ${\displaystyle h'\in F_{2^{e}}^{r-\theta }}$ to the set of indices of non-zero entries in ${\displaystyle h'}$. Thus, ${\displaystyle \chi (h')\subseteq \left\{1,...,r\right\}}$ and ${\displaystyle |\chi (h')|}$ equals the Hamming weight of the codeword ${\displaystyle h'}$.

An easy adaptation of Proposition 1 shows that if we are given a codeword ${\displaystyle h'\in C'^{\perp }}$ and an element ${\displaystyle \Delta '\in F_{2}^{(r-\theta )en'}}$, then ${\displaystyle \Delta '}$ can only be in ${\displaystyle \varpi (C'^{PRE})}$, if ${\displaystyle ({\overline {\varphi }}(h'^{T})\bigotimes I_{n'})\delta '=0}$, where the only parts of ${\displaystyle \Delta '}$ relevant for this check are those lining up with the nonzero entries of ${\displaystyle h'}$. Indeed, an element ${\displaystyle \Delta '_{h'}\in \sum _{i\in \chi (h')}L_{i}}$ can be completed to an element in the range of derived mapping ${\displaystyle C'^{PRE}}$ if ${\displaystyle ({\overline {\varphi }}(h'^{T})\bigotimes I_{n'})(\Delta '_{h'}+0)=0}$. Efficient creation of

${\displaystyle L_{h'}=\left\{(\Delta '_{h'},X,X')\in \sum _{i\in \chi (h')}L_{i}|({\overline {\varphi }}(h'^{T})\bigotimes I_{n'})(\Delta '_{h'}+0)=0\right\}}$


can be done adapting standard techniques [13], [14], [15]by splitting the codeword in two and looking for all collisions in respective entries. That is, assume that ${\displaystyle h'=h'_{0}+h'_{1}}$ with ${\displaystyle \chi (h'_{0})\cap \chi (h'_{1})=0}$, assume, for ${\displaystyle j=0,1}$

${\displaystyle {\widetilde {L_{h'_{j}}}}=\left\{(\Delta '_{h'},X,X',({\overline {\varphi }}(h'^{T})\bigotimes I_{n'})(\Delta '_{h'}+0)=0|(\Delta '_{h'},X,X')\in \sum _{i\in \chi (h'_{j})}L_{i}\right\}}$.

Then ${\displaystyle L_{h}'}$ consists of those elements ${\displaystyle \Delta '_{h'_{0}}+\Delta '_{h'_{1}}}$, for which ${\displaystyle (\Delta '_{h'_{0}},X_{0},X'_{0},Y_{0})\in {\widetilde {L_{h'_{0}}}},(\Delta '_{h'_{1}},X_{1},X'_{1},Y_{1})\in {\widetilde {L_{h'_{1}}}}}$ and ${\displaystyle Y_{0}=Y_{1}}$.

Theorem 4
Let ${\displaystyle H=KP^{b}([r,k,d]_{2^{e}})}$ code be given and ${\displaystyle C'}$ be a shortened ${\displaystyle [r-\theta ,k-\theta ,d]^{2^{e}}}$ code, derived from ${\displaystyle C}$ for ${\displaystyle \theta =r-k}$. Let ${\displaystyle d'^{\perp }}$ - be the minimum distance of the dual code of ${\displaystyle C'}$. Suppose ${\displaystyle C}$ is MDS and consider the collision attack described in Alg. 4 run against ${\displaystyle H_{n}}$ using ${\displaystyle q=2^{\alpha n}}$ queries for ${\displaystyle \alpha =k/(3k-r)}$. Then the expected number of collision outputs is equal to one and the expectations for the internal list sizes are:

${\displaystyle |L_{i}|=2^{(2\alpha -1)n}}$, ${\displaystyle |L_{h'}|=2^{((2\alpha -1)d'^{\perp }-\alpha )n}|}$, ${\displaystyle |{\widetilde {L_{h'_{0}}}}|=|L_{h'}|=2^{((2\alpha -1)[d'^{\perp }/2]-\alpha )n}|}$, ${\displaystyle |{\widetilde {L_{h'_{1}}}}|=|L_{h'}=2^{((2\alpha -1)[d'^{\perp }/2]-\alpha )n}|}$. The average case time complexity of the algorithm is max ${\displaystyle max(q,{\widetilde {L_{h'_{0}}}},L_{h'})}$ with a memory requirement of ${\displaystyle max(q,{\widetilde {L_{h'_{1}}}})}$ (expressed in 𝑐𝑛-bit blocks).

Proof
W/o proof

## Conclussion

In this paper we provide an extensive security analysis of the Knudsen-Preneel compression functions by focusing on their collision resistance. We present three improved collision attacks namely the revised Watanabe, symbiotic collision and parametrized collision attacks. Our new attacks work with the least number of queries reported so far. Moreover, except for only one out of 16 suggested parameters, these attacks beat the time-complexity of any prior attack we are aware of.

Acknowledgments. We thank Joachim Rosenthal and Thomas Shrimpton for their useful comments and suggestions.

## Authors

1. LACAL, EPFL Station 14, CH-1015 Lausanne, Switzerland,E-mail:onur.ozen@epfl.ch
2. LACAL, EPFL Station 14, CH-1015 Lausanne, Switzerland,E-mail:martijn.stam@epfl.ch

## References

1. Yuval, G.: How to swindle Rabin. Cryptologia 3, 187–189 (1979)
2. Black,J.,Rogaway,P.,Shrimpton,T.:Black-boxanalysisoftheblock-cipher-based hash-function constructions from PGV. In: Yung [15], pp. 320–335
3. Preneel, B., Govaerts, R., Vandewalle, J.: Hash functions based on block ciphers: A synthetic approach. In: Stinson, D. (ed.) Advances in Cryptography—Crypto’93. LNCS, vol. 773, pp. 368–378. Springer, Heidelberg (1993)
4. Stam, M.: Blockcipher-based hashing revisited. In: Dunkelman, O. (ed.) FSE’09. LNCS, vol. 5665, pp. 67–83. Springer, Heidelberg (2009)
5. Knudsen, L., Muller, F.: Some attacks against a double length hash proposal. In: Roy, B.K. (ed.) Advances in Cryptography—Asiacrypt’05. LNCS, vol. 3788, pp. 462–473. Springer, Heidelberg (2005)
6. O ̈zen, O., Stam, M.: Another glance at double-length hashing. In: Parker, M.G. (ed.) CCC’09. LNCS, vol. 5921, pp. 176–201. Springer, Heidelberg (2009)
7. Knudsen, L.R., Preneel, B.: Hash functions based on block ciphers and qua- ternary codes. In: Kim, K., Matsumoto, T. (eds.) Advances in Cryptography— Asiacrypt’96. LNCS, vol. 1163, pp. 77–90. Springer, Heidelberg (1996)
8. Knudsen, L.R., Preneel, B.: Fast and secure hashing based on codes. In: Burt Kaliski, J., Burton, S. (eds.) Advances in Cryptography—Crypto’97. LNCS, vol. 1294, pp. 485–498. Springer, Heidelberg (1997)
9. Knudsen, L.R., Preneel, B.: Construction of secure and fast hash functions using nonbinary error-correcting codes. IEEE Transactions on Information Theory 48(9), 2524–2539 (2002)
10. Watanabe, D.: A note on the security proof of Knudsen-Preneel construction of a hash function (2006), unpublished manuscript, Available at http://csrc.nist.gov/groups/ST/hash/documents/WATANABE_kp_attack.pdf
11. Ozen O.,Stam,M.:CollisionattacksagainstKnudsen-Preneelcompressionfunc- tions, full version of this paper, Manuscript (2010)
12. Ozen, O., Shrimpton, T., Stam, M.: Attacking the Knudsen-Preneel compression functions. In: Hong, S., Iwata, T. (eds.) FSE’10. LNCS, vol. 6147, pp. 94–115. Springer, Heidelberg (2010)
13. Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: An algorithmic point of view. In: Knudsen, L. (ed.) Advances in Cryptography—Eurocrypt’02. LNCS, vol. 2332, pp. 209–221. Springer, Heidelberg (2002)
14. Schroeppel, R., Shamir, A.: A 𝑇 = 𝑂(2𝑛/2), 𝑆 = 𝑂(2𝑛/4) algorithm for certain NP-complete problems. SIAM Journal on Computing 10, 456–464 (1981)
15. Wagner, D.: A generalized birthday problem. In: Yung [15], pp. 288–303