Algebraic Fault Analysis of SHA-256 Compression Function and Its Application

Abstract

Cryptographic hash functions play an essential role in various aspects of cryptography, such as message authentication codes, pseudorandom number generation, digital signatures, and so on. Thus, the security of their hardware implementations is an important research topic. Hao et al. proposed an algebraic fault analysis (AFA) for the SHA-256 compression function in 2014. They showed that one could recover the whole of an unknown input of the SHA-256 compression function by injecting 65 faults and analyzing the outputs under normal and fault injection conditions. They also presented an almost universal forgery attack on HMAC-SHA-256 using this result. In our work, we conducted computer experiments for various fault-injection conditions in the AFA for the SHA-256 compression function. As a result, we found that one can recover the whole of an unknown input of the SHA-256 compression function by injecting an average of only 18 faults on average. We also conducted an AFA for the SHACAL-2 block cipher and an AFA for the SHA-256 compression function, enabling almost universal forgery of the chopMD-MAC function.

1. Introduction

1.1. Background

Side-channel attacks are severe threats to hardware implementations of cryptographic algorithms. Fault attacks (FAs) are side-channel attacks that intentionally cause faults in the cryptographic process on a hardware device and try to recover the secret information from internal information that is not usually output. They can cause faults, for example, by irradiating electromagnetic waves, such as lasers, or by manipulating the device’s voltage. Fault attacks were first proposed by Boneh et al. in 1996 [1,2], and then Biham and Shamir proposed a differential fault analysis (DFA) for DES in 1997 [3]. The basic principle of DFAs is to recover the secret key by using the output difference between normal and fault-injected executions and the cryptographic algorithm from the point of fault injection to the output. DFAs were also applied to other ciphers [4,5,6]. In addition, DFAs on the compression functions of cryptographic hash functions were studied. Hemme et al. proposed a DFA against the SHA-1 compression function using a 32-bit random fault model [7]. Based on this attack, DFAs were also applied to the HAS-160 [8] and MD5 [9] compression functions. On the other hand, Courtois et al. proposed an algebraic fault analysis (AFA) for DES [10]. An AFA can analyze more information than a DFA and recover secret information with fewer fault injections. AFAs were also applied to other ciphers [11,12].

When performing an AFA, a SAT solver and an SMT solver are used to solve algebraic equations. A SAT solver is a program that judges whether a given problem is satisfiable or not and outputs a solution if it is satisfiable. The problem is given in the form of a CNF formula. An SMT solver is an extension of the SAT solver for propositional logic and deals with predicate logic satisfiability problems. STP [13] is a kind of SMT solver, which solves bit-vector theory. STP converts a given problem into a CNF equation and then calls a SAT solver to solve it. The SAT solver we used was CryptoMiniSat 5 [14], which is capable of processing cryptographic problems quickly.

1.2. Related Work

SHA-2 is a family of cryptographic hash functions standardized by NIST in FIPS PUB 180-4 [15]. SHA-256 is included in the family. It is widely deployed and is one of the most important cryptographic hash functions. HMAC is a MAC function standardized by NIST in FIPS PUB 198-1 [16].

Jeong et al. [17] recovered the secret key of HMAC/NMAC-SHA-2 by injecting a fault during the computation of HMAC/NMAC and reducing the number of steps in the SHA-2 compression function. Their fault model assumes that an attacker can change the number of steps in the SHA-2 compression function. Hao et al. [18] proposed an AFA for the SHA-256 compression function using a 32-bit random fault model. They recovered the whole of an unknown input of the SHA-256 compression function by injecting 65 faults. They also presented an almost universal forgery attack on HMAC-SHA-256 based on this result. Nejati et al. [19] assumed an advanced fault injection device and improved the AFA by Hao et al. [18] in 2018. They recovered the whole of an unknown input message block of the SHA-256 compression function with fewer fault injections.

1.3. Our Contribution

We first conducted computer experiments on various fault injection conditions and showed that one can recover the whole of an unknown input of the SHA-256 compression function by injecting about 18 faults on average. While our AFA reduces the number of fault injections compared to that of Hao et al., it requires more time to solve algebraic equations. However, a standard PC can solve them in less than an hour, and it still seems practical. Next, we performed an AFA for the block cipher SHACAL-2 [20]. It can recover the secret key with 12 fault injections by using a standard PC to solve algebraic equations in less than an hour. Finally, we performed an AFA for the SHA-256 compression function, which enabled almost universal forgery of the chopMD-MAC function [21].

1.4. Organization

In Section 2, we describe the SHA-256 compression function, the block cipher SHACAL-2, and the chopMD-MAC function. We also review the AFA for the SHA-256 compression function of Hao et al. In Section 3, we first describe the results of computer experiments on the AFA of Hao et al. and show that the number of injected faults can be greatly reduced. Next, we present the results of the AFA for SHACAL-2 and the AFA for the SHA-256 compression function, which enables almost universal forgery of the chopMD-MAC function. Section 4 is the conclusion.

2. Materials and Methods

This section describes the SHA-256 compression function [15], the SHACAL-2 block cipher [20], and the chopMD-MAC function [21]. We also review the AFA for the SHA-256 compression function of Hao et al. [18].

2.1. SHA-256 Compression Function

SHA-256 is an iterated hash function producing a 256-bit output. The SHA-256 compression function takes a 512-bit message block and a 256-bit intermediate hash value as an input and produces a 256-bit new intermediate hash value as an output.

The algorithm of the SHA-256 compression function is described below. It is also depicted in Figure 1. In the following description, the operation $+$ denotes addition modulo $2^{32}$, $\oplus$ denotes bitwise XOR, $\wedge$ denotes bitwise AND, ¬ denotes bitwise NOT, and $\parallel$ denotes the concatenation of bit strings.

The SHA-256 compression function first divides a given 512-bit message block $M$ as follows:

$$M=m_0\parallel m_1\parallel m_2\parallel m_3\parallel \cdots \parallel m_{14}\parallel m_{15}$$

where $m_j\in {\left\{0,1\right\}}^{32}$. Next, it computes $w_j\in {\left\{0,1\right\}}^{32} \left(j=0, 1, \dots , 63\right)$ using the following message schedule:

$$w_j=\left\{\begin{array}{c}{m}_j\hfill \\ {\sigma }_1\left(w_{j-2}\right)+w_{j-7}+{\sigma }_0\left(w_{j-15}\right)+w_{j-16}\end{array}\right.\begin{array}{c}\mathrm{if} 0\le j\le 15, \\ \mathrm{if} 16\le j\le 63. \end{array}$$

${\sigma }_0$ and ${\sigma }_1$ are defined as follows. $ROTR\left(n, x\right)$ denotes the right $n$-bit cyclic shift of $x$, and $SHR\left(n, x\right)$ denotes the right $n$-bit shift of $x$.

$${\sigma }_0\left(x\right)=ROTR\left(7, x\right)\oplus ROTR\left(18, x\right)\oplus SHR\left(3, x\right),$$

$${\sigma }_1\left(x\right)=ROTR\left(17, x\right)\oplus ROTR\left(19, x\right)\oplus SHR\left(10, x\right).$$

Next, it assigns an input intermediate hash value to ($a_0, b_0, \dots , h_0$) and calculates the following steps for $i=0, 1,\dots , 63$ (Figure 2). $a_i, b_i, \dots , h_i$ are called chaining values, ${\alpha }_i, {\beta }_i$ are called auxiliary values, and $k_i$ is called a step constant.

$${\alpha }_i=h_i+{\mathsf{\Sigma }}_1\left(e_i\right)+\mathrm{Ch}\left(e_i, f_i, g_i\right)+k_i+w_i,$$

$${\beta }_i={\mathsf{\Sigma }}_0\left(a_i\right)+\mathrm{Maj}\left(a_i, b_i, c_i\right),$$

$$a_{i+1}={\alpha }_i+{\beta }_i,b_{i+1}=a_i,$$

$$c_{i+1}=b_i, d_{i+1}=c_i,$$

$$e_{i+1}=d_i+{\alpha }_i, f_{i+1}=e_i,$$

$$g_{i+1}=f_i, h_{i+1}=g_i,$$

where $\mathrm{Ch}, \mathrm{Maj},{ \mathsf{\Sigma }}_0, {\mathsf{\Sigma }}_1$ are defined as follows:

$$\mathrm{Ch}\left(x, y, z\right)=\left(x\wedge y\right)\oplus \left(\neg x\wedge z\right),$$

$$\mathrm{Maj}\left(x, y, z\right)=\left(x\wedge y\right)\oplus \left(x\wedge z\right)\oplus \left(y\wedge z\right),$$

$${\mathsf{\Sigma }}_0\left(x\right)=ROTR\left(2, x\right)\oplus ROTR\left(13, x\right)\oplus ROTR\left(22, x\right),$$

$${\mathsf{\Sigma }}_1\left(x\right)=ROTR\left(6, x\right)\oplus ROTR\left(11, x\right)\oplus ROTR\left(25, x\right).$$

Finally, the SHA-256 compression function outputs $H$ as a new intermediate hash value:

$$H=Y_a\parallel Y_b\parallel Y_c\parallel Y_d\parallel Y_e\parallel Y_f\parallel Y_g\parallel Y_h$$

where

$$Y_a=a_{64}+a_0, Y_b=b_{64}+b_0,$$

$$Y_c=c_{64}+c_0, Y_d=d_{64}+d_0,$$

$$Y_e=e_{64}+e_0, Y_f=f_{64}+f_0,$$

$$Y_g=g_{64}+g_0, Y_h=h_{64}+h_0.$$

2.2. SHACAL-2

SHACAL-2 [20] is a block cipher based on the SHA-256 compression function. A plain text is given as an intermediate hash value, and a secret key as a message block. The ciphertext is ($a_{64}, b_{64}, \dots , h_{64}$). The key length is recommended to be at least 128 bits.

2.3. ChopMD-MAC

The chopMD-MAC function [21] adds a chop function to the output of the MD hash function, whose initial value is the secret key. The chop function truncates an $n$-bit input and outputs an $s$-bit output (Figure 3). In this work, we assume that chopMD-MAC uses the SHA-256 compression function ($n=256$) and $s=128$.

2.4. Algebraic Fault Analysis for the SHA-256 Compression Function by Hao et al.

This section reviews the AFA procedure for the SHA-256 compression function in the study by Hao et al. [18]. It assumes that a 32-bit fault is injected into a specified chaining value among $a_i,b_i,\dots ,h_i \left(i=0,1,\dots ,63\right)$. When a fault is injected, the chaining value is changed to a random value unknown to the attacker, and a faulty output is obtained after the cryptographic operation. With the faulty output and the normal output, an algebraic equation is constructed for the operations from the injected fault location to the output. Through repeated fault injection into the same chaining value, multiple algebraic equations are obtained for the same operations. STP is used to solve the algebraic equations.

The process of the AFA for the SHA-256 compression function can be divided into two phases. Phase 1 recovers the chaining value $p_{63}=(a_{63}, b_{63},\dots , h_{63})$. Phase 2 recovers the whole input to the SHA-256 compression function.

2.4.1. Phase 1

In this phase, 14 faults are injected into $c_{60}$, and the 14 corresponding faulty outputs are obtained. Next, the algebraic equations are constructed based on the normal and faulty outputs and the operations (including feed-forward operations) for the four steps from 60 to 63. STP solves the algebraic equations and returns a solution for $p_{63}$. Hao et al. reported that they succeeded in recovering $p_{63}$ in all of the 100 trials of the procedure above. They also reported that they always succeeded in recovering $p_{63}$ in the same way by injecting 13 faults into $c_{58}$ or $c_{59}$.

In addition, they examined the number of chaining values $p_i$’s recovered at the same time and the computation time for the cases where 13 faults were injected into one of $a_{59}, b_{59}, \dots ,h_{59}$. The results showed that there was a positive correlation between the number of recovered chaining values and the percentage of computation time larger than 200 s.

2.4.2. Phase 2

First, from the non-faulty chaining value $p_{63}$ obtained in Phase 1 and the correct output $Y$, the faulty chaining value $p_{63}^{\ast }=\left(a_{63}^{\ast }, b_{63}^{\ast },\dots , h_{63}^{\ast }\right)$ corresponding to a faulty output $Y^{\ast }$ can be calculated as follows:

$$a_{63}^{\ast }=Y_b^{\ast }-Y_b+a_{63},$$

$$b_{63}^{\ast }=Y_c^{\ast }-Y_c+b_{63},$$

$$c_{63}^{\ast }=Y_d^{\ast }-Y_d+c_{63},$$

$$d_{63}^{\ast }=Y_e^{\ast }-Y_e-\left(T_{63}^{\ast }-T_{63}\right)+d_{63}$$

$$e_{63}^{\ast }=Y_f^{\ast }-Y_f+e_{63},$$

$$f_{63}^{\ast }=Y_g^{\ast }-Y_g+f_{63},$$

$$g_{63}^{\ast }=Y_h^{\ast }-Y_h+g_{63},$$

$$h_{63}^{\ast }=T_{63}^{\ast }-T_{63}+f_1\left(e_{63}^{\ast }, f_{63}^{\ast }, g_{63}^{\ast }\right)-f_1\left(e_{63}, f_{63}, g_{63}\right)+h_{63},$$

where

$$T_{63}^{\ast }=h_{63}^{\ast }+{\mathsf{\Sigma }}_1\left(e_{63}^{\ast }\right)+\mathrm{Ch}\left(e_{63}^{\ast }, f_{63}^{\ast }, g_{63}^{\ast }\right)+k_{63}+w_{63},$$

$$f_1\left(e_{63}, f_{63}, g_{63}\right)={\mathsf{\Sigma }}_1\left(e_{63}\right)+\mathrm{Ch}\left(e_{63}, f_{63}, g_{63}\right).$$

Phase 2 proceeds as follows. First, 13 faults are injected into $c_{56}$, and faulty outputs are obtained. For each faulty output $Y^{\ast }$, the corresponding faulty chaining value $p_{63}^{\ast }$ is calculated. Based on these values, the algebraic equations for the seven steps from 56 to 62 are constructed. Subsequently, STP solves them and finds the values of $w_{59},w_{60},w_{61},w_{61},w_{62}$. Hao et al. claimed that they were successful in all of their 100 trials.

Second, 13 faults are injected into $c_{52}$. For each faulty output $Y^{\ast }$, the faulty chaining value $p_{63}^{\ast }$ is calculated in the same way as above. For faulty $p_{63}^{\ast }$ and non-faulty $p_{63}$, $p_{59}^{\ast }$ and $p_{59}$ are calculated, respectively, with recovered $w_{59},w_{60},w_{61},w_{62}$. Then, based on $p_{59}^{\ast }$ and $p_{59}$, algebraic equations for the seven steps from 52 to 58 are constructed. STP solves them and finds the values of $w_{55},w_{56},w_{57},w_{58}$.

In a similar way, by injecting faults into $c_{48}$ and $c_{44},$ $w_{51}, w_{52}, w_{53}, w_{54}$ and $w_{47}, w_{48}, w_{49}, w_{50}$ are recovered. The input message block $m_0\parallel m_1\parallel \cdots \parallel m_{15}$ can be calculated from the recovered $w_{47}, \dots , w_{62}$ according to the message schedule. Once the input message block is recovered, $w_{63}$ can be calculated. Next, $p_{64}$ can be calculated from $p_{63}$ and $w_{63}$, and the input intermediate hash value $p_0=H-p_{64}$ is recovered.

In summary, by injecting 65 32-bit random faults in total (13 faults are injected five times), the whole input of the SHA-256 compression function can be recovered.

3. Results

3.1. Detailed Examination of AFA

We conducted computer experiments on various fault-injection conditions in the AFA for the SHA-256 compression function described in Section 2. In the experiments, we implemented the SHA-256 compression function in the C language and simulated fault injections. STP was used as an automatic tool, and CryptoMiniSat5 was used as a SAT solver. The experiments were performed on a PC with Intel(R) Xeon(R) Silver 4110 CPU @ 2.10 GHz, 32 G memory, and Ubuntu 18.04.3 LTS.

For Phase 1, we first injected 13 faults into each of the chaining values from $a_{60}$ to $h_{60}$, and tried to recover as many chaining values $p_i=\left(a_i,b_i,\dots ,h_i\right)$ as possible. The results are shown in

Table 1. Recovered chaining values and computation time.

Fault Position	Recovered Chaining Values	Computation Time [s]
$a_{60}$	none	-
$b_{60}$	none	-
$c_{60}$	$p_{63}$	20.3
$d_{60}$	$p_{63}, p_{62}$	176.5
$e_{60}$	$p_{63}, p_{62}, p_{61}$	66.7
$f_{60}$	$p_{63}, p_{62}$	82.0
$g_{60}$	$p_{63}$	109.6
$h_{60}$	$p_{63}, p_{62}$	110.0

. The computation time is the average of 100 trials. The results show that the fault injections into $e_{60}$ can recover more chaining values than the fault injections into other positions.

Next, we changed the number of faults injected into $c_{60}$ or $e_{60}$ in Phase1 and $c_{56}$ or $e_{56}$ in Phase 2 and measured the number of times the correct chaining values were recovered out of 100 trials. The results are shown in

Table 2. Success rate and average time for each number of faults (Phase 1). “-” indicates that the result was not output within 72 h.

Phase 1	Fault Position ${\mathit{c}}_{60}$		$\mathbf{Fault} \mathbf{Position} {\mathit{e}}_{60}$
Number of Faults	Success Rate [%]	Average Time [s]	Success Rate [%]	Average Time [s]
14	100	11.6	100	39.9
13	97	11.0	100	41.7
12	98	10.9	100	41.0
11	100	11.2	100	37.4
10	96	10.5	99	47.4
9	93	11.2	100	45.5
8	88	10.8	100	59.3
7	80	10.3	96	44.5
6	75	12.6	89	88.0
5	50	13.7	82	123.9
4	30	31.3	-	-
3	1	112.5	-	-

and

Table 3. Success rate and average time for each number of faults (Phase 2).

Phase 2	Fault Position${\mathit{c}}_{56}$		$\mathbf{Fault} \mathbf{Position} {\mathit{e}}_{56}$
Number of Faults	Success Rate [%]	Average Time [s]	Success Rate [%]	Average Time [s]
14	100	1.00	100	81.34
13	97	0.93	100	83.48
12	98	0.91	100	89.20
11	100	0.86	100	95.11
10	96	0.84	100	67.34
9	93	0.76	100	72.71
8	88	0.77	100	102.73
7	80	0.73	100	98.08
6	75	0.70	100	102.01
5	50	0.64	100	87.25
4	30	0.77	100	121.75
3	1	0.78	100	492.76

for Phase 1 and Phase 2, respectively. For Phase 1, except for the cases where four or fewer faults were injected, the correct chaining values were recovered with higher probabilities when faults were injected into $e_{60}$ than when faults were injected into $c_{60}$. For Phase 2, even when only three faults were injected into $e_{56}$, all 100 trials were successful.

From the experimental results described above, the procedure of AFA with the smallest expected number of faults (with the cases of the colored parts in Table 2 and Table 3) is given below.

Phase 1: Inject five faults into $e_{60}$ and recover the chaining value $p_{63}$.

Phase 2:

(1)

Inject three faults into $e_{56}$ and recover $w_{59}$, $w_{60}$, $w_{61}$, and $w_{62}$.

(2)

Inject three faults into $e_{52}$ and recover $w_{55}$, $w_{56}$, $w_{57},$ and $w_{58}$.

(3)

Inject three faults into $e_{48}$ and recover $w_{51}$, $w_{52}$, $w_{53}$, and $w_{54}$.

(4)

Inject three faults into $e_{44}$ and recover $w_{47}$, $w_{48}$, $w_{49}$, and $w_{50}$.

(5)

Calculate the input message block and intermediate hash value.

For the procedure, the expected number of faults is 18.1, and the computation time is about 35 min.

3.2. AFA for SHACAL-2

Since SHACAL-2 feeds the key to the message input of the SHA-256 compression function, the goal of the AFA is to recover the message input of the SHA-256 compression function. SHACAL-2 outputs the chaining value $\left(a_{64},b_{64},\dots , h_{64}\right)$ as a ciphertext without the feed-forward operation of the SHA-256 compression function. Thus, we can start the AFA with Phase 2 in Section 2. The procedure is shown below:

(1)

Inject three faults into $e_{57}$ and recover $w_{60}$, $w_{61}$, $w_{62}$, and $w_{63}$.

(2)

Inject three faults into $e_{53}$ and recover $w_{56}$, $w_{57}$, $w_{58}$, and $w_{59}$.

(3)

Inject three faults into $e_{49}$ and recover $w_{52}$, $w_{53}$, $w_{54}$, and $w_{55}$.

(4)

Inject three faults into $e_{45}$ and recover $w_{48}$, $w_{49}$, $w_{50}$, and $w_{51}$.

(5)

Calculate the input message.

For the procedure with 12 fault injections in total, all of 100 trials were successful. The total computation time was about 33 min.

3.3. AFA for Almost Universal Forgery of chopMD-MAC

For almost universal forgery of the chopMD-MAC function, we recover the hash value input $\left(a_0,b_0,\dots ,h_0\right)$ of the SHA-256 compression function under the condition that the message input and only 128 bits of the 256-bit output are known. Since $\left(a_0,b_0,\dots ,h_0\right)$ can be calculated from $p_{63}$ and the message input, only $p_{63}$ has to be recovered.

We assumed that the chop function outputs four words among the eight-word output $\left(Y_a, Y_b, \dots , Y_h\right)$ of the SHA-256 compression function. We injected 14 faults into $c_{60}$ and analyzed the SHA-256 compression function under the condition mentioned above. Since we found that the SHA-256 compression function does not propagate the faults to $Y_h$, we excluded the cases that the chop function outputs $Y_h$. We verified all the other 35 cases.

Table 4. Average time and success rate of the analysis for chop-MD.

Output of Chop Function	Average Time [s]	Success Rate [%]
$\left(Y_a,Y_b,Y_d,Y_e\right)$	1072	100
$\left(Y_a,Y_b,Y_c,Y_e\right)$	46,344	80
$\left(Y_a,Y_b,Y_e,Y_f\right)$	37,574	100
$\left(Y_a,Y_b,Y_e,Y_g\right)$	49,950	70
$\left(Y_b,Y_c,Y_e,Y_f\right)$	2012	90
$\left(Y_b,Y_d,Y_e,Y_f\right)$	15,444	80

shows all the successful cases ($p_{63}$ was recovered). The success rate is for 10 trials.

4. Conclusions

In this study, we changed the fault-injection condition of the AFA for the SHA-256 compression function in the study by Hao et al. and conducted computer experiments. We found that the whole input of the SHA-256 compression function can be recovered with a smaller number of faults. We also demonstrated the results of computer experiments on the AFA for SHACAL-2 and the AFA for the SHA-256 compression, which enabled almost universal forgery of chopMD-MAC. Future work should include an AFA for the SHA-512 compression function.