Design Article
Defending against side-channel attacks - Part I
Gilbert Goodwill, Cryptography Research, Inc.
9/19/2012 10:17 AM EDT
2.3. Differential power analysis (DPA)
Differential power analysis (DPA) is a set of techniques for analyzing changes in power consumption that are too small to be observed directly. It was first published in the late 1990’s by Kocher, Jaffe, and Jun in [4], and has become one of the primary tools for non-invasive analysis. There is now a very large body of literature on the subject.
To give a brief example of the how DPA can be used, Figure 3 below shows a power trace from a device performing a single AES encryption. If multiple traces were collected, data dependent differences in the traces would be too small to observe directly.
However, suppose many traces are collected from a device performing AES on random input data, and the traces partitioned into 2 sets. In the first set, bit 18 of the input (18 is an arbitrary choice here) is 0, and in the other set bit 18 is 1. Since the input was random, the two sets will each contain about half of the original traces. Now compute the average of the traces in each set. Visually, the resulting power traces would look the same as the trace in Figure 3. However, as Figure 4 below shows, taking the difference between the averages of the two sets reveals the influence of bit 18 on the power consumption of the device.
Similar techniques can be used to extract secret keys. For example, consider the construction shown in Figure 5 below.
In the above construction, a sub-block of plaintext P is XORed with a sub-block of key K, and the result is transformed by the nonlinear function S, which outputs intermediate value I. This type of construction appears in many modern block ciphers. In AES, P, K and I are all 8-bit bytes, and S is an invertible nonlinear lookup table. The small size of the sub-blocks helps enable a divide and conquer strategy in which individual sub-blocks of key are extracted independently until the entire key is recovered.
To see how the basic DPA attack proceeds, consider an attack against AES-128 in which a device encrypts a moderate number of, say 1000, random blocks of plaintext, during which the power consumption is monitored. Then the key can often be extracted using the following steps.
1. Select a byte of key to recover.
2. Select a bit of the intermediate I (say bit 3) on which the traces are to be sorted.
3. Guess a value for the byte of key.
4. For each block of plaintext:
a. Compute the value of I using the (known) plaintext and (guessed) byte of key.
b. Assign each power trace to one of two sets, depending upon whether bit 3 of I has the value 0 or 1. Since the plaintext is randomly chosen, there should be roughly 500 power traces in each set.
5. Average the power traces in each of the two sets, and compute the difference of the two.
6. Looks for large spikes in the difference trace, which shows that the influence of the value of bit 3 of I on power consumption. See Figures 6 through 8 below for an example difference traces for correct and incorrect key byte guesses.
a. If large spikes are not present, return to step 3 and guess a different value for the key.
b. If no guesses for the key byte result in large spikes in the difference trace, try sorting on a different bit of the intermediate I. It is often the case that some bits will exhibit stronger leaks than others.
7. If a key byte recovered in step 6, go to step 1 and select a new byte of key to recover.
Part One discussed a basic DPA attack against AES. Many different variations of DPA attacks exist, depending upon the type of algorithm and how it is being implemented. Part Two will discuss a DPA attack against AES using EM emissions from the devices.
References
[1] Paul Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems”, Advances in Cryptology – Crypto ‘96 Proceedings, Lecture Notes in Computer Science Vol. 1109, Neal Koblitz (Ed.), Springer-Verlag, 1996, pp. 104–113.
[2] Joseph Bonneau and Ilya Mironov, “Cache-Collision Timing Attacks against AES”, Cryptographic Hardware and Embedded Systems – CHES 2006, Lecture Notes in Computer Science, Vol. 4249, L. Goubin and M. Matsui (Ed.), Springer-Verlag, 2006, pp. 201-215.
[3] D. Brumly and D. Boneh, “Remote Timing Attacks are Practical”, Proceedings of the 12th USENIX Security Symposium, August 4–8, 2003. (Paper available at http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf).
[4] Paul Kocher, Joshua Jaffe, Benjamin Jun, “Differential Power Analysis,” Advances in Cryptology - Crypto 99 Proceedings, Lecture Notes In Computer Science Vol. 1666, M. Wiener, (Ed.), Springer-Verlag, 1999, pp. 388–397. (Whitepaper available at http://www.cryptography.com/resources/whitepapers/DPATechInfo.pdf)
See related links:
Using MISRA C and C++ for security and reliability. Part I
Using MISRA C and C++ for security and reliability. Part II
Using MISRA C and C++ for security and reliability. Part III
How secure is AES against brute force attacks?
Public key cryptography and security certificates
----------------------
If you found this article to be of interest, visit Military/Aerospace Designline where you will find the latest and greatest design, technology, product, and news articles with regard to all aspects of military, defense and aerospace. And, to register to our weekly newsletter, click here.
Differential power analysis (DPA) is a set of techniques for analyzing changes in power consumption that are too small to be observed directly. It was first published in the late 1990’s by Kocher, Jaffe, and Jun in [4], and has become one of the primary tools for non-invasive analysis. There is now a very large body of literature on the subject.
To give a brief example of the how DPA can be used, Figure 3 below shows a power trace from a device performing a single AES encryption. If multiple traces were collected, data dependent differences in the traces would be too small to observe directly.
Figure 3: Power trace of device performing a single AES encryption.
However, suppose many traces are collected from a device performing AES on random input data, and the traces partitioned into 2 sets. In the first set, bit 18 of the input (18 is an arbitrary choice here) is 0, and in the other set bit 18 is 1. Since the input was random, the two sets will each contain about half of the original traces. Now compute the average of the traces in each set. Visually, the resulting power traces would look the same as the trace in Figure 3. However, as Figure 4 below shows, taking the difference between the averages of the two sets reveals the influence of bit 18 on the power consumption of the device.
Figure 4: Difference between averages of AES power traces sorted on input bit 18 vertically magnified by a factor of 25. The spikes show the influence of bit 18 on the power consumption of the device.
Similar techniques can be used to extract secret keys. For example, consider the construction shown in Figure 5 below.
Figure 5: Common construction in many modern block ciphers.
In the above construction, a sub-block of plaintext P is XORed with a sub-block of key K, and the result is transformed by the nonlinear function S, which outputs intermediate value I. This type of construction appears in many modern block ciphers. In AES, P, K and I are all 8-bit bytes, and S is an invertible nonlinear lookup table. The small size of the sub-blocks helps enable a divide and conquer strategy in which individual sub-blocks of key are extracted independently until the entire key is recovered.
To see how the basic DPA attack proceeds, consider an attack against AES-128 in which a device encrypts a moderate number of, say 1000, random blocks of plaintext, during which the power consumption is monitored. Then the key can often be extracted using the following steps.
1. Select a byte of key to recover.
2. Select a bit of the intermediate I (say bit 3) on which the traces are to be sorted.
3. Guess a value for the byte of key.
4. For each block of plaintext:
a. Compute the value of I using the (known) plaintext and (guessed) byte of key.
b. Assign each power trace to one of two sets, depending upon whether bit 3 of I has the value 0 or 1. Since the plaintext is randomly chosen, there should be roughly 500 power traces in each set.
5. Average the power traces in each of the two sets, and compute the difference of the two.
6. Looks for large spikes in the difference trace, which shows that the influence of the value of bit 3 of I on power consumption. See Figures 6 through 8 below for an example difference traces for correct and incorrect key byte guesses.
a. If large spikes are not present, return to step 3 and guess a different value for the key.
b. If no guesses for the key byte result in large spikes in the difference trace, try sorting on a different bit of the intermediate I. It is often the case that some bits will exhibit stronger leaks than others.
7. If a key byte recovered in step 6, go to step 1 and select a new byte of key to recover.
Figure 6: Mean trace.
Figure 7: Difference trace for correct key byte guess.
Figure 8: Difference trace for incorrect key byte guess.
Part One discussed a basic DPA attack against AES. Many different variations of DPA attacks exist, depending upon the type of algorithm and how it is being implemented. Part Two will discuss a DPA attack against AES using EM emissions from the devices.
References
[1] Paul Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems”, Advances in Cryptology – Crypto ‘96 Proceedings, Lecture Notes in Computer Science Vol. 1109, Neal Koblitz (Ed.), Springer-Verlag, 1996, pp. 104–113.
[2] Joseph Bonneau and Ilya Mironov, “Cache-Collision Timing Attacks against AES”, Cryptographic Hardware and Embedded Systems – CHES 2006, Lecture Notes in Computer Science, Vol. 4249, L. Goubin and M. Matsui (Ed.), Springer-Verlag, 2006, pp. 201-215.
[3] D. Brumly and D. Boneh, “Remote Timing Attacks are Practical”, Proceedings of the 12th USENIX Security Symposium, August 4–8, 2003. (Paper available at http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf).
[4] Paul Kocher, Joshua Jaffe, Benjamin Jun, “Differential Power Analysis,” Advances in Cryptology - Crypto 99 Proceedings, Lecture Notes In Computer Science Vol. 1666, M. Wiener, (Ed.), Springer-Verlag, 1999, pp. 388–397. (Whitepaper available at http://www.cryptography.com/resources/whitepapers/DPATechInfo.pdf)
See related links:
Using MISRA C and C++ for security and reliability. Part I
Using MISRA C and C++ for security and reliability. Part II
Using MISRA C and C++ for security and reliability. Part III
How secure is AES against brute force attacks?
Public key cryptography and security certificates
----------------------
If you found this article to be of interest, visit Military/Aerospace Designline where you will find the latest and greatest design, technology, product, and news articles with regard to all aspects of military, defense and aerospace. And, to register to our weekly newsletter, click here.
|
|
|
|
|
Navigate to related information