What about vulnerability to a fault attack of the Miller’s algorithm during an identity based protocol? (English) Zbl 1334.94075
Park, Jong Hyuk (ed.) et al., Advances in information security and assurance. Third international conference and workshops, ISA 2009, Seoul, Korea, June 25–27, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02616-4/pbk). Lecture Notes in Computer Science 5576, 122-134 (2009).
Summary: We complete the study of [D. Page and F. Vercauteren, IEEE Trans. Comput. 55, No. 09, 1075–1080 (2006; Zbl 1189.94046)] and [C. Whelan and M. Scott, Lect. Notes Comput. Sci. 4575, 225–246 (2007; Zbl 1151.94582)] about the Miller’s algorithm. The Miller’s algorithm is a central step to compute the Weil, Tate and Ate pairings. The aim of this article is to analyse the weakness of the Miller’s algorithm when it undergoes a fault attack. We prove that the Miller’s algorithm is vulnerable to a fault attack which is valid in all coordinate systems, through the resolution of a nonlinear system. We show that the final exponentiation is no longer a counter measure to this attack for the Tate and Ate pairings.
For the entire collection see [Zbl 05567404].
For the entire collection see [Zbl 05567404].
MSC:
| 94A60 | Cryptography |
| 14G50 | Applications to coding theory and cryptography of arithmetic geometry |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
Software:
PARI/GPReferences:
| [1] | Abraham, D.G., Dolan, G.M., Double, G.P., Stevens, J.V.: Transaction Security System. IBM Systems Journal 30, 206–229 (1991) · doi:10.1147/sj.302.0206 |
| [2] | Anderson, R., Kuhn, M.: Tamper Resistance – a Cautionary Note. In: The Second USENIX Workshop on Electronic Commerce Proceedings, Okland, California, pp. 1–11 (1996) |
| [3] | Bajard, J.C., El Mrabet, N.: Pairing in cryptography: an arithmetic point de view. In: Advanced Signal Processing Algorithms, Architectures, and Implementations XVI, part of SPIE (August 2007) |
| [4] | Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001) · Zbl 1002.94023 · doi:10.1007/3-540-44647-8_13 |
| [5] | Brier, E., Joye, M.: Point multiplication on elliptic curves through isogenies. In: Fossorier, M.P.C., Høholdt, T., Poli, A. (eds.) AAECC 2003. LNCS, vol. 2643, pp. 43–50. Springer, Heidelberg (2003) · Zbl 1030.11027 · doi:10.1007/3-540-44828-4_6 |
| [6] | Boneh, D., DeMillo, R., Lipton, R.: On the importance of checking cryptographic protocols faults. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 37–51. Springer, Heidelberg (1997) · doi:10.1007/3-540-69053-0_4 |
| [7] | Cohen, H., Frey, G. (eds.): Handbook of elliptic and hyperelliptic curve cryptography. Discrete Math. Appl. Chapman & Hall/CRC, Boca Raton (2006) · Zbl 1082.94001 |
| [8] | Yang, B., Wu, K., Karri, R.: Scan Based Side Channel Attack on Dedicated Hardware Implementation of Data Encryption Standard. In: Test Conference 2004, proceedings ITC 2004, pp. 339–344 (2004) |
| [9] | Edwards, H.: A normal Form for Elliptic Curve. Bulletin of the American Mathematical Society 44(3) (2007) · Zbl 1134.14308 · doi:10.1090/S0273-0979-07-01153-6 |
| [10] | Habing, D.H.: The Use of Lasers to Simulate Radiation-Induced Transients in Semiconductor Devices and Circuits. IEEE Transactions On Nuclear Science 39, 1647–1653 (1992) · doi:10.1109/23.211348 |
| [11] | Ionica, S., Joux, A.: Another approach to pairing computation in Edwards coordinates. In: INDOCRYPT 2008 [11], pp. 400–413 (2008), http://eprint.iacr.org/2008/292 · Zbl 1203.94104 · doi:10.1007/978-3-540-89754-5_31 |
| [12] | Koblitz, N., Menezes, A.J.: Pairing-based cryptography at high security levels. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 13–36. Springer, Heidelberg (2005) · Zbl 1122.94038 · doi:10.1007/11586821_2 |
| [13] | Macwilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes II. North-Holland Mathematical Library, vol. 16. North-Holland, Amsterdam (1998) · Zbl 0369.94008 |
| [14] | Menezes, A.: An introduction to pairing-based cryptography. Notes from lectures given in Santander, Spain (2005), http://www.cacr.math.uwaterloo.ca/ ajmeneze/publications/pairings.pdf |
| [15] | Miller, V.: The Weil pairing and its efficient calculation. Journal of Cryptology 17, 235–261 (2004) · Zbl 1078.14043 · doi:10.1007/s00145-004-0315-8 |
| [16] | Dan, P., Frederik, V.: Fault and Side Channel Attacks on Pairing based Cryptography. IEEE Transactions on Computers 55(9), 1075–1080 (2006) · Zbl 1189.94046 · doi:10.1109/TC.2006.134 |
| [17] | PARI/GP, version 2.1.7, Bordeaux (2005), http://pari.math.u-bordeaux.fr/ |
| [18] | Shamir, A.: Identity Based Cryptosystems and Signature Schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985) · Zbl 1359.94626 · doi:10.1007/3-540-39568-7_5 |
| [19] | Whelan, C., Scott, M.: Side Channel Analysis of Practical Pairing Implementation: Which Path is More Secure? In: Nguyên, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 99–114. Springer, Heidelberg (2006) · Zbl 1295.94155 · doi:10.1007/11958239_7 |
| [20] | Whelan, C., Scott, M.: The Importance of the Final Exponentiation in Pairings When Considering Fault Attacks. In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp. 225–246. Springer, Heidelberg (2007) · Zbl 1151.94582 · doi:10.1007/978-3-540-73489-5_12 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
