Abstract
Recent advances in code-based cryptography paved new ways for efficient asymmetric cryptosystems that combine decent performance with moderate key sizes. In this context, Misoczki et al. recently proposed the use of quasi-cyclic MDPC (QC-MDPC) codes for the McEliece cryptosystem. It was shown that these codes can provide both compact key representations and solid performance on high-end computing platforms. However, for widely used low-end microcontrollers only slow implementations for this promising construction have been presented so far.
In this work we present an implementation of QC-MDPC McEliece encryption providing 80 bits of equivalent symmetric security on low-cost ARM Cortex-M4-based microcontrollers with a reasonable performance of 42ms for encryption and 251-558ms for decryption. Besides practical issues such as random error generation, we demonstrate side-channel attacks on a straightforward implementation of this scheme and finally propose timing- and instruction-invariant coding strategies and countermeasures to strengthen it against timing attacks as well as simple power analysis.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Atmel. Atmel AVR1924: XMEGA A1 Xplained Hardware User Guide (2010), http://www.atmel.com/Images/AVR1924.zip
Avanzi, R., Hoerder, S., Page, D., Tunstall, M.: Side-channel attacks on the McEliece and Niederreiter public-key cryptosystems. Journal of Cryptographic Engineering 1(4), 271–281 (2011)
Berlekamp, E., McEliece, R., van Tilborg, H.: On the Inherent Intractability of Certain Coding Problems (Corresp.). IEEE Transactions on Information Theory 24(3), 384–386 (1978)
Biasi, F., Barreto, P., Misoczki, R., Ruggiero, W.: Scaling efficient code-based cryptosystems for embedded platforms. Journal of Cryptographic Engineering, 1–12 (2014)
Chen, C., Eisenbarth, T., von Maurich, I., Steinwandt, R.: Differential Power Analysis of a McEliece Cryptosystem. Cryptology ePrint Archive, Report 2014/534 (2014), http://eprint.iacr.org/
Gallager, R.: Low-density Parity-check Codes. IRE Transactions on Information Theory 8(1), 21–28 (1962)
Heyse, S., Moradi, A., Paar, C.: Practical Power Analysis Attacks on Software Implementations of McEliece. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 108–125. Springer, Heidelberg (2010)
Heyse, S., von Maurich, I., Güneysu, T.: Smaller Keys for Code-Based Cryptography: QC-MDPC McEliece Implementations on Embedded Devices. In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 273–292. Springer, Heidelberg (2013)
Huffman, W.C., Pless, V.: Fundamentals of Error-Correcting Codes (2010)
Kobara, K., Imai, H.: Semantically Secure McEliece Public-Key Cryptosystems-Conversions for McEliece. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 19–35. Springer, Heidelberg (2001)
Kocher, P.C., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
McEliece, R.J.: A Public-Key Cryptosystem Based On Algebraic Coding Theory. Deep Space Network Progress Report 44, 114–116 (1978)
Misoczki, R., Tillich, J.-P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes. Cryptology ePrint Archive, Report 2012/409 (2012), http://eprint.iacr.org/
Misoczki, R., Tillich, J.-P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: New McEliece variants from Moderate Density Parity-Check codes. In: ISIT, pp. 2069–2073. IEEE (2013)
Niederreiter, H.: Knapsack-type cryptosystems and algebraic coding theory. Problems Control Inform. Theory/Problemy Upravlen. Teor. Inform. 15(2), 159–166 (1986)
Nojima, R., Imai, H., Kobara, K., Morozov, K.: Semantic security for the McEliece cryptosystem without random oracles. Des. Codes Cryptography 49(1-3), 289–305 (2008)
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., 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)
STMicroelectronics. UM1472 User manual - Discovery kit for STM32F407/417 lines, http://www.st.com/st-web-ui/static/active/en/resource/technical/document/user_manual/DM00039084.pdf , 2014.
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)
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)
von Maurich, I., Güneysu, T.: Lightweight code-based cryptography: QC-MDPC McEliece encryption on reconfigurable devices. In: DATE, pp. 1–6. IEEE (2014)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
von Maurich, I., Güneysu, T. (2014). Towards Side-Channel Resistant Implementations of QC-MDPC McEliece Encryption on Constrained Devices. In: Mosca, M. (eds) Post-Quantum Cryptography. PQCrypto 2014. Lecture Notes in Computer Science, vol 8772. Springer, Cham. https://doi.org/10.1007/978-3-319-11659-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-11659-4_16
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11658-7
Online ISBN: 978-3-319-11659-4
eBook Packages: Computer ScienceComputer Science (R0)