Improved Timing Attacks against the Secret Permutation in the McEliece PKC

Authors

  • Dominic Bucerzan Aurel Vlaicu University of Arad Department of Mathematics and Computer Science Romania, 310330 Arad, Elena Dragoi, 2 Corresponding
  • Pierre-Louis Cayrel Laboratoire Hubert Curien, UMR CNRS 5516, Université de Lyon, Saint-Etienne, France
  • Vlad Dragoi Laboratoire LITIS - EA 4108 Université de Rouen - UFR Sciences et Techniques, 76800 Saint Etienne du Rouvray, France
  • Tania Richmond Laboratoire IMATH, EA 2134, Avenue de l’Université , BP 20132, 83957 La Garde Cedex, France

Keywords:

communication systems, theory of error correcting codes, code-based cryptography, McEliece PKC, side-channel attacks, timing attack, extended Euclidean algorithm

Abstract

In this paper, we detail two side-channel attacks against the McEliece public-key cryptosystem. They are exploiting timing differences on the Patterson decoding algorithm in order to reveal one part of the secret key: the support permutation. The first one is improving two existing timing attacks and uses the correlation between two different steps of the decoding algorithm. This improvement can be deployed on all error-vectors with Hamming weight smaller than a quarter of the minimum distance of the code. The second attack targets the evaluation of the error locator polynomial and succeeds on several different decoding algorithms. We also give an appropriate countermeasure.

References

Roberto Avanzi, Simon Hoerder, Dan Page, Mike Tunstall (2010), Side-channel attacks on the McEliece and Niederreiter public-key cryptosystems, Cryptology ePrint Arch., Report 2010/479, 2010.

Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen (eds.) (2009), Post-Quantum Cryptography, Springer, 2009.

Daniel J. Bernstein, Tung Chou, Peter Schwabe (2013), McBits: fast constant-time codebased cryptography, https://binary.cr.yp.to/mcbits-20130616.pdf, 1-26.

Vlad Dragoi, Pierre-Louis Cayrel, Brice Colombier, Tania Richmond (2013), Polynomial structures in code-based cryptography, Indocrypt 2013, LNCS2850: 286-296. https://doi.org/10.1007/978-3-319-03515-4_19

Whitfield Diffie, Martin Hellman (1976), New directions in cryptography, IEEE Trans. Inform. Theory, 22(6):644-654. https://doi.org/10.1109/TIT.1976.1055638

W.G. Horner (1819), A new method of solving numerical equations of all orders by continuous approximation, Phil. Trans. R. Soc. Lond., 109:308-335. https://doi.org/10.1098/rstl.1819.0023

Florence J. MacWilliams, Neil J. A. Sloane (1986), The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 5th ed., 1986.

Robert J. McEliece (1978), A public-key cryptosystem based on algebraic coding theory, Jet Propulsion Laboratory DSN Progress, Report 42-44, 114-116.

Robert Niebuhr et al. (2010), On lower bounds for information set decoding over fq, In C. Cid, J.-C. Faugere, (eds.), Proc. of the Second Intl. Conf. on Symbolic Computation and Cryptography, SCC 2010, 143-157.

Ayoub Otmani, Jean-Pierre Tillich, Leonard Dallot (2008), Cryptanalysis of a McEliece cryptosystem based on quasi-cyclic LDPC codes, Proc. of First Intl. Conf. on Symbolic Computation and Cryptography (SCC 2008), 69-81.

Victor Y. Pan (1966), On Methods of Computing the Values of Polynomials, UspeKhi Mathematicheskikh Nauk, 21:103-134. https://doi.org/10.1070/rm1966v021n01abeh004147

Nicholas J. Patterson (1975), The algebraic decoding of goppa codes, IEEE Transactions on Information Theory, 21(2): 203-207. https://doi.org/10.1109/TIT.1975.1055350

Peter W. Shor (1997), Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, 26(5):1484-1509. https://doi.org/10.1137/S0097539795293172

Abdulhadi Shoufan et al. (2010), A Timing Attack against Patterson Algorithm in the McEliece PKC, ICISC 2009, LNCS 5984: 161-175.

V.M. Sidelnikov and S.O. Shestakov (1992), On the insecurity of cryptosystems based on generalized Reed-Solomon codes, Discrete Math. Appl., 2(4):439-444. https://doi.org/10.1515/dma.1992.2.4.439

Falko Strenzke (2010), A Timing Attack against the Secret Permutation in the McEliece PKC, In N. Sendrier (ed.), Post-Quantum Cryptography, Third intl. workshop, LNCS6061: 95-107. https://doi.org/10.1007/978-3-642-12929-2_8

Falko Strenzke (2010), Fast and secure root-finding for code-based cryptosystems, Cryptology ePrint Arch., Report 2011/672, 2011.

Falko Strenzke (2011), Timing attacks against the syndrome inversion in code-based cryptosystems, Cryptology ePrint Arch., Report 2011/683, 2011.

Falko Strenzke et al. (2008), Side channels in the McEliece PKC, In J. Buchmann and J. Ding (eds.), Post-Quantum Cryptography, Second intl. workshop, LNCS5299: 216-229. https://doi.org/10.1007/978-3-540-88403-3_15

Published

2016-12-02

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.