Can quantum computing break encryption algorithms?

Chinese researchers, led by Wang Chao from Shanghai University, claim to have achieved a significant breakthrough by using a D-Wave quantum computer to mount the first successful quantum attack on widely used encryption algorithms. This advancement, highlighted in their peer-reviewed paper in the Chinese Journal of Computers, demonstrates the potential threat that quantum computing could pose to sensitive sectors like banking and the military, especially as it relates to cryptographic algorithms based on the Substitution-Permutation Network (SPN) structure.

Using a quantum computer not originally intended for cryptographic applications, Wang’s team targeted algorithms such as Present, Gift-64, and Rectangle, which share structural similarities with Advanced Encryption Standard (AES). While these algorithms were breached, no specific passcodes were cracked, underlining the early-stage nature of the threat.

Quantum computing is still hindered by limitations like environmental interference, underdeveloped hardware, and the inability to create a universal attack method for different encryption systems. Despite these barriers, the research marks a significant step forward, showing that quantum computers are inching closer to compromising encryption systems.

The study highlights quantum annealing as the technique employed to solve complex mathematical problems more efficiently than classical methods, thanks to the unique properties of quantum tunneling. Although quantum computing has not yet fully realized its cryptographic potential, ongoing developments could expose new vulnerabilities in encryption systems used across critical industries.

Is AES-256 Encryption at Risk from Quantum Computing?

Recent claims by Chinese researchers using a D-Wave quantum computer to breach cryptographic algorithms have reignited concerns about the potential vulnerabilities of AES-256 encryption in a quantum world. The researchers’ experiment, which targeted Substitution-Permutation Network (SPN)-structured algorithms (similar to those found in AES), raises the question: Is AES-256 encryption truly at risk from quantum computing?

AES-256 and Quantum Computing

AES-256 is widely considered the gold standard in encryption, particularly for sensitive sectors like finance, defense, and government. Its strength lies in the fact that it uses a 256-bit key, making brute-force attacks virtually impossible for classical computers. Even with the best available technology, it would take classical computers billions of years to crack AES-256 encryption. However, quantum computing, with its ability to solve certain types of problems exponentially faster, poses a potential long-term threat.

Quantum Threats: Reality or Hype?

The recent study by Wang Chao’s team certainly highlights the advances in quantum computing, specifically using quantum annealing to breach SPN-structured algorithms. However, several key factors suggest that AES-256 remains secure for the foreseeable future:

1. No Direct Attack on AES-256: The research targeted algorithms similar to AES but did not crack AES-256 itself. While the Substitution-Permutation structure is a critical component of AES, breaching similar structures does not directly translate into an immediate threat to AES-256 encryption. The researchers also acknowledged that no specific passcodes were revealed during their study.
2. Current Quantum Computing Limitations: The quantum computer used in the research is still in its early stages of development. The team behind the study admitted that environmental interference, immature hardware, and the inability to create a universal attack algorithm are significant hurdles. While the D-Wave quantum computer demonstrated some success in cryptographic challenges, it is not yet capable of cracking AES-256 due to the sheer computational complexity required.
3. Quantum Annealing vs. General Quantum Computing: The D-Wave quantum computer uses quantum annealing, a process optimized for specific problem-solving tasks like optimization and machine learning, but not necessarily suited for general cryptographic attacks. For a full-fledged quantum computer to crack AES-256, it would need to run Shor’s algorithm, which would require a quantum computer with millions of qubits—a capability that is still years, if not decades, away.
4. Post-Quantum Cryptography in Development: Even though quantum computing is evolving, cryptographic experts are not standing idle. The National Institute of Standards and Technology (NIST) is already developing post-quantum cryptography algorithms designed to resist quantum attacks. By the time quantum computers mature enough to pose a credible threat to AES-256, these new encryption standards will likely be in place.

The Timeline of Quantum Threats

Experts agree that while quantum computers will one day be capable of breaking current encryption algorithms, we are not there yet. The consensus among cryptographers is that it could be 10-20 years before quantum computers can run algorithms like Shor’s at a scale necessary to break AES-256 encryption. This gives organizations ample time to transition to post-quantum cryptographic methods.

Conclusion: AES-256 Remains Safe for years to come

The findings of Wang Chao’s team are noteworthy, but they do not signal an immediate threat to AES-256 encryption. The challenges in quantum computing, combined with the continued development of post-quantum cryptography, suggest that AES-256 will remain secure for years to come. While the future of encryption in a quantum world is uncertain, current quantum capabilities are far from making AES-256 obsolete.

What about ASE 128?

Older encryption algorithms, such as AES-128, are more susceptible to compromise by quantum computing compared to stronger variants like AES-256. However, both AES-128 and AES-256 remain secure against traditional (classical) computing attacks for the time being.

Key Length and Security

• AES-128 uses a 128-bit key, while AES-256 uses a 256-bit key. The strength of an encryption algorithm is closely tied to the length of its key; a longer key generally provides exponentially more security.
• Classical brute-force attacks on AES-128 would take an unfeasibly long time, but quantum computing can significantly reduce the time required to break encryption through algorithms like Shor’s algorithm and Grover’s algorithm.

2. Grover’s Algorithm Impact

• Grover’s algorithm is a quantum algorithm that speeds up brute-force attacks. For AES-128, Grover's algorithm can reduce the search space from 2^128 to 2^64, meaning that AES-128 would only provide 64-bit security against a quantum computer. This makes AES-128 much more vulnerable to quantum attacks compared to AES-256.
• In contrast, AES-256’s security is reduced from 2^256 to 2^128, which still offers an extremely high level of protection.

3. Shor’s Algorithm Impact

• Shor’s algorithm is designed for factoring large numbers and solving discrete logarithms, which makes it a threat to public-key cryptosystems like RSA and ECC (Elliptic Curve Cryptography), but it does not directly apply to symmetric algorithms like AES. However, the concern remains that future advances in quantum algorithms may introduce new ways to attack symmetric encryption methods.

4. AES-128 vs. AES-256 in a Quantum Context

• AES-128: With 128-bit key length, Grover's algorithm cuts its security down to 64 bits, which is considered inadequate for long-term protection against quantum computers.
• AES-256: Even with Grover’s reduction, AES-256’s 128-bit effective security is still viewed as highly secure and much more resistant to quantum attacks.

5. What you need to do

• AES-128 may still be suitable for many current applications because quantum computers that can run algorithms like Grover’s at scale are likely at least a decade or more away.
• However, AES-256 is already widely recommended, especially for use cases requiring long-term security (e.g., in banking, military, and healthcare sectors), because it offers greater future-proofing against quantum threats.
• If you are running an in-house PKI and / or issuing certificates for corporate network authentication such as Microsoft Active Directory ensure that the Kerberos authentication certificates you are issuing are ASE 256 and not ASE 128.

How to improve protection against quantum computing hacks:

Move to RSA-2048+ or ECC-384+: While quantum-resistant algorithms are still being standardized, it’s advisable to use the strongest classical algorithms available. RSA keys shorter than 2048 bits and ECC keys shorter than 384 bits are considered weak against future quantum computers. Increasing key lengths (e.g., RSA-4096) can provide some additional protection in the meantime, though these will still eventually be vulnerable to quantum attacks.

Increase Symmetric Key Sizes: Symmetric encryption algorithms like AES will also be affected by quantum computers, though to a lesser extent. Using AES-256 rather than AES-128 will offer greater resilience, as even with quantum speedup (e.g., Grover’s algorithm), AES-256 provides 128-bit security.

Update Key Lifetimes: Shorten the lifetime of cryptographic keys to minimize exposure to potential future quantum attacks. By refreshing keys more frequently, even if quantum computers become a threat, the amount of sensitive data that could be decrypted by future quantum attacks is reduced.

Audit and Inventory Certificates: Perform a comprehensive audit of your PKI infrastructure to understand where vulnerable algorithms are in use. Replace outdated certificates and keys with stronger ones, and ensure that processes are in place to regularly update them.

Offline Root CA: Keeping the root CA offline adds an additional layer of security by protecting the most critical keys from being exposed to network-based attacks, including potential future quantum attacks. An offline root CA is less susceptible to compromise since it isn’t directly accessible to malicious actors.

Protect Cryptographic Hardware: Ensure Hardware Security Modules (HSMs) used in your PKI infrastructure are updated with secure firmware and hardened against both classical and quantum-based attacks. These devices protect private keys and must be physically secured to prevent tampering.

Maintain Operational Security: Ensure that access to PKI systems is tightly controlled and regularly audited. Poor operational security could allow adversaries to compromise a system even before quantum threats become fully realized.