logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 3: 032110(2018) https://doi.org/10.1007/s11432-017-9209-0

Impossible meet-in-the-middle fault analysis on the LED lightweight cipher in VANETs

More info
  • ReceivedMay 10, 2017
  • AcceptedJul 19, 2017
  • PublishedJan 12, 2018

Abstract

With the expansion of wireless technology, vehicular ad-hoc networks (VANETs) are emerging as a promising approach for realizing smart cities and addressing many serious traffic problems, such as road safety, convenience, and efficiency. To avoid any possible rancorous attacks, employing lightweight ciphers is most effective for implementing encryption/decryption, message authentication, and digital signatures for the security of the VANETs. Light encryption device (LED) is a lightweight block cipher with two basic keysize variants: LED-64 and LED-128. Since its inception, many fault analysis techniques have focused on provoking faults in the last four rounds to derive the 64-bit and 128-bit secret keys. It is vital to investigate whether injecting faults into a prior round enables breakage of the LED. This study presents a novel impossible meet-in-the-middle fault analysis on a prior round. A detailed analysis of the expected number of faults is used to uniquely determine the secret key. It is based on the propagation of truncated differentials and is surprisingly reminiscent of the computation of the complexity of a rectangle attack. It shows that the impossible meet-in-the-middle fault analysis could successfully break the LED by fault injections.


References

[1] Misener A J. Vehicle-infrastructure integration (VII) and safety: rubber and radio meets the road in California. Intellimotion, 2005, 11: 1--12. Google Scholar

[2] Hubaux P J, Capkun S, Luo J. The security and privacy of smart vehicles. IEEE Secur Priv, 2004, 2: 49--55. Google Scholar

[3] Raya M, Hubaux P J. Securing vehicular ad hoc networks. J Com Secur, 2007, 15: 39--68. Google Scholar

[4] Raya M, Papadimitratos P, Hubaux P J. Securing vehicular communications. IEEE Trans Dependable Secure Comput, 2006, 13: 8--15. Google Scholar

[5] Zhang W T, Bao Z Z, Lin D D, et al. RECTANGLE: a bit-slice lightweight block cipher suitable for multiple platforms. Sci China Inf Sci, 2015, 58: 122103. Google Scholar

[6] Li L, Liu B T, Wang H. QTL: a new ultra-lightweight block cipher. Microprocessor Microsy, 2016, 45: 45--55. Google Scholar

[7] Engels D, Saarinen O J M, Schweitzer P, et al. The Hummingbird-2 lightweight authenticated encryption algorithm. In: Proceedings of the 7th International Conference on RFID Security and Privacy, Amherst, 2011. 19--31. Google Scholar

[8] Hong D, Sung J, Hong S, et al. HIGHT: a new block cipher suitable for low-resource device. In: Proceedings of the 8th International Conference on Cryptographic Hardware and Embedded Systems, Yokohama, 2006. 46--59. Google Scholar

[9] Lim H C, Korkishko T. mCrypton-a lightweight block cipher for security of low-cost RFID tags and sensors. In: Proceedings of the 6th International Conference on Information Security Applications, Jeju Island, 2005. 243--258. Google Scholar

[10] Ojha K S, Kumar N, Jain K. TWIS-a lightweight block cipher. In: Proceedings of the 5th International Conference on Information Systems Security, Kolkata, 2009. 280--291. Google Scholar

[11] Bogdanov A, Knudsen L R, Lender G, et al. PRESENT: an ultra-lightweight block cipher. In: Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems, Vienna, 2007. 450--466. Google Scholar

[12] Wu W L, Zhang L. LBlock: a lightweight block cipher. In: Proceedings of the 9th International Conference on Applied Cryptography and Network Security, Nerja, 2011. 327--344. Google Scholar

[13] Dai X, Huang Y, Chen L, et al. VH: a lightweight block cipher based on dual pseudo-random transformation. In: Proceedings of International Conference on Cloud Computing and Security, Nanjing, 2015. 3--13. Google Scholar

[14] Guo J, Peyrin T, Poschmann A, et al. The LED block cipher. In: Proceedings of the 13th International Conference on Cryptographic Hardware and Embedded Systems, Nara, 2011. 326--341. Google Scholar

[15] Mendel F, Rijmen V, Toz D, et al. Differential analysis of the LED block cipher. In: Proceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, 2012.łinebreak 190--207. Google Scholar

[16] Isobe T, Shibutani K. Security analysis of the lightweight block ciphers XTEA, LED and Piccolo. In: Proceedings of the 17th Australasian Conference on Information Security and Privacy, Wollongong, 2012. 71--86. Google Scholar

[17] Nikolic I, Wang L, Wu S. Cryptanalysis of round-reduced LED. In: Proceedings of International Workshop on Fast Software Encryption, Washington, 2013. 112--129. Google Scholar

[18] Soleimany H. Probabilistic slide cryptanalysis and its applications to LED-64 and Zorro. In: Proceedings of International Workshop on Fast Software Encryption, London, 2014. 373--389. Google Scholar

[19] Jeong K, Lee C. Differential fault analysis on block cipher LED-64. In: Future Information Technology, Application, and Service. Berlin: Springer, 2012. 747--775. Google Scholar

[20] Li W, Gu D W, Xia X L, et al. Single byte differential fault analysis on the LED lightweight cipher in the wireless sensor network. Int J Comput Intell Syst, 2012, 5: 896--904. Google Scholar

[21] Jovanovic P, Kreuzer M, Polian I. A fault attack on the LED block cipher. In: Proceedings of the 3rd International Conference on Constructive Side-Channel Analysis and Secure Design, Darmstadt, 2012. 120--134. Google Scholar

[22] Zhao X J, Guo S Z, Zhang F. Improving and evaluating differential fault analysis on LED with algebraic techniques. In: Proceedings of the 2013 Workshop on Fault Diagnosis and Tolerance in Cryptography, Washington, 2013. 41--51. Google Scholar

[23] Ghalaty F N, Yuce B, Schaumont P. Differential fault intensity analysis on PRESENT and LED block ciphers. In: Proceedings of the 6th International Workshop on Constructive Side-Channel Analysis and Secure, Berlin, 2015.łinebreak 174--188. Google Scholar

[24] Li W, Zhang W W, Gu D W, et al. Impossible differential fault analysis on the LED lightweight cryptosystem in the vehicular ad-hoc networks. IEEE Trans Depend Secure Comput, 2016, 13: 84--92. Google Scholar

[25] Boneh D, DeMillo A R, Lipton J R. On the importance of eliminating errors in cryptgraphic computations. J Cryptol, 2001, 14: 101--119. Google Scholar

[26] Boneh D, DeMillo A R, Lipto J R, et al. On the importance of checking cryptographic protocols for faults. In: Proceedings of the 16th Annual International Conference on Theory and Application of Cryptographic Techniques, Konstanz, 1997. 37--51. Google Scholar

[27] Dusart P, Letourneux G, Vivolo O. Differential fault analysis on A.E.S. In: Proceedings of International Conference on Applied Cryptography and Network Security, Kunming, 2003. 293--306. Google Scholar

[28] Bl$\ddot{o}$mer J, Seifert J P. Fault based cryptanalysis of the advanced encryption standard (AES). In: Proceedings of International Conference of Financial Cryptography, Guadeloupe, 2003. 162--181. Google Scholar

[29] Zhang F, Zhao X J, He W, et al. Low-cost design of stealthy hardware trojan for bit-level fault attacks on block ciphers. Sci China Inf Sci, 2017, 60: 048102. Google Scholar

[30] Zhao X J, Zhang F, Guo S Z, et al. Optimal model search for hardware-trojan-based bit-level fault attacks on block ciphers. Sci China Inf Sci, 2018, 61: 039106. Google Scholar

[31] Liao N, Cui X X, Liao K, et al. Improving DFA attacks on AES with unknown and random faults. Sci China Inf Sci, 2017, 60: 042401. Google Scholar

[32] Derbez P, Fouque A P, Lereateux D. Meet-in-the-middle and impossible differential fault analysis on AES. In: Proceedings of International Workshop of Cryptographic Hardware and Embedded Systems, Nara, 2011. 274--291. Google Scholar

  • Figure 1

    Structure of LED.

  • Table 1   Summary of fault analysis on LED
    Type First fault location $\sharp$Faults on LED-64 $\sharp$Faults on LED-128 Ref.
    DFA $r$-$2$ 1 $-$ [19]
    3 6 [20]
    1 2 [21]
    AFA $r$-$2$ 1 2 [22]
    DFIA $r$ 14 28 [23]
    IDFA $r$-$3$ 48 96 [24]
    IMFA $r$-$4$ 44.2 88.4 This paper
  • Table 2   Versions of LED
    Version Key size Block size Rounds Key schedule
    LED-64 64 64 32 $K=k_1$
    LED-128 128 64 48 $K=k_1||k_2$
  • Table 3   Notations of LED
    Notation Description
    $x$ The 64-bit plaintext
    $y$, $\hat{y}$ The 64-bit correct and faulty ciphertexts
    $k_1,$ $k_2$ The 64-bit subkeys from the secret key $K$
    $r$ The number of rounds with $r~\in~\{32,~48\}$
    $\alpha_{l}$, $\beta_{l}$, $\gamma_{l}$, $\delta_{l}$ The 64-bit output of the AC, SC, SR, and MC layers in the $l$-th round with $1~\leq~l~\leq~r$
    $\hat~\alpha_{l}$, $\hat~\beta_{l}$, $\hat~\gamma_{l}$, $\hat~\delta_{l}$ The 64-bit faulty output of the AC, SC, SR, and MC layers in the $l$-th round with $1~\leq~l~\leq~r$
    $\beta_r$, $\hat{\beta}_r$ The values before addition with the correct subkey $k_1$, and $\beta_r=~y\oplus~k_1,$ $\hat{\beta}_r=\hat{y}~\oplus~k_1$
    $g$ The guess for $k_1$
    $z$, $\hat{z}$ The values obtained by xoring the ciphertexts with the guess for the subkey, and $z=~y\oplus~g$,
    $\hat{z}=\hat{y}~\oplus~g$
    $\mu$, $\hat{\mu}$ The values derived from $z$ in the same way as $\delta_{r-1}$ is derived from $\beta_r$
    $\omega$, $\hat{\omega}$ The values derived from $\mu$ in the same way as $\beta_{r-1}$ is derived from $\delta_{r-1}$
    IAC, ISC, ISR, IMC The inverse operation of the AC, SC, SR, and MC layers
  • Table 4   The relation between the numbers of nonzero input and output nibbles in MixColumnsSerial
    0 1 2 3 4
    0 1 0 0 0 0
    1 0 0 0 0 60
    2 0 0 0 360 990
    3 0 0 360 3600 9540
    4 0 60 990 9540 40035
  • Table 5   The probability that a wrong key guess survives a test
    $d$ $p_1(d)$ $p_2(d)$ $p_1(d)~\cdot~p_2(d)$
    0 0 0 0
    1 60/50625 1 60/50625
    2 990/50625 990/1350 98010/68343750
    3 9540/50625 9540/13500 91011600/683437500
    4 40035/50625 40035/50625 1602801225/2562890625
    $\sum$ $-$ $-$ 0.774
  • Table 6   The subkey recovery on accuracy by RMSE
    Group 1st intersection 11th intersection 22nd intersection 33rd intersection 44th intersection 55th intersection
    $G_1$ 197.33 61.09 16.59 4.47 1.19 0
    $G_2$ 197.30 60.72 16.61 4.47 1.18 0
    $G_3$ 197.28 60.97 16.63 4.46 1.18 0
    $G_4$ 197.10 61.07 16.64 4.49 1.21 0
    $G_5$ 197.17 61.12 16.61 4.47 1.16 0
  • Table 7   The subkey recovery on reliability
    Group 1st intersection 11th intersection 22nd intersection 33rd intersection 44th intersection 55th intersection
    $G_1$ 0% 0% 0% 0% 22.5% 100%
    $G_2$ 0% 0% 0% 0% 25.0% 100%
    $G_3$ 0% 0% 0% 0% 24.5% 100%
    $G_4$ 0% 0% 0% 0% 22.0% 100%
    $G_5$ 0% 0% 0% 0% 22.0% 100%

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

京ICP备18024590号-1