Evaluation Study of Original McEliece Cryptosystem Against Side Channel Attack.

Newroz N. Abdulrazaq & Thuraya M. Qaradaghi

College of Science/Computer Science & IT Department, Salahaddin University-Erbil, Kurdistan Region – Iraq

College of Engineering/ Electrical Engineering Department, Salahaddin University-Erbil, Kurdistan Region – Iraq

DOI: https://doi.org/10.17656/jzs.10579

Abstract

Side channel attack is the most efficient attack against original McEliece cryptosystem, especially ball-collision and Bernstein et al.Stern attacks. The modified Stern attack hasan ability to break original McEliece cryptosystem with parameter [1024,524,101] in 1400 days with personal computers.While with 200 clusters CPU breaking could be done in 7 days. While ball-collision attacks have smallerexponent time than Stern algorithm.This paper will present a modified version of Patterson decoding algorithm using a new evaluation for finding error locations.This approach gave the sender an opportunity to choose errors less than identified errors in public key without notifying the receiver;therefore, it reduces the probability of modified Stern attack against McEliece cryptosystem to (0.02) and increases exponent time of ball-collision attack. In this paper alsothe leakage of proposed implementation has beenmeasured using a measurement type for possible leakage in Patterson’s decoding algorithm suggested by previous work, and we concluded that the designed system have fewer leakage compared to previous implementation. The workhas done using Visual Studio C#.

Key Words: McEliece Cryptosystem Side Channel Attack

References

[1] R. McEliece, "A Public-Key Cryptosystem Based on Algebraic Coding Theory", Technical report, NASA, (1978).

[2] T. P. Berger, P.-L. Cayrel, P. Gaborit, and A. Otmani, "Reducing Key Length of the McEliece Cryptosystem", In B. Preneel, editor, AFRICACRYPT, Lecture Notes in Computer Science, Vol. 5580, pp 77-97. Springer, (2009).

[3] E. M. Gabidulin, A. V. Ourivski, B. Honary, and B. Ammar, "Reducible rank codesand their applications to cryptography", IEEE Transactions on Information Theory, Vol. 49, No.12, pp 3289-3293, (2003).

[4] C. Monico, J. Rosenthal, and A. Shokrollahi, "Using low density parity check codesin the McEliece cryptosystem", IEEE International Symposium on Information Theory, ISIT 2000, pp 215. IEEE, (2000).

[5] J. -C. Faug re, A. Otmani, L. Perret, and J. -P. Tillich, "Algebraic Cryptanalysis of McEliece Variants with Compact Keys", EUROCRYPT, Lecture Notes in Computer Science, Vol. 6110, pp 279-298. (2010).

[6] R. Overbeck, "A New Structural Attack for GPT and Variants", E. Dawson and S. Vaudenay, editors, Mycrypt, Lecture Notes in Computer Science, Vol. 3715, pp 50-63. (2005).

[7] D. J. Bernstein, T. Lange, and C. Peters, "Attacking and Defending the McEliece Cryptosystem", J. Buchmann and J. Ding, editors, PQCrypto, Lecture Notes in Computer Science, Vol. 5299, pp 31-46. (2008).

[8] D. J. Bernstein, T. Lange, and C. Peters, "Smaller Decoding Exponents: Ball- Collision Decoding", P. Rogaway, editor, CRYPTO, Lecture Notes in Computer Science, Vol. 6841, pp 743-760. (2011).

[9] A. Canteaut and F. Chabaud, "A New Algorithm for Finding Minimum- Weight Words in a Linear Code: Application to McEliece Cryptosystem and to Narrow- Sense BCH Codes of Length 511", IEEE Transactions on Information Theory, Vol. 44, No.1, pp 367-378, (1998).

[10]J. Stern, "A Method for Finding Codewords of Small Weight", G. D. Cohen and J. Wolfmann, editors, Coding Theory and Applications, Lecture Notes in Computer Science, Vol. 388, pp 106-113. (1988).

[11]Repka Marek, "Leakage Measurement Tool of McEliece PKC Calculator", TELEDU-17, WSEAS, ISBN 978-1-61804-262-0, Istanbul, pp 128, (2014).

[12]Gadoulean Maximilien, "Cryptosystem Using Error-Correction Codes Based on the Rank Metric", Lehigh University, Master Thesis (2005).

[13]Hudde Hans, "Development and Evaluation of Code-Based Cryptography Library for Constrained Devices", Ruhr University, (2013).

[14]Qaradaghi, T., Abdulrazaq, N. "Comparison between Separable and Irreducible Goppa Code in McEliece Cryptosystem", World Academy of Science, Engineering and Technology, International Science Index 106, International Journal of Computer, Electrical, Automation, Control and Information Engineering, Vol. 9, No. 10, pp 1717 - 1723.( 2015).

[15]Abdulrazaq N.; Qaradaghi T., "Cryptosystem Based on Error Correcting Codes", Salahaddin University-Erbil, Zanco Journal of Pure and Applied Science, Vol. 28, No. 2, pp 99-109. (2016).

[16]Edoardo Persichetti, "Improving the Efficiency of Code-Based Cryptography", Auckland University, PHD Thesis, Nov. (2012).

View Full Article