Post-quantum cryptography: Password security in the quantum era

Quantum mechanics is the study of physics at the level of incredibly small things – smaller than atoms. Anyone who’s looked into theories like wave-particle duality and entanglement, knows things can get confusing (and weird) very quickly. But it’s not all theory. Quantum computing is an attempt to harness the principles of quantum mechanics and get computers to process information in fundamentally new ways. For cybersecurity professionals, this presents both a challenge and an opportunity.

The main concern that comes up is quantum computers could render current encryption methods obsolete. Algorithms which underpin much of today’s secure communications, rely on the difficulty of factoring large numbers or solving discrete logarithms—tasks that quantum computers could perform with ease. This means sensitive data, from financial transactions to national security communications, could become vulnerable. On the other hand, quantum computing also opens the door to new, post-quantum cryptography techniques that could provide even stronger security.

How do quantum computers crack passwords?

Quantum computers don’t directly “crack” passwords in the traditional sense, but they can significantly impact the security of the cryptographic systems that protect passwords. Specifically, quantum computers can break certain types of encryption and hashing algorithms that are currently used to secure password storage and transmission.

Classical computers use bits (1s and 0s) to represent data. Quantum computers instead use quantum bits, or qubits, which can exist in multiple states simultaneously (we did warn it gets weird!). This property, known as superposition, allows quantum computers to perform complex calculations at an unprecedented speed, potentially solving problems that would take classical computers millions of years to crack.

Conventional cryptography algorithms work by picking two big prime numbers and multiplying them to get an even larger number. A computer must reverse the process to work out which prime numbers were multiplied together if it is to break the encryption, which could take a conventional system billions of years.

Shor’s algorithm

These calculations can be tied back to ‘Shor’s Algorithm’, created by Peter Shor in 1994, which could in theory break the mathematical problems tied to public key cryptography (PKC). This was because it would be able to perform prime factorization much more quickly than normal computers. However, it would need a large quantum computer to work – technology that is now nearing reality.

A powerful quantum computer could work through all of the potential prime factors simultaneously, instead of just one at a time. It could use Shor’s algorithm to efficiently factor large integers and solve the discrete logarithm problem. This means that it’s possible a quantum computer could solve a puzzle in days or even hours that may have taken a traditional computer billions of years.

What is post-quantum cryptography?

Post-quantum cryptography, also known as quantum-resistant cryptography, is a branch of cryptography focused on developing algorithms that can withstand attacks from quantum computers. As we’ve discussed, quantum computers have the potential to rapidly solve mathematical problems that would seem impossible with traditional technology. Post-quantum cryptography tries to combat this by using different mathematical problems that are believed to be hard for both classical and quantum computers to solve.

This is an evolving field and several approaches are being explored in post-quantum cryptography, including:

• Lattice-based cryptography: relies on the difficulty of finding the shortest vector in a high-dimensional lattice, a problem that is believed to be resistant to quantum attacks
• Code-based cryptography: uses error-correcting codes to create cryptographic systems that are resistant to attacks by quantum computers
• Multivariate polynomial cryptography: approach that relies on the difficulty of solving systems of multivariate polynomial equations
• Hash-based signatures: digital signature schemes that use hash functions to create signatures, providing security against quantum computer attacks by leveraging the properties of hash functions to ensure integrity and authenticity.

Can hackers use quantum technology?

Currently, quantum computers are not widely available or powerful enough for most hackers to use effectively. But as the technology advances, there is a growing concern that they could potentially be used to break many of today’s cryptographic systems. Quantum computing certainly has the potential to dramatically change the landscape of password security. On the cracking side, quantum computers could break through traditional password hashing algorithms with relative ease.

Current encryption methods like bcrypt, scrypt, and PBKDF2 rely on the computational difficulty of reversing hash functions, but quantum computers could potentially brute-force these hashes much faster than classical computers. This means that even strong, complex passwords could be at risk, as the time required to crack them would be significantly reduced.

Is quantum computing going to break passkeys?

Passkeys are a form of passwordless authentication are designed to be more secure than traditional passwords by using public-key cryptography. So quantum computing does pose a significant threat to the cryptographic algorithms that underpin passkeys. Specifically, the algorithms used for key generation, such as RSA and ECC, could be vulnerable to quantum attacks.

However, the cryptographic community is already working on solutions to this potential problem in the form of post-quantum cryptography. As these post-quantum algorithms mature and are standardized, they can be integrated into passkey systems to ensure they remain secure even in the face of quantum computing.

Will post-quantum cryptography keep passwords secure?

While passwords themselves are not directly affected by quantum computing, the systems that protect and manage passwords, such as those used for secure authentication and encryption of password databases, could be. For example, if the encryption used to protect password hashes is based on vulnerable algorithms, it could become susceptible to quantum attacks.

However, post-quantum cryptography also offers ways to enhance password security. Quantum-resistant algorithms are being developed to withstand attacks from quantum computers. These algorithms are designed to be computationally infeasible to break, even with the power of quantum computing. Additionally, quantum key distribution (QKD) could provide a way to securely transmit encryption keys, ensuring that even if passwords are intercepted, they remain protected.

However, it’s important to note that post-quantum cryptography won’t protect your end users from having their passwords stolen via malware, social engineering, or compromised through password reuse. Interested to know how many of your Active Directory passwords are already weak or compromised? Run a read-only scan with our free tool: Specops Password Auditor.

What does NIST say about post-quantum cryptography?

The National Institute of Standards and Technology (NIST) has been actively involved in the development and standardization of post-quantum cryptographic algorithms. Last August, NIST released its first three finalized post-quantum encryption standards, designed to withstand attacks from quantum computers.

Here’s a summary of their key recommendations and actions:

1. Standardization process: NIST has been running a multi-year process to evaluate and standardize post-quantum cryptographic algorithms. This process involves multiple rounds of evaluation, where candidate algorithms are rigorously tested for security, performance, and practicality.
2. Selected algorithms: In July 2022, NIST announced the first set of post-quantum cryptographic algorithms that will be standardized:
   • Cryptography for Key Encapsulation Mechanisms (KEMs): CRYSTALS-Kyber
   • Cryptography for Digital Signatures: CRYSTALS-Dilithium, FALCON, and SPHINCS+
3. Implementation guidance: NIST has provided guidance on how organizations can prepare for the transition to post-quantum cryptography. This includes:
   • Hybrid approaches: Using a combination of classical and post-quantum algorithms to ensure security during the transition period.
   • Algorithm agility: Designing systems to easily switch between different cryptographic algorithms as new standards are adopted.
4. Testing and validation: NIST emphasizes the importance of thorough testing and validation of post-quantum algorithms to ensure they meet security and performance requirements. They provide test vectors and other resources to help developers and organizations test their implementations.
5. Ongoing research: NIST continues to monitor and research new developments in post-quantum cryptography. They are also considering additional algorithms for standardization in the future. They also offers a range of educational materials and workshops to help organizations understand the implications of quantum computing and the steps needed to adopt post-quantum cryptography.

Are there steps organizations should be taking to prepare for the quantum era?

A lot of what we’re discussing here is still theory. In practical terms, there aren’t immediate steps you need to take. However, thinking about the transition to post-quantum algorithms now will make things easier if they were to become standardized. The underlying systems that handle password storage and authentication may need to be upgraded to use quantum-resistant algorithms at some point in the future.

For now, keep up-to-date with the latest developments in post-quantum cryptography. Follow NIST’s publications and other reputable sources for updates on standardized algorithms and best practices. You could also consider using hybrid cryptographic schemes that combine classical and post-quantum algorithms – this can provide an additional layer of security during the transition period.

Don’t neglect traditional password threats

Remember that it doesn’t matter how strong a stolen password is. We’ve carried out research into how long it takes to crack encrypted passwords with brute force techniques, but a compromised password is cracked instantly. Quantum computers and protection are very unlikely to impact the majority of password threats an organization faces – like phishing, malware, and risky end user behavior like password reuse.

Organizations will continue to rely on the advantages that password security provides, notably its simplicity, flexibility (passwords can easily be reset) and underlying effectiveness (they’re either right or wrong). Optimum security depends on layering multi-factor authentication on top of strong password policies.

Specops Password Policy prevents users from creating weak, easily-guessed passwords, while continuously scanning your Active Directory for more than 4 billion compromised passwords. Reach out to learn how Specops Password Policy could fit in with your organization.