Polynomial-Time Attacks Reduce Complexity of FBC Algorithm Key Recovery

The security of symmetric encryption algorithms faces increasing threats as computing power grows, prompting researchers to investigate vulnerabilities to advanced attacks. Yan-Ying Zhu, Bin-Bin Cai, and Fei Gao, along with Song Lin, present a detailed analysis of the FBC algorithm, evaluating its resilience against adversaries employing different query methods. Their work reveals new methods for distinguishing between legitimate encryption and random data within the FBC framework, enabling key-recovery attacks that significantly reduce the computational effort required compared to traditional brute-force approaches. These attacks, effective in both advanced quantum and classical computing scenarios, demonstrate a substantial weakening of the FBC algorithm’s security, requiring remarkably few plaintext-ciphertext pairs to recover the encryption keys and highlighting a critical need for improved cryptographic designs.

Quantum Attacks Reduce FBC Cipher Security

This research investigates quantum attacks against a lightweight block cipher called FBC and its variants. The study focuses on utilizing quantum algorithms, including variations of Simon’s algorithm and related techniques, to assess and reduce the security of these ciphers. The primary goal is to determine the minimum amount of data required for a successful quantum attack. Feistel ciphers, which repeatedly split data, transform one half based on the other and a key, and then swap the halves, form the foundation of this analysis. The research also considers “offline” versions of Simon’s algorithm, effective even when an attacker cannot directly query the encryption system, crucial for analyzing scenarios with limited data access.

The team explores generalized Feistel schemes and focuses on lightweight cryptography, designed for resource-constrained devices like those used in the Internet of Things. The research presents new results on the quantum cryptanalysis of FBC and its variants, establishing upper bounds on the data an attacker needs to break the cipher using quantum algorithms. The findings suggest that FBC and its variants are vulnerable to quantum attacks with relatively low data complexity, meaning an attacker with a quantum computer could potentially break these ciphers with limited data.

Grover-Simon Algorithm for FBC Security Analysis

Researchers developed a comprehensive methodology to assess the security of the FBC algorithm by considering adversaries with varying computational capabilities. Recognizing the threat quantum attacks pose to symmetric cryptography, the team moved beyond brute-force approaches and focused on sophisticated techniques like Simon’s and Grover’s algorithms. A key innovation lies in the application of a “Grover-meets-Simon” algorithm, integrating Simon’s algorithm within a Grover search to significantly reduce the complexity of key recovery. This technique first uses Grover’s algorithm to narrow down potential key candidates, then employs Simon’s algorithm to efficiently identify periodic functions that reveal the key, achieving substantial speedups compared to traditional methods.

The researchers extended this approach by developing an “offline” version of Simon’s algorithm, enabling quantum attacks even when the encryption system only accepts classical queries. To rigorously test the algorithm’s resilience, the team designed quantum distinguishers, algorithms that can differentiate encrypted data from random noise, for different structures within the FBC algorithm. These distinguishers, constructed with varying numbers of rounds, were then used as the foundation for key-recovery attacks. Notably, the researchers achieved polynomial-time distinguishers, meaning the time required to break the encryption grows at a manageable rate with increasing key length. This comprehensive approach allowed them to identify vulnerabilities under realistic threat scenarios and to quantify the reduction in complexity achieved by their novel quantum algorithms.

FBC Algorithm Weaknesses Revealed by New Attacks

Researchers have significantly advanced the cryptanalysis of the FBC algorithm, a block cipher employing a complex Feistel network, by developing new attacks that exploit vulnerabilities in its structure. Their work focuses on assessing security against adversaries with varying computational capabilities. The team has demonstrated attacks applicable to different configurations of the FBC algorithm, FBC-F, FBC-KF, and FBC-FK, improving upon existing methods and revealing new weaknesses. In quantum cryptanalysis, the researchers designed quantum distinguishers for the FBC-F and FBC-KF structures in just four rounds.

These distinguishers then form the basis of key-recovery attacks, reducing the computational effort needed to break the cipher by a factor of 24. 5 times for certain configurations. A new six-round quantum distinguisher was also developed for the FBC-FK structure. Importantly, the team also achieved breakthroughs in attacking the FBC algorithm using limited data in a classical setting. By combining the Grover algorithm with efficient search techniques, they developed attacks on the FBC-KF and FBC-FK structures that require only a constant amount of plaintext-ciphertext pairs, a significant reduction compared to previous methods.

This low-data attack recovers all keys with a time complexity of O(2 n/2 ), while maintaining negligible storage requirements. These findings demonstrate that the FBC algorithm is susceptible to attacks with significantly reduced complexity compared to exhaustive key searches, both in quantum and classical computational models. The researchers’ work not only identifies specific vulnerabilities but also highlights the importance of considering diverse attack vectors when evaluating the security of cryptographic systems. The new distinguishers and key-recovery attacks provide valuable insights for improving the design and implementation of future block ciphers.

FBC Cipher Vulnerabilities Exploited With Key Recovery

This research presents new attacks against the FBC algorithm, a cipher designed with a specific structure to improve efficiency. The team demonstrated that, under certain conditions, the cipher’s security is lower than previously thought. Specifically, they developed distinguishers and key-recovery attacks applicable to the FBC-F, FBC-KF, and FBC-FK structures when an attacker can make multiple queries, reducing the computational effort needed to break the cipher compared to a brute-force approach. Furthermore, the researchers showed that, with limited access to plaintext-ciphertext pairs, they could still recover the keys for the FBC-KF and FBC-FK structures, exploiting vulnerabilities in how the cipher handles key injection.

The attacks require minimal data and reduce the time complexity of key recovery. The authors acknowledge that their work focuses on specific attack models and that the practical impact of these attacks may depend on the implementation and deployment of the cipher. Future research could explore the effectiveness of these attacks in more realistic scenarios and investigate potential countermeasures to strengthen the FBC algorithm against these vulnerabilities.