Quantum-resistant crypto #975
Comments
|
Okay, so I'm a quantum information guy, and I can chime in: The main threat to security is that the discrete log problem is no longer hard for quantum computer, and computing the discrete log is only slightly more expensive than a modular exponentiation. So RSA and ECDH, along with most signature schemes, are no longer safe, in the absolute worst sense that the hardness assumption is completely broken and you can easily compute the private key from the public key. In general, fault tolerant quantum computers have an exponential speedup compared to classical computers for any instance of the hidden subgroup problem. For the time frame, assuming current trends for IBM (others may be slower or faster) and assuming that they can maintain their recent trend of scaling up in a Moores law exponential trend, their quantum computers should be assumed to be able to do this by the end of the decade, with a very boring "scale up and put it in a large building" approach to achieving that target. For specific protocols that may be used, I would suggest starting by taking a look at the post quantum cryptography wikipedia article. Most of them do something similar to Diffie-Hellman key exchange, but necessarily do so in a structure that is not an abelian group (for example, with matrix multiplication). NIST is currently running a competition between various candidates but hasn't picked a winner yet. Lattice based cryptography seems to have the most mature understanding of their hardness assumptions with regards to quantum algorithms. The variants that pick weaker hardness assumptions to compress key sizes are also very fast, and the protocols support a very wide variety of features. Typically they are based on the LWE problem, where you can reduce the problem for a random key, to the worst case complexity problem for a lattice problem (typically finding the shortest vector in a high dimensional lattice assuming that a short one exists), so that it has an average case safety guarentee rather than just a worst case complexity guarentee. In terms of having the most compact keys, protocols based on isogenies of elliptic curves (i.e. replacing exponentiation within a curve with a more general map between curves) seem to have the best performance but are much more complex to understand than classical ECC. I'm currently learning more about elliptic curves in order to properly grok SIDH. |
|
@saolof thanks for the in-depth explanation, do you know anything about any prominent IETF drafts or RFCs that would standardise PQ IANA-designated cipher suites and the likes? Specifically that could be a good yardstick for standardisation, imo. Furthermore, I'm tagging @uhoreg into this, to maybe shed light on how MegOLM/MLSv2 could take steps to prepare itself for PQ, or what mitigations should maybe happen here. |
|
I mentioned some of this in the #e2ee room, but to keep the discussion here: From a technical perspective, olm, megolm, and MLS could be easily adapted to use other encryption algorithms. We basically just need something to do signatures, and something that to do key agreement. (Aside from olm/megolm/MLS, we also need to worry about server signatures, 3PID invites, etc. but it's basically the same story there too.) However, switching things will involve a migration plan, because it will affect many things. e.g. we'll need to find a good implementation of the new algorithms for clients to use, people will need to generate new keys, etc. I think that we will likely wait until the NIST competition is done before trying to transition to any post-quantum algorithm, before trying to migrate to something post-quantum. |
|
OK, in that case, the general recommendation that I have for anyone getting into this right now is:
|
|
There appears to be news on this subject, NIST just released the list of the final quantum-resistant algorithms. Source: https://venturebeat.com/2022/07/05/nist-post-quantum-cryptography-standard/ |
|
Are there any updates to this? Considering the stance of certain US officials to safe data now and decrypt with quantum later, i would rather convert my database as soon as possible. |
|
These links could be useful https://openquantumsafe.org/applications/tls.html and https://github.com/open-quantum-safe/openssl |
|
Signal has now post quantum e2ee https://signal.org/docs/specifications/pqxdh/#post-quantum-key-encapsulation-keys |
|
Our focus has been on bringing MLS to Matrix, so we haven't looked much at post-quantum encryption for Olm/Megolm. There is an Internet Draft that defines a hybrid traditional/post-quantum encryption for MLS, similar to what Signal is doing and using the same algorithms (X25519 and CRYSTALS-Kyber), though I don't know if there are any MLS implementations that support that yet. So it is possible that after we get MLS in Matrix, and after there is an implementation for either that draft or some other post-quantum encryption, we will make that available in Matrix. As for Olm, it's likely that we could just define a version of Olm that uses Signal's PQXDH (Thank you to Signal for putting it in the public domain). I don't forsee it as being difficult, but it would take time and effort to define, implement, and test, so it's unlikely that we will get to it before we have MLS available. But anyone else who is interested is free to look into it. Note that this only covers encryption. Both Signal and the MLS post-quantum Internet Draft still use elliptic curves for signatures. We'd need to decide whether we want to switch to something else for signatures. |
I think this should be the first priority besides existing vulnerabilities as quantum computers are near and collect now decrypt later is most definitely happening, effectively rendering any non-qr encryption basically useless right now. |
|
For key exchange a hybrid scheme is the only rational option. And there are several sub options. Option 1: ECC DH + Kyber KEM Option 1 is in use by Signal. For signatures there is the option of a hybrid with ECC + Dilithium Note that a signature scheme can render distribution of static public keys for key exchange null and void: There are implementations for all these PQC algorithms in pure Rust: There had been some recent potential drama relating to Kyber that may mean that using the smallest Kyber key size is ill advised. https://blog.cr.yp.to/20231003-countcorrectly.html |
|
I don't trust KYBER, it seems that the NIST manipulated the competition results to make it win over NTRU in almost all cases and i am concerned about the US's motives to do so.
|
|
It may be worth noting that NTRU can be used to refer to a fairly large family, not just a single algorithm. NTRU prime as used by openssh is quite a bit newer than the original NTRU. But it is also designed to be very easy to audit and is a great option just based on that property and the fact that anything picked by openssh and its ssh-keygen is basically a widespread standard already. Imho, the most important step for now is to have any quantum resistance against store and decrypt. Specific algorithms may have vulnerabilities and this is difficult to predict, but having no quantum resistant encryption at all guarentees vulnerability when quantum computers arrive. Also, "boring" features like making it as straightforward as possible to generate a single-use key pair for a single communication and ensuring that those have enough random bits is a useful way to get security in practice. If you have an allegedly secure channel when bootstrapping, a communication clients should make it as easy and user-friendly as possible to make use of it in a way that isn't classically unsafe if the user messes up. Being able to share classical single-use elliptic curve public keys via QR code is one example for this, as it is safe in-person, while requiring the asymmetric crypto guardrail in case someone shares it via a video chat. |
The problem of Post-Quantum Safety ("PQS") is publicly known since like 2018 (published by iacr in 2017 and known about in the Computer Science since 90s) where most projects that are serious about privacy and security has implemented management e.g. OpenSSH, SimpleX, Signal and Lokinet. By 2019 it was reported to matrix (element-hq/element-web#8889) and by 2022 it was correctly triaged in matrix-spec where it seems to be treated as "nice to have thing" to this day instead of "shit hit the fan" that this problem seems to require and imho should have been proactively handled by 2019 max. This is just not enough, this problem basically defeats the encryption of all harvested data as soon as efficient enough Quantum Computer gets in the hands of a threat actor where based on my tests yesterday and gathering statistics from home server admins it's realistic to collect more than 8 GB of encrypted data in 12 hours where judging by matrix's popularity we can probably sanely assume that a global adversary is already doing this in a much larger scale and for much longer.. That to me is a privacy and security nightmare that each day after it's disclosure in 2018 expands exponentially on severity project-wise and impact on the users as the longer this goes the more sensitive data can be harvested from the users that we have no way of retroactively fixing as we would need a physical access to the threat actor's system to remove them. This is why this issue exists, beyond the threat to the common user matrix is projected to be used for critical infrastructure in the EU where many banks are already using it and NATO members such as the German Bundeswehr are already known to be using Conduit.rs for their mission-critical and sensitive information in their operation and that's why i believe that we should be focusing a lot more resources into managing this problem as soon as possible which is all that this issue is about. Originally posted by @Kreyren in #1868 (comment) |
Apologies for the drive-by comment, but I want to point out that is absolutely not a consensus opinion in the cryptography community. We're all standardizing on ML-KEM, and also the projects that use other things because they started earlier are probably going to migrate. |
|
Imho there was maybe a bit too much of a political drive during the NIST competition to only standardize one lattice based solution in each category even though some of the runnerups had advantages that made them complementary, and this would probably be the best way to summarize NIST "excluding" solutions. But the most important factor for post quantum encryption at this point is getting it as widely adopted as quickly as possible imho, and picking the NIST recommended option is one way to avoid bikeshedding. |
Who is "we" here ? Many projects share the same concerns about Kyber, so it is a bit disingenuous to suggest that "the cryptography community" is standardizing on Kyber. It is very much split, with some choosing Kyber, and some choosing NTRU (or variants thereof). |
I will also pitch in that I also don't think that this reflect the reality and seems like a concerning bad actor move to force kyber on first look, but i am still reviewing the provided information and brainstorming it atm and will reply later with the findings. Currently i couldn't find any reliable evidence that one of the NTRU authors is engaged in a FUD campaign as claimed on FiloSottile/age#578 (comment):
And i would say that it's bad faith to ignore this obvious issue as "[there is no threat actor with CRQC for another 10+ years for this to be a concern]" while i clearly stated and i believe that it's very obvious that the problem is realistic now as anyone can scrape the 23.3K! age encrypted files from github and get a good idea what they are storing (as lot of people name the files in a meaningful way as stated in FiloSottile/age#578 and integrate them in their infrastructure) to be more strategic about it for storage and decrypt them later. Additionally i think it would be a good idea to CC some from the cryptographic community who decided to use NTRU to share their opinion: Statement by SimpleX on Kyber vs NTRU: https://github.com/simplex-chat/simplex-chat/blob/4000fe383d6563509555d5d51a0b5f116e0fb363/docs/rfcs/2023-09-30-pq-double-ratchet.md?plain=1#L56 CC The SimpleX Founder @epoberezkin Next OXEN Foundation: CC @majestrate - The developer who implemented NTRU Prime in Lokinet CC @jagerman - One of the founders of OXEN Next Signal to have an opinion on Kyber: From commit signalapp/libsignal@ff09619 these developers worked on the initial implementation: -- Apologies for pings, but this to me seems as a major security problem for thousands of Matrix Users and your input would be very helpful in getting this problem managed |
|
I recommend reading Daniel’s Bernstein’s blog. I am not a cryptography expert, but I have a master’s degree in mathematics, so I am not looking at it from purely engineering point of view. DJB’s arguments and mathematics against Kyber are sound, and I don’t observe any violations of logic in any of his writings, which is extremely rare. To put the long story short: NIST removed hashing step of the random number that is used in key agreement. This decision makes security of the encryption dependent on security of the used random number generators. The latter can be compromised in variety of ways, and The criticism of this decision is shared by many cryptographers: https://csrc.nist.gov/files/pubs/fips/203/ipd/docs/fips-203-initial-public-comments-2023.pdf The whole NIST logic - “RNGs are secure so no need to hash” violates defence in depth principle - hashing compensates exactly the compromised RNG. Further, NIST recommendation to not use hybrid schemes is very strange - DJB also wrote a lot about it. As for security of RNGs, read this: https://www.computerweekly.com/news/366552520/New-revelations-from-the-Snowden-archive-surface https://www.theregister.com/2023/09/19/marvell_disputes_claim_that_cavium Streamlined NTRU Prime also looks better from many other point of views. So reasons to choose Kyber are only political, technically sound decision would be Streamlined NTRU-Prime |
|
So the statement that cryptographers are divided doesn’t seem correct - I don’t see any credible cryptographer who supports Kyber (ML-KEM). And I’d be very surprised if SSH migrated to it. We certainly have no such plans. |
|
I am muting this thread because a conversation based on opposing opinions of who are the credible experts is not productive, and because oceans of ink were spilled in the relevant forums about every issue mentioned here, and they can't be re-debated (by experts) in every downstream project. I stopped by to provide a professional opinion and insider perspective as a cryptography engineer, because I'm aware that what are decidedly fringe opinions in the experts community were successfully marketed outside of it. If anyone wants to read more, there are some links in this comment. https://news.ycombinator.com/item?id=37990225 |
|
Signal is a prominent supporter of Kyber (their impl of PQXDH uses it), which is why I say it's divided, otherwise I would discredit Kyber entirely (kind of like how I avoid P-256). Signal's Double Ratchet is the base of most current E2EE chat schemes (including the current Olm), which is why I give them weight. I am for sure leaning on the side of NTRU (to be exact, sntrup761x25519) as the only thing Kyber has going for it is that one prominent group has adopted them though. Another thing that might be worth considering is CTIDH, considering currently Olm utilizes a non-interactive key exchange. Unsure about its properties (outside of it being supposedly slower, which should be fine since Olm exchanges are not really performed that often and most is delegated to Megolm, the most frequent exchanges are usually in large E2EE rooms with users that have many devices), though. Linking the article about hybrid schemes : https://blog.cr.yp.to/20240102-hybrid.html if this is the one that was meant ?
This would not be the first time that a US agency decided to willfully weaken encryption with an exploit others could exploit. There was a great article about NSA's history with intentionally weakening encryption then being surprised when they got hit by another nation. All-in-all, the answer is not clean-cut. I will personally be avoiding Kyber not because of any existing proof that it is insecure, but rather because the alternatives seem to have a higher likelyhood of being secure, both because of major projects adopting them, and the fact that organizations that are well-known to have historically intentionally weakened encryption are backing Kyber. |
Establishing credibility and relevant expertise on the subject is often the first step into an academic discussion, Evgeny seemed to have provided a well written and on first look sensible counter-point to your claims about kyber including relevant references while your reply to it seems to be a bad faith trying to discredit it and link to your post on ycombinator where you disclose that you are quote "woefully unqualified to judge the intricacies of attack cost estimation myself" yet claim here that you are an expert on the subject representing the cryptographic community as a whole despite other community members disagreeing with you and seemingly contradict yourself to claim that you are qualified to judge whether "kyber is fine". To me this doesn't seem like a good faith behavior and makes me want to consider you as a not trustworthy person to migrate my whole infrastructure away from age in addition to the apparent ignorance of the Harvest Now, Decrypt later problem highlighted in FiloSottile/age#578 that you seemed to have shrugged off as non-issue while it clearly is a major problem affecting thousands of users on GitHub who use your cryptographic implementation. |
|
Folks, this is not the place to have a NTRU v. Kyber debate, and certainly not one with ad hominems. Please take it elsewhere. Matrix has cryptographic agility, and can support different schemes as needed. The approach we've taken right now is to implement Signal's PQXDH in Vodozemac: matrix-org/vodozemac#120. We hope to resume work on this in the coming months. Meanwhile, we're also trying to organise a framework to encourage others to implement different approaches on Matrix (e.g. McEliece KEM) - both to hedge our bets if needed, and to let folks prove out other implementations. More details on this in the coming weeks/months. Obviously this risks some fragmentation, but such is the cost of agility, especially when the state of the art is still in flux. |
|
Is there any work planned on improving the Double Ratchet, similar to what SimpleX has done https://github.com/simplex-chat/simplex-chat/blob/stable/docs/rfcs/2023-09-30-pq-double-ratchet.md or is the Key Agreement the only thing planned to be improved ? I suppose implementing PQXDH is okay, at least we will now be on some properly standardized Key Agreement, instead of only having source code and an old Signal blog post. An important question is whether the standardized, less-secure Kyber or the original more-secure Kyber are planned to be utilized, I suppose. I am presuming the choice to use Kyber was made because Signal already has an implementation and Kyber has many libraries implementing it, while NTRU derivatives are currently lacking, so it is less work to get something out there ? |
|
The plan from the Matrix core team is first to implement PQXDH as bit-identical-to-Signal (much as Olm is pretty much bit-identical to libsignalprotocol's DR), and so benefit from all the scrutiny that Signal gets, while also keeping the door open to interop in future. But the architecture is set up so that folks can propose and trial other approaches too. |
Considering the rationale in #975 (comment) and #1868 saying that the work on this will be resumed in "the coming months" seems like a bad parody to me. Please treat this problem with the urgency it needs. |
|
The crypto team do this as their day job, and so work on the stuff they're paid to work on. Right now they're funded to working on fixing key exchange bugs, which screw up crypto whether it's PQ or not: element-hq/element-meta#245. Then we have someone (hopefully) continuing to fund PQ in Sept. Meanwhile there was a major spurt of PQ at the end of last year. I'm afraid this is as high an urgency as we can do; if you want faster timelines then we would be very happy for someone to put $$$K behind the bar to make it happen sooner. |
His blog post is arguing in bad faith and vastly misrepresents the situation. See https://keymaterial.net/2023/11/18/kyber512s-security-level/ for my attempt at explaining the issue. Note also that there is no credible cryptographer who shares djb's concerns. As for the claims that the changes to the FO transform somehow weaken Kyber, it's fairly straightforward to prove that both variants have IND-CCA2. You can even prove that both versions have the same binding properties, as I've done in https://eprint.iacr.org/2024/523 for ML-KEM (with both attacks and proofs being exactly analogous for Kyber). As for the lack of the hash of shame, it is not true that a hash defends against a broken DRBG. It defends against specific backdoored DRBG, but the better defense here is to use a DRBG that isn't backdoored. |
This is simply an ad hominem attack. That institutions can be corrupt is not new, and has many other historic precedents. DJB, on another hand, has no vested interests here, and you have to remember that thanks to his litigation efforts we can do open-source cryptography at all - so it's good he didn't change.
Signal expertise lies in communication protocol and cryptographic schemes design, but Signal has no established expertise in cryptographic algorithms. While they call Double Ratchet "an algorithm", it really is a scheme combining other cryptographic primitives. So I would not consider Signal as part of cryptography experts community - they are the users of cryptography, same as we all are, not providers. Also Signal has a pattern of advertising component qualities as if they pertained to the whole system, which kind of reduces the weight of their opinions. Their decision to pick ML-KEM, in the same way as Apple's decision, is based on pure politics. It doesn't change the mathematical reality that final ML-KEM design accommodated an attack via a compromised RNGs.
This is not my analysis, I disagree.
That's exactly the point here - ML-KEM is vulnerable to attacks via backdoored RNGs, and this attack would be easy to mitigate with the hashing step that was present in the original Kyber submission - its cost is negligible. So not sure why you disagree, when you agree with that. The history of backdoored RNGs makes this decision even more worrying.
Not all systems have ability to choose. E.g., in iOS you don't have access to system entropy and have to use a surrogate provided by the system. Also, defence in depth principle is to have redundant defences - which in this case means what was done in the original Kyber design - use hashing in addition to choosing correct RNG. Both in this case, and also in their recommendation to not use hybrid constructions, NIST seems to disagree with "defence in depth" principle, which is also worrying. |
Can you make an estimate to how much finances you would need to implement this and place to where it can be donated for this purpose? |
Are those UTDs that are being worked on element-specific, or is it work that benefits the entire ecosystem ? What's the policy of Vodozemac on alternative crypto ? That is, will they only accept a single cipher or all standardized ones, or all ones with a spec ? What's the spec's team point of view, will the list of accepted ciphers grow along with various specs (eg sntrup761x25519 in addition to Kyber) ? I am asking because while the core protocol can support multiple ciphers, I am unsure whether doing so will remain spec-compliant. Is help with matrix-org/vodozemac#120 by third parties welcome ? That is, aiding in porting libsignal's PQXDH impl to Vodozemac. Is work on additional ciphers welcome at this time ? I would like to work on an alternative implementation that will not be utilizing Kyber. I know you've mentioned cryptographic agility, but I am unsure what are the exact standards for what ciphers will or will not get supported and by whom, thus my questions. |
|
Referencing EU's PQCRYPTO (part of Horizon 2020 project) paper on the subject with recommendations: https://pqcrypto.eu/docs/initial-recommendations.pdf |
per element-hq/element-web#8889
see also #934
see also #932
Wire has done this: https://wire.com/en/blog/post-quantum-resistance-wire/
Disclaimer: I have no idea what this entails.
The text was updated successfully, but these errors were encountered: