Attack on CRYSTALS-Kyber

[Loganaden Velvindron]

Hi All,

I wonder if anybody went through this before ?

https://eprint.iacr.org/2022/1713.pdf

[Markku-Juhani O. Saarinen]

Hello,

Yes, it came up in an earlier thread: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/w4o-VCza_so/m/nY8IZ4MLAgAJ

There's another publication that also attacks the same function in the same Kyber implementation -- but in a different way: https://eprint.iacr.org/2023/294.pdf

(You may compare Fig 3. on p. 6 in Dubrova et al. to Fig. 3 on p. 25 in Guo et al. -- the flaw is the same.)

These are nice technical papers, both with independent merits, but one certainly shouldn't draw too many conclusions about Kyber itself based on one very leaky encoding gadget in the "mkm4" implementation.

This encoding gadget uses share bits sequentially, one at a time, so you basically get a direct "readout" of the share bits in a side-channel setting. https://github.com/masked-kyber-m4/mkm4/blob/55d5d43a0b69eaff45c10d1fcc9c60eb5966ee03/crypto_kem/kyber768/m4/masked-poly.c#L20

The encoding step can be arranged so that it uses more than 1 random "masking" bit in each word; both attacks are certainly much less effective against such an implementation. Note that this does not require a change the overall masking order and has neglible performance penalty.

Note that side-channel attacks in this setting are always "ultimately successful" even against the most hardened implementations -- one just needs to make the attacks sufficiently costly. The security industry generally uses "attack potential" scoring systems to measure the cost. For this particular implementation, the attack potential just isn't very high. These industry standards already account for things like machine learning template attacks. See Sect 5.5  https://www.sogis.eu/documents/cc/domains/sc/JIL-Application-of-Attack-Potential-to-Smartcards-v3.2.pdf

Cheers,

- markku