Outline
Introduction to Rules to Defend Against Fault Injection and Power Analysis Attacks
Power Analysis Attack: What Is It?
Simple Power Analysis
Random Noise: A Simple Defense Against Simple Power Analysis
Masking: A Second Defense
Montgomery Ladder: A Third Defense
Introduction to Differential Power Analysis and Higher-Order Analysis
Defenses Against Differential Power Analysis
Higher-Order Masking
Blinding for Public-Key Cryptography
Perform Decoy Operations
Montgomery Ladder
Randomize Access to Confidential Array Values
Operation Shuffling
Non-Deterministic Processor
Rules to Defend Against Power Analysis
Apply noise by executing programs in parallel on several CPU cores.
Apply masking. This can defend up to the nth-order differential power analysis attack. However, an (n+1)th order differential power analysis attack can bypass this defense.
If you are programming a public-key cryptosystem such as RSA or Elliptic Curve Cryptography you can use blinding to protect the private key from power analysis attacks.
You can blind the message itself.
You should also blind the exponent used for encryption too.
Apply Decoy operations: calculations that pretend to be authentic calculations based on secret data but are not in reality.
Randomize Access to Confidential Array Values: Loop through elements of an array of secret values in random order.
Fault Injection Attack: What Is It?
How Practical Is It?
Why You Should Still Care About Fault Injection Attacks Demanding Physical Access
Voltage Glitch Attack: A Practical, Remote Fault Injection Attack Targeting Intel Systems
Electromagnetic Fault Injection Attack
Defenses Against Fault Injection Attack
Use Nontrivial Constants
Clear Variables After Use
Search for Fault-Injection Resistant Implementations
Introduction to Rules to Defend Against Fault Injection and Power Analysis Attacks
In the last blog post I discussed techniques to defend against timing attacks. There are two more attacks that plague cryptosytems: power analysis and fault injection attacks. These attacks are usually deemed less of a threat than timing attacks in most programs of cryptosystems. As such many cryptographic libraries such as OpenSSL do not offer defenses against them. They are usually a concern only if you are worried about the attacker gaining physical access to the computer performing the cryptographic operation. Still, these attacks do matter if you are worried about the attacker doing so--especially if you have to perform cryptographic operations on someone else's computer--such as in cloud computing.
If you are interested in a much deeper discussion on how these attacks work I strongly recommend you read "The Hardware Hacking Handbook" by No Starch Press. It was written by members of the RISCURE Security group.
Power Analysis: What Is It?
In power analysis the attacker measures power consumption and identifies patterns that reveal the secrets managed by the machine. The history of power analysis goes as far back as World War II in the infamous TEMPEST attack. It was one of the attacks mentioned in paper co-written by Paul Kocher, the same person who published the discovery of the timing attack. This paper's name is "Differential Power Analysis".
Simple Power Analysis is the simplest version of power analysis. The attacker observes graphs measuring power consumption over time. From this information alone it is sometimes possible to deduce secret keys! The next sections explain simple defenses coders can use to defend against Simple Power Analysis based on the advice given in "The Hardware Hacking Handbook".
Random Noise: A Simple Defense Against Simple Power Analysis
The simplest technique to add noise to the power consumption. Coders can do this by running software in parallel. The coder can run software in parallel on another CPU core that does dummy or decoy operations. This will not make your code immune to the attack but does make it harder.
Masking: A Second Defense Against Simple Power Analysis
According to "The Hardware Hacking Handbook" a simple technique a coder can use to defend against Simple Power Analysis is called masking. In masking, a coder usually applies the xor operation to the cryptographic secret and a random value. The downside to masking is that whatever cryptosystem we are programming must be modified to ensure the secret remains masked throughout the calculation. Never in any stage of the cryptosystem's execution should the cryptographic secret be in an unmasked state.
A common problem with masks is that they are often reused--this is something you should avoid when using them. And even if a unique mask is applied to each unique cryptographic secret operation as you should the attacker can still undo the masking with just some more effort--in a Differential Power Analysis Attack.
Montgomery Ladder
Another technique to prevent power analysis attacks against RSA and Elliptic Curve Cryptography is by introducing dummy operations in the Montgomery Ladder.
The Montgomery Ladder is inspired by the famous square-and-multiply algorithm. It was invented to make scalar multiplication work faster for modular exponentiation in elliptic curve cryptography. All elliptic curve cryptography is based on raising some public base number g to the power of a secret number x and apply the result to the modulus operation with some large prime number p in the following formula:
Just as with the square-and-multiply algorithm for RSA the Montgomery Ladder also suffers from power analysis vulnerability.
Below is a sample of the Montgomery exponentiation algorithm that is resistant to Simple Power Analysis:
The Montgomery Ladder can be applied to Elliptic Curve Cryptography and RSA.
Differential Power Analysis
The attacker can simply capture two distinct mask values X and Y masked by the same mask M and xor them together. This yields the xor of the two secret values since X xor M xor Y xor M cancels out the mask value! Of course, this is not enough to discern what the two secrets are since we are stuck with X xor Y. If the attacker knows the absolute value of the difference in power traces between X and Y ( a.k.a | t_x - t_y | ) the attacker can use this and knowledge of X xor Y to discern X and Y each.
Defenses Against Differential Power Analysis
Higher-Order Masking
Just as we applied a mask to defend against Simple Power Analysis we can apply multiple, consecutive masks to defend against differential power analysis attacks. For example, instead of xoring a single mask to the secret value we can do this: Secret xor Mask_1 xor Mask_2. This is called second-order masking. Of course, the attacker can repeat the attack technique described above against both mask values, which is known as a third-order differential power analysis attack. It is just that this requires more determination. As "The Hardware Hacking Handbook" states any nth-order masking can be overcome by an (n+1)th order masking. In summary, masking alone just makes it harder to perform a power analysis attack and does not make your cryptosystem program immune to it.
Blinding for Public-Key Cryptography
Blinding is a technique to make anonymous digital signatures. It was invented by US cryptographer David Chaum. It was never invented to be a defense against side channel attacks. Nevertheless it is recommended as a defense for public-key cryptography. Let me review how blinding works for RSA to illustrate how it works:
In standard RSA we take a small message of bits M and encrypt it by performing the computation using a public-known exponent e:
In blinding we do this instead to get the Blinded Ciphertext:
To digitally sign the Blinded_Ciphertext we do the following with private exponent d:
In the above calculation we first raise the Blinded_Ciphertext to the power of the private exponent d. This cancels out the exponent e that r was raised to--leaving the ciphertext multiplied to the r value. This makes the digital signature message blinded. It is important to understand that only the private key owner knows the values of d and r. So only the private key owner can unblind the digital signature message:
Since the attacker does not know the random value r they cannot perform a successful attack!
Unfortunately RSA has another problem: RSA only uses the exponent d only a few bits at a time--making d vulnerable to side channel attacks. A technique to prevent this is to blind the d exponent too:
In RSA:
Both p and q are secret primes that are parts of the private key in RSA.
It is best practice to blind d using the above technique each time we encrypt/decrypt with RSA. Since each encryption uses a unique blind value d' the attacker will only get a single to discern the d value in any case of RSA encryption/decryption. Coders must be careful to program this. If done wrong the attacker can extract the blinded exponent too since it is leaked from the program.
Perform Decoy Operations
Decoy operations pretend to make calculations based on secret data--but in reality are not. It is meant to fool an attacker into paying attention to misleading power traces.
One case where decoy operations can help is in the square-and-multiply algorithm. In the square-and-multiply algorithm we scan through the bits of the exponent we are raising a message to. If the current-most bit is a 0 we simply square the in-progress ciphertext. If it is a 1 bit we multiply and then square the in-progress ciphertext. This difference in behavior between the 0 and 1 bits is an attack vector for power analysis attacks. Yet square-and-multiply is a very helpful technique to accelerate modular exponentiation.
To avoid side channel attacks decoy operations can be made in parallel and the results are discarded if the current bit of the exponent is a 0.
Randomize Access to Confidential Array Values
When the program must verify if a secret value is correct, such as a password or a Hash-based Message Authentication code, such information can be leaked if the program traverses through the secret object in a predictable fashion. Often coders simply traverse through the array representing the secret value from the most-significant bit to the least-significant bit.
"The Hardware Hacking Handbook" recommends traversing through the secret object in a random order--preferably using a CSPRNG to decide the next element to be checked until all are exhausted.
Operation Shuffling
Lookup tables are an attack vector for power analysis attacks. Lookup tables are part of the implementation for symmetric ciphers such as Advanced Encryption Standard. To prevent a power analysis attack the execution order of looking up values in the lookup table can be randomized. This will thwart Power Analysis Attack attempts.
Non-Deterministic Processor
These CPUs have additional hardware to randomize the execution of instructions through Instruction Level Parallelism. This allows for the execution of non-dependent instructions simultaneously in a parallel processor pipeline. Instructions are non-dependent if they do not depend on the results of another instruction that has yet to be executed or finish executing.
Fault Injection: What Is It?
Modern computer hardware is designed to be very consistent. It is very rare for the machine hardware to malfunction to cause a program to execute incorrectly. Instead the coder wrote the program wrong. However, attackers have discovered ways to write programs that cause the machine hardware to malfunction--such that it can leak secret information!
That is the central idea behind fault-injection--planned machine hardware failure to cause leakage of secrets such as cryptographic secrets. This is known as differential fault analysis. Real differential fault analysis attacks have been known to extract secret keys from AES, 3DES, RSA-CRT, and Elliptic Curve Cryptography. For AES only one or two faults are necessary to steal the key. The Bellcore Attack against RSA-CRT only needs one fault injection attack to steal the private key.
For a more complete look on these attacks you can read the book "Fault Analysis in Cryptography" by Springer Publications.
Thankfully, in the real world the attacker will need to have physical access to the device. So if you are performing a computation with some secret value on your personal computer you will not need to worry about this attack if it requires the attacker to have physical access to the machine.
However, some fault injection attacks can be done remotely. It depends on the Instruction Set Architecture of your machine. Below is an excellent table from the paper "How Practical Are Fault Injection Attacks, Really?" that explains which fault injection attacks are remote on which Instruction Set Architecture:
Most likely you own a smartphone and a machine that either uses an Intel or AMD-based Instruction Set Architecture. If using a smartphone you have little reason to worry about fault injection attacks for the case where the CPU's Instruction Set is ARM (standalone).
If using an Intel machine you will have to be concerned about the random byte fault injection induced by the voltage glitch. What makes matters worse: it only costs ~$30 USD for the equipment to perform the voltage glitch attack when done against Intel systems!
Why You Should Still Care About Fault Injection Attacks Demanding Physical Access
In the modern world we rent access to another person's machine and allow that machine handled by another person to do our computing for us. The issue is that other person has physical access to the machine--and you have no say on how they handle the machine. This is called cloud computing. Cloud Computing providers can perform all the attacks requiring physical access without you ever knowing that they do.
If most fault injection attacks
For the case where you must be concerned about Fault Injections against targeting your machine's Instruction Set Architecture this section is for you.
In the cases aforementioned the fault model is "random byte". This means the attacker changes a specific byte to a random value--causing a differential fault analysis.
Let me explain the voltage glitch fault injection attack more.
Voltage Glitch Attack
Voltage glitches are the primary attack that can target Intel/AMD/ARM (standalone) systems [e.g. smartphones/Apple macOS computers as of now]. This is the fault injection attack you are most likely concerned about.
In a voltage glitch fault injection attack the attacker tries to create a stable power supply for the chip except for moments where secret operations are being made. In that moment the power supply should be dropped or spiked to outside the normal operating voltage range. The Hardware Hacking Handbook gives more information on the three main methods it is done.
Optical Fault Injection
Modern microprocessors are based on semiconductor technology. When a light beam with enough luminosity strikes this material it changes the conductivity of logic gates, causing a fault.
Defenses Against Fault Injection Attacks
Use Nontrivial Constants
Often when comparing two values in programs we check for a 1 or 0 value. This can be encoded in only 1 bit. This is easy for an attacker using a fault injection attack to flip. The Hardware Hacking Handbook gives some examples of cryptographic APIs, such as OpenSSL, that can be affected by a single bit-flip attack of this nature.
Instead of using a 1 or 0 value we should use constants with large Hamming distances. The hamming distance between two streams of bits are the number of bits at corresponding positions that have opposing bits. For example: (1001)_2 and (0101)_2 have a Hamming Distance of 2 since the first and second bits between the two bitstreams differ from each other. Meanwhile (1101)_2 and (0011)_2 has a Hamming Distance of 3 since the first three bits differ.
To calculate the Hamming distance you can xor the bits between the bitstreams and count the number of 1 bits to find the Hamming Distance. So calculating the Hamming Distances for both binary numbers above:
When we use constants that have a large value (64-bits instead of a single bit) and that have a large Hamming Distance between each other there is a large amount of bits that the attacker must flip to pass a comparison test. Sample code on how to apply this can be found in the "Countermeasures" chapter in The Hardware Hacking Handbook".
Clear Variables After Use
Always clear the value of variables after they are out of scope by setting the value to zero. Otherwise attackers can induce fault injections that take advantage of outdated values of variables to bypass verification.
Search for Fault Injection-Resistant Implementations
Luckily for you someone probably already has wrote a fault-injection resistant implementation for the algorithm you are seeking such as the paper Algorithmic Countermeasures Against Fault and Power Analysis for RSA CRT. Here are sample implementations of the Montgomery Ladder exponentiation and RSA-CRT:
Your favorite search engine should be very helpful in helping you find algorithms modified to be resistant to the power analysis and fault injection attacks you are concerned about.
Call to Action
Are you interested in programming these countermeasures like I am? I got so tired of searching for such books I started writing my own. If you are interested in learning more please feel free to read the beta draft of my book: Program Cryptography.
You can leave comments and reactions directly on the webpage.