Update for pqcrypto-kyber crate to avoid potential DIV side-channel

[thomwiggers]

I have backported the patch pq-crystals/kyber@dda29cc onto the 0.7 "finalist Kyber" crate release series of pqcrypto-kyber. This will allow Signal to receive this patch without migrating to ML-KEM.

Two notes:

• I've not tested this patch as thoroughly as I usually do (by virtue of pulling the code from PQClean, which extensively tests everything). NIST KATs seem to work, but please run your own interop tests.
• ML-KEM will probably be a tiny bit longer before it will get patched, because I need to see about properly updating them through PQClean.

I would have created a PR, but running Cargo update touches slightly more version updates than I'm comfortable with.

[jrose-signal]

Thank you for this backport! We really appreciate you doing that specifically for us.

I'm trying to verify that it's actually a backport to "finalist Kyber", though, and it doesn't seem to be: the diff in the submodule is only to the poly_tomsg functions, when it ought to include all the other changes (significant or not) that happened between "finalist Kyber" and "proposed ML-KEM". How did you create this release?

[thomwiggers]

I switched the branch on the pqcrypto repo to a new one for this backport. Next, I rolled back the pqcrypto-kyber submodule to the PQClean commit just before Matthias' PR PQClean/PQClean#504 landed. Then I just added in the division patch to poly_tomsg and pushed that to yet another branch, this time on PQClean.

Note that PQClean's meta.yml files track the upstream commit from which the source originates, so you can use that to work out which changes had been added to the pq-crystals/kyber repository since the merge into PQClean. I don't think there's much significant that happened.

[thomwiggers]

For reference:

• https://github.com/rustpq/pqcrypto/tree/kyber-fix-backport-0.7-branch/pqcrypto-kyber
• https://github.com/PQClean/PQClean/tree/kyber-ct-backport

[jrose-signal]

So I don't think the division patch actually went in on top of the rollback. In https://github.com/PQClean/PQClean/commits/kyber-ct-backport/, Matthias' PR is still listed in the history, two commits back.

[thomwiggers]

Hmm, so it does. I will look at this as soon as I get near a computer.

[thomwiggers]

I have yanked 0.7.7 and published 0.7.8

[loganaden]

Will there be some kind of announcement to signal users about the impending security update @jrose-signal ?

[thomwiggers]

It's unclear if the compiled and shipped code is vulnerable (though inspection of the assembly can be done to determine this), and secondly the side channel itself is not immediately obviously exploitable to the best of my knowledge. I mostly see this as a hardening patch; especially as any attacker would still need to be able to break the X25519 components as well.

[thomwiggers]

I have backported the second patch to Kyber pq-crystals/kyber@272125f#diff-4ffc94d35aed90b45df3a140b8d1ddd0f6da1fd45b005d26c02792e7803b0772 and released version 0.7.9

I've removed the NEON implementations from the crate, as they were failing to work correctly when I tested them. I don't think Signal were using them anyway (default-features = false excluded neon)

[jrose-signal]

Would you mind pushing the commit that got published as 0.7.9 (088bf56b2da2b1c58f29705ddab56d8e8b1a3c19)? Easier to compare releases on GitHub than manually downloading from crates.io.

[thomwiggers]

Whoops, thanks for the reminder, of course I intended to push that.

[brjsp]

I have backported the second patch to Kyber pq-crystals/kyber@272125f#diff-4ffc94d35aed90b45df3a140b8d1ddd0f6da1fd45b005d26c02792e7803b0772 and released version 0.7.9

I've removed the NEON implementations from the crate, as they were failing to work correctly when I tested them. I don't think Signal were using them anyway (default-features = false excluded neon)

Is disabling the SIMD implementations intentional? I have been patching this in a downstream distribution due to broken AVX detection breaking build, but since this is a security library i'm not sure if this is correct.

[Also i'm noticing libsignal 0.6.0 includes two copies of pqclean — this may cause mislinks due to symbol collision but haven't tried building it yet]

[thomwiggers]

The ARM NEON implementations shipped in the version of PQClean included by the 0.7 branch (and probably prior versions as well) were just plain computing wrong values. I think we didn't have any Arm64 + NEON machines set up to test them when they were included and CI relies on QEMU which also doesn't support SIMD (at least not with how we set it up, it seems). So yeah, that was intentional

[brjsp]

Is this code actually used anywhere in signal-desktop? I know we have at least one ARM64 user and have not received any complaints about Signal not working it so at this point i'm going to assume all of pqcrypto-kyber is dead code…