nach oben

Cryptography and Communications

Erschienen in:

01.03.2015

Complete reverse-engineering of AES-like block ciphers by SCARE and FIRE attacks

verfasst von: Christophe Clavier, Quentin Isorez, Damien Marion, Antoine Wurcker

Erschienen in: Cryptography and Communications | Ausgabe 1/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Despite Kerckhoffs’s principle, proprietary or otherwise secret cryptographic algorithms are still used in real life. For security and efficiency reasons a common design practice simply modifies some parameters of widely used and well studied encryption standards. In this paper, we investigate the feasibility of reverse engineering the secret specifications of an AES-like block cipher by a FIRE attack based on Ineffective Fault Analysis (IFA) or by SCARE techniques based on two models of collision power analysis. In the considered fault or observational models, we demonstrate that an adversary who does not know the secret key can recover the full set of secret parameters of an AES-like software implementation and, in some models, even if it is protected by common Boolean masking and shuffling of independent operations. We thereby intend to demonstrate that protecting the implementation of such AES-like function is not an option even if its specifications are not public.

Vorheriger Artikel Horizontal collision correlation attack on elliptic curves

Nächster Artikel Masking and leakage-resilient primitives: One, the other(s) or both?

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

FIRE: Fault Injection for Reverse Engineering.

SCARE: Side-Channel Analysis for Reverse Engineering.

The two S-Box lookups may be located at different rounds, and possibly on different traces with different plaintexts.

In the case that \(n_{i_{1},j_{1}} =1\), we already learn that \(\gamma _{i_{1}}=\gamma _{j_{1}}\).

Taking account all secret components: S-Box (\(\log _{2}(256!) \simeq 1684\) bits), ShiftRows (4 × 2 bits), MixColumns (4 × 8 bits), RotWord (2 bits), Rcon (8 bits).

Due to the ShiftRows the ciphertext byte related to the collision is located at index \(j^{\prime } = \ell + 4 ((c -\sigma _{c}) \bmod 4)\) where ℓ=j mod 4 and c=⌊j/4⌋.

A mask conversion is applied to masked intermediate values before or at the end of each round to adapt from the r _{o
u
t} of one round to the r _{i
n} of the next one.

Here also the shuffling of other AES operations such as ShiftRows, MixColumns, AddRoundKey, etc. have no influence on the attack proposed in the considered S-Box collisions model.

The opposite case should be rare and is easily detectable by observing a reduction of the number of occurrences of S ⁻¹(0). In that case, simply modify c to change the column of the active cell.

It may happen that less than four values are identified when one or two of them produce multiple extra S ⁻¹(0) values. In such case, these special v values should be counted as many times as their collision order.

Taking account of all secret components: S-Box (\(\log _{2}(256!) \simeq 1684\) bits), ShiftRows (4 × 2 bits), MixColumns (16 × 8 bits), RotWord (2 bits), Rcon (8 bits).

In these cases there are only 2.1 candidates on average.

Actually this figure is certainly overestimated as in many cases there may be no collisions at all amongst the rounds we are interested in. This situation can often be identified with only one or two encryptions.

Biham, E., Shamir, A.: Differential fault analysis of secret key cryptosystems. In: Kaliski, Jr., B.S. (ed.) Advances in Cryptology – CRYPTO ’97, of Lecture Notes in Computer Science, vol. 1294, pp 513–525. Springer-Verlag (1997)

Biryukov, A., Bogdanov, A., Khovratovich, D., Kasper, T.: Collision attacks on AES-based MAC: Alpha-MAC. In: Paillier and Verbauwhede [27], pages 166–180

Bogdanov, A.: Improved side-channel collision attacks on AES. In: Adams, C.M., Miri, A., Wiener, M.J. (eds.) Selected Areas in Cryptography – SAC ’07, of Lecture Notes in Computer Science, vol. 4876, pp 84–95. Springer (2007)

Bogdanov, A.: Multiple-differential side-channel collision attacks on AES. In: Oswald, E., Rohatgi, P. (eds.) Cryptographic Hardware and Embedded Systems – CHES ’08, of Lecture Notes in Computer Science, vol. 5154, pp 30–44. Springer (2008)

Boneh, D., DeMillo, R.A., Lipton, R.J.: On the importance of checking cryptographic protocols for faults (extended abstract). In: Fumy, W. (ed.) Advances in Cryptology – EUROCRYPT ’97, of Lecture Notes in Computer Science, vol. 1233, pp 37–51. Springer-Verlag (1997)

Brier, É., Clavier, C., Olivier, F.: Correlation power analysis with a leakage model. In Joye and Quisquater [15], pages 16–29

Clavier, C.: Secret external encodings do not prevent transient fault analysis. In Paillier and Verbauwhede [27], pages 181–194

Clavier, C.: An improved SCARE cryptanalysis against a secret A3/A8 GSM algorithm. In: McDaniel, P.D., Gupta, S.K. (eds.) International Conference on Information Systems Security – ICISS ’07, of Lecture Notes in Computer Science, vol. 4812, pp 143–155. Springer (2007)

Clavier, C., Wurcker, A.: Reverse engineering of a secret AES-like cipher by ineffective fault analysis. In: Fischer, W., Schmidt, J.-M. (eds.) Fault Diagnosis and Tolerance in Cryptography – FDTC ’13, pp 119–128. IEEE Computer Society Press (2013)

10.

Clavier, C., Gierlichs, B., Verbauwhede, I.: Fault analysis study of IDEA. In: Malkin, T. (ed.) Topics in Cryptology – CT-RSA ’08, of Lecture Notes in Computer Science, vol. 274–287. Springer (2008)

11.

Clavier, C., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Improved collision-correlation power analysis on first order protected AES. In: Preneel, B., Takagi, T. (eds.) Cryptographic Hardware and Embedded Systems – CHES ’11, of Lecture Notes in Computer Science, vol. 6917 , pp 49–62. Springer (2011)

12.

Clavier, C., Isorez, Q., Wurcker, A.: Complete SCARE of AES-like block ciphers by chosen plaintext collision power analysis. In: Paul, G., Vaudenay, S. (eds.) International Conference on Cryptology in India – INDOCRYPT ’13, Lecture Notes in Computer Science, pp 116–135. Springer (2013)

13.

Daudigny, R., Ledig, H., Muller, F., Valette, F.: SCARE of the DES. In: Ioannidis, J., Keromytis, A.D., Yung, M. (eds.) Applied Cryptography and Network Security – ACNS ’05, of Lecture Notes in Computer Science, vol. 3531, pp 393–406. Springer-Verlag (2003)

14.

Guilley, S., Sauvage, L., Micolod, J., Réal, D., Valette, F.: Defeating any secret cryptography with SCARE attacks. In: Abdalla, M., Barreto, P.S.L.M. (eds.) Progress in Cryptology – LATINCRYPT ’10, of Lecture Notes in Computer Science, vol. 6212, pp 273–293. Springer (2010)

15.

Joye, M., Quisquater, J.-J. (eds.): Cryptographic Hardware and Embedded Systems – CHES ’04. In: Proceedings of 6th International Workshop Cambridge, MA, USA, of Lecture Notes in Computer Science. August 11-13, vol. 3156. Springer-Verlag (2004)

16.

Joye, M., Quisquater, J.-J., Yen, S.-M., Yung, M.: Observability analysis – detecting when improved cryptosystems fail. In: Preneel, B. (ed.) Topics in Cryptology – CT-RSA ’02, of Lecture Notes in Computer Science, vol. 2271 , pp 17–29. Springer-Verlag (2002)

17.

Koç, Ç.K., Paar, C. (eds.): Cryptographic Hardware and Embedded Systems – CHES ’00. In: Proceedings of Second International Workshop, Worcester, MA, USA, of Lecture Notes in Computer Science. August 17-18, vol. 1965. Springer-Verlag (2000)

18.

Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) Advances in Cryptology – CRYPTO ’96, of Lecture Notes in Computer Science, vol. 1109, pp 104–113. Springer-Verlag (1996)

19.

Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M.J. (ed.) Advances in Cryptology – CRYPTO ’99, of Lecture Notes in Computer Science, vol. 1666, pp 388–397. Springer-Verlag (1999)

20.

Mayer-Sommer, R.: Smartly Analyzing the Simplicity and the Power of Simple Power Analysis on Smartcards. In Koç and Paar [17], pp. 78–92

21.

Messerges, T.S.: Using Second-Order Power Analysis to Attack DPA Resistant Software. In Koç and Paar [17], pages 238–251

22.

Messerges, T.S., Dabbish, E.A., Sloan, R.H.: Investigations of power analysis attacks on smartcards WOST ’99. In: Proceedings of the USENIX Workshop on Smartcard Technology, USENIX Association. Berkeley, CA, pp 151–162, USA (1999)

23.

National Bureau of Standards. Data Encryption Standard. Federal Information Processing Standard #46, 1977

24.

National Institute of Standards and Technology. Advanced Encryption Standard (AES). Federal Information Processing Standard #197, (2001)

25.

Novak, R.: Side-channel attack on substitution blocks. In: Zhou, J., Yung, M., Han, Y. (eds.) Applied Cryptography and Network Security – ACNS ’03, of Lecture Notes in Computer Science, vol. 2846, pp 307–318. Springer-Verlag (2003)

26.

Novak, R.: Sign-based differential power analysis. In: Chae, K., Yung, M. (eds.) Workshop on Information Security Applications – WISA ’03, of Lecture Notes in Computer Science, vol. 2908, pp 203–216. Springer (2003)

27.

Paillier, P., Verbauwhede, I. (eds.): Cryptographic Hardware and Embedded Systems – CHES ’07. In: Proceedings of 9th International Workshop, Vienna, Austria, of Lecture Notes in Computer Science. September 10–13, vol. 4727. Springer-Verlag (2007)

28.

Réal, D., Dubois, V., Guilloux, A.-M., Valette, F., Drissi, M.: SCARE of an unknown hardware feistel implementation. In: Grimaud, G., Standaert, F.-X. (eds.) Smart Card Research and Advanced Application – CARDIS ’08, of Lecture Notes in Computer Science, vol. 5189, pp 218–227. Springer (2008)

29.

Rivain, M., Roche, T.: SCARE of secret ciphers with SPN structures. In: Sako, K., Sarkar, P. (eds.) Advances in Cryptology – ASIACRYPT ’13, of Lecture Notes in Computer Science, vol. 8269, pp 526–544. Springer-Verlag (2013)

30.

Schramm, K., Wollinger, T.J., Paar, C.: A new class of collision attacks and its application to DES. In: Johansson, T. (ed.) Fast Software Encryption – FSE ’03, of Lecture Notes in Computer Science, vol. 2887, pp 206–222. Springer-Verlag (2003)

31.

Schramm, K., Leander, G., Felke, P., Paar, C.: A collision-attack on AES: combining side channel- and differential-attack. In Joye and Quisquater [15], pages 163–175

32.

Yen, S.-M., Joye, M.: Checking before output may not be enough against fault-based cryptanalysis. IEEE Trans. Comput. 49(9), 967–970 (2000)CrossRefMATH

Titel: Complete reverse-engineering of AES-like block ciphers by SCARE and FIRE attacks
verfasst von: Christophe Clavier
Quentin Isorez
Damien Marion
Antoine Wurcker
Publikationsdatum: 01.03.2015
Verlag: Springer US
Erschienen in: Cryptography and Communications / Ausgabe 1/2015
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-014-0112-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2015

The distributions of individual bits in the output of multiplicative operations

Masking and leakage-resilient primitives: One, the other(s) or both?

Guest Editorial

Threshold implementations of small S-boxes

Construction of RSBFs with improved cryptographic properties to resist differential fault attack on grain family of stream ciphers

A survey of fault attacks in pairing based cryptography

Premium Partner