Improved Timing Attacks against the Secret Permutation in the McEliece PKC
Keywords:
communication systems, theory of error correcting codes, code-based cryptography, McEliece PKC, side-channel attacks, timing attack, extended Euclidean algorithmAbstract
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
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
