Summary of Side-Channel and Fault Injection Attacks

This article is contributed by the ChaMd5 Security Team IOT Group.

This is a summary of the theoretical knowledge learned recently about side-channel attacks and fault injection. If there are any mistakes or areas for improvement, I hope experts will correct me.

First, let’s introduce several common encryption algorithms.

Encryption Algorithms

RSA Encryption Algorithm

RSA is an asymmetric encryption algorithm.

Generation of Public and Private Keys

Randomly select two distinct large prime numbers p and q, and calculate N=p * q.

Using Euler’s function, obtain φ(N)=φ(p) * φ(q)=(p−1) * (q−1).

Select an integer e less than φ(N) such that e and φ(N) are coprime. Then find the modular inverse of e with respect to φ(N), named d, such that:

φ(N) mod (e * d) = 1 (which indicates φ(N) % (e * d) == 1).

Destroy the records of p and q.

At this point, (N,e) is the public key and (N,d) is the private key.

Message Encryption

First, the message needs to be transformed into an integer m that is less than N and coprime to N, in a format agreed upon by both parties. If the message is too long, it can be split into several parts, which is known as block encryption. Each part is then encrypted using the following formula:

c ≡ m^e mod N (where ^ denotes exponentiation; plaintext m is transformed into ciphertext c after encryption).

Message Decryption

Utilize the key d for decryption.

m ≡ c^d mod N.

If the key d is obtained, the ciphertext can be decrypted.

AES Encryption Algorithm

AES is a block cipher that encrypts data through iterative encryption operations.

AES128, AES192, and AES256 represent encryption with key lengths of 128, 192, and 256 bits, respectively, with iteration rounds of 10, 12, and 14.

AES divides each plaintext block into 128 bits, which is 16 bytes. If it does not meet the 16-byte requirement, padding is necessary.

(As shown, the order can be expressed in matrix form.)

Padding strategies:

NoPadding (requires plaintext to be a multiple of 16 bytes).
PKCS5Padding (default).

If the plaintext block is less than 16 bytes, the necessary number of characters is appended at the end, and the value of each byte equals the number of missing characters.

For example, plaintext: {1,2,3,4,5,a,b,c,d,e} missing 6 bytes would be completed as {1,2,3,4,5,a,b,c,d,e,6,6,6,6,6,6}.
ISO10126Padding.

If the plaintext block is less than 16 bytes, the necessary number of bytes is appended at the end, with the last character’s value equal to the number of missing bytes, and other characters filled with random numbers.

For example, plaintext: {1,2,3,4,5,a,b,c,d,e} missing 6 bytes could be completed as {1,2,3,4,5,a,b,c,d,e,5,c,3,G,$,6}.

The general process for AES128 encryption:

Initial Round (1 time).
Normal Rounds (N times).
Final Round (1 time).

Summary of Side-Channel and Fault Injection Attacks

Initially, the key is 128 bits, or 16 bytes, and through key expansion, it is extended to 176 bytes.

Following the sequence of normal rounds:

Byte Substitution.

Each byte of the plaintext block is replaced with another byte according to the S-box.

S-box:

0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
0	0x63	0x7c	0x77	0x7b	0xf2	0x6b	0x6f	0xc5	0x30	0x01	0x67	0x2b	0xfe	0xd7	0xab	0x76
1	0xca	0x82	0xc9	0x7d	0xfa	0x59	0x47	0xf0	0xad	0xd4	0xa2	0xaf	0x9c	0xa4	0x72	0xc0
2	0xb7	0xfd	0x93	0x26	0x36	0x3f	0xf7	0xcc	0x34	0xa5	0xe5	0xf1	0x71	0xd8	0x31	0x15
3	0x04	0xc7	0x23	0xc3	0x18	0x96	0x05	0x9a	0x07	0x12	0x80	0xe2	0xeb	0x27	0xb2	0x75
4	0x09	0x83	0x2c	0x1a	0x1b	0x6e	0x5a	0xa0	0x52	0x3b	0xd6	0xb3	0x29	0xe3	0x2f	0x84
5	0x53	0xd1	0x00	0xed	0x20	0xfc	0xb1	0x5b	0x6a	0xcb	0xbe	0x39	0x4a	0x4c	0x58	0xcf
6	0xd0	0xef	0xaa	0xfb	0x43	0x4d	0x33	0x85	0x45	0xf9	0x02	0x7f		0x50	0x3c	0x9f	0xa8
7	0x51	0xa3	0x40	0x8f	0x92	0x9d	0x38	0xf5	0xbc	0xb6	0xda	0x21	0x10	0xff	0xf3	0xd2
8	0xcd	0x0c	0x13	0xec	0x5f	0x97	0x44	0x17	0xc4	0xa7	0x7e	0x3d	0x64	0x5d	0x19	0x73
9	0x60	0x81	0x4f	0xdc	0x22	0x2a	0x90	0x88	0x46	0xee	0xb8	0x14	0xde	0x5e	0x0b	0xdb
a	0xe0	0x32	0x3a	0x0a	0x49	0x06	0x24	0x5c	0xc2	0xd3	0xac	0x62	0x91	0x95	0xe4	0x79
b	0xe7	0xc8	0x37	0x6d	0x8d	0xd5	0x4e	0xa9	0x6c	0x56	0xf4	0xea	0x65	0x7a	0xae	0x08
c	0xba	0x78	0x25	0x2e	0x1c	0xa6	0xb4	0xc6	0xe8	0xdd	0x74	0x1f	0x4b	0xbd	0x8b	0x8a
d	0x70	0x3e	0xb5	0x66	0x48	0x03	0xf6	0x0e	0x61	0x35	0x57	0xb9	0x86	0xc1	0x1d	0x9e
e	0xe1	0xf8	0x98	0x11	0x69	0xd9	0x8e	0x94	0x9b	0x1e	0x87	0xe9	0xce	0x55	0x28	0xdf
f	0x8c	0xa1	0x89	0x0d	0xbf	0xe6	0x42	0x68	0x41	0x99	0x2d	0x0f	0xb0	0x54	0xbb	0x16

For example, byte a[0,0]='a' which is 0x61, is replaced with b[0x6,0x1]=0xef according to the S-box, thus after replacement a[0,0]=0xef.

Row Shift.

The first row remains unchanged.

The second row is cyclically shifted left by 1 byte.

The third row is cyclically shifted left by 2 bytes.

The fourth row is cyclically shifted left by 3 bytes.
Column Mixing.

After the row shift, each column of the matrix is multiplied by a fixed constant matrix to get the corresponding output column.
Add Round Key.

Each byte of the input array is XORed with the corresponding byte of the key array.

Key expansion is also performed (the expansion algorithm is reversible, meaning that the first 16 bytes of the key can be derived from the last 16 bytes).

In summary, the entire AES128 encryption process involves XORing the plaintext with the key in the first round, followed by four transformations for nine normal rounds, and then performing three transformations in the final round, excluding column mixing, to complete the encryption.

If any round key is obtained, combined with the S-inverse box and other known information, all keys can be derived to decrypt the ciphertext.

Basics of Oscilloscopes

Digital Oscilloscope

Collects voltage signals.

Sampling: Set the sampling rate (the number of signals collected per second), generally 5-10 times the chip signal frequency.
Quantization: Set the vertical resolution and vertical range.
Trigger: The starting signal for recording by the oscilloscope.

Setting Up a Collection Environment

Passive high-impedance probes require one end to be grounded.

Active differential probes have no such requirement.

Add a resistor and use an active differential probe to collect the voltage across the resistor to calculate the current flowing through the circuit board and measure the power of the circuit board.
Add a resistor at the ground end, use a passive high-impedance probe to collect the voltage across the resistor, and calculate the current flowing through the circuit board to measure the power of the circuit board.

However, this may cause the resistor to be grounded.
Use a current probe to measure the current flowing through the circuit board to measure the power of the circuit board.
Use an electromagnetic probe to measure the electromagnetic radiation on the surface of the chip to measure the power of the circuit board.

Side-Channel Attacks

The principle is that the energy consumption of a circuit is related to the data involved in the computation and the operations performed.

Under the influence of predicting keys, we can obtain all intermediate computation results through a circuit model. Based on the dependency of energy consumption on the intermediate results, we can derive predicted energy consumption outputs.

Software Power Consumption Models

Hamming Weight Model.

Hamming Weight: The number of non-zero symbols in a string of symbols.

Because the CPU pre-charges all bit values to 1 after processing data in registers and buses, changes from 0 to 1 can result in energy variations that may leak data. Thus, the circuit power consumption is approximately linearly correlated with the Hamming weight of the data written to the register.

T(power) = k(constant) * HW(x)(Hamming Weight) + d(constant)
Hamming Distance Model.

Hamming Distance: The number of differing bits between two binary numbers of the same length, which is the number of 1s after XORing the two binary numbers (Hamming Weight).

When a device flips in the circuit at a moment, meaning it changes from high to low or vice versa, dynamic power consumption occurs; otherwise, only static power consumption occurs.

The more bits flipped, the greater the circuit’s power consumption.

The power consumption before and after the device flips is approximately linearly correlated with the Hamming distance between the binary numbers before and after the flip.

T(power) = k(constant) * HD(V0, V1)(Hamming Distance) + d(constant)

Simple Power Analysis — SPA

SPA Attack on RSA Key

RSA can be attacked by SPA based on the fast modular exponentiation algorithm included in RSA.

The fast exponentiation algorithm is as follows:

The C code implementation is:

int PowerMod(int a, int b, int c)
{
    int ans = 1;
    a = a % c;
    while(b>0) {
        if(b % 2 == 1) // When b is odd, the following instruction will execute more
            ans = (ans * a) % c;
        b = b/2;
        a = (a * a) % c;
    }
    return ans;
}

During the calculation of fast exponentiation, the value of the exponent is determined bit by bit, leading to different operations.

Thus, during the decryption process, the key d (the value of b in the above figure and code) can be restored from the energy traces, directly yielding the binary value of d in reverse order.

SPA Attack on AES Algorithm Structure

Due to different operations, the energy trace waveforms have distinct characteristics, allowing the analysis of energy traces to determine the algorithm structure used during AES encryption.

Differential Power Analysis — DPA

Encrypt a large number of plaintexts pi with the key to obtain multiple energy traces Ti. Then, for these plaintexts, perform operations with a guessed key k (256 times), resulting in multiple intermediate values x. Using the value of a certain state byte of x as a distinguishing function, divide the data into two groups, calculate the average power consumption of the two groups, and then analyze the differences between the two average power consumptions to derive the key (bit by bit).

Understanding through examples:

Taking AES128 as an example:

It can be viewed as the encryption method with transformation steps, excluding the last round:

Add Round Key.
Byte Substitution.
Row Shift.
Column Mixing.

Attack steps:

Perform encryption operations on pi and obtain i energy traces Ti through the oscilloscope.
Brute-force the key k byte by byte, requiring 256 attempts for each byte (0~0xff). For each guessed value of k, perform the following operations to brute-force the key byte by byte.
Perform i operations to XOR the plaintext pi with the guessed k and obtain the intermediate value xi through S-box substitution (in other words, for each byte of the key k, there are i*256 values of x).
Use the value of a certain state byte of the XORed intermediate result xi as a distinguishing function (for example, checking if the last byte is 1) to divide the i energy traces (where the energy traces are obtained by encrypting pi with the correct key) into two groups, calculate the average power consumption of the two groups, and then analyze the difference between the two average power consumptions.
Only the correct key can distinguish between the two groups of power consumption data, so the differential power value of the correct key is the largest.

(The graph is approximately as shown.)

The purpose of this is:

Compared to the Hamming weight power consumption model, when calculating xi, the power consumption for each bit in xi differs when it is 1 versus when it is 0.

Assuming that for a certain guessed k, when calculating xi, the power consumption is P+a when a certain bit in xi is 1 and P when it is 0.

Thus, only when the groups of energy traces corresponding to whether the bit in xi is 1, using the guessed key k, match with the groups using the correct key will the differential power value a be significantly visible at a certain point in the differential curve.

Otherwise, in the case of mutual cancellation, the differential power at that point cannot be distinguished clearly.

Correlation Power Analysis — CPA

By comparing the Hamming weight of the intermediate values calculated using multiple plaintexts and guessed key values with the energy traces of the normal decryption process, if there are points with a high linear correlation, it indicates that the process of calculating the intermediate values (using this key) exists in the encryption process, thus confirming the key’s correctness (bit by bit).

Understanding through examples:

Taking AES128 as an example:

It can be viewed as the encryption method with transformation steps, excluding the last round:

Add Round Key.
Byte Substitution.
Row Shift.
Column Mixing.

The main power consumption occurs during the Byte Substitution stage. For transformations 1 and 2, it can be summarized as XORing the input data with the key byte by byte and then replacing it according to the S-box.

Attack steps:

Perform encryption operations on pi and obtain i energy traces Ti through the oscilloscope.
Brute-force the key k byte by byte, requiring 256 attempts for each byte (0~0xff). For each guessed value of k, perform the following operations to brute-force the key byte by byte.
Perform i operations to XOR the plaintext pi with the guessed k and obtain the intermediate value xi through S-box substitution.
Calculate the Hamming weight hw of xi, and perform correlation analysis with each point of the corresponding energy trace Ti, generating a correlation curve.

If the Hamming weight of x generated by a guessed k has a high correlation coefficient with a point in the energy trace T (between -1 and 1), it indicates that the computation generating x (using this key) occurred during the encryption process (at a time point with a high correlation coefficient), thus confirming that k is the correct key.

Side-Channel Defense Techniques

Time Dimension: Randomized pseudo operations/shuffled operations — randomizing the energy consumption of cryptographic devices.
Amplitude Dimension: Increasing noise/reducing power consumption — lowering the energy consumption signal-to-noise ratio, making different operands/operations have the same energy consumption.
Masking Techniques: Altering the intermediate values.

Fault Injection

By external interference, the normal logic of the device is altered, causing the program to produce exploitable errors.

if(pay_pwd_is_correct)
 transfer_money();
else
 reject_operation();

Non-invasive attacks: Change external variables such as voltage.
Semi-invasive attacks: Disassemble the device without direct contact with the chip.
Invasive attacks: Alter or damage the internal circuitry of the device.

Principles and Types

Critical Path: The normal delay experienced by combinational logic circuits from input to output.

Voltage Fault Injection: Lowering the voltage increases the critical path delay, exceeding the clock interval.
Clock Glitch Injection: The rising edge of the clock arrives early, making the clock interval less than the critical path.
Electromagnetic Pulse Injection: Electromagnetic effects create localized induced currents (the specific model is still under discussion in academia).
Laser Injection: The photoelectric effect causes carrier energy level transitions, leading to abnormal conduction of PN junctions.
Temperature: Generally, an increase in environmental temperature lengthens the critical path.

Objectives

Bypass some security mechanisms (file access permissions, secure boot).
Generate erroneous ciphertext or signatures.
Combination attacks.

Fault Injection Parameters

Attack timing.
Attack intensity.
Duration of action.
Spatial location.

Debugging Parameter Process

Record the device state corresponding to different parameters.
Repeated attempts to narrow the parameter range.
Adjust strength and duration based on experience.
Monitor fault injection timing using side-channel analysis.

Error Models

Byte errors.
Word errors.
Bit errors.
Random errors.
Fixed to 0/1.

Attack Steps

Identify the attack target.

Modify the value of registers.
Modify memory (values in DRAM/SRAM).
Modify addresses.
Modify bus signals.
Execute erroneous instructions.
Password algorithms.

… …

Carefully read the target device’s data manual and materials.

Normal and maximum operating voltage of the chip.
Chip clock frequency.

… …

Identify useful signals generated by the target device.

Helpful for finding the timing of attacks.
Helpful for narrowing the scope of attack events.
Helpful for locating the physical position of the attack.
High signal-to-noise ratio, easy to implement.
Signals from the circuit board can be modified.
GPIO control signals.
LED indicators on the circuit board.
UART, SPI, IIC.
Debugging interfaces.
Chip reset.

… …

Determine the attack method.

Prepare samples (more than ten).

Criteria for judging attack results.

Begin the attack.

Example

PANDA-CTF 2019 Story

Send “story” to the serial port, and the serial port will output a string of characters where the last part is the flag, triggered by pin8, which is high when outputting to the serial port.

The key process is loading the length of the data to be sent into register R1, setting R2 to 0, and then incrementing R2 for output.

During the operation “loading the length of the data to be sent into register R1”, an attack can be made to increase the number of characters stored in R1, thereby outputting the final flag.

Attack process:

Since the output serial port will first pull low as a start bit before outputting the first character, the timing from the trigger rising to the output serial port pulling low can be identified through side-channel analysis, marking it as the timing for our attack, allowing us to attack the operation of loading into R1.

(In the figure, red indicates the trigger pin8, and blue indicates the output serial port.)
Use electromagnetic fault injection devices to attack the chip during that time.
Control the device to restart by powering it on and off, repeatedly trying and adjusting attack parameters (trigger time, attack time, intensity, pulse width, location, etc.).

References:

What is the AES Algorithm? (Integrated Edition) https://www.cxyxiaowu.com/3239.html

CTF-wiki https://ctf-wiki.org/crypto/introduction

New Creation Information Security – Bilibili https://space.bilibili.com/556358812

“Power and Data Correlation Models in Power Analysis Attacks” http://www.infocomm-journal.com/txxb/CN/article/downloadArticleFile.do?attachType=PDF&id=165670

“Research on the Sample Size Required for Differential Energy Attacks” http://www.ecice06.com/CN/article/downloadArticleFile.do?attachType=PDF&id=24414

end

Recruitment Advertisement

ChaMd5 Venom is recruiting experts to join.

A newly established group focusing on IOT, industrial control, and sample analysis is recruiting long-term.

Welcome to contact[email protected]