Single-sample DPA (aka horizontal DPA)

This week's study group covered 'old' papers by Colin Walter (big-mac attack) to current work of Mike where focus is to apply DPA techniques to a single trace. More specifically, we discussed the following papers:

• Colin D. Walter “Sliding Windows Succumbs to Big Mac Attack” [pdf]
• Colin D. Walter “Longer Keys May Facilitate Side Channel Attacks” [pdf]
• Jean-Christophe Courrège et al. “Simple Power Analysis on Exponentiation Revisited” [pdf]
• Werner Schindler and Kouichi Itoh “Exponent Blinding Does Not Always Lift (Partial) Spa Resistance to Higher-Level Security” [pdf]

Stefan kicked off the study group by explaining us why longer keys may facilitate Side Channels Attacks (SCAs). Common sense would suggest that longer keys should be used to provide more security. This is true for the mathematical strength of a cipher, however, Colin Walter shows in his work that for embedded RSA crypto-systems the increase in leaked data through longer keys in fact lowers security. We discussed two types of attacks, namely a timing and a power analysis attack, that may be possible from increasing the key length. The implementation under attack uses a variant of the binary "square-and-multiply" algorithm to compute the RSA exponentiation. As so often when trying to attack such implementations, the goal is to distinguish between squares and multiplications to extract secret key material.

One way to distinguish these two core operations is to look at timing variations that occur for computing the modular products. Typically, a form of Montgomery's modular multiplication (MMM) is used to compute these products. From a side-channel perspective, the interesting aspect of MMM is the fact that it includes a final conditional subtraction which reduces the output to less than the modulus. This final subtraction occurs with higher probability for squares than for multiplications and this forms a timing side-channel that can be exploited by an attacker that observes a number of exponentiations. The data leaked through this side-channel is proportional to the square of the key length and thus longer keys are being less safe. The simplest countermeasure to thwart this kind of attack is to use an unconditional subtraction and select the appropriate result afterwards.

The second attack that Stefan described exploits the power leakage of the internal hardware multiplier. For MMM a number of single precision multiplications need to be computed. The idea is here to fix one of the multiplier inputs while the second input is more or less random and then average the power traces over a number of multiplications. The power trace that we end up with is then dependent on the Hamming weight of the fixed operand. If we apply this technique to all chunks of a long integer multiplication we can build templates during pre-computation which we can then use during the actual exponentiation to guess which operation has been computed. The nice property of this attack is that we only need to collect a single power trace of an exponentiation to characterise the different operations plus mount the actual attack.

In the second part, Mike was talking a bit about the stuff he is doing at the moment. For example, on an ARM chip it is apparently easy to identify the occurrence of the different single precision multiplication operations in the power trace while executing an exponentiation. Using a horizontal DPA, the idea is to recover in each iteration the i-th operation (whether a square or multiplication has been executed) under the assumption that we have successfully recovered the first i − 1 operations. Next, an attacker makes a prediction (e.g., using the Hamming weight) of how the power consumption should look like for the two core operations. Depending on which of these two power profiles correlates best with the actual power trace reveals another operation of the exponentiation. Collecting one power trace of the device under attack is enough to mount such attack.

Mike also described another attack on the exponentiation that exploits some bias in the Hamming weight of the output of single precision multiplication and squaring operations. Basically, what is exploited in this attack is the fact that the second most least significant bit of a single precision squaring operations will always be zero. With this information we can build templates by characterising these squaring and multiplication operations to try to make a distinction between the operations. Mike reports that he had a 95% success rate in choosing the right operation using this technique. The advantages of this attack is that the bias is caused by the operation itself and it will remain there irrespective of the message input.

Finally, Mike briefly discussed some techniques to attack implementations that use exponent blinding as countermeasure.