User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Unified and optimized linear collision attacks and their application in a non-profiled setting

Primary tabs

download
  • Open access
  • PDF
  • 430.34 K
Gérard, Benoît [UCL] Standaert, François-Xavier [UCL]

Side-channel collision attacks are one of the most investigated techniques allowing the combination of mathematical and physical cryptanalysis. In this paper, we discuss their relevance in the security evaluation of leaking devices with two main contributions. On the one hand, we suggest that the exploitation of linear collisions in block ciphers can be naturally re-written as a Low Density Parity Check Code decoding problem. By combining this re-writing with a Bayesian extension of the collision detection techniques, we succeed in improving the efficiency and error tolerance of previously introduced attacks. On the other hand, we provide various experiments in order to discuss the practicality of such attacks compared to standard DPA. Our results exhibit that collision attacks are less efficient in classical implementation contexts, e.g. 8-bit microcontrollers leaking according to a linear power consumption model.We also observe that the detection of collisions in software devices may be difficult in the case of optimized implementations, because of less regular assembly codes. Interestingly, the soft decoding approach is particularly useful in these more challenging scenarios. Finally, we show that there exist (theoretical) contexts in which collision attacks succeed in exploiting leakages whereas all other non-profiled side-channel attacks fail.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès libre
Publication date 2013
Language Anglais
Journal information "Journal of Cryptographic Engineering" - Vol. 3, no.1, p. 45-58 (2013)
Peer reviewed yes
Publisher Springer ((Germany) Heidelberg)
issn 2190-8508
e-issn 2190-8516
Publication status Publié
Affiliation UCL - SST/ICTM/ELEN - Pôle en ingénierie électrique
Links
  1. Bennatan A., Burshtein D., Design and analysis of nonbinary LDPC codes for arbitrary discrete-memoryless channels, 10.1109/tit.2005.862080
  2. Bogdanov, A.: Improved side-channel collision attacks on AES. In: Adams, C.M., Miri, A., Wiener, M.J. (eds.) Selected Areas in Cryptography-SAC 2007, vol. 4876 of LNCS, pp. 84–95. Springer, Heidelberg (2007)
  3. Bogdanov, A.: Multiple-differential side-channel collision attacks on AES. In: Oswald, E., Rohatgi, P. (eds.) Cryptographic Hardware and Embedded Systems-CHES 2008, vol. 5154 of LNCS, pp. 30–44. Springer, Heidelberg (2008)
  4. Bogdanov, A., Kizhvatov, I.: Beyond the limits of DPA: combined side-channel collision attacks. IEEE Trans. Comput. 61(8), 1153–1164 (2011)
  5. Brier, E., Clavier, C., Olivier, F.: Correlation power analysis with a leakage model. In: Joye, M., Quisquater, J.-J. (eds.) Cryptographic Hardware and Embedded Systems-CHES 2004, vol. 3156 of LNCS, pp. 16–29. Springer, Heidelberg (2004)
  6. Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In: Kaliski, B., Koç, C.K., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems-CHES 2002, vol. 2523 of LNCS, pp. 13–28. Springer, Heidelberg (2003)
  7. 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 2011, vol. 6917 of LNCS, pp. 49–62. Springer, Heidelberg (2011)
  8. Doget Julien, Prouff Emmanuel, Rivain Matthieu, Standaert François-Xavier, Univariate side channel attacks and leakage modeling, 10.1007/s13389-011-0010-2
  9. Gallager R., Low-density parity-check codes, 10.1109/tit.1962.1057683
  10. Gérard, B., Standaert, F.-X.: Unified and optimized linear collision attacks and their application in a non-profiled setting. In: Prouff, E., Schaumont, P. (eds.) Cryptographic Hardware and Embedded Systems-CHES 2012, vol. 7428 of LNCS, pp. 175–192. Springer, Heidelberg (2012)
  11. Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M.J. (ed.) Advances in Cryptology-CRYPTO 1999, vol. 1666 of LNCS, pp. 388–397. Springer, Heidelberg (1999)
  12. Ledig, H., Muller, F., Valette, F.: Enhancing collision attacks. In: Joye, M., Quisquater, J.-J. (eds.) Cryptographic Hardware and Embedded Systems-CHES 2004, vol. 3156 of LNCS, pp. 176–190. Springer, Heidelberg (2004)
  13. Lomne, V., Roche, T.: Collision-correlation attack against some 1st-order Boolean masking schemes in the context of secure devices. In: Prouff, E. (ed.) Constructive Side-Channel Analysis and Secure Design: COSADE, LNCS. Springer (2013, to appear)
  14. Mangard, S.: Hardware countermeasures against DPA? a statistical analysis of their effectiveness. In: Okamoto, T. (ed.) Topics in Cryptology-CT-RSA 2004, vol. 2964 of LNCS, pp. 222–235. Springer, Heidelberg (2004)
  15. Moradi, A., Mischke, O., Eisenbarth, T.: Correlation-enhanced power analysis collision attack. In: Mangard, S., Standaert, F.-X. (eds.) Cryptographic Hardware and Embedded Systems-CHES 2010, vol. 6225 of LNCS, pp. 125–139. Springer, Heidelberg (2010)
  16. Moradi, A.: Statistical tools flavor side-channel collision attacks. In: Johansson, T., Pointcheval, D. (eds.) Advances in Cryptology-EUROCRYPT 2012, vol. 7237 of LNCS, pp. 428–445. Springer, Heidelberg (2012)
  17. Poettering, B.: Fast AES implementation for Atmel’s AVR microcontrollers. http://point-at-infinity.org/avraes/
  18. Renauld, M., Standaert, F.-X., Flandre, D.: Information theoretic and security analysis of a 65-nanometer DDSLL AES S-box. In: Preneel, B., Takagi, T. (eds.) Cryptographic Hardware and Embedded Systems-CHES 2011, vol. 6917 of LNCS, pp. 223–239. Springer, Heidelberg (2011)
  19. Schindler, W., Lemke, K., Paar, C.: A stochastic model for differential side channel cryptanalysis. In: Rao, J., Sunar, B. (eds.) Cryptographic Hardware and Embedded Systems-CHES 2005, vol. 3659 of LNCS, pp. 30–46. Springer, Heidelberg (2005)
  20. Schramm, K., Leander, G., Felker, P., Paar, C.: A collision-attack on AES: Combining side channel and differential-attack. In: Joye, M., Quisquater, J.-J. (eds.) Cryptographic Hardware and Embedded Systems-CHES 2004, vol. 3156 of LNCS, pp. 163–175. Springer, Heidelberg (2004)
  21. 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 2003, vol. 2887 of LNCS, pp. 206–222. Springer, Heidelberg (2003)
  22. Standaert, F.-X., Malkin, T., Yung, M.: A unified framework for the analysis of side-channel key recovery attacks. In: Joux, A. (ed.) Advances in Cryptology-EUROCRYPT 2009, vol. 5479 of LNCS, pp. 443–461. Springer, Heidelberg (2009)
  23. Veyrat-Charvillon, N., Gérard, B., Renauld, M., Standaert, F.-X: An optimal key enumeration algorithm and its application to side-channel attacks. In: Knudsen, L.R., Wu, H. (eds.) Selected Areas in Cryptolography-SAC 2012, vol. 7707 of LNCS, pp. 390–406. Springer, Heidelebrg (2012)
  24. Veyrat-Charvillon, N., Gérard, B., Standaert, F.-X.: Security evaluations beyond computing power: how to analyze side-channel attacks you cannot mount? To be published at EUROCRYPT (2013) (Preliminary work can be found at http://eprint.iacr.org/2012/578 )
  25. Veyrat-Charvillon, N., Standaert, F.-X.: Generic side-channel distinguishers: Improvements and limitations. In: Rogaway, P. (ed.) Advances in Cryptology-CRYPTO 2011, vol. 6841 of LNCS, pp. 354–372. Springer, Heidelberg (2011)
Bibliographic reference Gérard, Benoît ; Standaert, François-Xavier. Unified and optimized linear collision attacks and their application in a non-profiled setting. In: Journal of Cryptographic Engineering, Vol. 3, no.1, p. 45-58 (2013)
Permanent URL http://hdl.handle.net/2078.1/129933