[Feature request] Post-quantum encryption

Summary

KeePassXC currently uses AES or Twofish block cipher to encrypt a database. This issue is a feature request to add support for an established post-quantum encryption algorithm. I searched for related issues but didn't find anything.

Context

I'm aware that quantum computing won't be a realistic threat for a long time, but I believe it's wise to prepare for it sooner rather than later. If someone uses KeePassXC to store secrets meant to be held for a long time, the database might become vulnerable at some point. Further, databases that exist now might become vulnerable to harvest now decrypt later attacks by quantum computing.

I honestly don't know how effective quantum computing based attacks would be if/when quantum computing becomes feasible. My understanding is AES-256 remains secure for now because of its large key size, but could change with time. Grover's algorithm effectively halves AES's key size, making AES-128 insecure (equivalent to brute-forcing a 64-bit key) but AES-256 still secure against that particular attack, but other quantum attacks might break AES-256 in the future.

Implementations by other projects:

Signal
Tuta

I don't know that an established post-quantum block cipher exists yet or will ever be created, or whether or not post-quantum encryption should be added via key encapsulation or another way. I don't propose that this be implemented immediately but when it has been properly hashed out.

My understanding is adding this kind of support would require an update to the database format (to allow for a new encryption algorithm) as well as client support.

How credible does the KeePassXC community believe the risk of quantum computing is?
What would be the best way to add post-quantum encryption?
How difficult would adding support for a post-quantum encryption algorithm be?
Aside from old versions of KeePassXC being unable to open databases that use a new encryption algorithm, what unintentional consequences could arise by adding support for a new encryption algorithm?
Overall, what is the KeePassXC community's stance?

Further, databases that exist now might become vulnerable to harvest now decrypt later attacks by quantum computing.

This is of grave concern for applications that are designed to send/receive ciphertexts over networks (email, web, instant messaging and so on), but less so for databases that tend to stay on devices. Even so, some scenarios merit strong crpytography:

A user's device containing a database is lost or stolen in an unlocked state.
The contents including a database of a user's device is backed up to a server in plaintext.
A user's device containing a database is hacked into remotely.
The contents including a database of a user's device is copied while unattended or via coercion.
A user sends/receives a database over the internet unencrypted.

Most currently popular public-key cryptographic systems rely on the integer factorization problem or discrete logarithm problem, both of which would be easily solvable on large enough quantum computers using Shor's algorithm.

Post-Quantum Cryptography (PQC), also known as Quantum Safe Cryptography (QSC), refers to cryptographic algorithms designed to withstand attacks by quantum computers.

CRYSTALS-Kyber algorithm can be applied for general encryption like password managers, and CRYSTALS-Dilithium, FALCON, and SPHINCS+ for digital signatures.

CRYSTALS-Kyber offers several advantages, including comparatively small encryption keys that can be easily exchanged between two parties and its speed of operation. It is designed to create secure websites and protect sensitive information from quantum attacks like Kyber-1024-90s.

Having the ability in KeePassXC to digitally sign documents, to establish identity, is also extremely useful.

Computers are getting better and better at breaking encrypted things. Whether it is because of quantum computing or “regular” computing, AES 256 (even 512) WILL, one day, be unsafe. That day, KeePassXC should update the cryptographic algorithm to use a safe one. So in my opinion, this point is not, at all, a problem to consider in this brainstorming :

"Aside from old versions of KeePassXC being unable to open databases that use a new encryption algorithm, what unintentional consequences could arise by adding support for a new encryption algorithm?"

Everything I have read (which is quite a lot) about the theoretical capability of quantum computers to break encryption... has basically stated that AES-256 is going to remain unbreakable. AES-128 is potentially vulnerable but also highly unlikely to be actually broken any time soon. RSA is a whole other story and completely unrelated to AES.

https://csrc.nist.gov/Projects/post-quantum-cryptography/faqs#question_LVQL

If the path to post-quantum encryption is doable, it is about time to pursue it.

[!IMPORTANT]

The Importance of Upgrading to Post-Quantum Encryption for Password Managers

As we move further into the era of quantum computing, the security landscape is evolving rapidly. Traditional encryption methods, such as AES-256, while currently robust, may not withstand the capabilities of future quantum computers. Here’s why upgrading to post-quantum encryption for password manager databases is not just beneficial but essential.

1. Quantum Threats to Current Encryption Standards

Quantum computers have the potential to break widely used encryption algorithms, including those that secure password managers. For instance, Shor's algorithm can efficiently factor large numbers, which threatens RSA encryption, while Grover's algorithm could significantly reduce the effective security of symmetric key algorithms like AES-256. This means that what is considered secure today may become vulnerable tomorrow.

2. Future-Proofing Security

By adopting post-quantum cryptography, you are not only addressing current vulnerabilities but also future-proofing your security measures. Post-quantum algorithms are designed to be secure against the capabilities of quantum computers, ensuring that your sensitive data remains protected even as technology advances. This proactive approach is crucial for maintaining trust in digital security systems.

3. Enhanced Security for Sensitive Data

Password managers store sensitive information, including passwords, personal identification numbers, and financial data. The implications of a data breach can be catastrophic, leading to identity theft and financial loss. Post-quantum encryption provides a stronger defense against potential breaches, making it significantly harder for attackers to decrypt stored data, even with advanced quantum computing capabilities.

4. Encouraging Innovation in Password Management

The current landscape of password managers often relies on outdated encryption methods that may not be sufficient for future threats. By advocating for post-quantum encryption, we can drive innovation in the development of password management solutions. This shift can lead to more secure, user-friendly applications that leverage the latest advancements in cryptography.

5. Building Confidence in Digital Security

As users become more aware of the potential risks associated with quantum computing, there is a growing demand for solutions that offer enhanced security. Implementing post-quantum encryption in password managers can help build confidence among users, reassuring them that their data is protected against emerging threats. This trust is essential for the continued adoption of digital security tools.

[!NOTE] In summary, upgrading to post-quantum encryption for password manager databases is not just a technical enhancement; it is a necessary evolution in response to the changing landscape of cybersecurity. By embracing these advanced cryptographic methods, we can ensure that our sensitive information remains secure in the face of future technological advancements. This is a critical step towards improving the overall security of password management solutions and protecting users in an increasingly digital world.

Chinese Journal of Computers Vol. 47 No. 5 May 2024

A recent Chinese publish research paper:

Source: http://cjc.ict.ac.cn/online/onlinepaper/wc-202458160402.pdf

The research focuses on quantum annealing algorithms for attacking RSA public key cryptography, specifically utilizing the D-Wave quantum computer. The study highlights two main approaches to factor large integers, which is crucial for breaking RSA encryption:

Transformation of Attack Methods: The first approach involves converting traditional mathematical methods for cryptographic attacks into combinatorial optimization problems. This is achieved using the Ising model or QUBO model. The researchers developed a high-position optimization model for multiplication tables and established a new dimensionality reduction formula. This method allowed them to factor the integer 2269753, achieving results that significantly surpassed those from institutions like Purdue University, Lockheed Martin, and Fujitsu. Notably, the coefficients in the Ising model were reduced by 84%, which greatly improved the success rate of factorization.
Integration of Quantum Annealing: The second approach integrates quantum annealing with cryptographic attack methods to optimize components of the cryptographic system. By optimizing the Closest Vector Problem (CVP) using quantum annealing, the researchers were able to find vectors closer than those produced by the Babai algorithm, enhancing the efficiency of searching for smooth pairs in the CVP problem. This led to the first successful factorization of a 50-bit RSA integer using the D-Wave Advantage.

[note] The findings suggest that, despite the slow progress in general quantum computing, the D-Wave system demonstrates "superior practical attack capabilities".

Additionally, quantum annealing avoids the barren plateau problem that affects other quantum algorithms, allowing for better scalability in large-scale attacks.

This research indicates a significant advancement in the application of quantum computing to cryptography, particularly in the context of RSA encryption, which relies on the difficulty of integer factorization for its security.

I think there is this underlying assumption that post quantum algorithms are actually quantum resistant. There is also an assumption that Shor's and Grover's algorithms are actually implementatable in quantum computing. Note that Grover's algorithm suffers from serialized execution which is why AES-256 is fundamentally safe. Please don't spread further FUD on the subject.

@droidmonkey - Jonathan White notifications@github.com

[note] I understand that you feel I’m spreading FUD, and I appreciate your perspective. However, the information I shared is based on current research and expert consensus regarding the implications of quantum computing on encryption. I’d be interested to hear your thoughts on why you think these facts are not valid. What "evidence" do you have that contradicts this information?

It’s crucial for us to discuss these topics openly, especially as they have significant implications for security and technology. Given the rapid advancements in technology, it’s vital that we stay informed and prepared for any challenges that may arise, rather than dismissing them outright, right?

The Urgent Need to Upgrade Encryption in the Age of Quantum Computing

As we stand on the brink of a technological revolution, the implications of quantum computing for encryption cannot be overstated. Governments and organizations worldwide are investing vast sums of money into artificial intelligence and quantum research, with the potential goal of breaking existing encryption standards. This raises a critical question: Is our current reliance on encryption methods like AES (Advanced Encryption Standard) truly secure, or have we already been compromised?

1. The Reality of Quantum Algorithms

The notion that Grover's algorithm is limited in its ability to break AES is dangerously misleading. Grover's algorithm can effectively reduce the security level of symmetric key algorithms like AES by half. For instance, AES-256, which is currently deemed secure, would only offer the equivalent protection of a 128-bit key against a quantum adversary. This is a significant vulnerability that cannot be ignored, especially as quantum computing technology continues to advance.

2. The Implementation of Quantum Algorithms

While there are challenges in building large-scale quantum computers, the theoretical foundations of quantum algorithms like Shor's and Grover's are robust. Shor's algorithm poses a direct threat to widely used public-key cryptography, such as RSA and ECC (Elliptic Curve Cryptography), while Grover's algorithm threatens symmetric key algorithms like AES. The reality is that as quantum technology matures, the risk of these algorithms being implemented effectively increases, potentially rendering our current encryption methods obsolete.

3. The Future of Cryptography

The rapid evolution of quantum computing necessitates a proactive approach to cryptography. We must transition to post-quantum cryptographic standards before it’s too late. The conversation surrounding quantum computing and encryption should not be about whether these risks exist, but rather how we can mitigate them. The urgency to upgrade our encryption methods is paramount, as the consequences of inaction could be catastrophic.

4. The Role of Quantum Cryptography in Securing Digital Transactions

The banking industry is already recognizing the limitations of traditional encryption methods like AES in the face of quantum threats. This sector is increasingly adopting quantum cryptography, particularly Quantum Key Distribution (QKD), to secure digital transactions. QKD allows for the creation of secure keys that are immune to eavesdropping, leveraging the principles of quantum mechanics to ensure that any interception attempts are detectable.

Moreover, the banking industry is actively supporting initiatives to standardize post-quantum cryptographic algorithms, acknowledging the need for systems that can withstand future quantum threats. As the financial landscape evolves, integrating quantum cryptography is not just a precaution; it is a necessity to safeguard against vulnerabilities that quantum computing presents.

5. The Hidden Threats

It is crucial to consider the possibility that AES has already been compromised, with governments and organizations potentially keeping this information secret for various reasons, including national security and economic stability. The reality is that the race to develop quantum computing capabilities is not just about advancement; it is also about power and control over information.

6. The Military's Shift to Quantum Computing

The military is also at the forefront of adopting quantum computing technologies, moving away from traditional encryption methods like AES. This shift is driven by the recognition that quantum computing can provide significant advantages in secure communications and data protection.

Military applications of quantum technology include quantum computing, quantum sensing, and quantum communication, all of which are poised to revolutionize defense strategies.

Recent reports indicate that quantum computing poses a "real and substantial threat" to classical cryptography, including military-grade encryption used in defense systems.

As nations race to develop quantum capabilities, the military's investment in quantum computing and AI is not merely about enhancing security; it is about maintaining strategic superiority in an increasingly complex global landscape.

The potential for quantum attacks to compromise existing encryption methods has led to a reevaluation of security protocols, emphasizing the need for advanced quantum-resistant solutions.

Conclusion

In summary, the trillions of dollars flowing through the global banking system and the increasing sophistication of quantum computing demand an urgent upgrade to our encryption standards. The risks posed by quantum algorithms are real and imminent, and the time to act is now.

We must not underestimate the potential of quantum computing to disrupt our current security frameworks. The question is not whether quantum computing is a threat, but rather how prepared we are to face it. The future of our digital security depends on our ability to adapt and evolve in the face of these unprecedented challenges.

One problem to consider before using post quantum crypto is the technical implementation. As post quantum algorithms are relatively new, it may be unsafe to use one that has not been reviewed and tested for a long time. A new vulnerability may be discovered in these algorithms in the next years. So it may be safer to wait for a better maturity of post quantum cryptography implementations.

Thank you for backing up my common sense @Tireur2cables

Posting, what appears to be GPT output, about quantum computing threats is not helpful and further muddies the situation. Posting anything about RSA is 100% irrelevant.

The Chinese paper recently published carries absolutely no way to reproduce their claims. They used D-Wave equipment, which is a company on the brink of bankruptcy, and their claims only apply to trivially small key size and algorithms with no way forward.

So yah, let's discuss, but if you do come with the truth, not the headline.

AFAICT there's no reason for any immediate concern regarding AES or Twofish's vulnerability to attack. Be it from a classical computer or quantum computer. This I believe is doubly true for KeepassXC which also uses Argon2 for key derivation. I'm entirely new here and only found this issue as I think it's less of a why should we and a why shouldn't we but I think it's worth attacking this FUD topic directly. I will respond to the spammed ChatGPT message in good faith:

1. "The Reality of Quantum Algorithms"

It is presumed here that the efficacy of Grover's and Shor's algorithm entirely subverts AES's efficacy. This is misleading, ironically. First, even if we presume the case that AES's efficacy is halved with these algorithms, that would still make them effectively impervious to a brute force attack. See this reddit post for an example of someone doing the math on how much time it takes. To surmise, "It would take 10^38 Tianhe-2 Supercomputers running for the entirety of the existence of everything to exhaust half of the keyspace of a AES-256 key." If we half that, it's still just too long. Algorithms like RSA and AES are not designed to be impervious; they're designed to be so difficult as to take forever. Halving the heat death of the universe in time taken is still a wildly long time.

2. "The Implementation of Quantum Algorithms"

The problem assumption here is that quantum computing will improve quickly enough to be a relevant threat to anything developed today. Quantum computers will only be relevant in at best 2-4 decades. This is assuming they follow a model similar to that of Moore's law. But that's not necessarily true, and the current development pace suggests an even longer time frame. If your proposed "threat" is nearly 50 years into the future, it's more likely any mitigation made today will be irrelevant by the time it is planned to be useful.

3. "The Future of Cryptography"

This is just irrelevant, frankly. KeepassXC is a password management app. Not a cryptography app. You want the latest and greatest in cryptography? Use the relevant libraries. Cryptography (bleeding edge or otherwise) is only relevant to a password manager insofar as it needs to be secure.

4. "The Role of Quantum Cryptography in Securing Digital Transactions"

Again, irrelevant. KeepassXC is a password manager.

5. "The Hidden Threats"

Again irrelevant. This could also apply to any theoretical quantum algorithm.

6. "The Military's Shift to Quantum Computing"

There is no reason to believe the military is going to speed up the development of quantum computing. Funding is not an issue. Also, again, KeepassXC is not a nuclear codes management app. The same level of security is unnecessary. I doubt anyone is keeping state secrets in their .kdbx file (please don't do this).

Anyways, I think this explains why I don't think "Post-quantum" encryption methods are needed.

keepassxreboot / keepassxc