Improved Timing Attacks against the Secret Permutation in the McEliece PKC

  • 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

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

[1] 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.

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

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

[4] 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

[5] 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

[6] 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

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

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

[9] 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.

[10] 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.

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

[12] 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

[13] 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

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

[15] 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

[16] 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

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

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

[19] 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
How to Cite
BUCERZAN, Dominic et al. Improved Timing Attacks against the Secret Permutation in the McEliece PKC. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 12, n. 1, p. 7-25, dec. 2016. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/2780>. Date accessed: 02 july 2020. doi: https://doi.org/10.15837/ijccc.2017.1.2780.

Keywords

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