Side-Channel Attack against CRYSTALS-Kyber

CRYSTALS-Kyber is one of the public-key algorithms currently recommended by NIST as part of its post-quantum cryptography standardization process.

Researchers have just published a side-channel attack—using power consumption—against an implementation of the algorithm that was supposed to be resistant against that sort of attack.

The algorithm is not “broken” or “cracked”—despite headlines to the contrary—this is just a side-channel attack. What makes this work really interesting is that the researchers used a machine-learning model to train the system to exploit the side channel.

Posted on February 28, 2023 at 7:19 AM8 Comments


Clive Robinson February 28, 2023 11:08 AM

@ Bruce, ALL,

“The algorithm is not “broken” or “cracked”—despite headlines to the contrary—this is just a side-channel attack.”

The problem is not many understand the difference between,

1, Broken algorithm.
2, Broken implementation.

Or the implication of the latter.

As I’ve indicated in the past side channels appear in many ways, and they can leak many things.

What would be fair to say is that outside certain “Tripple Fence” organisations, not much research has been done.

Trying to deal with each type of side channel is not something many can do, and like “rolling your own crypto” is something where your success will be doubtful, without knowledge you may find difficult to aquire.

Thus the safe rule of thumb to mitigate side channels is not to use any crypto algorithm you need to rely on in an “On-Line” mode.

So encrypt your secrets on an “energy gapped” machine where neither side channeles or other communications can carry secret information out into the world for the third party ears of Eve and friends to pick up.

Clive Robinson February 28, 2023 5:46 PM

@ Ted, ALL,

Re : Side channel protection gives slow algorithms.

“Moody adds that Kyber may be about twice as slow when lots of countermeasures are added.”

And those measures will probably not be enough…

But before anyone goes “but but but.
..” The AES finalist suffers from this very issue quite badly as well. And the NSA darn well knew about side channel issues before they pursuaded NIST to rig the contest to not just ignore them but select for probably worat case algorithms… Which ment that the “fastness” of the AES finalist pushed out other better algorithms that did not have anywhere near as bad side channel leakage.

I’ve said for years on this blog, there is a trade off of “Security v Efficiency” in general the more efficient you make an algorithm or implementation the worse the side channel leakage will be in a practical implementation.

I’ve even said how you minimise some side channel issues.

One of those old English idioms os pertinent,

“There’s many a slip twixt the cup and lip”

As well as the more general,

“Don’t count your chickens till they’ve hatched”

That apply to information security.

The enemy of privacy and security when it comes to information has always been statistics, that lift apparent noise into being a signal.

When all is said and done about “Machine Learning”(ML), the reality is it’s in effect statistics on steroids. I’m only surprised that it’s taken so long for it to be shown as such against a “black box output”.

The flip side of this by the way, is it will enable us to get more information through a Shannon Channel, especially when time/distance precludes the use of feedback error correction.

So I expect to see some papers about ML applied to “Feedforward Error Correction”(FEC) to come out of this.

Which will actually be a better use of it from society and mankinds perspective, than cracking codes.

Clive Robinson February 28, 2023 6:26 PM

@ Bruce, ALL,

Re : NSA stich ups.

From the article @Ted points to from SC Magazine, towards the bottom you find,

“Their use will be mandatory for most civilian federal agencies per a White House national security memorandum, and many industries and international standards bodies rely on NIST standards when developing their own encryption policies.”

We both know beyond reasonable doubt the NSA has previously “stiched up” the US Government not just US Civilisns and US Industry with their crypto gaming.

The classic was perhaps what Matt Blaze discovered about the “Law Enforcment Access Field”(LEAF) in the “Clipper chip” algorithm.

Basically the NSA made the LEAF too short, such that you could knowing how it worked provide a fake LEAF in realtime. Thus law enforcment or other Government Agency would be “locked out” of accessing the encrypted channel. This would benifit the NSA but no other US Gov Agency that would have to use clipper as specified with the NSA using their genuine LEAF to access the encrypted communications.

As far as I can tell every algorithm the NSA has either designed for others –not IC, Diplomatic– to use, or they have been involved with the selection process, has come up short in some way giving a practical back door in every case…

Even military use encryption for “Field Ciphers” from the NSA has come up short in some way. Originally I thought this was incase it was captured, and the enemy used it, they would unknowingly activate the weaknesses thus provide a backdoor into some of their signals, but enough to provide “probables” and the like to break stronger traffic and so the NSA / GCHQ etc could work their way up to the strongest of communications.

The fact the NSA appear to ensure weaknesses “as normal practice” makes me wonder, who they think the enemy they are sworn to defend against actually is in their eyes…

iAPX March 2, 2023 1:47 PM

This is not an attack on the algorithm itself, as previously stated by other commenters, it is only due to a weak implementation with 2 lines documented to be prone to determiner leakage (see reference 34).

The novelty is the usage of AI that is essentially a pattern-retriever, that shares with our own brain the ability to very efficiently extract information from noise.

This weakness could mitigated on different ways, and should be, with a reference implementation change.

  • Change the mask values to be 2 (for 0) and 1 (for -1), subtracting -2 when used on the next line, less signal but still present.
  • Randomizing the byte and bit counters (using generated lists each time it’s called), probably my take
  • Adding more noise, MULtiplication is a great noise booster

bobthebuilder March 2, 2023 8:30 PM

Ah Successful Side Channel attacks, will they never learn…

The short answer is NO, regardless of who they is they won’t ever learn to defeat side channel attacks.

So what does this mean, simply put there’s no such thing as data security without physical security. The physical security needs to start at the materials level (the stuff we make encryption devices with) and continue all the way through to site security. A simple mistake at any point and the whole encryption system is potentially compromised.

I remember a few years back there was a lot of noise about Chip security because some smart young lad had devised a way to get a miniature hall effect sensor within a few microns of an encryption chip surface and kept the whole thing operating until he had extracted the encryption key.
Not to be out done another enterprising lad polished the backside of a chip to within a few microns of the active device and analyzed the Photon emissions of Cmos gates switching, and guess what he was also able to extract the encryption key.

Both of these are a sort of “side channel” attack, from an execution perspective they’re both a level of complexity above DPA but still not outside the scope of what can be done at any reasonably equipped Technical University lab.

Makes me believe there is no data security without physical security and more to the point the limitation of data security is inherent human limitations of physical security.

Clive Robinson March 3, 2023 1:10 AM

@ bobthebuilder,

“because some smart young lad had devised a way to get a miniature hall effect sensor within a few microns of an encryption chip surface”

It was not a “hall effect sensor” but a “pico-probe” made from a microwave inductor. He was in communications with Ross J. Anderson back when Ross was trying to solve Power Analysis by using non synchronized clocks.

I’d pointed out to Ross that the logic could be forced into synchronisation by the use of what we now call an EM Fault Injection Attack (basically a CW RF signal sufficient to cause “injection locking”).

Ross put me incontact with the researcher who sent me a pre-publish of his paper, which I still have somewhere in my “Dead Tree Cave”.

Others went on later to use even magnetostrictive “barber-pole” sensors and even SQUID.

Basically anything that works as an H-Field sensor as generally this gives tighter sensor imaging than an E-Field sensor.

With regards,

“Makes me believe there is no data security without physical security and more to the point the limitation of data security is inherent human limitations of physical security.”

There are two “information objects” that need to be protected,

1, The “plaintext”.
3, The “root of trust”.

Currently we have no general practical ways to use them unless they are in their unprotected or not secure state. However it is something that is being worked on.

For instance consider the XOR or ADD -MOD used as the mixer in a stream cipher. You can thus have the information encrypted by stream cipher but perform a limited number of actions on it as though it were not encrypted. One such is in a database where a field contains an integer number, you can add a value to that field without knowing what it contains, however you can not do a compare to find or sort a record.

It’s a form of David Chaum’s “Dining Cryptographers” problem from the 1980’s,

Another variation allegedly thought up by a cryptograpers daughter is how to find the average income of the cryptographers without any revealing directly what they earn.

She said get the waiter to write a number down and give it to the first cryptographer who adds his income to it writes the result on another piece of paper and hands that to the second cryptograper who does the same. The final piece of paper is given to the waiter who subtracts his number, then divides the result by the number of cryptographers to get the result and then tells the table what it is.

bobthebuilder March 3, 2023 5:27 AM

I played around all afternoon with a Squid system and exhausted our R&D budget for a month. That’s about all I really know about Squid as a crypto attack.
I know a heck of a lot more about active interference attacks using Infrared injection through optical fibres pulled to a 5nm tip and attached to pico probes but since none of this has been published I better also keep my mouth shut.

Fun stuff, f’ing expensive entertainment, public sponsored in the interests of who the heck knows what.

Leave a comment


Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via

Sidebar photo of Bruce Schneier by Joe MacInnis.