Hello from Kudelski Security. This is super timely, because we recently had to discontinue one of the other only existing Go libraries for quantum-resistant cryptography in Go! Full story at https://research.kudelskisecurity.com/2024/02/01/the-kybersl...
To expand on this: Daniel J Bernstein (of Curve25519 etc fame) has alleged that NIST and/or NSA knows a secret weakness in Kyber and therefore pushed it instead of NTRU. While the allegations are vaguely plausible -- NSA employs some very clever people, and of course they would like to interfere -- the evidence DJB put forth hasn't convinced very many other cryptographers.
There was also an incident a few months back when someone with an NSA email address suggested significant last-minute changes to Kyber on the PQC forum mailing list. These changes had a security flaw, and they were rejected. NSA might still know a different weakness, of course.
Note also that DJB's allegations focus on Kyber-512 being too weak, and this post is about Kyber-768.
I don't think there's a single PQC cryptography researcher other than Bernstein himself (corrections welcome) that takes the claims he made seriously, and one of the basic mathematical arguments he made may have been refuted, two messages down in the mailing list thread, by Chris Peikert.
I appreciate the follow-up. I read the long DJB page but never saw any follow-up; to be fair I wasn't directly looking for any. In either case it's great to know the allegations don't apply to Kyber-768 and up (and great there's a Golang implementation now!).
I'm sure he's alleged something about the other variants. Like a few years ago he had this theory about "S-Unit attacks" on Kyber and NewHope, but it hasn't gone anywhere.
IMHO the lattice finalists -- Kyber, Saber and NTRU -- are all basically good, each having advantages over the others but no decisive advantages, and Kyber was the community favorite. So that whole rant about NIST picking Kyber for unconvincing reasons is like ... yeah, that's just what happens when all remaining choices are fine.
There is also the issue that cryptanalysis has advanced. There haven't been any fundamental breakthroughs yet, but there have been significant optimizations. If this trend continues, Kyber-512 might become certificationally weak (i.e. it might be considered weaker than AES-128), but unless there is a deeper breakthrough, it probably will not become feasible to break it in practice. This threat is why the Kyber team recommends Kyber-768 for mainstream use. The same threat applies to Saber and NTRU, with NTRU having (IIUC) the weakest security at a given dimension, but the most freedom in choosing how many dimensions to use.
So what is the actual state of Quantum computing in regards to the level that would make something like this necessary?
Is it become like AI where instead of actually coming into existence the definition is mostly just changing to bring forth a new product under a previously existing name?
Cryptography has a peculiar approach to the threat of quantum computers, because it is not acceptable for some of the data and connections encrypted today to become decryptable even thirty, fifty years in the future. That means that the question is not "are QC coming soon" but "might QC plausibly come into existence in the next half century". Since the answer, despite not having a precise consensus, is not "no", here we are.
This is also why you are seeing a lot more progress on PQ key exchanges, as opposed to signatures: signature verification today is not affected by QC fifty years from now, while encryption is.
There is also the problem of embedded devices. Some of these will still be operational in 20 years, at which point a "cryptographically relevant quantum computer" might exist. So we want to ensure today that these devices can support post-quantum algorithms, and depending on the device, this support might need side-channel and fault protection.
In some cases we can add support with a device firmware update, but things like secure boot flows and hardware accelerators can't always be updated in the field. And we need to make sure that the devices are fast enough, have big enough key storage, RAM and packet sizes, etc to support the new algorithms.
It's also important to have an established history of use and vetting so by the time PQ is needed, systems with a long history of security are available
The risk is that adversaries can store today’s payloads, and decrypt them in the future. So the sooner you switch to quantum-safe cryptography, the less of a “backlog” you leave vulnerable to future exploit.
If the answer was "the NSA is operating quantum cryptanalysis in production and ECDH should be considered completely broken", then anyone who knew this and told you would be in enormous trouble.
It seems unlikely that that's the case, but still, the question is sort of unanswerable. For now it's not known to be a threat, but how much paranoia you have over its potential is subjective.
One can be paranoid in a completely different direction, like “any quantum computer can’t survive long enough to perform any useful computation because objective collapse theories are right, the whole post-quantum cryptography exists to push implementations with backdoors injected by government”.
We're likely to see hybrid PQ + ECDH key exchange for the foreseeable future, running the pair of exchanged values through a hash-based key derivation function.
Partially due to fears of backdoors, but also out of caution because the mathematics of PQ cryptography has seen much less attention than DH / ECDH / RSA cryptography.
For a long time, there was similar conservative skepticism regarding ECDH.
The paranoid answer is to assume that certain organizations (e.g., nation state intelligence services, corporations that have enormous capital available, extremely wealthy people who can create organizations to pursue this) already have quantum cryptanalysis capabilities or very soon will.
In any case, it does no harm to be ready for a PQ world.
Within the last two-ish years, the NIST settled on some post quantum crypto algorithms and there's been some implementation of them more and more since. Quantum computing is still far off, but I think the mindset is "why not start now?"
I don't know for certain, but I'd assume things like elliptic curve were implemented a good bit before it garnered mainstream usage. I'd love for someone who was around that when it was happening to correct me if I'm wrong though.
You're correct. For a while, elliptic curves were avoided by most for 2 reasons (1) worry about interpretation of some of the now-expired patents and (2) there were some known "gotchas" for constructing curves, and there were some fears that there were still some "gotchas" to be found. (And, perhaps, the NSA knew some of the gotchas and were keeping them in their back pockets.)
Side note: arithmetic/range coding had similar slow adoption due to patents. Depending on your interpretation, IBM's range coding was prior art for the arithmetic coding patents, but nobody really wanted to test it in court. For instance, bzip2 is the original bzip with the arithmetic coding step replaced by a Huffman code. Nobody wanted a repeat of the debacle with GIF images being widely adopted before many realized the use of the patented LZW compression might be a problem.
For quantum computers to break RSA2048, the current quality of physical qubits needs to go up 10x and the quantity needs to go up 10000x. These are rough numbers.
The next major milestone to watch for is a logical qubit with fidelity 1000x better than the physical qubits making it up. That will signal the physical qubits are good enough that you could start only scaling quantity.
I'm just barely scratching the surface of quantum computing mostly out of curiosity after almost a decade of traditional software work. So I mostly have done things like qiskit tutorials, but other than reading about the theory I have yet to see a coherent explanation as to how the devices actually implement the theory.
The main argument it makes is based on counting amplitudes, and noting there are far too many to ever control:
> The hypothetical quantum computer is a system with an unimaginable number of
continuous degrees of freedom - the values of the 2^N quantum amplitudes with N ~ 10^3–10^5 . [...] Now, imagine a bike having 1000 (or 2^1000 !) joints that allow free rotations of their parts with respect to each other. Will anybody be capable of riding this machine? [...] Thus, the answer to the question in title is: As soon as the physicists and the engineers will learn to control this number of degrees of freedom, which means - NEVER.
The reason this is a joke is because it fundamentally misunderstands what is required for a quantum computation to succeed. Yes, if you needed fine control over every individual amplitude, you would be hosed. But you don't need that.
For example, consider a quantum state that appears while factoring a 2048 bit number. This state has 2^2048 amplitudes with sorta-kinda-uniform magnitudes. Suppose I let you pick a million billion trillion of those amplitudes, and give you complete control over them. You can apply any arbitrary operation you want to those amplitudes, as long it's allowed by the postulates of quantum mechanics. You can negate them, merge them, couple them to an external system, whatever. If you do your absolute worst... it will be completely irrelevant.
Errors in quantum mechanics are linear, so changing X% of the state can only perturb the output by X%. The million billion trillion amplitudes you picked will amount to at most 10^-580 % of the state, so you can reduce the success of the algorithm by at most 10^-580 %. You are damaging the state, but it's such an irrelevantly negligible damage that it doesn't matter. (In fact, it's very strange to even talk about affecting 1 amplitude, or a fraction of the amplitudes, because rotating any one qubit affects all the amplitudes.)
To consistently stop me from factoring, you'd need to change well more than 10% of the amplitudes by rotations of well more than 10 degrees. That's a completely expected amount of error to accumulate over a billion operations if I'm not using error correction. That's why I need error correction. But Dyakonov argues like you'd only need to change 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001% of the amplitudes to stop me from factoring. He's simply wrong.
And your rebuttal amounts to "if I let you mess with a trivial number of amplitudes then the error will be trivial". Well duh. Another way of phrasing what you said is that you need to control 90% of 2^2048 amplitudes. Which is Dyakanov's point, that nobody knows how to do this.
I maintain that Dyakonov's arguments are completely missing the mark. I predict this will be experimentally obvious, instead of just theoretically obvious from linearity, within 5 years (due to the realization of logical qubits with lifetimes thousands of times better than their parts).
Do you not think that AI has been doing quite a lot of "actually coming into existence" the past decade? Did we have computers 10 years ago that could beat the best humans at Go, generate photorealistic images or converse in natural language? Rather than the definition changing, the goalpost might be moving a little bit here.
I don't really, no. 10, 20 and even 30+ years ago you could see the path of existence for the current state of things like Image Generation, knowledge engines and language learning models. I don't personally envision anything that exists today as AI as I would have back then. IBM's Watson won on Jeopardy 13 years ago. I don't think of the goals posts having changed at all because all of those things have existed for a long time they have just gotten better, but they weren't AI then and they aren't AI now.
In my mind, and what I think most people thought of back before the current AI push is that AI has critical thinking skills to develop new information. I certainly think that the current wave of AI named tools are impressive but they aren't the leap that makes something AI to me, because you could easily see them coming for a very long time.
Did you really see 5 years ago that we will have talking computers now that understand when you speak to them? I certainly haven't. What GPT-4 is now has been squarely in sci-fi realm for many people.
Perhaps relevant to the discussions is this friendly book on crypto systems implementation in the latest version of Go by John Arundel. Inside the last section there is a passing mention on post quantum crypto. Perhaps if John can update the book later with this library once the NIST PQ is standardized.
Go is as susceptible to timing side channels as C, if not less. (The difference being that while there is one major Go compiler, which usually does not go overboard with optimizations, when writing C you have to do increasingly complex tricks to defend against the compiler realizing what you are trying to do and replacing it with a more efficient variable-time branch.) This implementation was written to avoid any secret dependent code path.
Power side channels, which require physical access, are indeed outside the threat model of Go.
Note that there may be incompatibilities (as noted in the article) until NIST has published the final revisions. Some specifications are on Round 3 kyber, others are on FIPS 203.
This one will interoperate with Bouncy Castle (both Java and C#) as we both use FIPS 203 draft, but it won't interoperate with OQS simultaneously (three-way interop) as that is still on the Round 3 submission.
Yeah, replacing the hash would take a fork. Note that this implementation spends only about 20% of CPU time in SHA-3, so the gain wouldn't be massive. That proportion would probably grow after optimizing the field implementation, but almost certainly not enough to make it worth using a non-standardized, less-tested mode.
Hah, touché my friend. It's just that every time I think about touching that page it scope creeps into making it autogenerated from the kernel sources via CI etc. etc. :)
Gotta disagree. It's neat, but I don't like to see it in the real world.
For a start, I don't know how to type these on a keyboard.
Secondly, most people wouldn't know what these symbols are called. Granted, those looking at the code probably have a greater chance of knowing. But it isn't friendly code in my opinion. I think clarity is key, and "rho" or "sigma" are pretty clear.
Also, add in that there's a constant "n" and a constant "η". Just begging for confusion.
In a more general sense I'd agree, but in this instance, the ML-KEM draft specification (FIPS 203) uses the exact same greek symbols.
This code will be read many more times than it is written, and anyone auditing its correctness will be comparing against the spec.
If the variables are spelt out, then you have to do the mental (or otherwise) translation before you can compare the two, adding overhead. For comparing the symbols visually, you don't even need to know their names.
> For comparing the symbols visually, you don't even need to know their names.
Well, no, this was the main issue with homograph attacks in domain names [1] that brought us to the use of punycode in browsers [2]
In particular for a cryptographic library, I wouldn't want to constantly have to watch out for sneaky malicious variables put in the right place (e.g. try to compare visually the Cyrillic а, с, е, о, р, х, у with the ascii a, c, e, o, p, x, y (no, they're not the same characters).
EDIT: I realize that many programming languages today allow the use of unicode variables and I like that it's a possibility, it's just not the best when you need to be paranoid about the code
Preventing/detecting homoglyph attacks is a feature of competent text editors, and not a feature of the source code itself. If the source spelt out the variable names using latin characters, it would be no more or less susceptible to being backdoored in this way.
> the ML-KEM draft specification (FIPS 203) uses the exact same greek symbols
I'm as proud of my heritage as the next Greek-American, but just because mathematicians use unintelligible symbols in their manuscripts doesn't mean we have do the same thing in code. Let's prioritize comprehensibility and give variables meaningful names, instead.
FIPS 203 is not a math paper, it's a specification, giving concrete algorithms that use aforementioned variable names. Maybe they should use more descriptive variable names in the spec (you could tell them about it - they accept and respond to feedback from the public), but in the meantime, I think it's more useful for an implementation to use the same variable names as the spec.
> For a start, I don't know how to type these on a keyboard.
You can learn how to do that, even find a way to type "sigma", but more importantly, it best benefits readers, not writers, so you don't need to learn to type it
> and "rho" or "sigma" are pretty clear.
no it's not, where would you get clarity from is all the clarifying literature for these notions use the actual math notation σ?
> "n" and a constant "η". Just begging for confusion
looks very distinct, one is obviously mathy, another isn't
I think you misinterpreted their comment. It's not that only people who use Unicode characters should be doing crypto math. It's that if you're doing crypto math, you certainly know what the symbols mean since they're used in the original specification, so reading the code shouldn't be a problem.
Yeah, so they don't actively handle them as greek letters and translate the variable name. Nevertheless, if you don't know what those mean, there is a great chance that you do not understand the whole thing enough, that way you shouldn't touch any crypto code.
following the old adage: "never roll your own crypto"
I am not saying you should use Unicode symbols in your code... What I am saying is that not knowing how to read greek alphabet, a corner stone of math and physics, does not bode well for someone working on cryptography algorithms, arguably one of the most practical uses of math.
I must say, I don't like it at all. As with all characters that aren't part of my keyboard, the extra steps to type these add so much friction. Also, I would probably misread ρ as p, giving me the weirdest compile errors.
How would you feel about adding acutes and cedilles to characters? It just adds complexity. Let's stick to the smallest common denominator.
the smallest common denominator for math is math symbols, full ascii notation instead of those is the extra complexity in reading comprehension, which, as the saying goes, is a more frequent occurence
Shame it doesn't have plausible deniability built in. That is you could encrypt at least two files and decrypt one of them based on which key you provide.
This seems to be a security flaw of most of these kind of tools. That is there is only one possible key, so someone with a hammer can make you disclose it. But if the number of keys is unknown, you can give up some keys and hope attacker will leave you alone, without revealing the actual protected file.
I don’t understand the threat model for plausible deniability in a file encryption tool: any adversary that would physically compel you to provide one key would also know that you’re potentially being dishonest about that key.
In other words: plausible deniability on decryption doesn’t satisfy the adversary; they’re just going to torture you until you hand over the real key.
(Maybe there are scenarios, like airport security, where the adversary probably won’t torture you but needs the appearance of decryption? But I don’t think the adversary in those scenarios is thinking about file encryption tools; they’re thinking about your phone’s PIN or biometric lock.)
> In other words: plausible deniability on decryption doesn’t satisfy the adversary;
If there is only one key that decrypts the file, then they will have validation whether you provided the right one.
For instance if you have encrypted your crypto wallet info. You would have to give up the real key that will decrypt the file.
With plausible deniability scenario, you could have encrypted two wallets, one that you afford to lose. You can give it up and it's possible the attacker will be satisfied and you can keep the wallet that you care about.
The attacker will also never know if there are more keys. Mind you, they can always shoot you either way, but with the plausible deniability you might have a chance to leave the wallet you care about to your dependents.
> With plausible deniability scenario, you could have encrypted two wallets, one that you afford to lose. You can give it up and it's possible the attacker will be satisfied and you can keep the wallet that you care about.
The observation here is that there's a _very_ narrow slice of adversaries that satisfy the following constraints:
1. Are willing to force you to hand over private key material;
2. Are ignorant to the underlying thing they're looking for;
3. Are ignorant to the fact that your choice of encryption scheme allows for plausible deniability.
This model assumes all 3, when in reality almost any adversary that satisfies (1) is not going to satisfy (2) or (3) -- they almost always have a sense of what they're looking for (i.e., they know the wallet isn't empty or they wouldn't waste their time on you) and, given that, they aren't going to be fooled by a scheme that explicitly supports plausible deniability.
We can always contrive exceptions, of course. But part of secure design and threat modeling is having a reasonable conception of your adversary.
You are moving the goal posts. I didn't say the second wallet is empty, but such that you can afford to lose.
For instance you could have one wallet with £10m on it an another with £1.5m. You could certainly convince adversary that they got bad intel and £1.5m is what you have. It's better to lose £1.5m than £11.5m.
There are other scenarios like journalist taking compromising photos. They could have two sets of photos - one with key photo missing and another with key photo in the set. When questioned by adversary they could claim they have missed and didn't take the photo and show the set as evidence.
Someone in abusive relationship planning on leaving the partner. They could have a folder with properties they are interested in without the property they are actually going to rent. When caught they could convince the partner that they were just looking, but have not committed to anything.
If you are not in these kind of situations, sure this additional layer may not be to your interest and frankly you wouldn't have to use it! But for many people lack of such feature is a deal breaker.
The "empty wallet" isn't an operative part of the argument. The argument is that all three properties need to hold; this is true even in the 11.5m example.
Each of the scenarios above fails test (3). The most compelling of them is the abusive relationship one, since we can reasonably imagine a non-sophisticated adversary in that setting. But even then, you're relying on conflicting terms: what kind of abusive partner is sufficiently irrational to be abusive but also sufficiently rational to believe a cryptographic proof? Or, put another way: overwhelming evidence has not historically been a strong defense against abuse.
You seem to understand it with your own example of airport security types of situations. There are also other similar law enforcement actions where the people wouldn't have enough info to have a high enough degree of certainty that you possess something to be able to get suspect enough to cause additional harm on not finding it when the keys are disclosed
I want to like this tool, but it lacks a manual or a tutorial that describes typical usage. I don't mean how to use the command line. That is well-documented. But I want to know how I should manage and distribute my keys and what I need to look out for. The entire social layer on top of the technology is unclear to me.
Some stories featuring Alice and Bob would be great.
I have a wishlist for v2 changes, and I am considering slowly and carefully making such a release this year, but the difference in security between scrypt and Argon2 doesn't really justify making a change there.
I wouldn't describe age as having stagnated, it's simply stable. It has a well defined spec which it fully implements (seemingly correctly), so there isn't any need for more recent releases.
Also I think it's a bit sly to not mention that you're the creator of the alternative you suggest.
Taking this rare opportunity to put OpenSSL on blast a little bit - I have experienced no other software library or vendor where seemingly benign patch updates have completely broken functionality at the system level (in the web world). Semver people! Use it properly (and be consistent with the rest of the ecosystem you operate in)!!
Golang doesn't typically use OpenSSL: there is a BoringCrypto mode which can be enabled, but it's unsupported outside Google [1]. Instead, they have a policy of implementing well-known cryptographic algorithms themselves, in Go.
The author in this case is the lead cryptographic maintainer for Go.
Possibly worth noting for folks that BoringCrypto is necessary if you're having to deal with FIPS certification (which hopefully you don't). There's the usual FFI penalty to using it, so Go-native code is preferred for most use cases.
Golang has its own native crypto implementations where possible. Having used openssl extensively and having read some of its source code[1], I would personally like good alternatives. The developer (Filippo Valsorda) is a cryptographer and Go maintainer (incl. of some well known Go crypto packages in its std lib).
In this particular instance he seems to have implemented this (ML-KEM-768) as an exercise (incl. educational), but still, just some context!
[1] openssl is a gift that keeps on giving (CVEs). Just look at all those nice (incl. recent) issues, incl. RCEs iirc. Also, very anecdotal, but I find it funny that they haven't updated this page for the last I don't know 15 years? https://wiki.openssl.org/index.php/Code_Quality
Beyond what the other replies have already pointed out, the most sensible way to deploy PQ crypto today is to use it as part of a hybrid scheme. This way, even if the PQ crypto is broken (either fundamentally, or due to implementation bugs), the scheme as a whole will still be secure under a pre-quantum threat model - so not worse than what you started with, assuming you were using pre-quantum crypto to begin with.
Because he's a security engineer/cryptographer. He's the maintainer of the crypto package in the Go standard library. https://words.filippo.io/hi/. It's literally his job to write the crypto code everyone else uses.
I always took that to mean, "don't come up with your own cryptographic schemes", not "don't implement well-specified and standardized algorithms which are accompanied by a reference implementation and test vectors".
Go can link to C but the process is a bit horrible. I wonder if Go's memory safety in comparison to C and the security implications reverses this a bit.
None of that is an actual implementation of the cryptography, that's just the interfaces. The actual implementations are elsewhere and use architecture specific assembly for anything that needs constant time properties.
No, we use assembly for access to specialized (e.g. AES-NI) or vector instructions, and we do so reluctantly. We much prefer writing cross-platform constant time Go. https://go.dev/wiki/AssemblyPolicy
