Abstract
Side-channel attacks are a powerful tool to discover the cryptographic secrets of a chip or other device but only too often do they require too many traces or leave too many possible keys to explore. In this paper we show that for side channel attacks on discrete-logarithm-based systems significantly more unknown bits can be handled by using Pollard’s kangaroo method: if \(b\) bits are unknown then the attack runs in \(2^{b/2}\) instead of \(2^b\). If an attacker has many targets in the same group and thus has reasons to invest in precomputation, the costs can even be brought down to \(2^{b/3}\).
Usually the separation between known and unknown keybits is not this clear cut – they are known with probabilities ranging between 100 % and 0 %. Enumeration and rank estimation of cryptographic keys based on partial information derived from cryptanalysis have become important tools for security evaluations. They make the line between a broken and secure device more clear and thus help security evaluators determine how high the security of a device is. For symmetric-key cryptography there has been some recent work on key enumeration and rank estimation, but for discrete-logarithm-based systems these algorithms fail because the subkeys are not independent and the algorithms cannot take advantage of the above-mentioned faster attacks. We present \(\epsilon \)-enumeration as a new method to compute the rank of a key by using the probabilities together with (variations of) Pollard’s kangaroo algorithm and give experimental evidence.
This work was supported by the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005. Permanent ID of this document: c1c4c98f98c7ca3cb1b1f4208b95e8b8. Date: February 15, 2015.
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
Similar content being viewed by others
References
Bernstein, D.J., Lange, T.: Computing small discrete logarithms faster. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 317–338. Springer, Heidelberg (2012)
Bernstein, D.J., Lange, T., Schwabe, P.: On the correct use of the negation map in the Pollard rho method. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 128–146. Springer, Heidelberg (2011)
Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In: Kaliski, B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 13–28. Springer, Heidelberg (2003)
Clavier, C., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Horizontal correlation analysis on exponentiation. In: Soriano, M., Qing, S., López, J. (eds.) ICICS 2010. LNCS, vol. 6476, pp. 46–61. Springer, Heidelberg (2010)
Galbraith, S.D., Pollard, J.M., Ruprai, R.S.: Computing discrete logarithms in an interval. Math. Comput. 82(282), 1181–1195 (2013)
Galbraith, S., Ruprai, R.S.: An improvement to the Gaudry-Schost algorithm for multidimensional discrete logarithm problems. In: Parker, M.G. (ed.) Cryptography and Coding 2009. LNCS, vol. 5921, pp. 368–382. Springer, Heidelberg (2009)
Gaudry, P., Schost, É.: A low-memory parallel version of Matsuo, Chao, and Tsujii’s algorithm. In: Buell, D.A. (ed.) ANTS 2004. LNCS, vol. 3076, pp. 208–222. Springer, Heidelberg (2004)
Gopalakrishnan, K., Thériault, N., Yao, C.Z.: Solving discrete logarithms from partial knowledge of the key. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) Indocrypt 2007. LNCS, vol. 4859, pp. 224–237. Springer, Heidelberg (2007)
Hankerson, D., Menezes, A.J., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer-Verlag New York Inc., Secaucus (2003)
Pan, J., van Woudenberg, J.G.J., den Hartog, J.I., Witteman, M.F.: Improving DPA by peak distribution analysis. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 241–261. Springer, Heidelberg (2011)
Pollard, J.M.: Monte Carlo methods for index computation (mod p). Math. Comput. 32, 918–924 (1978)
Pollard, J.M.: Kangaroos, monopoly and discrete logarithms. J. Cryptol. 13(4), 437–447 (2000)
Shanks, D.: Class number, a theory of factorization, and genera. In: Lewis, D.J. (ed.) 1969 Number Theory Institute. Proceedings of Symposia in Pure Mathematics, Providence, Rhode Island, vol. 20, pp. 415–440. American Mathematical Society (1971)
Stein, A., Teske, E.: The parallelized Pollard kangaroo method in real quadratic function fields. Math. Comput. 71(238), 793–814 (2002)
Straus, E.G.: Addition chains of vectors (problem 5125). Am. Math. Mon. 70, 806–808 (1964). http://cr.yp.to/bib/entries.html#1964/straus
van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1–28 (1999)
Veyrat-Charvillon, N., Gérard, B., Renauld, M., Standaert, F.-X.: An optimal key enumeration algorithm and its application to side-channel attacks. In: Knudsen, L.R., Wu, H. (eds.) SAC 2012. LNCS, vol. 7707, pp. 390–406. Springer, Heidelberg (2013)
Veyrat-Charvillon, N., Gérard, B., Standaert, F.-X.: Security evaluations beyond computing power. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 126–141. Springer, Heidelberg (2013)
Walter, C.D.: Sliding windows succumbs to big mac attack. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 286–299. Springer, Heidelberg (2001)
Witteman, M.F., van Woudenberg, J.G.J., Menarini, F.: Defeating RSA multiply-always and message blinding countermeasures. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 77–88. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Lange, T., van Vredendaal, C., Wakker, M. (2015). Kangaroos in Side-Channel Attacks. In: Joye, M., Moradi, A. (eds) Smart Card Research and Advanced Applications. CARDIS 2014. Lecture Notes in Computer Science(), vol 8968. Springer, Cham. https://doi.org/10.1007/978-3-319-16763-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-16763-3_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16762-6
Online ISBN: 978-3-319-16763-3
eBook Packages: Computer ScienceComputer Science (R0)