Power CryptanalysisA study of SPA and DPAHow does it work?Sample Power TraceWhat does power consumption tell you?Evolution of Power CryptanalysisSimple Power AnalysisDifferential Power AnalysisAES CandidatesResultsMesserges ResultsKnown CountermeasuresKnown Countermeasures (cont.)Shamir’s Detached Power SupplyTechnologies relevant to Power AnalysisTechnologies relevant to Power Analysis (cont.)ConclusionPower CryptanalysisA study of SPA and DPATom LashECE 543December 13, 2000How does it work?Smart CardSmart Card Place small resistor in series with smart card Sample voltage across resistor, compute current Analyze samples for desired time intervalsSample Power TraceWhat does power consumption tell you? Different processor/memory operations have different current requirements Many operations are data dependent E.g. power required to store a 1 in a register is different than the power required to store a 0 Operations themselves “leak” information and give insight to the encryption algorithmEvolution of Power Cryptanalysis Attack was invented by Paul Kocher et al in 1996/1997, published in 1998 Attained previous recognition for work in timing cryptanalysis by breaking RSA in linear time (22 years old, biology major) Two primary variants Simple Power Analysis (SPA) Differential Power Analysis (DPA)Simple Power Analysis Attacker directly analyzes data samples to determine cryptographic operations Attacker looking for data-dependent patterns E.g. square and multiply Key bits revealed by analysis of several rounds of encryption or several messagesDifferential Power Analysis More powerful statistical analysis of data samples Statistics used to generate thresholds for determining key bits Leverages the fact that operating on 1’s and 0’s consume different amounts of powerAES Candidates Three studies presented at the AES2 Conference, March 1999 Reported results of power cryptanalysis on 15 submitted algorithms All three studies took different approaches to cryptanalysis attacks Chari, Jutla, Rao, Rohatgi used Twofish attack as basis of comparison Daemen and Rijmen used computational operation analysis Bihan and Shamir used Hamming weight analysis to analyze vulnerabilitiesResults Different approaches revealed different vulnerabilities For the most part, the five finalists (MARS, RC6, Rijndael, Serpent, Twofish) performed near the topMesserges Results Thomas Messerges analyzed five AES finalists and evaluated for how difficult it would be to implement ‘ArithmeticToBoolean’ and ‘BooleanToArithmetic’ functions Rijndael and Twofish were deemed to be “least computationally costly” to protect using this methodKnown Countermeasures Physical Shielding Costly to implement Likely that attacker can get to the power source somewhere in the circuit Add noise to power signature DPA may still be effective at high noise levels Costly to implement, effects of adding noise to system may have adverse effects on other componentsKnown Countermeasures (cont.) Software No-op dummy instructions to vary power signature Operation/operand balancing Hardware Costly, not possible to implement for all operations (arithmetic operations troublesome) Performance degradationShamir’s Detached Power Supply+VSwitch controlProcessor, MemoryTwo capacitors+--VTechnologies relevant to Power Analysis Artificial Intelligence Pattern recognition Detect cipher patterns or recognize effects of countermeasures Data mining Compute correlations not obvious from simple statistical analysis Neural networks Model cipher behavior as a function of power signature, excellent for “black box” operationsTechnologies relevant to Power Analysis (cont.) Digital signal processing Eluded to by HO-DPA authors (Kocher, Messerges) Allows for frequency-domain processing May be able to detect countermeasures such as parallelization, no-ops Easy segregation of DPA spikes and flat spotsConclusion Power cryptanalysis is a very powerful technique for gaining insight into a cipher’s operation and should be a significant design consideration for all future ciphers and implementations“We have not yet encountered a card that couldn’t be broken”-Paul Kocher,
View Full Document