Reducing the amount of required key coefficients when attacking a pair-point-wise multiplication in Kyber

No Thumbnail Available

Files

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.

Date

2024-05-01

Department

Major/Subject

Matematiikka ja systeemitieteet

Mcode

SCI3029

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

en

Pages

46

Series

Abstract

We expand upon previous research that uncovered a template attack against pair- point-wise multiplication, which is employed during polynomial multiplication in the Kyber algorithm. The pair-point-wise multiplication refers to multiplication of first degree polynomials, where a pair of secret key coefficients is utilized with a pair of ciphertext coefficients in a particular way. When using a known ciphertext, this introduces several operations depending solely on secret key coefficients which allows the adversary to gather enough information through power consumption to determine their values. We will in particular, target the C-implementation for Kyber from the PQClean repository. The authors of this repository claim that it serves as a solid starting point for investigating implementation security. However, it’s worth noting that this implementation does not include any machine-dependent optimizations and performs the pair-point-wise multiplication in a suboptimal way. Consequently, attacking this implementation is expected to be a little bit easier, but it also allows anyone to easily replicate the attack without special resources. In this thesis, we will first establish the foundation for understanding the Number Theoretic Transform (NTT) and then explore how its properties could be leveraged in the template attack. Interestingly, the properties of the in-place NTT, combined with the observation that Kyber samples secret key coefficients from a small domain, allow us to recover the full key from only the first quarter of the key in the NTT domain. We also explore the practical challenges encountered during the implementation of the template attack. Specifically, we investigate how register contents in the CPU adversely affect power consumption traces, complicating the extraction of useful information. Furthermore, we propose possible solutions that can help to mitigate this effect and eventually, we are able to develop an attack strategy that demonstrates sufficiently high success probability for our targeted Kyber implementation.

Kyber-algoritmi on NIST:n (National Institute of Standards and Technology) standardointiprosessiin valittu avaimenkapsulointimekanismi (engl. Key Encapsulation Mechanism, KEM), joka on postuloitu kestäväksi kvanttitietokoneita vastaan. Tyypillisesti Kyber-algoritmia käytetään salaisen avaimen generoinnissa ja sen turvallisessa jakamisessa kahden osapuolen välillä epäluotettavan kanavan kautta. Työssä laajennettiin aiempaa tutkimusta, joka paljasti template-hyökkäyksen Kyber-algoritmin paripistekertolaskua vastaan. Paripistekertolasku viittaa ensimmäisen asteen polynomien kertolaskuun, jossa salaisen avaimen ja salatun viestin kertoimien väliset kertolaskut suoritetaan tietyllä tavalla. Käytettäessä tunnettua salattua viestiä useat operaatiot paripiste kertolaskun aikana riippuvat samanaikaisesti ainoastaan yhdestä salaisen avaimen kertoimesta. Tämä mahdollistaa sen, että hyökkääjä voi päätellä avaimen kertoimien arvoja vertaamalla kohdelaitteen tehonkulutusta identtisen koelaitteen tehonkulutukseen eri avaimilla. Hyökkäys kohdistettiin erityisesti Kyber C -implementaatiolle PQClean-kirjastossa, jonka kehittäjät väittävät sen tarjoavan vankan pohjan toteutuksen turvallisuuden tutkimiseen. On kuitenkin syytä huomata, että tämä implementsatio ei sisältänyt prosessorikohtaisia optimointeja ja suoritti paripistekertolaskun epäoptimaalisesti. Tämän odotetaan helpottavan hyökkäyksen toteuttamista, mutta samalla se mahdollistaa kenen tahansa toistaa hyökkäyksen ilman erityisiä resursseja. Tässä opinnäytteessä luomme ensin perustan ymmärtämääksemme numeroteoreettista muunnosta (engl. Number Theoretic Transform, NTT) ja sitten tutkimme, miten sen ominaisuuksia voidaan hyödyntää template-hyökkäyksessä. Osoittautuu, että koko salainen avain voidaan palauttaa pelkästään avaimen ensimmäisestä neljänneksestä. Tämä on mahdollista hyödyntämällä NTT:n ominaisuuksia ja havaintoa siitä, että Kyber valitsee salaisen avaimen kertoimet hyvin pienestä joukosta. Tutkimme myös käytännön haasteita, joita ilmenee template-hyökkäyksen toteutuksessa. Erityisesti tarkastelemme miten rekisterien sisällöt prosessorissa vaikuttavat haitallisesti tehonkulutusmittauksiin, mikä vaikeuttaa hyödyllisen tiedon erottamista. Lisäksi esitämme ratkaisuehdotuksia, joiden avulla voidaan lieventää tätä vaikutusta, ja kehitämme hyökkäysstrategian, joka osoittaa kohtuullisen korkeaa onnistumistodennäköisyyttä kohdentamallemme Kyberin implementaatiolle.

Description

Supervisor

Brzuska, Chris

Thesis advisor

Illikainen, Aada

Keywords

post-quantum cryptography, template attack, kyber, number theoretic transform, side-channel attack

Other note

Citation