search

signalapp / libsignal

Home to the Signal Protocol as well as other cryptographic primitives which make Signal possible.
GNU Affero General Public License v3.0
3.51k stars 409 forks source link

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

Closed thomwiggers closed 9 months ago

thomwiggers commented 9 months ago

I have backported the patch https://github.com/pq-crystals/kyber/commit/dda29cc63af721981ee2c831cf00822e69be3220 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 would have created a PR, but running Cargo update touches slightly more version updates than I'm comfortable with.

jrose-signal commented 9 months ago

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 commented 9 months ago

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 https://github.com/PQClean/PQClean/pull/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 commented 9 months ago

For reference:

jrose-signal commented 9 months ago

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 commented 9 months ago

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

thomwiggers commented 9 months ago

I have yanked 0.7.7 and published 0.7.8

loganaden commented 9 months ago

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

thomwiggers commented 9 months ago

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 commented 9 months ago

I have backported the second patch to Kyber https://github.com/pq-crystals/kyber/commit/272125f6acc8e8b6850fd68ceb901a660ff48196#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 commented 9 months ago

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 commented 9 months ago

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

brjsp commented 9 months ago

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 commented 9 months ago

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 commented 9 months ago

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…

thomwiggers commented 9 months ago

The rust crate is imported by libsignal/protocol with settings that disable SIMD and only use the portable implementation.

brjsp commented 9 months ago

[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]

currently this does not cause problems as pqcrypto-kyber 0.8.0 is not linked when building for electron

jrose-signal commented 9 months ago

We don't actually use pqcrypto-kyber 0.8.0 in shipping apps, yeah. We wanted to test if we could have both versions side-by-side, but as you say it results in symbol collisions, which silently used the same implementation for both sets of Rust calls! We left in the code to have two implementations but it absolutely does not work yet.

jrose-signal commented 9 months ago

Released libsignal v0.38.0, which depends on pqcrypto-kyber v0.7.9. Thank you again for doing the rustpq side for us!