Design Article
Defending against side-channel attacks - Part I
Gilbert Goodwill, Cryptography Research, Inc.
9/19/2012 10:17 AM EDT
2. Side-channel analysis
This section provides a very brief introduction to some of the more commonly exploited side-channel analysis techniques. While the majority of the examples in this paper use power analysis, the techniques presented are largely agnostic to how the data is collected. Other physical measurements used in side-channel analysis include, but are not limited to, RF signals and E-Field data. Other sources such as sound, heat and photon emissions have been proposed and researched.
2.1. Timing attacks
Timing attacks exploit small differences in execution time to extract secret information from systems. Commonly discovered sources of timing leaks include, but are not limited to:
• Data dependent differences in instruction times;
• Early exit;
• Data dependent code branches;
• Cache access times.
A very commonly seen timing attack exploits the early exit from loops comparing passwords or message authentication codes (MACs). This allows the attacker to use the verifier as an oracle to extract the secret key. Although these attacks are decades old, they are still found in systems that are both currently deployed and still under development.
There are many examples of practical timing attacks against cryptographic algorithms. Timing attacks against standard cryptosystems such as Diffie-Hellman, RSA, and DSS were introduced by Kocher in [1]. Cache collision timing attacks against AES executing on modern processors were demonstrated by Bonneau and Mironov in [2]. Brumly and Boneh [3] demonstrated that practical remote timing attacks against networks were possible. These examples show that cryptographic algorithms and protocols may be vulnerable to timing attacks, even when operating on modern hardware.
2.2 Simple power analysis
Simple power analysis (SPA) is a set of techniques for analyzing large-scale changes in power consumption which occur due to changes in the algorithm being performed or the data being processed. It is often used to help analyze devices by:
• Determining what operations are taking place;
• Determining timelines for the sequence of operations performed;
• Identifying changes in power consumption due to changing operation or data;
• Extracting secrets non-invasively.
SPA leaks can usually be exploited using just one or a few power measurements. In general, the same sources of timing leaks also result in SPA leaks, since power traces can be used to determine the precise timing of the different operations.
Public key algorithms tend to be particularly susceptible to SPA, since the big-number arithmetic required by these algorithms often uses a lot of power relative to other operations, and can vary greatly with the data being processed. For example, the most straightforward method for implementing a modular exponentiation is a loop similar to the following:
Note that in the above loop, a modular square is always performed, but whether a modular multiplication occurs depends upon the current bit of the exponent being processed. Figure 2 below is a power trace obtained from a device performing modular exponentiation using the RSA decryption exponent.
In this device, the squaring routine is an optimized version of the general multiplication routine. As a result, the squaring routine uses less power than the general multiplication routine. Combined with the fact that a square can follow either a square or a multiply, but a multiply must always follow a square, it is then a simple matter to read off the secret decryption exponent from a single trace.
Section 3 shows how this type of attack works against cryptographic applications running on several different popular mobile devices.
This section provides a very brief introduction to some of the more commonly exploited side-channel analysis techniques. While the majority of the examples in this paper use power analysis, the techniques presented are largely agnostic to how the data is collected. Other physical measurements used in side-channel analysis include, but are not limited to, RF signals and E-Field data. Other sources such as sound, heat and photon emissions have been proposed and researched.
2.1. Timing attacks
Timing attacks exploit small differences in execution time to extract secret information from systems. Commonly discovered sources of timing leaks include, but are not limited to:
• Data dependent differences in instruction times;
• Early exit;
• Data dependent code branches;
• Cache access times.
A very commonly seen timing attack exploits the early exit from loops comparing passwords or message authentication codes (MACs). This allows the attacker to use the verifier as an oracle to extract the secret key. Although these attacks are decades old, they are still found in systems that are both currently deployed and still under development.
There are many examples of practical timing attacks against cryptographic algorithms. Timing attacks against standard cryptosystems such as Diffie-Hellman, RSA, and DSS were introduced by Kocher in [1]. Cache collision timing attacks against AES executing on modern processors were demonstrated by Bonneau and Mironov in [2]. Brumly and Boneh [3] demonstrated that practical remote timing attacks against networks were possible. These examples show that cryptographic algorithms and protocols may be vulnerable to timing attacks, even when operating on modern hardware.
2.2 Simple power analysis
Simple power analysis (SPA) is a set of techniques for analyzing large-scale changes in power consumption which occur due to changes in the algorithm being performed or the data being processed. It is often used to help analyze devices by:
• Determining what operations are taking place;
• Determining timelines for the sequence of operations performed;
• Identifying changes in power consumption due to changing operation or data;
• Extracting secrets non-invasively.
SPA leaks can usually be exploited using just one or a few power measurements. In general, the same sources of timing leaks also result in SPA leaks, since power traces can be used to determine the precise timing of the different operations.
Public key algorithms tend to be particularly susceptible to SPA, since the big-number arithmetic required by these algorithms often uses a lot of power relative to other operations, and can vary greatly with the data being processed. For example, the most straightforward method for implementing a modular exponentiation is a loop similar to the following:
Figure 1: Straightforward implementation of a modular exponentiation
Note that in the above loop, a modular square is always performed, but whether a modular multiplication occurs depends upon the current bit of the exponent being processed. Figure 2 below is a power trace obtained from a device performing modular exponentiation using the RSA decryption exponent.
Figure 2: Power trace of device performing modular exponentiation using RSA decryption exponent. In this device, the squaring operation was an optimized version of the general multiplication routine, leading to an SPA attack.
In this device, the squaring routine is an optimized version of the general multiplication routine. As a result, the squaring routine uses less power than the general multiplication routine. Combined with the fact that a square can follow either a square or a multiply, but a multiply must always follow a square, it is then a simple matter to read off the secret decryption exponent from a single trace.
Section 3 shows how this type of attack works against cryptographic applications running on several different popular mobile devices.
|
|
|
|
|
Navigate to related information