Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Improving Non-profiled Attacks on Exponentiations Based on Clustering and Extracting Leakage from Multi-channel High-Resolution EM Measurements Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Toward Secure Implementation of McEliece Decryption

Authors : Mariya Georgieva, Frédéric de Portzamparc

Published in: Constructive Side-Channel Analysis and Secure Design

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We analyse the security regarding timing attacks of implementations of the decryption in McEliece PKC with binary Goppa codes. First, we review and extend the existing attacks, both on the messages and on the keys. We show that, until now, no satisfactory countermeasure could erase all the timing leakages in the Extended Euclidean Algorithm (EEA) step. Then, we describe a version of the EEA never used for McEliece so far. It uses a constant number of operations for given public parameters. In particular, the operation flow does not depend on the input of the decryption, and thus closes all previous timing attacks. We end up with what should become a central tool toward a secure implementation of McEliece decryption.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Faster Software for Fast Endomorphisms
next chapter Fault Injection with a New Flavor: Memetic Algorithms Make a Difference
Literature
1.
Avanzi, R., Hoerder, S., Page, D., Tunstall, M.: Side-channel attacks on the McEliece and Niederreiter public-key cryptosystems. J. Cryptographic Eng. 1(4), 271–281 (2011)CrossRef
2.
Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978)CrossRefMATH
3.
Berlekamp, E., Seroussi, G., Po, T.: A hypersystolic reed–solomon decoder. In: Bhargava, V.K., Wicker, S.B., IEEE Communications Society, IEEE Information Theory Society (eds.) Reed-Solomon Codes and Their Applications, pp. 205–241. IEEE Press, Piscataway (1994)
4.
Bernstein, D.J., Chou, T., Schwabe, P.: McBits: fast constant-time code-based cryptography. In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 250–272. Springer, Heidelberg (2013) CrossRef
5.
Biswas, B.: Aspects de mise en oeuvre de la cryptographie basée sur les codes. These, Ecole Polytechnique X, October 2010
6.
Heyse, S.: Implementation of McEliece based on quasi-dyadic goppa codes for embedded devices. In: Yang, B.-Y. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 143–162. Springer, Heidelberg (2011) CrossRef
7.
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes, 5th edn. North-Holland, Amsterdam (1986)
8.
Overbeck, R., Sendrier, N.: Code-based cryptography. In: Bernstein, D., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 95–145. Springer, Heidelberg (2009)CrossRef
9.
Patterson, N.: The algebraic decoding of Goppa codes. IEEE Trans. Inf. Theory 21(2), 203–207 (1975)CrossRef
10.
Sarwate, D., Shanbhag, N.: High-speed architectures for Reed-Solomon decoders. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 9(5), 641–655 (2001)CrossRef
11.
Sarwate, D., Yan, Z.: Modified Euclidean algorithms for decoding Reed-Solomon codes. In: IEEE International Symposium on Information Theory, ISIT 2009, pp. 1398–1402, June 2009
12.
Shoufan, A., Strenzke, F., Molter, H.G., Stöttinger, M.: A timing attack against patterson algorithm in the McEliece PKC. In: Lee, D., Hong, S. (eds.) ICISC 2009. LNCS, vol. 5984, pp. 161–175. Springer, Heidelberg (2010) CrossRef
13.
Shoufan, A., Wink, T., Molter, H., Huss, S., Kohnert, E.: A Novel cryptoprocessor architecture for the McEliece public-key cryptosystem. IEEE Trans. Comput. 59(11), 1533–1546 (2010)MathSciNetCrossRef
14.
Strenzke, F.: A smart card implementation of the McEliece PKC. In: Samarati, P., Tunstall, M., Posegga, J., Markantonakis, K., Sauveron, D. (eds.) WISTP 2010. LNCS, vol. 6033, pp. 47–59. Springer, Heidelberg (2010)
15.
Strenzke, F.: A timing attack against the secret permutation in the McEliece PKC. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 95–107. Springer, Heidelberg (2010) CrossRef
16.
Strenzke, F.: Timing attacks against the syndrome inversion in Code-Based cryptosystems. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 217–230. Springer, Heidelberg (2013) CrossRef
17.
Strenzke, F., Tews, E., Molter, H.G., Overbeck, R., Shoufan, A.: Side channels in the McEliece PKC. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 216–229. Springer, Heidelberg (2008) CrossRef
18.
Sugiyama, Y., Kasahara, M., Hirasawa, S., Namekawa, T.: A method for solving key equation for decoding goppa codes. Inf. Control 27(1), 87–99 (1975)MathSciNetCrossRefMATH
19.
Thull, K., Yap, C.: A Unified Approach to HGCD Algorithms for polynomials and integers (1990)
Metadata
Title
Toward Secure Implementation of McEliece Decryption
Authors
Mariya Georgieva
Frédéric de Portzamparc
Copyright Year
2015
Book
Constructive Side-Channel Analysis and Secure Design

Print ISBN: 978-3-319-21475-7

Electronic ISBN: 978-3-319-21476-4

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-21476-4_10

Premium Partner

    Image Credits