Show HN: filippo.io/mlkem768 – Post-Quantum Cryptography for the Go Ecosystem
words.filippo.io
words.filippo.io
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.
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.
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?
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.
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.
Again. I'd love to be enlightened
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.
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.
In any case, it does no harm to be ready for a PQ world.
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 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.
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.
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.
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.
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.
Explore Go: Cryptography (Go 1.22 edition):
Should have clicked all the way through links to the project docs--looks like they're keeping this in mind.
Power side channels, which require physical access, are indeed outside the threat model of Go.
As far timing attacks, what about Go makes it more susceptible to timing side channels than any other language?
For general here is a list: https://pq-crystals.org/kyber/software.shtml
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.
See also: https://github.com/bcgit/bc-java/issues/1578
(Disclosure: BC is my employer)
How hard would it be to support a fast Kyber 90's mode, without SHA-3? (I suppose you would have to break the abstraction for that one).
ρ, σ := G[:32], G[32:]
Somehow much better than seeing "rho", "sigma".How would you feel about adding acutes and cedilles to characters? It just adds complexity. Let's stick to the smallest common denominator.
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.
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.
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.
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
- [1] https://en.wikipedia.org/wiki/IDN_homograph_attack - [2] https://en.wikipedia.org/wiki/Punycode
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
Of the languages I've checked, Perl, Python, and JavaScript (in Chrome and Firefox) do not. PHP does.
> invalid character U+2081 '₁' in identifier
Though that's also not surprising given how poor overall Unicode support is
> invalid character U+2081 '₁' in identifier
But AutoHotkey does allow it
super² := 1, sub₂ := 2
I really like this tool.
If you're looking for something designed for secret storage/sharing, checkout rot: https://github.com/candiddev/rot
Also I think it's a bit sly to not mention that you're the creator of the alternative you suggest.
There is a lot of activity in the integration and plugin ecosystem, which I am very happy about. https://github.com/FiloSottile/awesome-age
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.
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.
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.)
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.
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.
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.
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.
Sorry my friend, but you are not discussing this in good faith.
Plausible deniability works, in the real world, today. There's nothing contrived about it.
Some stories featuring Alice and Bob would be great.
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.
The actual implementations are in that tree, too: https://cs.opensource.google/go/go/+/master:src/crypto/
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
The author in this case is the lead cryptographic maintainer for Go.
(I personally also wouldn't use OpenSSL as an example of good cryptographic code)
The author has actually talked explicitly about "Don't roll your own crypto":
https://securitycryptographywhatever.com/2021/07/31/the-grea...