0

Suppose today I'm designing a new application that will employ asymmetric cryptography to allow users to securely exchange data with one another. As far as I can tell there are no quantum-safe algorithms yet generally accepted, let alone that are ready to be used in production. (Please correct me if I'm wrong!) Thus I'm assuming I'm still looking at RSA as the gold standard. Estimates for when RSA can be cracked vary from 5 to 15 years or more. 15 years doesn't bother me too much, but 5 years does, especially for a new application.

So, if I'm starting from scratch, what would be considered the best practices to be as prepared as possible for a post-quantum world? And to explain what I mean by prepared, I don't simply mean ready to change algorithms, but rather to best ensure that data transmitted today won't be vulnerable in the future.

Two things I've considered -

  • Using 4096-bit keys. However I don't see a consensus on whether this actually makes much of a difference even for classical attacks, let alone quantum ones.
  • Keeping public keys effectively private. My idea here is to keep even public keys within the confines of the secure application servers and unavailable to users. We would not allow clients to encrypt or verify sender signatures directly, but rather servers would hold public keys as closely as they hold their other secrets. Encrypting and verifying signatures would thus require client API calls.

I'm wondering if these ideas add any genuine security value, or if not why not, and if there are other measures that experts would recommend at this time to architect a new application to be as resilient as possible to the so-called quantum apocalypse.

2
  • 1
    Security is constant game of whack-a-mole. Every time you squash one issue, another pops out. The idea that you can somehow "solve" security at the start and not worry about it afterwards is fundamentally wrong. As others have pointed out, you should focus on how to keep your security up-to-date with new algorithms and threats.
    – Euphoric
    Apr 24, 2023 at 7:08
  • @Euphoric Of course. I hope I didn't give the impression that I think otherwise. Asking "what can we do to best be ready for something we know is coming" is not inconsistent with being constantly vigilent. Apr 24, 2023 at 16:22

2 Answers 2

2

Think about your threat model, then select appropriate algorithms. If you are concerned about long-term (5+ years) confidentiality versus nation state adversaries, then yes, conventional asymmetric crypto is not going to cut it.

Your idea of larger keys is generally sensible, but does not secure you against quantum computing.

Your idea of holding public keys private misses the point of asymmetric cryptography. If you can use such a design, then you can probably do without asymmetric crypto entirely.

Before moving on to post-quantum cryptography, it makes sense to first use the current state of the art. For asymmetric crypto, this means elliptic curve cryptography. This is not more secure than RSA, but uses significantly smaller keys and can be significantly faster. Different curves such as Curve25519 or Curve448 have different key sizes, different security levels, and support different use cases (e.g. Diffie-Hellman key negotiation, signatures, or key encapsulation).

For PQC, various algorithms such as the Dilithium/Kyber system already exist. That they have not found widespread use yet comes down to two factors:

  • they are relatively young, with standardisation still ongoing. Young algorithms are more likely to have as-yet undiscovered flaws.
  • they are computationally unattractive, for example requiring larger key sizes or requiring larger messages to be exchanged over a network.

For the first reason, it might be unwise to bet on PQC alone. For the second reason, you wouldn't use PQC nowadays unless you were forced to by your threat model.

But if your threat model requires that you use PQC, algorithms are already available. You can use classical and PQC algorithms in tandem by nesting their operation. For example in a key agreement scheme over an untrusted network, you might first use conventional crypto (like a TLS connection), and then run a PQC scheme over that encrypted connection. Thus, an attacker would have to break both algorithms. But careful: incorrect application would invert this, requiring an attacker to only break any one of the multiple cryptography schemes.

14
  • Good point re: threat model. What most concerns me is the "harvest now, decrypt later" attack. Not sure if it's only nation-states to worry about there. Love the idea of wrapping classical asymmetric encryption with PQC, thank you. Re: keeping public keys private, there's still a use case for asymmetric - only the user could access the private key (protected with a pw or whatnot), while any system user could make an API call to encrypt or verify a signature. So there'd still be the benefit of asymmetric without needing to make the public key accessible outside the server. Apr 24, 2023 at 16:26
  • (con't) granted that would make more sense for encryption at rest than TLS. I suppose publicizing the public key for TLS is pretty unavoidable. One question though - you recommend looking at ECC. My understanding is that is even more susceptible to quantum than RSA, and as you say it's not more secure than RSA, so why would someone want to go that route at this point? Apr 24, 2023 at 16:30
  • 1
    @PeterMoore Cracking either would require a breakthrough in QC, but once that breakthrough is there it's mostly a matter of scaling up. ECC will fall first, but RSA won't be far behind. Until then, ECC is much more efficient and is therefore widely preferred, at least for transport encryption. Note that modern TLS uses two distinct sets of keys: ephemeral keys created via Diffie-Hellman for a (symmetrically encrypted) confidential channel, and long-lived public keys for authentication/certificates. Later cracking would have to attack the ephemeral keys for each connection, which doesn't scale.
    – amon
    Apr 25, 2023 at 5:52
  • 1
    @JimmyJames Stronger keys are obviously better. But for performance reasons, there's an interest in using the smallest key that meets security requirements. Longer keys also don't provide security against QC threats, they just provide a slightly larger buffer. If an adversary has overcome the technological challenges in order to be able to factor a 2048 bit key, it is likely that they can scale up to 4098 bit keys within a fairly short time. Note that Shor's algorithm is "polylogarithmic", scaling approximately in O((log n)²) which is sub-linear in the key length.
    – amon
    Apr 28, 2023 at 8:42
  • 1
    @amon oh I see, so certain asymmetric ECC algorithms (assuming they're not backdoored ;)) provide more entropy than standard RSA .Then that does make sense to consider using them now. Yeah I think my takeaway is to try to have as little dependence as possible on asymmetric keys, recycle often, make it easy to swap out algorithms, and consider stacking conventional algo's with PQC until the latter are fully tried and tested. Apr 28, 2023 at 13:55
5

The best you can do is to not look at quantum cryptography as something special. It doesn't really change much for a properly designed security. All it will do is make some algorithm obsolete, while likely introducing new ones to replace the obsolete stuff. This happened in the past and it will happen again in the future. Security isn't just about the strength of the algorithm. It is about mitigating risks. You can't fully mitigate everything, don't even try that, but you can do your best.

So, ask yourself these questions instead:

  1. How difficult is it to introduce a new cryptographic algorithm? How will you approach the situation in which 2 users on different versions of the app are trying to communicate to one another? Code wise, is your application modular enough to allow you to quickly introduce new security features without breaking everything? Is your coms protocol capable of downgrading its security components? Do you have security protocol negotiation capabilities built in?
  2. How do you approach data migration? if data is stored at rest, how do you plan to move data from encryption under a weaker algorithm to a stronger algorithm?
  3. Do you maintain a public registry of security breaches found in your application? You gain trust by doing so.
  4. How do you approach updates to cryptographic algorithms? Think SSL security breaches.
  5. How about the lifecycle of your keys? Do you regenerate those RSA key pairs every now and then?

The conclusion is, rephrase the problem differently: How would you currently approach a security breach in your app, be it caused by a first party (e.g. your code) or a third party (e.g. some lib implementing RSA)?

4
  • Interesting. So there's really nothing you'd do differently/additionally now knowing that quantum is coming that you wouldn't do otherwise? In my mind it at least warrants reevaluating how we treat "public" keys; conventional wisdom is that public keys can truly be publicized to the world, but is that really a good practice still? That said, certainly all of these are good recommendations. Your best point is probably on key recycling, as it not only limits the damage from any one compromised key but also is consistent with an architecture that lends itself to switching algorithms as well. Apr 23, 2023 at 22:28
  • Quantum computing isn't the only thing that can compromise your private keys. A compromised OS can do it too. You should be rotation keys every 2 years at least. Sooner depending on how exactly you use the keys. The idea is to design the application in such a way that you have choices and can act quickly in times of need. If the keys get compromised in some way, you need to mitigate the risk in some other way to make up for it (like quickly creating new keys and migrate existing data, having different keys for storing data etc). It really depends on your exact usecase and data.
    – Ccm
    Apr 24, 2023 at 0:58
  • Part 2. So yes, i wouldn't regard quantum computing in any special way. There's a lot of uncertainty as of right now. It may blow out RSA out of usage. That is fine and not much you can do about it. But you can make sure you move quickly when this is happening and limit the damage.
    – Ccm
    Apr 24, 2023 at 1:09
  • Yeah certainly, all true. The whole thing feels very reminiscent of Y2K. Having worked some on that (showing my age :)) it was always frustrating how people knew for decades it was coming but many kept kicking the can. It seems like history's repeating a bit; I'm surprised there's not a more aggressive effort to make PQC industry standard while so much data is traversing around right now that could potentially be decrypted in 10 years. Alas. Apr 24, 2023 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.