cloudflare / boring

BoringSSL bindings for the Rust programming language.
354 stars 107 forks source link

PQ: fix timing sidechannels and add IPDWing #243

Closed bwesterb closed 2 months ago

bwesterb commented 2 months ago

Fix three potential timing sidechannels. These don't affect ephemeral usage of Kyber as in TLS, but it's good practice to get rid of them anyway.

Also adds IPDWing, a preliminary version of X-Wing using the initial public draft (IPD) of ML-KEM. Don't use it.

bwesterb commented 2 months ago

I've reviewed up to IPDWing and everything looks good. Again, I would strongly reocommend pulling in the test vectors from the draft.

I cross tested connections with the Go implementation, which tests against the test vectors.

What remains to check:

  1. It looks like this there is a new abosrb-then-squeeze API for SHAKE25.

It's re-introduced. Upstream always contained the functions, but didn't use it, so I pruned it for this patch.

  1. The side channel mitigations. Can you please provide a reference for this? I don't really know what I'm looking at. An in-line comment with a pointer would be most helpful.

For 2/3 division is replaced by Barrett reduction, which is the exact same fix as upstream (1, 2).

For the third, we use BoringSSL's internal value barrier to prevent the compiler from using the fact that an intermediate is {0,1}-valued. Upstream fixes that in a less robust way that presumes that one does not use LTO.

bwesterb commented 2 months ago

Thanks for the review!

I'm able to verify most of the changes, except those to polyvec_compress(), as there is no corresponding change in pq-crystals as far as I can tell. I'll just have to trust you that you got the magic constants right. (And one day I'll learn Kyber!)

The patch is here

Here is an explanation of the magic constants. That implementation chooses different ones, but the idea is the same.