Abstract
The security of McEliece public-key cryptosystem is based on the difficulty of the decoding problem which is NP-hard. In this article, we propose a simple power analysis attack on this cryptosystem. The attack exploits an information leakage, which results from the relation between the error vector weight and the iteration number of the extended Euclidean algorithm used in Patterson Algorithm. Executing the proposed attacks enables the extraction of the secret error vector, and thus the plain text with minimal overhead. A countermeasure is presented which removes the information leakage and prevents the simple power analysis attack. The attack procedure and the countermeasure are applied to a cryptoprocessor implementation of the McEliece cryptosystem running on a FPGA platform.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Balasubramanian, S., et al.: Fast multivariate signature generation in hardware: the case of rainbow. In: Proceedings of the 19th IEEE International Conference on Application-Specific Systems, Architectures and Processors, ASAP 2008 (2008)
Beuchat, J.C., Sendrier, N., Tisserand, A., Villard, G.: FPGA Implementation of a Recently Published Signature Scheme. Rapport de recherche RR LIP 2004-14 (2004)
Diffie W., Hellman M.: New directions in cryptography. IEEE Trans. Inform. Theory 22(6), 644–654 (1976)
El-Hadedy, M., Gligoroski, D., Knapskog, S.J.: High performance implementation of a public key block cipher—MQQ, for FPGA platforms. In: Proceedings of the International Conference on ReConFigurable Computing and FPGAs, ReConFig 2008 (2008)
ElGamal T.: A public key cryptosystem and a signature based on discrete logarithms. IEEE Trans. Inform. Theory 31, 469–472 (1985)
Fell, H., Diffie, W.: Analysis of a public key approach based on polynomial substitution. In: LNCS on Advances in Cryptology, CRYPTO’85 (1986)
Heyse, S., Moradi, A., Paar, C.: Practical power analysis attacks on software implementations of McEliece. In: Post-Quantum Cryptography, pp. 108–125 (2010). doi:10.1007/978-3-642-12929-2_9
Kocher, P.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, pp. 104–113 (1996)
Kocher, P.: Differential power analysis. In: Advances in Cryptology-CRYPTO’99, 19th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 15–19, 1999, Proceedings 1666, 388–397 (1999)
Lenstra A.K., Lenstra H.W., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)
Lin S.: Error Control Coding: Fundamentals and Applications. Prentice-Hall, Englewood Cliffs, NJ (1983)
McEliece R.J.: A public key cryptosystem based on algebraic coding theory. DSN Progr. Rep. 42–44, 114–116 (1978)
Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996). http://www.cacr.math.uwaterloo.ca/hac/
Merkle, R.: A Certified digital signature. In: Proceedings on Advances in Cryptology, CRYPTO 89 (1989)
Miller, V.: Use of Elliptic Curves in Cryptography. Lecture Notes in Computer Science, vol. 218, pp. 417–426 (1985)
Patterson N.: Algebraic decoding of Goppa codes. IEEE Trans. Inform. Theory 21, 203–207 (1975)
Proos, J., Zalka, C.: Shor’s Discrete Logarithm Quantum Algorithm for Elliptic Curves. ArXiv Quantum Physics e-prints (2003)
Rivest R., Shamir A., Adleman L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
Rodriguez-Henriques F., Saqib N., Perez A., Koc C.: Cryptographic algorithms on reconfigurable hardware. Springer, Heidelberg (2006)
Side-Channel Attack Standard Evaluation Board SASEBO-G Specification: Tech. rep., Research Center for Information Security (RCIS) (2008)
Schindler W., Lemke K., Paar C.: A stochastic model for differential side channel cryptanalysis. Proc. CHES 3659, 30–46 (2005)
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundation of Computer Science (1994)
Shor P.W.: Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)
Shoufan, A., Strenzke, F., Molter, H.G., Stoettinger, M.: A timing attack against Patterson Algorithm in the McEliece PKC. In: Proceedings of the 12th International Conference on Information Security and Cryptology (ICISC’09), Lecture Notes in Computer Science (2009)
Shoufan, A., Wink, T., Molter, G., Huss, S., Strenzke, F.: A novel processor architecture for McEliece cryptosystem and FPGA platforms. In: Proceedings of the 20th IEEE International Conference on Application-specific Systems, Architectures and Processors, ASAP 2009 (2009)
Strenzke, F., Tews, E., Molter, H.G., Overbeck, R., Shoufan, A.: Side channels in the McEliece PKC. In: Proceedings of International Workshop on Post-Quantum Cryptography, PQCrypto 2008, pp. 30–46 (2008)
Tsunoo, Y., Tsujihara, E., Minematsu, K., Miyauchi, H.: Cryptanalysis of block ciphers implemented on computers with cache. In: Proceedings of International Symposium on Information Theory and Applications, pp. 803–806 (2002)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Molter, H.G., Stöttinger, M., Shoufan, A. et al. A simple power analysis attack on a McEliece cryptoprocessor. J Cryptogr Eng 1, 29–36 (2011). https://doi.org/10.1007/s13389-011-0001-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13389-011-0001-3