Side-Channel Analysis: Countermeasures and Application to Embedded Systems Debugging

摘要

Side-Channel Analysis plays an important role in cryptology, asit represents an important class of attacks against cryptographicimplementations, especially in the context of embedded systemssuch as hand-held mobile devices, smart cards, RFID tags, etc.These types of attacks bypass any intrinsic mathematical securityof the cryptographic algorithm or protocol by exploiting observableside-effects of the execution of the cryptographic operation thatmay exhibit some relationship with the internal (secret) parametersin the device. Two of the main types of side-channel attacks aretiming attacks or timing analysis, where the relationship betweenthe execution time and secret parameters is exploited; and poweranalysis, which exploits the relationship between power consumptionand the operations being executed by a processor as well as thedata that these operations work with. For power analysis, twomain types have been proposed: simple power analysis (SPA) whichrelies on direct observation on a single measurement, anddifferential power analysis (DPA), which uses multiplemeasurements combined with statistical processing to extractinformation from the small variations in power consumptioncorrelated to the data.In this thesis, we propose several countermeasures to thesetypes of attacks, with the main themes being timing analysisand SPA. In addition to these themes, one of our contributionsexpands upon the ideas behind SPA to present a constructiveuse of these techniques in the context of embedded systemsdebugging.In our first contribution, we present a countermeasure againsttiming attacks where an optimized form of idle-wait is proposedwith the goal of making the observable decryption time constantfor most operations while maintaining the overhead to a minimum.We show that not only we reduce the overhead in terms of executionspeed, but also the computational cost of the countermeasure,which represents a considerable advantage in the context ofdevices relying on battery power, where reduced computationstranslates into lower power consumption and thus increasedbattery life. This is indeed one of the important themes forall of the contributions related to countermeasures to side-channel attacks.Our second and third contributions focus on power analysis;specifically, SPA. We address the issue of straightforwardimplementations of binary exponentiation algorithms (or scalarmultiplication, in the context of elliptic curve cryptography)making a cryptographic system vulnerable to SPA. Solutionspreviously proposed introduce a considerable performancepenalty. We propose a new method, namely Square-and-Buffered-Multiplications (SABM), that implements an SPA-resistant binaryexponentiation exhibiting optimal execution time at the cost ofa small amount of storage --- O(sqrt(ell)), where ell is thebit length of the exponent. The technique is optimal in thesense that it adds SPA-resistance to an underlying binaryexponentiation algorithm while introducing zero computationaloverhead.We then present several new SPA-resistant algorithms that resultfrom a novel way of combining the SABM method with an alternativebinary exponentiation algorithm where the exponent is split intwo halves for simultaneous processing, showing that by combiningthe two techniques, we can make use of signed-digit representationsof the exponent to further improve performance while maintainingSPA-resistance. We also discuss the possibility of our methodbeing implemented in a way that a certain level of resistanceagainst DPA may be obtained.In a related contribution, we extend these ideas used in SPA andpropose a technique to non-intrusively monitor a device and traceprogram execution, with the intended application of assisting inthe difficult task of debugging embedded systems at deploymentor production stage, when standard debugging tools or auxiliarycomponents to facilitate debugging are no longer enabled in thedevice. One of the important highlights of this contribution isthe fact that the system works on a standard PC, capturing thepower traces through the recording input of the sound card.