variable-time Kyber ref software

2,335 views
Skip to first unread message

D. J. Bernstein

unread,
Dec 15, 2023, 8:16:02 AM12/15/23
to pqc-...@list.nist.gov
I've been recently carrying out code analysis for some of the KEM
implementations submitted to SUPERCOP. In the case of kyber*/ref, I
noticed various "/KYBER_Q" occurrences with variable inputs. In at least
one case, line 190 of crypto_kem/kyber768/ref/poly.c, this is clearly a
secret input. I'd expect measurable, possibly exploitable, timing
variations, very much as in the graph here:

https://www.imperialviolet.org/2013/02/04/luckythirteen.html

Sometimes C compilers will convert divisions to multiplications, but
this depends very much on compiler options. Within available tools to
scan for variable-time instructions, a few (e.g., saferewrite) know how
to check for divisions but most don't.

Side note: As far as I can tell, this sort of security issue is outside
the scope of NIST's draft (see, e.g., "Equivalent implementations" and
the comment "The pseudocode is agnostic regarding how an integer modulo
m is represented in actual implementations or how modular reduction is
computed"). However, occasionally the draft dives into implementation
issues for some unclear reason. I'd suggest deleting the sentence
"Floating-point computations should not be used":

* In context, floating-point computations are no harder to test than
integer computations.

* Maybe floating-point implementations will be variable-time, but the
same is (obviously) true of integer implementations. (Hard to tell
at this point whether the risk is higher or lower; I'd think that
people writing floating-point code are more likely to multiply by a
precomputed constant/q where people writing integer code would use
divisions, and maybe they'll use variable-time floating-point
rounding methods less often than variable-time integer reduction.)

* Having this line about floating-point computations undermines the
draft's consistency in staying away from implementation issues.
Hopefully readers won't think that floating-point is the only Kyber
implementation issue to worry about!

I realize this is past the deadline for comments on the draft, but this
is a very easy change.

---D. J. Bernstein
signature.asc

Peter Schwabe

unread,
Dec 15, 2023, 8:29:17 AM12/15/23
to pqc-...@list.nist.gov
"D. J. Bernstein" <d...@cr.yp.to> wrote:

Dear Dan, dear all,

> I've been recently carrying out code analysis for some of the KEM
> implementations submitted to SUPERCOP. In the case of kyber*/ref, I
> noticed various "/KYBER_Q" occurrences with variable inputs. In at least
> one case, line 190 of crypto_kem/kyber768/ref/poly.c, this is clearly a
> secret input. I'd expect measurable, possibly exploitable, timing
> variations, very much as in the graph here:
>
> https://www.imperialviolet.org/2013/02/04/luckythirteen.html
>
> Sometimes C compilers will convert divisions to multiplications, but
> this depends very much on compiler options. Within available tools to
> scan for variable-time instructions, a few (e.g., saferewrite) know how
> to check for divisions but most don't.

Thank you for pointing this out. This has been independently reported to
us by Goutam Tamvada, Franziskus Kiefer, and Karthikeyan Bhargavan and
has been fixed in the "main" and "standard" branches of
https://github.com/pq-crystals/kyber.
See commit
https://github.com/pq-crystals/kyber/commit/dda29cc63af721981ee2c831cf00822e69be3220

Of course, also this updated version doesn't guarantee that a very smart
compiler won't notice that this an be implemented through a DIV
instruction, but the updated version makes it much less likely.
Systematic guarantees cannot be obtained when compiling C code with a
mainstream optimizing compiler.

All the best,

Peter

> Side note: As far as I can tell, this sort of security issue is outside
> the scope of NIST's draft (see, e.g., "Equivalent implementations" and
> the comment "The pseudocode is agnostic regarding how an integer modulo
> m is represented in actual implementations or how modular reduction is
> computed"). However, occasionally the draft dives into implementation
> issues for some unclear reason. I'd suggest deleting the sentence
> "Floating-point computations should not be used":
>
> * In context, floating-point computations are no harder to test than
> integer computations.
>
> * Maybe floating-point implementations will be variable-time, but the
> same is (obviously) true of integer implementations. (Hard to tell
> at this point whether the risk is higher or lower; I'd think that
> people writing floating-point code are more likely to multiply by a
> precomputed constant/q where people writing integer code would use
> divisions, and maybe they'll use variable-time floating-point
> rounding methods less often than variable-time integer reduction.)
>
> * Having this line about floating-point computations undermines the
> draft's consistency in staying away from implementation issues.
> Hopefully readers won't think that floating-point is the only Kyber
> implementation issue to worry about!
>
> I realize this is past the deadline for comments on the draft, but this
> is a very easy change.

I agree that it would be good to add a note to the standard.

All the best,

Peter

D. J. Bernstein

unread,
Dec 15, 2023, 9:00:49 AM12/15/23
to pqc-...@list.nist.gov
Peter Schwabe writes:
> https://github.com/pq-crystals/kyber/commit/dda29cc63af721981ee2c831cf00822e69be3220

OK. I see that this was two weeks ago; is there a reason that there
hasn't been a vulnerability announcement?

---D. J. Bernstein
signature.asc

Peter Schwabe

unread,
Dec 15, 2023, 1:17:11 PM12/15/23
to pqc-...@list.nist.gov
"D. J. Bernstein" <d...@cr.yp.to> wrote:
> Peter Schwabe writes:

Dear Dan, dear all,

> > https://github.com/pq-crystals/kyber/commit/dda29cc63af721981ee2c831cf00822e69be3220
>
> OK. I see that this was two weeks ago; is there a reason that there
> hasn't been a vulnerability announcement?

Fair point, I could have sent a message to pqc-forum after I updated the
code.

I'm curious, did you check that the code executes in variable time on
any particular CPU for the input ranges that are fed into the DIV
instruction (if a compiler issues a DIV)?

All the best,

Peter

D. J. Bernstein

unread,
Dec 15, 2023, 2:46:46 PM12/15/23
to pqc-...@list.nist.gov
Peter Schwabe writes:
> I'm curious, did you check that the code executes in variable time on
> any particular CPU for the input ranges that are fed into the DIV
> instruction (if a compiler issues a DIV)?

The range is 1664 through 8320? I tried the script below on Zen 2 as a
random example and saw what looks like an extra cycle starting at 8192.
The only safe presumption is that this is exploitable in the same way as
CacheBleed.

---D. J. Bernstein


echo 'int div3329(int x) { return x / 3329; }' > div.c
echo '#include <stdio.h>' > divtest.c
echo '#include <stdlib.h>' >> divtest.c
echo '#include <cpucycles.h>' >> divtest.c
echo 'extern int div3329(int);' >> divtest.c
echo '#define TIMINGS 31' >> divtest.c
echo 'long long t[TIMINGS];' >> divtest.c
echo 'int main(int argc,char **argv)' >> divtest.c
echo '{' >> divtest.c
echo ' int d = atoi(argv[1]);' >> divtest.c
echo ' for (long long loop = 0;loop < TIMINGS;++loop) {' >> divtest.c
echo ' t[loop] = cpucycles();' >> divtest.c
echo ' for (long long i = 0;i < 1000;++i) div3329(d);' >> divtest.c
echo ' }' >> divtest.c
echo ' printf("%lld",d);' >> divtest.c
echo ' for (long long loop = 1;loop < TIMINGS;++loop)' >> divtest.c
echo ' printf(" %lld",t[loop]-t[loop-1]);' >> divtest.c
echo ' printf("\n");' >> divtest.c
echo ' return 0;' >> divtest.c
echo '}' >> divtest.c
gcc -Os -c div.c
gcc -Os -o divtest divtest.c div.o -lcpucycles
for d in `seq 1664 8320`
do
./divtest $d
done
signature.asc

D. J. Bernstein

unread,
Dec 15, 2023, 3:42:59 PM12/15/23
to pqc-...@list.nist.gov
I wrote:
> gcc -Os -c div.c
> gcc -Os -o divtest divtest.c div.o -lcpucycles

I should add that the Zen 2 machine I tried is running Debian 11, so gcc
(Debian 10.2.1-6) 10.2.1 20210110, but I also tried a few other versions
of gcc and they also produced div instructions.

Obviously the code in question has already been copied into more places,
as illustrated by the line

t = (((uint16(a[8*i+j]) << 1) + uint16(paramsQ/2)) / uint16(paramsQ)) & 1

in https://github.com/symbolicsoft/kyber-k2so/blob/master/poly.go. There
really should be a vulnerability announcement from the Kyber team and a
table tracking which downstream implementations have this code.

I've sent out a new version of SUPERCOP already, _maybe_ properly fixing
the Kyber code in SUPERCOP, but of course SUPERCOP doesn't vouch for
security of anything. (SUPERCOP benchmarks MD5! It benchmarks SIKE!)
Submitters to SUPERCOP are responsible for the security of their code.

---D. J. Bernstein
signature.asc

Filippo Valsorda

unread,
Dec 16, 2023, 6:06:23 AM12/16/23
to pqc-...@list.nist.gov
I think this is actually a good opportunity for the NIST spec to provide additional implementation guidance, as I mentioned in my formal comments. Compression and to a lesser extent decompression were in my experience the parts that were the least straightforward to implement.

While implementing the rest of FIPS 203 is an exercise in translating pseudocode to the careful subset of our relevant programming language, or applying modular arithmetic techniques we are very familiar with, implementing compression and decompression involved translating a very abstract description ("here's a fraction, there's a rounding rule in the introduction, produce an integer") to an unspecified and non-trivial algorithm.

It's not surprising this would lead to variable time implementations. Even when the code is correct, the proliferation of implementation strategies is detrimental to reviewability.

The spec is already very clear that an implementation can anyway choose to deviate as long as the output is the same, so providing extra guidance would be in my opinion a net benefit, helping most implementers without constraining those that wish to pick different strategies.

D. J. Bernstein

unread,
Dec 16, 2023, 10:47:11 AM12/16/23
to pqc-...@list.nist.gov
I wrote:
> Obviously the code in question has already been copied into more places,
> as illustrated by the line
> t = (((uint16(a[8*i+j]) << 1) + uint16(paramsQ/2)) / uint16(paramsQ)) & 1
> in https://github.com/symbolicsoft/kyber-k2so/blob/master/poly.go.

I've now looked at a few more of the third-party Kyber implementations
mentioned on the Kyber page, and all of them are variable-time (not just
the Python implementations---hopefully people are already aware that
Python integer arithmetic isn't constant-time). Look at, e.g.,

const uint16_t t = (((static_cast<uint16_t>(this->m_coeffs[8 * i + j]) << 1) + KyberConstants::Q / 2) / KyberConstants::Q);

in https://github.com/randombit/botan/blob/master/src/lib/pubkey/kyber/kyber_common/kyber.cpp
or

t = (((t << 1) + KYBER_Q as i16 / 2) / KYBER_Q as i16) & 1;

in https://github.com/Argyle-Software/kyber/blob/master/src/reference/poly.rs
or

t = (int) ((((((int) (a[8 * i + j])) << 1) + (KyberParams.paramsQ / 2)) / KyberParams.paramsQ) & 1);

in https://github.com/fisherstevenk/kyberJCE/blob/main/src/main/java/com/swiftcryptollc/crypto/provider/kyber/Poly.java.

The official AVX2 implementation looks ok at first glance but of course
isn't useful for ARM etc. I tried divisions on a typical RISC-V chip
(cfarm103: SiFive U74) and found that cycle counts increase at both 4096
and 8192.

---D. J. Bernstein

P.S. The "Proof-of-concept Python implementation using RSA accelerators"
is not an implementation of Kyber. That use of RSA accelerators is
incompatible with the Kyber design (whereas it would provide easy
speedups for SABER and even easier speedups for NTRU). Why is this in a
list of "third-party implementations of Kyber"?
signature.asc

Tony Arcieri

unread,
Dec 16, 2023, 11:06:59 AM12/16/23
to pqc-...@list.nist.gov
On Sat, Dec 16, 2023 at 8:47 AM D. J. Bernstein <d...@cr.yp.to> wrote:
   t = (((t << 1) + KYBER_Q as i16 / 2) / KYBER_Q as i16) & 1;

in https://github.com/Argyle-Software/kyber/blob/master/src/reference/poly.rs

Note there's an open issue for this: https://github.com/Argyle-Software/kyber/issues/108 

--
Tony Arcieri

D. J. Bernstein

unread,
Dec 16, 2023, 11:18:59 AM12/16/23
to pqc-...@list.nist.gov
Filippo Valsorda writes:
> providing extra guidance would be in my opinion a net benefit, helping
> most implementers without constraining those that wish to pick
> different strategies.

I agree, but procedurally there's too much chance of error from having
this inserted into the FIPS, especially at a late stage that isn't going
through more rounds of public review. A separate NIST SP on "How to not
botch your Kyber implementation" would have a new review process and
would be easier to update in case of problems. So I think it's good for
the FIPS to focus on the mathematical specification (and I'd eliminate
the floating-point comment).

---D. J. Bernstein
signature.asc

D. J. Bernstein

unread,
Dec 16, 2023, 12:44:47 PM12/16/23
to pqc-...@list.nist.gov
I wrote:
> The official AVX2 implementation looks ok at first glance but of course
> isn't useful for ARM etc.

Also, https://twitter.com/bwesterb/status/1734601576788980216 says "we
deployed a non AVX2 implementation of Kyber, because we're more worried
about implementation mistakes".

It's interesting to compare this to the timing variation at hand being
in the official reference implementation, and various implementations
based on that, but _not_ in the official AVX2 implementations.

The broader pattern here is that rewriting integer arithmetic as vector
operations for speed often gets rid of timing variability en passant. As
I wrote in https://cr.yp.to/papers/ram-20210423.pdf, there is a "synergy
between vectorization and constant-time programming".

To be clear, I'm not questioning the decision to avoid the AVX2 code.
Vector code is obviously harder to review than serial code and can have
hard-to-spot bugs; keygen+enc+dec with the kyber768 reference code costs
roughly 2^(-31) dollars of CPU time, and it's not plausible that this is
an important cost in context. (Upgrading to kyber1024 is affordable for
similar reasons, and I recommend doing that to reduce security risks.)

---D. J. Bernstein
signature.asc

Markku-Juhani O. Saarinen

unread,
Dec 16, 2023, 1:00:36 PM12/16/23
to pqc-forum, D. J. Bernstein, pqc-...@list.nist.gov
Hi Dan & Co,

I guess with "FIPS" before, you're referring to FIPS 203 (ipd), which specifies ML-KEM. I hope no one is too offended if I note that for 10+ years, NIST has "intended" that timing attacks are addressed under FIPS 140-3, "Security Requirements for Cryptographic Modules," at least at Levels 3 and above. However, this has of course already been done under CC AVA_VAN for some time; resistance to these attacks is a commercial requirement, at least for hardware "modules" but unfortunately not for software modules -- the most common platform. I can say that the implementations from some makers of commercial Kyber modules look nothing like the reference implementation, and I share some of the blame for not reporting some timing issues in the reference implementations more widely so that those issues don't end up being replicated.

Anyway, in the NIST / FIPS 140-3 world, sIde-channel resistance requirements don't go into the algorithm specs, so where do they go?
- Timing Attacks (TA) are under the "non-invasive attack" umbrella, together with power and electromagnetic attacks (DPA, SPA, DEMA, SEPA). NIST SP 800-140F ("CMVP Approved Non-Invasive Attack Mitigation Test Metrics") is supposed to point to the testing methods against timing attacks, but a version with appropriate references has not been ratified yet ( there was an IPD: https://csrc.nist.gov/pubs/sp/800/140/f/r1/ipd ).
- The actual non-invasive (including TA) testing should be carried out as specified in ISO 17825 (test methods), ISO 20085-1 (test tools), and ISO 20085-2 (test calibration and apparatus). Direct pointers to these standards already exist in the latest revisions of ISO standards that FIPS 140-3 is based on ( ISO 19790 and ISO 24759 ).
- The testing is largely based on TVLA-style statistical distinguishers. If applied correctly, the testing methodology can pick up since-cycle CSP leakage, such as the one caused by non-constant time division. However, we're far from having the "correct testing methodology" in the FIPS 140-3 Implementation Guidance (IG) documents. Somehow my impression that the FIPS 140-3 testing labs don't always have the creativility of CC AVA_VAN testing labs (as AVA_VAN is a more like "penetration testing"), so this stuff would need to be explicitly written down for them in the IG.
- As everyone involved knows, reviewing and revising those side-channel testing methods for FIPS 140-3 has taken a veeeery long time, but most of the pieces seem to be in place now. NIST could technically start requiring side-channel attack testing in the FIPS 140-3 framework soon (NIST: you don't need to require everything all at once -- how about starting from timing attacks?) I'd hope that if the testing methods are standardized and become some kind of requirement, the software-executable ones (like those on timing attacks) can then become a part of continuous integration flows even outside a small clique of SCA nerds, and the world will be basically a better place!

In Common Criteria (another commercial testing system), vulnerability analysis ( AVA_VAN.x ) testing for timing attacks has been in scope for a very long time, and the application of AVA_VAN methods to Kyber and other PQC algorithms is straightforward in the sense that AVA_VAN itself is largely algorithm-agnostic. AVA_VAN is really at the center of EUCC, so high-assurance implementations under that new European system should have a fairly good level of protection. I'd say that a Kyber implementation at AVA_VAN.3 or above wouldn't be able to have that kind of division timing attack leakage unless the testing lab really botched their work.

Cheers,
- markku

D. J. Bernstein

unread,
Dec 16, 2023, 2:20:19 PM12/16/23
to pqc-...@list.nist.gov
Markku-Juhani O. Saarinen writes:
> I guess with "FIPS" before, you're referring to FIPS 203 (ipd),

Yes: when I wrote "procedurally there's too much chance of error from
having this inserted into the FIPS, especially at a late stage that
isn't going through more rounds of public review", I was referring to
the forthcoming FIPS 203.

I also don't think that standards for _testing_ implementations make
sense as a place for providing guidance to implementors. For example,
for timing variations, a Kyber implementor needs specific advice such as
"here's how to do mod" and "here's how to do division" and "here's how
to deal with the nightmare you're facing on CPUs with variable-time
multipliers", whereas the right way to test is with general-purpose
code-analysis tools (e.g., saferewrite's warning-div and warning-mul).

---D. J. Bernstein
signature.asc

Markku-Juhani O. Saarinen

unread,
Dec 16, 2023, 3:14:09 PM12/16/23
to pqc-forum, D. J. Bernstein, pqc-...@list.nist.gov
Hi,

Yep, there can be all kinds of guidance documents. Informational guidance has its place in helping implementors "get it right," but I think it's also high time to make timing attack resistance a requirement (at least for those of us who need to care about compliance), and the only way to enforce that effectively seems to be via product testing. You mention some good ways of doing TA testing it during development. If a developer uses those, then one doesn't have to worry that much about other types of tests that might be required for a final product (assuming that the correct assumptions about the CPU/MCU are made.) It's a bit easier with TA than with other types of SCA in that sense.

FIPS 140-3 Implementation Guidance (IG) that I mentioned really just tells how to interpret some (of the more unclear) parts of the testing standards; it is for the implementation of FIPS 140-3 itself, not the cryptographic module under test. Unlike the FIPS 140-3 standards, its IG is a public document, updated relatively frequently. (Here's the latest version for the curious:  https://csrc.nist.gov/csrc/media/Projects/cryptographic-module-validation-program/documents/fips%20140-3/FIPS%20140-3%20IG.pdf  ) Perhaps something with the publication model could be made for "implementation best practices," too.

As you note, different CPUs may have different timing "features" -- I'd like to bang the drum a bit for RISC-V Zkt and Zvkt. Zkt is a couple of years old now, but Zvkt is for vector architectures and was only ratified a couple of months ago. However, it is expected to be adopted in mainstream application-CPU profiles and use cases like upcoming RISC-V Android devices. 

Basically, Zkt/Zvkt feature extensions mandate that specific instructions are "safe" and have data-independent execution latency ("DIEL"). For example, multiplication on a Zkt/Zvkt RISC-V system is DIEL, while it may not be on a RISC-V system without it. This allows the portability of secure implementations from one processor to another they support Zkt/Zvkt. Division instructions are actually never "safe" in Zkt/Zvkt, so the reference Kyber implementation division issue mentioned pops up in automated testing when tracing data flows of CSPs. As you imply, it may not be reported with some tools (like those based on valgrind); if they just catch cache-timing attacks). One needs to actually know which instructions are DIEL and which are not.

Cheers,
-markku

Markku-Juhani O. Saarinen

unread,
Dec 16, 2023, 3:25:30 PM12/16/23
to pqc-forum, Markku-Juhani O. Saarinen, D. J. Bernstein, pqc-...@list.nist.gov
Hi,

A slight correction before NIST gets angry at me! I wrote "Unlike the FIPS 140-3 standards, its IG is a public document" .. all of the FIPS 140-3 standards are technically public, but the ISO standards that they point to (such as those side-channel testing standards that are intended to be used with it) cost several hundred Swiss Francs to license. I feel guilty even showing the relevant side-channel standards to my students, which is a suboptimal state of affairs.

However, RISC-V is, of course, an open-source ISA, so the recently ratified Zvkt DIEL stuff can be found in Section 2.15, the 1.0.0 spec. PDF can be downloaded under https://github.com/riscv/riscv-crypto/releases

Cheers,
-markku

D. J. Bernstein

unread,
Dec 17, 2023, 2:57:16 PM12/17/23
to pqc-...@list.nist.gov
Another example of the same timing variation is

t = (((t << 1) + KYBER_Q / 2) / KYBER_Q) & 1;

in https://github.com/PQClean/PQClean/blob/master/crypto_kem/kyber768/clean/poly.c.

liboqs had the same timing variation, but, on the bright side, my
announcement led to a liboqs patch:

https://github.com/open-quantum-safe/liboqs/commit/0febc30848e23cbeb6977672cf9326a95cb6130b

However, I don't see a security announcement from liboqs telling liboqs
downstream users to patch. I do see a statement fairly far down in part
of the liboqs documentation saying "WE DO NOT CURRENTLY RECOMMEND
RELYING ON THIS LIBRARY IN A PRODUCTION ENVIRONMENT OR TO PROTECT ANY
SENSITIVE DATA" but I'm having trouble reconciling

https://openquantumsafe.org/applications/external.html

with that.

---D. J. Bernstein
signature.asc

Karthik Bhargavan

unread,
Dec 17, 2023, 3:58:21 PM12/17/23
to pqc-...@list.nist.gov
Hello Dan, others,

We've been writing a formally verified implementation of Kyber in Rust, and as part of this project, we found the division issue a couple of weeks ago in our own code, since it was blocking our proof of secret independence.
This then led us to looking at other implementations and finding the bug in the PQ-Crystals reference code.
We have been informing all the Kyber implementations we see using this pattern, including all the ones you mention in this thread.
It appears that many implementations copied and adapted the reference code, which is understandable, but several implementations (including the formally verified libjade code) rewrote it to not use division with secret inputs.

All my best,
Karthik




--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/20231217195431.2829125.qmail%40cr.yp.to.

D. J. Bernstein

unread,
Dec 17, 2023, 6:25:16 PM12/17/23
to pqc-...@list.nist.gov
Karthik Bhargavan writes:
> We've been writing a formally verified implementation of Kyber in Rust, and
> as part of this project, we found the division issue a couple of weeks ago
> in our own code, since it was blocking our proof of secret independence.

Looking forward to seeing the formalization. I noticed these divisions
a few days ago from a different direction, as part of finishing up a
paper analyzing the complexity of reference software for various KEMs:
https://cr.yp.to/papers.html#pqcomplexity

> We have been informing all the Kyber implementations we see using this
> pattern, including all the ones you mention in this thread.

Great! But keep in mind that most companies stay quiet by default about
the open-source software they're using, so public security announcements
are realistically the only hope of letting them know they should patch.

> It appears that many implementations copied and adapted the reference code,
> which is understandable, but several implementations (including the
> formally verified libjade code) rewrote it to not use division with secret
> inputs.

Hmmm. Is there documentation saying that this was to avoid divisions
with secret inputs? Surely it would then have occurred to someone to fix
the reference code too.

The two examples named so far are the official avx2 code, where the
multiplications are easily explained as saving cycles, and the libjade
code, where the multiplications are easily explained as using fewer
lines of code in that language (plus saving cycles for avx2).

Both of these are also using multiplications for the 4-bit and 10-bit
decompression (and, for avx2, the 5-bit and 11-bit decompression needed
for kyber1024; libjade doesn't have kyber1024). Those are applied to
public ciphertext components. One _could_ still try to fit this into the
avoid-secret-divisions explanation by pointing to applications that wrap
ciphertexts inside an outer layer of encryption and don't want the outer
layer broken by timing attacks against the inner layer---but surely such
applications would then also want to avoid the public-key leaks from
rej_uniform in both of these implementations.

---D. J. Bernstein
signature.asc

Blumenthal, Uri - 0553 - MITLL

unread,
Dec 17, 2023, 8:00:20 PM12/17/23
to pqc-...@list.nist.gov
>> We have been informing all the Kyber implementations we see using this
>> pattern, including all the ones you mention in this thread.
>
> Great! But keep in mind that most companies stay quiet by default about
> the open-source software they're using, so public security announcements
> are realistically the only hope of letting them know they should patch.

A company may not advertise the fact that they're using open-source software, but if they got it from somewhere, it's very likely that they keep track of its updates, patches, etc.

D. J. Bernstein

unread,
Dec 17, 2023, 8:52:52 PM12/17/23
to pqc-...@list.nist.gov
Blumenthal, Uri - 0553 - MITLL writes:
> A company may not advertise the fact that they're using open-source
> software, but if they got it from somewhere, it's very likely that
> they keep track of its updates, patches, etc.

How likely is "very likely", and what's your source for this claim?

https://www.synopsys.com/content/dam/synopsys/sig-assets/reports/rep-ossra-2023.pdf
says that, out of 1703 codebases scanned in 2022, 89% "contained open
source more than four years out-of-date".

---D. J. Bernstein
signature.asc

bruno

unread,
Dec 18, 2023, 12:49:34 AM12/18/23
to pqc-...@list.nist.gov
Hi Dan, Uri

You can have a look at this report also. Some large organizations may
scan corporate repo with similar tools.

https://snyk.io/reports/open-source-security/

It says 40% don't use tools that they are calling SCA (Software
Composition Analysis).  I think it outline also the issue.

Regards

Blumenthal, Uri - 0553 - MITLL

unread,
Dec 18, 2023, 10:59:03 AM12/18/23
to bruno, pqc-...@list.nist.gov
> You can have a look at this report also. Some large organizations may
> scan corporate repo with similar tools.
>
> https://snyk.io/reports/open-source-security/ <https://snyk.io/reports/open-source-security/>
>
> It says 40% don't use tools that they are calling SCA (Software
> Composition Analysis). I think it outline also the issue.

I don't think it does.

Keeping track of the open source packages you use, and running "industrial strength" scanners over your composite code are two somewhat orthogonal things. For example, I quietly track packages I use in my code. Whether somebody runs SCA on the composite - it outside of my visibility.

Plus, I'm certain that in many cases your code composition is simple enough to not require an SCA tool. ;-)

D. J. Bernstein

unread,
Dec 19, 2023, 7:39:53 AM12/19/23
to pqc-...@list.nist.gov
https://kyberslash.cr.yp.to/libraries.html now tabulates the reported
status of various Kyber libraries.

---D. J. Bernstein
signature.asc

Nadim Kobeissi

unread,
Dec 19, 2023, 7:47:40 AM12/19/23
to pqc-...@list.nist.gov
Hi everyone,

We've released a security announcement regarding this issue and how
we've addressed it in Kyber-K2SO, our Go implementation of Kyber:

https://symbolic.software/blog/2023-12-19-kyberk2sovariabletiming/

The security announcement also serves as a handy explainer of the entire
issue since it was first reported in the official Kyber C reference
implementation two weeks ago, so please feel free to share it with
anyone looking for a high-level explainer.

Thanks,
--
Nadim Kobeissi
Symbolic Software - https://symbolic.software

Filippo Valsorda

unread,
Dec 19, 2023, 11:36:20 AM12/19/23
to pqc-...@list.nist.gov
2023-12-19 13:38 GMT+01:00 D. J. Bernstein <d...@cr.yp.to>:
status of various Kyber libraries.

Not sure this needed a name, but for completeness sake I believe filippo.io/mlkem768 (Go) and boringssl/crypto/kyber (C) to be unaffected. They both use Barrett reduction for compression. (I have not reviewed the whole BoringSSL implementation, though.) Neither is a SIMD implementation.

Loganaden Velvindron

unread,
Dec 19, 2023, 1:09:40 PM12/19/23
to Filippo Valsorda, pqc-...@list.nist.gov

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

Loganaden Velvindron

unread,
Dec 26, 2023, 4:37:25 AM12/26/23
to Filippo Valsorda, pqc-forum
Signal appears to be ready to pull in the backport:
Reply all
Reply to author
Forward
0 new messages