Power Analytic Attacks on CRYSTALS-Kyber

Abstract

Denne avhandlingen undersøker effekten av effektanalytiske sidekanalangrep på den kvantesikre nøkkelkapslingsalgoritmen CRYSTALS-Kyber. Vi gjenskapte og forbedret et tidligere korrelasjonsangrep utført av Karlov et al. Vi implementerte Kyber512 i ChipWhisperer-systemet og utførte angrepet tre ganger, med effektmålinger fra 1000, 200 og 50 dekrypteringer.

Vi gjenopprettet alle hemmelige nøkkelparametere i alle gjennomførte angrep og vi har verifisert at angrepet kan gjenopprette den fullstendige hemmelige nøkkelen. Angrepet er også anvendelig på alle versjoner av CRYSTALS-Kyber, med en lineær økning i kjøretiden basert på størrelsen på sikkerhetsparameteren k. Vi er også sikre på at angrepet kan benyttes til å delvis gjenopprette den hemmelige nøkkelen i den tilsvarende digitale signaturalgoritmen CRYSTALS-Dilithium.

Resultatene våre viser en drastisk reduksjon i sannsynligheten for falske positiver i angrep som bruker et økt antall effektmålinger. Imidlertid observerte vi en betydelig økning i kjøretid i angrep med mange effektmålinger, noe som krever at fremtidige implementasjoner må veie risikoen for falske positiver mot kjøretiden.

Vi har avkreftet det foreslåtte mottiltaket av Karlov et al., som omhandler å regenerere den hemmelige nøkkelen innen hver 50. kommunikasjonssyklus. Dette ble gjort ved å gjenopprette den hemmelige nøkkelen ved hjelp av effektmålinger fra 50 dekrypteringer.

This thesis investigates the effect of power analytic side-channel attacks against the post-quantum key encapsulation algorithm CRYSTALS-Kyber. To achieve this, the previously known correlational power analytic attack performed by Karlov et al. \cite{karlov2021power} was recreated and improved upon. We implemented Kyber512 in the ChipWhisperer toolchain and performed the attack three times, with the power measurements of 1000, 200, and 50 decryptions.

In all the attacks, We successfully recovered all attempted secret key parameters and verified the attack could fully recover the secret key. The attack is also applicable to all versions of CRYSTALS-Kyber, with a linear increase in the runtime of the attack as the security parameter k of CRYSTALS-Kyber increases. We are also confident that the attack can partially recover the secret key in the corresponding signature scheme CRYSTALS-Dilithium.

Our results show a drastic decrease in the likelihood of false positives in the attack as the number of power recordings used increases. However, we observed a drastic increase in runtime due to large computations, requiring future implementations to consider the tradeoff between fault likelihood and runtime.

We have disproven the suggested countermeasure by Karlov et al. of regenerating the secret key every 50 communication cycles by successfully recovering the secret key with the power recordings of 50 decryptions.