Efficiency And Fault-Tolerance Of Power Analysis Attack On Block Ciphers

The block cipher is one of the most widely used cryptosystems.It is a type of symmetric ciphers, which uses the same key for both encryption and decryption. Es-sentially, a block cipher is a permutation with key. The plaintext is divided into several blocks, and each block yields an output block with the same size. The current ciphers have high security in terms of their mathematical structures, which are strong against the mathematical methods. However, the mathematical methods have some limitations to analysis on the security of cryptoequipment, because they are mostly concerned with plaintexts and ciphertexts.Since timing attack which observes variations on performing time was proposed by Kocher in1996[1], the field of side-channel attacks and countermeasures has grad-ually become an important branch of cryptography. Side-channel attacks, which pay close attention to the intermediate values, are based on the leakage of information from the physical implementation of a cryptosystem, rather than the traditional meth-ods such as brute force or theoretical weaknesses. Although the information of timing, electromagnetism, or even sound can be exploited to attack a cryptosystem, power con-sumption analysis is one of the most effective means of cryptanalysis. In practice, these techniques are typically implemented on cryptographic chips, such as microprocessor, FPGA, and ASIC[2]. In1999, Kocher et al. presented differential power analysis which can recover secret keys by analyzing the information of instantaneous power consump-tion of cryptographic chips[3,4].Template attack was introduced by Chari et al. in2002. The attacker matches the recorded power traces with the power consumption character-istics which are called templates for different key hypotheses in the template attack[5]. In2004, Brier et al. proposed correlation power analysis which recovers secret keys with the correlation coefficient model[6].In this dissertation, we focus on the power analysis attack on block ciphers. First, the fault-tolerant linear collision attack and bitwise collision attack are proposed, and performed on AES for example. Second, the fault-tolerant linear collision attack is im-proved, which is named fault-tolerant bitwise collision attack. At last, for the different S-boxes of DES, DES-E, AES and Serpent, we analysis and compare the efficiencies of the correlation power analysis, template attack and bitwise collision attack respectively.1. Fault-tolerant linear collision attackThe correlation power analysis[6] and collision attack are the common methods of power analysis attack. Bogdanov et al. proposed the concept of test of chain[7], which combines correlation power analysis with collision attack. They specified that their attack is more efficient than either stand-alone correlation power analysis or collision attacks. Although the test of chain discussed the high efficiency of their combined attack, they did not give a practical attack scheme. On the other hand, their method can only correct the errors in correlation power analysis, but can not in the part of collision attack. In other words, once a step error occurs in a path of the chain, it will lead to consecutive errors. And the errors may take place in the entire path, which will result a failed attack. Indeed, the efficiency of typical collision attack is much lower than correlation power analysis, which may lead to the unavailability of Bogdanov’s method.On the basis of test of chain, a concept of fault-tolerant chain is presented. The first key byte k1of AES is taken for example. In the fault-tolerant chain, k1is the only free variable. In other words, the independent relations between k1and the other15key bytes are constructed by collision attack. k1(?)ki=△1,i(2≤i≤16).(4) If one of these expressions is wrong, it does not affect the results of other expressions. In practice, the correlation-enhanced collision attack [F15] is employed for collision detection.In the process of fault-tolerant linear collision attack, not only is the fault-tolerant chain constructed, but also the correlation power analysis is used to sort and filter the key candidates. A threshold ThCPA is given to obtain the sets of key-byte candidates. If a key in the candidate set satisfies the relation expressions (1), it is mostly the correct key. Since the key bytes are independent of each other, a threshold ThCA can be given to tolerant the errors in collision attack. ThCA is the maximum of wrong key bytes. Then the correct key can be searched.The efficiencies of fault-tolerant linear collision attack and test of chain attack are compared in simulations. When the success rates of the two attacks are both above90%, the experimental results show that the trace number of our attack is less than that of Bogdanov’s attack.In order to reduce the search space further, the fault-identification mechanism is presented, which can identify the position of wrong key bytes with high probability. We discuss the probabilities of cases in which part errors occur, i.e. whether errors occur in correlation power analysis or in collision attack. At last, we analysis the relation between the success rate and ThCPA, and suggest ThCPA=10, which corresponds to the maximum success rate of our attack.2. Bitwise collision attack based on second-distanceIn2010, Moradi et al. proposed correlation-enhanced collision attack[8] on hard-ware implementation of AES. However, their inefficiency is a serious problem. In practice, due to its bytewise operations, numbers of power traces are needed to acquire256average traces in correlation-enhanced collision attack. The traces are needed to be averaged on a oscilloscope and stored manually. Or all of them are automatically stored, and then handled in MATLAB. But the process of trace acquisition, storage and averaging is complex and time-consuming.An attack is expected to be fast and efficient as far as possible. So we propose a more flexible attack, which can distinguish the collisions by bit instead of byte based on the trace distance model. Take the bitwise collision attack performed on AES for example. An all-zero plaintext P0and8special plaintexts Pα{α=1,2,...,8) are chosen. Each Pα contains16equal bytes pa. The a-th bit of pα is1, the other bits are0. After pα XORing with key, the inputs of S-box are the changed key bytes whose the ath bits are changed, and their hamming weights are changed too. Since P0will cause no changes, after a comparison between the differences of hamming weights of different inputs with P" and P0, wether the αth bits of different key bytes are equal can be deduced. P0and P1are chosen for example to introduce the basic idea.△HW0and AHW1denote the difference of the hamming weights of inputs of the first two S-boxes with P0or P1. The following conditions (2) and (3) are used to determine whether the first bits of k1and k2are equal:· If and only if u1-v1,|△HW0-△HWX1|=0.(5)· If and only if u1(?)v1,|△HW0-△HW1|=2.(6) In practice, the trace distance model is used to approximate the hamming weight model. So the collision and non-collision can be distinguished.Another distance model is found to implement bitwise collision attack. If the operation of first-order distance is addition instead of substruction, and the second-order distance is unchanged, the conclusions are contrary to those above.Bitwise collision attack has been implemented on an AT89S52singlechip for prac-tical experiment. The differences of average traces and the second-order distances on8bit positions are shown. We also made some simulations on trace number, opera-tion time and point number to evaluate the efficiency of our attack. The experimental results show that the efficiency of our attack is higher than correlation-enhanced col-lision attack. And in practice, the operation time of our attack is only8%of that of correlation-enhanced collision attack. The results of bitwise collision attack and correlation-enhanced collision attack are both the XORed value of key bytes. And the bitwise collision attack is more ef-ficient than correlation-enhanced collision attack. So the fault-tolerant chain can be constructed by bitwise collision. The improved fault-tolerant linear collision attack is named fault-tolerant bitwise collision attack. The experimental data show that the fault-tolerant bitwise collision attack is better than the fault-tolerant linear collision attack.3. The efficiencies of power analysis attack based on S-boxes of block ciphersIn1976, the National Security Agency selected a slightly modified version of DES, which was published as an official Federal Information Processing Standard (FIPS) for the United States[9,10]. The security of DES depends on the difficulty in computational complexity and time consumption. With the development of computer science and network technology, the current ability of calculation has been a threat to DES. In1997, the U.S. National Institute of Standards and Technology (NIST)initiated the solicitation of AES, and the Rijndael cipher was selected in2000. Serpent is also one of the AES candidates[11]. Currently the design of block ciphers focuses on S-box, permutation and key schedule. S-box firstly appeared in Lucifer cipher, and be wide-ly used with DES. S-box is the only nonlinear components of block ciphers, thus the security strength of ciphers are mostly determined by their S-boxes.In one round, DES uses8S-boxes of which each has6-bit input and4-bit output. AES uses16S-boxes of which each has8-bit input and8-bit output. Serpent uses32S-boxes of which each has4-bit input and4-bit output. The block of DES is64bits, and those of AES and Serpent are both128bits. In order to compare the efficiencies in reason, an expansion of DES named DES-E is assumed, which used128-bit block and16S-boxes in one round.Under the same experimental environment, we research on the efficiency of attack on a single S-box in one round. Suppose that the success rate of one round is at least0.5, it is easy to deduce that the success rate on a single DES S-box is0.917, and those of DES-E and AES are both0.9576, and that of Serpent is0.9786. In the correlation power analysis, as S-box disrupts the linear law of data, the at-tack object is the output of S-box. Several traces are needed to compute a correlation coefficient, so one sample point is enough to realize attack. According to the experi-mental results, the most number of traces are needed for Serpent, which is the strongest against correlation power analysis, and AES is the weakest. Thus, low wide S-box is stronger than high wide S-box against power analysis attack.In the template attack, in order to construct templates, we need to know the ac-curate hamming weight, so the attack object is the input of S-box.10sample points are chosen on one trace to match templates precisely. According to the experimental results, AES is the strongest, and DES is the weakest.In the bitwise collision attack, the idea depends on the hamming weights of inter-mediate value, so the attack object is the input of S-box.10sample points are chosen to measure the differences between traces. The experimental results show that AES is the strongest and Serpent is the weakest. In this case, high wide S-box is stronger than low wide S-box.The different S-boxes have advantages and disadvantages against different power analysis attacks. To meet the specific needs, the design of ciphers may follow with interest the security strength of S-boxes under a variety of circumstances.