Introduction
The NIST SHA-3 competition was initiated to identify a robust successor to the SHA-1 and SHA-2 families. Among the candidates, LANE emerged as a design leveraging the well-understood security properties of AES-like structures, specifically Substitution-Permutation Networks (SPNs). LANE processes data through parallel "lanes" of permutations, aiming for high performance and resistance to traditional differential cryptanalysis. This paper explores the security margins of LANE by identifying vulnerabilities in reduced-round versions through advanced cryptanalytic techniques.
The LANE Architecture
LANE's core is its compression function, which utilizes six parallel permutations, denoted as $P_0$ through $P_5$. The message expansion block takes the current message block $M_i$ and the previous hash state $H_{i-1}$ to generate six internal message words $W_0, \dots, W_5$. These words serve as inputs to the parallel permutations.
As shown in Figure 1, the outputs of these permutations are combined via XOR operations and passed through two final permutations, $Q_0$ and $Q_1$, before being XORed again to produce the next hash state $H_i$. This parallel structure was intended to provide efficiency, but it also introduces specific avenues for cryptanalysis.
Cryptanalytic Methodology
The analysis employs three primary strategies to find collisions in reduced-round variants of LANE.
1. The Rebound Attack
The rebound attack is a powerful tool against AES-like structures. It consists of two phases:
- Inbound Phase: The attacker identifies a match in the middle of the permutation where the degrees of freedom are highest. In an AES-like S-box, a random input difference and output difference match with a probability of 1/2, facilitating efficient matching.
- Outbound Phase: The differences found in the inbound phase are propagated forward and backward through the remaining rounds. The goal is to ensure these differences result in a collision at the output.
2. Fixed-Byte Technique
To manage the constraints imposed by LANE’s message expansion, the "fixed-byte" technique is introduced. By fixing specific bytes of the internal state to zero, attackers can pre-compute portions of the state and bypass some of the diffusion provided by the MixColumns and SwapColumns operations. This effectively reduces the complexity of the meet-in-the-middle step required for the rebound attack.
3. Inner Collision Construction
A critical insight in this analysis is the exploitation of LANE's parallel architecture. Because the message expansion is a linear code, an attacker does not need to control all six lanes to produce a collision.
As illustrated in Figure 4, by targeting four active lanes (shaded in the diagram), it is possible to force "inner collisions." In this scenario, the differences introduced in the active lanes cancel each other out during the XOR summation before reaching the $Q$ permutations, resulting in a zero difference at the final output $H_i$.
Results and Analysis
The application of these techniques led to the first successful collision attacks on reduced-round versions of LANE-256 and LANE-512. The results are summarized in the table below:
| Target Variant | P Rounds | Q Rounds | Attack Type | Complexity | Memory |
|---|---|---|---|---|---|
| LANE-256 | 3 | 3 | Semi-free start collision | $2^{62}$ | $2^{69}$ |
| LANE-512 | 3 | 4 | Semi-free start collision | $2^{62}$ | $2^{69}$ |
| LANE-512 | 3 | 4 | Full Collision | $2^{94}$ | $2^{133}$ |
For LANE-256, the attack complexity of $2^{62}$ represents a significant theoretical improvement over the standard birthday attack complexity of $2^{128}$.
Conclusion
While the attacks demonstrate structural weaknesses in reduced-round variants of LANE, the full hash function (employing 6 to 8 rounds for the $P$ permutations) remains secure against these specific methods. The diffusion provided by the MixColumns and SwapColumns operations eventually "washes out" the fixed values used in the attack. Furthermore, the astronomical memory requirements for the LANE-512 full collision ($2^{133}$) render the attack impractical for current hardware. Nonetheless, this analysis provides vital insights into the security margins of AES-based hash functions and the potential risks of parallel permutation architectures.
Summary updated