Exploiting Redundant Designs with Side-Channel Attacks

Abstract

Sidekanalsangrep (SKA) er en bred angrepsklasse der en angriper utnytter en uforventet informasjonslekkasje til å omgå et sikkerhetstiltak. Hvorfor skulle man orke å knekke en kryptert telefonsamtale når man kan stå i naborommet og lytte gjennom veggen? I en kryptografikontekst lar SKA en ondsinnet aktør komme seg rundt den teoretiske sikkerheten til personvernsalgoritmene, derfor har forskere viet mye tid og krefter til å studere og sette inn tiltak mot slike angrep.

Som en del av dette arbeidet har kryptografer blir kryptoanalytikere: de har tatt på seg rollen som den ondsinnede aktøren for å prøve å konstruere sterkest mulige angrep, for å på denne måten få en bedre forståelse for hvordan det er mulig å beskytte algoritmer mot disse angrepene. Vi antar den samme rollen i denne avhandlingen, og fokuserer på strøm-baserte angrep. Disse er særlig skadelige siden de utnytter en fysisk effekt av mikroprosessorer som ikke kan unngås. De blir også stadig mer relevante etter hvert som samfunnet liter mer og mer på sammenkoblede enheter.

For eksempel førte eksplosjonen av Tingenes internett eller skyberegning til lignende økninger av nye kryptografiske utforminger. Blant disse undersøkte vi motstandskraften mot sidekanaler hos de utformingene som bruker redundans direkte i beregningene. Mens mange kryptografer kan ha ansett redundans som kostnadsfritt fra et sikkerhetsperspektiv, ønsket vi å vise at når SKA er i bildet kommer redundans med potensielle sikkerhetsmessige haker, og avveiinger kan ikke unngås.

I den første artikkelen vår ser vi på et tiltak mot SKA, polynomiell maskering, som bruker redundans som et verktøy for å beskytte mot passive og aktive SKA samtidig. Polynomiell maskering har blitt studert tidligere, og hovedresultatet forut for denne avhandlingen pekte mot at redundans ikke påvirker sikkerheten. Vi viser det motsatte. For hver redundant del brukt i maskeringssystemet, viser vi empirisk at sikkerheten degraderer alvorlig. Videre viser vi påvirkningen interpoleringsmengden har på sikkerheten av systemet, og kobler flere populære maskeringssystemer sammen.

I den andre artikkelen vår angriper vi blokkchifferet SKINNY, et nylig publisert justerbart blokkchiffer. Vi vister at den sakte diffusjonsformen av SKINNY fører til høy redundans av de mellomliggende variablene en SKA angriper kan utnytte for å forsterke angrepet. For å utnytte denne redundansen introduserer vi et nytt angrep ved navn Klyngegrafinferens-Differensiell strømanalyse (KGI-DSA) som bruker verktøy fra probabilistisk grafteori. Vi viser kraften av det nye angrepet vårt ved å angripe flere implementeringer av SKINNY.

Side-Channel Attacks (SCA) are a broad class of attacks that exploit an unexpected leakage of information, allowing an attacker to side-step a security measure. Why would you go through the trouble of cracking an encrypted phone call if you could stand in the room next door and listen through the walls? In the context of cryptography, SCAs allow a malicious actor to get around the theoretical security of the algorithms that protect our privacy, which is why researchers have dedicated a lot of effort to studying and building protections against these attacks.

Among those efforts, cryptographers turn cryptanalysts: they take upon the role of the malicious adversary and try to craft the strongest possible attacks to better understand how to protect against them. This role is also the one we assume in this thesis, with a focus on power-based attacks. These are particularly pernicious since they exploit a physical effect of microprocessors which can hardly be prevented. They are also becoming more relevant than ever as our society relies more and more on connected devices.

For example, the explosion of the Internet-of-Things or cloud computing, led to a corresponding expansion of new cryptographic designs. Amongst these new designs, we investigated the resistance against side-channels of those that make explicit use of redundancy in their computations. While many cryptographic designers might have considered redundancy to be costless from a security standpoint, we wanted to show that when SCAs are in the picture, redundancy comes with potential security drawbacks and trade-offs that cannot be avoided.

In our first paper, we study a countermeasure to SCAs, polynomial masking, which uses redundancy as a tool to simultaneously protect against passive and active SCAs. Polynomial masking has previously been studied and the main result before this thesis pointed in the direction of redundancy bearing no influence on security. We show the opposite. For every redundant share used in the masking scheme, we empirically show that the security degrades severely. Furthermore, we point out the influence of the choice of the interpolation set on the security of the scheme and link several popular masking schemes together.

In our second paper, we attack the blockcipher SKINNY, a recently published tweakable blockcipher. We demonstrate that the slow diffusion design of SKINNY leads to a high redundancy of intermediate variables that an SCA attacker can leverage to build a stronger attack. To exploit this redundancy we introduce a new attack, dubbed Cluster Graph Inference-Differential Power Analysis (CGI-DPA) that uses tools from the field of probabilistic graphical theory. We demonstrate the efficacy of our new attack by attacking multiple implementations of SKINNY.