logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 3: 032101(2018) https://doi.org/10.1007/s11432-016-0616-4

Right or wrong collision rate analysis without profiling: full-automatic collision fault attack

More info
  • ReceivedOct 3, 2016
  • AcceptedNov 24, 2016
  • PublishedMay 22, 2017

Abstract

In CHES 2010, Fault Sensitivity Analysis (FSA) on Advanced Encryption Standard (AES) hardwarecircuit based on S-box setup-time acquired by injecting clock glitches is proposed.Soon after, some improvements of FSA were presented such as colliding timing characteristics from Moradi et al.However, the acquisition of timing characteristicsrequires complex procedure due to the very gradual decrease of clock glitch cycleand the heavy requirements of setup-time samples.In HOST 2015, Wang et al. presented template-based right or wrong collision rate attack to improve the efficiency of FSA,but its profiling and plaintexts-choice procedures required too many encryptions.In this paper, we fix only one specific clock glitch cycle,and take the right or wrong collision rate as a collision distinguisher.So, the whole process is a non-profiling collision attack which can be executed automaticallywithout massive pre-computations and interactions between PC and signal generator.According to the experiments, 256 encryptions are enough for exactly decidingwhether two plaintext bytes can induce an S-box collision.Compared with the existing power analysis and FSA-based attacks on AES hardware,it costs negligible time (about 6.65 s) and storage space (only one byte), and no offline computationsfor finding the collision between two masked S-boxes.Furthermore, our study shows that the signal-to-noise ratio in FSA-based attacksis much higher than power-based attacks.


References

[1] Kocher P. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Advances in Cryptology---CRYPTO96. Berlin: Springer, 1996. 104--113. Google Scholar

[2] Bogdanov A. Improved side-channel collision attacks on AES. In: Selected Areas in Cryptography. Berlin: Springer, 2007. 84--95. Google Scholar

[3] Bogdanov A. Multiple-differential side-channel collision attacks on AES. In: Cryptographic Hardware and Embedded Systems---CHES 2008. Berlin: Springer, 2008. 30--44. Google Scholar

[4] Schramm K, Leander G, Felke P, et al. A collision-attack on AES combining side channel- and differential-attack. In: Cryptographic Hardware and Embedded Systems---CHES 2004. Berlin: Springer, 2004. 163--175. Google Scholar

[5] Schramm K, Wollinger T J, Paar C. A new class of collision attacks and its application to DES. In: Fast Software Encryption. Berlin: Springer, 2003. 206--222. Google Scholar

[6] Brier E, Clavier C, Olivier F. Correlation power analysis with a leakage model. In: Cryptographic Hardware and Embedded Systems---CHES 2004. Berlin: Springer, 2004. 16--29. Google Scholar

[7] Bogdanov A, Kizhvatov I. Beyond the limits of DPA: combined side-channel collision attacks. IEEE Trans Comput, 2012, 61: 1153--1164. Google Scholar

[8] Clavier C, Feix B, Gagnerot G, et al. Improved collision-correlation power analysis on first order protected AES. In: Cryptographic Hardware and Embedded Systems---CHES 2011. Berlin: Springer, 2011. 49--62. Google Scholar

[9] Oswald E, Mangard S, Herbst C, et al. Practical second-order DPA attacks for masked smart card implementations of block ciphers. In: Topics in Cryptology---CT-RSA 2006. Berlin: Springer, 2006. 192--207. Google Scholar

[10] Chair S, Rao J R, Rohatgi P. Template attacks. In: Cryptographic Hardware and Embedded Systems---CHES 2002. Berlin: Springer, 2003. 13--28. Google Scholar

[11] Biham E, Shamir A. Differential fault analysis of secret key cryptosystems. In: Advances in Cryptology---CRYPTO97. Berlin: Springer, 1997. 513--525. Google Scholar

[12] Ege B, Eisenbarth T, Batina L. Near collision side channel attacks. In: Selected Areas in Cryptography---SAC 2015 Cryptology. Berlin: Springer. 2015. 277--292. Google Scholar

[13] Ye X, Chen C, Eisenbarth T. Non-linear collision analysis. In: Radio Frequency Identification: Security and Privacy Issues. Berlin: Springer, 2014. 198--214. Google Scholar

[14] Li Y, Sakiyama K, Gomisawa S, et al. Fault sensitivity analysis. In: Cryptographic Hardware and Embedded Systems, CHES 2010. Berlin: Springer, 2010. 320--334. Google Scholar

[15] Moradi A, Mischke O, Eisenbarth T. Correlation-enhanced power analysis collision attack. In: Cryptographic Hardware and Embedded Systems, CHES 2010. Berlin: Springer, 2010. 125--139. Google Scholar

[16] Moradi A, Mischke O, Paar C, et al. On the power of fault sensitivity analysis and collision side-channel attacks in a combined setting. In: Cryptographic Hardware and Embedded Systems---CHES 2011. Berlin: Springer, 2011. 292--311. Google Scholar

[17] Wang A, Chen M, Wang Z Y, et al. Fault rate analysis: breaking masked AES hardware implementations efficiently. IEEE Trans Circ Syst, 2013, 60: 517--521. Google Scholar

[18] Ren Y T, Wang A, Wu L J. Transient-steady effect attack on block ciphers. In: Cryptographic Hardware and Embedded Systems---CHES 2015. Berlin: Springer, 2015. 433--450. Google Scholar

[19] Wang Q, Wang A, Wu L J, et al. Template attack on masking AES based on fault sensitivity analysis. In: Proceedings of IEEE International Symposium on Hardware Oriented Security and Trust (HOST 2015), Washington, 2015. 96--99. Google Scholar

[20] Mangard S, Aigner M, Dominikus S. A highly regular and scalable AES hardware architecture. IEEE Trans Comput, 2003, 52: 483--491. Google Scholar

[21] Canright D. A very compact S-box for AES. In: Cryptographic Hardware and Embedded Systems---CHES 2005. Berlin: Springer, 2005. 441--455. Google Scholar

[22] Paar C. Efficient VLSI architectures for bit-parallel computation in Galois fields. Dissertation for Ph.D. Degree. Essen: University of Essen, 1994. Google Scholar

[23] Rudra A, Dubey P K, Jutla C S, et al. Efficient Rijdael encryption implementation with composite field arithmetic. In: Cryptographic Hardware and Embedded Systems---CHES 2001. Berlin: Springer, 2001. 171--184. Google Scholar

[24] Morioka S, Satoh A. An optimized S-box circuit architecture for low power AES design. In: Cryptographic Hardware and Embedded Systems---CHES 2002. Berlin: Springer, 2003. 172--186. Google Scholar

[25] Canright D, Batina L. A very compact “perfectly masked S-box for AES. In: Applied Cryptography and Network Security. Berlin: Springer, 2008. 446--459. Google Scholar

[26] Genelle L, Prouff E, Quisquater M. Thwarting higher-order side channel analysis with additive and multiplicative maskings. In: Cryptographic Hardware and Embedded Systems---CHES 2011. Berlin: Springer, 2011. 240--255. Google Scholar

[27] Kim H, Hong S, Lim J. A fast and provably secure higher-order masking of AES S-box. In: Cryptographic Hardware and Embedded Systems---CHES 2011. Berlin: Springer, 2011. 95--107. Google Scholar

[28] Endo S, Sugawara T, Homma N, et al. An on-chip glitchy-clock generator for testing fault injection attacks. J Cryptogr Eng, 2011, 1: 265--270. Google Scholar

  •   

    Algorithm 2 RW collision rate analysis on two masked S-boxes
    Pre-computation stage:
    1: Determine the maximum and minimum setup-time $t_1$ and $t_2$ of S-box circuit.
    2: Choose a glitch cycle $t$ such that $t_2<t<t_1$.
    3: Determine threshold $\rho_0$ of distinguisher in the case thatglitch cycle is $t$.
    Online stage:
    1: Under the normal clock, encrypt a random plaintext $P$ correctly.
    (Two ciphertext and subkey bytes corresponding to $S_1,~S_2$ of round 10 are denoted by $c_1,c_2,k_1,k_2$).
    2: Inject a glitch whose cycle is $t$ into round 10 and encrypt $P$ for $n$ times.
    3: Compare the outputs of step 2, $n$ pairs $(c_1,c_2)$, with the correct value $c_1$ and $c_2$.
    4: Compute the probability (or the number) $\rho$ of RW collision.
    5: If $\rho~\geq~\rho_0$, then $x_1=x_2$, else $x_1\neq~x_2$.
    6: If collision is decided, carry out key recovery stage, else repeat online stage.
    Key recovery stage:
    1: For a decided collision, $k_1\oplus~k_2=c_1\oplus~c_2$ holds.

  • Table 1   The efficiency comparisons of six methods for finding a collision
    Item CEPA [15] CCPA [8] CTC [16] FRA [17] T-RWCRA [19] This paper
    Attack channel Power Power Fault Fault Fault Fault
    Num of plaintexts 256 256 256 256 $256~\times~10$ 256
    Num of encryptions $>~5~\times~10^3$ $>~2~\times~10^3~\times~256$ $10^6$ $8~\times~10^4$ $256~\times~10$ $65~536$
    Num of pre-encryptions 0 0 0 $<~1000$ $>~300000$ $<~1000$
    Enc time (s) $>~500$ $>~200~\times~256$ 100 $<~8.1$ $>~30$ $<~6.65$
    Recorded samples 512 $>~4~\times~10^3$ 512 40 256 (templates) 0
    Space occupation (bytes) $2~\times~10^6$ $>~1.6~\times~10^7$ 2048 80 1024 + 4096 1
    Offline complexity 256 $C_{\rho_{256}}$ 256 $C_{\rho_{2000}}$ 256 $C_{\rho_{256}}$ 0 0 0
    Num of glitches 50 40 1 1
    Serial/parallel availability Both Serial Both Serial Both Both
    Extra assumption Need No need Need No need No need No need

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号