DPA Countermeasures — Theory vs. Practice

The Threat

In today’s interconnected world, the information that we generate, store, transmit, and receive has become a valuable commodity. We have increasingly turned to cryptography as a tool to protect the confidentiality and integrity of this information, but we read almost daily about those protections being defeated. Skilled practitioners can often successfully mount attacks using only very modest resources to break unprotected devices. Attacks on FPGA bitstream encryption, as often reported in the open literature, represent significant examples of the DPA (Differential Power Analysis) threat for the aerospace and defense community.

(Photo: Brian Murphy, INSCOM)
The magic of cryptography is the ability to protect our data – large secrets – with much smaller secrets, in the form of cryptographic keys. It has long been understood among experts in cryptographic implementation that the generation, storage, and use of keys must be performed in a way that prevents the loss of those keys, because loss of a key is tantamount to losing all of the data that has ever been protected using that key. It has been demonstrated that one does not have to physically tamper with a device to recover a cryptographic key – cryptographic keys may be recovered from an electronic device via information leakage in the form of timing variations, electromagnetic (EM) emanations, or variations in power consumption resulting from the operation of a cryptographic function. As a class, these methods are referred to as side-channel attacks; however, these attacks are often generically referred to as differential power analysis (DPA) attacks.

DPA attacks are particularly powerful techniques that can uncover the cryptographic key from large amounts of data by using statistical methods to determine the variance in a system’s electrical activity when the cryptographic element is operating. The electrical activity data can be obtained through direct circuit power measurement or electromagnetically via an antenna. Electric power or EM signal traces can be very noisy due to system or measurement effects. The statistical methods used in DPA help reject the noise and make it an effective technique in real-world applications.

What to Do About It

Fortunately, it is possible to create countermeasures against side-channel attacks. Different algorithm implementations leak in different ways, so each algorithm implementation will have different countermeasures requirements. Some algorithms may leak in such a way that collecting a power or EM trace from a single operation may reveal a key, while other algorithms may require collection of traces from a number of operations to recover a key. Selecting an effective countermeasure strategy requires knowing how much an algorithm implementation leaks and how many operations will be performed in the actual system. If a large number of operations will be performed in a short period of time, then an adversary may be able to collect a large amount of data quickly, which implies that stronger countermeasures may be required compared to an implementation that performs infrequent operations.

There are several general classes of countermeasures, each with advantages and disadvantages [see sidebar]. The strongest countermeasure implementations combine several techniques to create a robust solution. Two classes of countermeasures that reduce the signal-to-noise ratio (SNR) are leakage reduction and adding uncorrelated noise. Leakage can be reduced using a number of proprietary methods, and uncorrelated noise can be added by operating other circuitry using random data. Protocol countermeasures and other sources of randomness, if used, can provide a multiplicative benefit on top of SNR reduction. It is important to be aware when implementing countermeasures that there is a significant body of patents in this domain.

Figure 1 shows a very typical appearing power trace for a representative AES operation without countermeasures. Individual clock cycles are clearly identifiable in the trace, and the 10-round structure of the AES operation with a 128-bit key is readily apparent. Furthermore, the 10th round, which lacks the Mix-Columns operation of the prior 9 rounds, is distinct. Experienced attackers have learned to recognize structures such as the power trace shown in Figure 1 and use such structures to mount attacks.

Figure 1. AES-128 operation without countermeasures power trace. Note clearly visible characteristic AES 10-round structure with different 10th round.
Figure 2 shows a power trace for the same AES operation, but with SNR reduction countermeasure. Note the lack of apparent structure of the AES operation, especially when compared to Figure 1. Moreover, Figure 2 data was captured in a clearbox test environment using a dedicated trigger to identify the start of the AES operation. The blackbox environment available to an adversary creates a decided disadvantage for even locating the operation, let alone beginning an attack. While this compelling visual evidence demonstrates the impact of the countermeasures, what is really needed is quantitative evidence about the robustness of an implementation against SCAs.

Does it Work? Statistical Proof

Knowing that a countermeasure is effective is a challenging problem. Much of the literature on side-channel attacks focuses on actually recovering a key from a device. If such an attack recovers a key, then it certainly leaks; however, if an attack fails, the only conclusion is that the specific attack failed. Further, the result of a specific attack provides little or no information about the robustness of an implementation against another attack – extant or future. The challenge for the designer is to verify the robustness of their implementation against any attack.

Figure 2. AES-128 operation with countermeasures power trace. Location of AES rounds provided by a separate trigger signal (not shown).
The solution is to measure the cryptographic function operation for any statistically significant variation in emanations that is correlated to the key and any related intermediate values against a specific number of traces. This method, introduced by Rambus Cryptography Research Division, is called test vector leakage assessment (TVLA). As its name implies, leakage of information is assessed by the execution of millions – even billions – of test vectors. Power and EM fluctuations are measured and processed as each vector is executed by the device under test, revealing if there is any statistically significant correlation between the measured fluctuations and the keys. The TVLA measurements are normally taken in a laboratory environment using advanced test equipment to provide the best data possible.

TVLA provides a means to assess the effectiveness of countermeasures. Significantly, TVLA shows whether there is a side-channel information leak, but does not show how to exploit it, or whether it can be successfully exploited. Therefore, TVLA is a pessimistic assessment tool; however, to have confidence in the resistance of countermeasures to future attacks, each implementation must pass TVLA for the specific use case. In specific, if TVLA shows information leakage, there is a probability that an attack can be developed to exploit it, provided that the adversary can observe the number of operations used for TVLA. Conversely, if TVLA shows no statistically significant leakage, the probability is that no effective attack could be developed based on observing the number of operations used for TVLA. This is the ultimate goal.

There are many countermeasures described in the open literature, and many of the resulting implementations leak – a lot – against TVLA. There are a variety of specific reasons why a countermeasure that mathematically should be effective might not work in practice; however, in general there is a large abstraction between the mathematical representation of a countermeasure and its implementation in digital logic, which itself is an abstraction constructed from an analog circuit.

The takeaway is that the effectiveness of any countermeasure implementation must be verified. Verification using a key recovery attack may reveal a leak; however, a failed key recovery attack proves little. The TVLA methodology is a kitchen-sink approach that identifies any leakage, whether exploitable or not.

Countermeasures: Costs and Benefits

The development of countermeasures is a costly endeavor. Successfully developing effective countermeasures may require hundreds of iterations, potentially over a period of years, through a costly process of design, implementation, and assessment. Therefore, to produce a new design with countermeasures, it is necessary both to establish the design and test infrastructure and invest the necessary human resources. In addition, implementing countermeasures actively changes system computational and/or electrical operations in ways that can make the system more difficult to design and more expensive to build. And then there is the ongoing cost of ownership when the design is applied to new systems with varying requirements and evolving implementation technologies.

Like other cybersecurity techniques, countermeasures address a particular type of threat. The system security as a whole must be designed with an understanding of the role that countermeasures play in the system solution, balanced with the cost/benefit of their implementation. For example, many unique countermeasures techniques may be used in tandem, as individually each unique technique can incrementally contribute to overall countermeasure performance. Therein lies the tradeoff analysis – how strong do the countermeasures need to be, and what are costs in terms of performance, area, power, and schedule? Correctly implementing security is difficult, and correctly implementing DPA countermeasures is even more so. There is no simple blueprint.

This article was written by Dr. Jonathon Mellott, Chief Technology Officer, The Athena Group, Inc. (Gainesville, FL). For more information, Click Here .