I recently found an exploitable timing leak in the reference implementation of Kyber (ML-KEM), the soon-to-be NIST standard for post-quantum key encapsulation.
Let’s see if you can spot it in the source code - msg is secret:
Let’s see if you can spot it in the source code - msg is secret:
“I don’t see it. Looks good to me?”
Sure does! It’s written to avoid any control-flow or data dependency on the message.
" ... "
Let’s look at an obviously insecure version of the same function. The following code leaks the bits of msg one by one:
Sure does! It’s written to avoid any control-flow or data dependency on the message.
" ... "
Let’s look at an obviously insecure version of the same function. The following code leaks the bits of msg one by one:
Now let's inspect the x86 assembly for the first (secure!) version with clang, using the -Os option to optimize for size
Notice what happens?
Notice what happens?
“So the compiler helpfully reverts the side-channel countermeasure?”
Indeed, the secure and insecure source are compiled to the exact same x86 assembly
Indeed, the secure and insecure source are compiled to the exact same x86 assembly
“Looks like a small leak. Is it exploitable?”
Yes. During decaps, the leak can be used as a plaintext-checking oracle leading to key recovery.
“PoC || GTFO.”
…
Okay - here goes: github.com/antoonpurnal/c…
Yes. During decaps, the leak can be used as a plaintext-checking oracle leading to key recovery.
“PoC || GTFO.”
…
Okay - here goes: github.com/antoonpurnal/c…
“Which compilers/options are affected?”
Blast radius of this particular security regression is limited to x86 Clang (v15-18), for several options including -Os, -O1 and several others.
Plain -O3, a common default, is (luckily) not affected. But some variations of it are.
Blast radius of this particular security regression is limited to x86 Clang (v15-18), for several options including -Os, -O1 and several others.
Plain -O3, a common default, is (luckily) not affected. But some variations of it are.
“How novel is this?”
It’s known that compilers may break source-level side-channel resistance [1,2] and it was reported before that Clang may swap cmovs for branches [3].
Still, to my knowledge it’s been a while since it caused an exploitable leak in important crypto code?
It’s known that compilers may break source-level side-channel resistance [1,2] and it was reported before that Clang may swap cmovs for branches [3].
Still, to my knowledge it’s been a while since it caused an exploitable leak in important crypto code?
“Optimizing compilers optimize. This is unsurprising. CT evaluation should happen at binary level.”
Couldn’t agree more. That’s our approach at @PqShield. But it’s not uncommon for crypto code to be distributed as source & compiled by users (w/ a mainstream optimizing compiler).
Couldn’t agree more. That’s our approach at @PqShield. But it’s not uncommon for crypto code to be distributed as source & compiled by users (w/ a mainstream optimizing compiler).
For more details, check out the piece I wrote for the PQShield website: pqshield.com/pqshield-plugs…
Many thanks to @cryptojedi for the swift and collaborative disclosure process.
References throughout thread:
[1]
[2]
[3] cl.cam.ac.uk/~rja14/Papers/…
leslyann-daniel.fr/ressources/pap…
electricdusk.com/cmov-conversio…
References throughout thread:
[1]
[2]
[3] cl.cam.ac.uk/~rja14/Papers/…
leslyann-daniel.fr/ressources/pap…
electricdusk.com/cmov-conversio…
• • •
Missing some Tweet in this thread? You can try to
force a refresh
