# Kangaroos in side-channel attacks

T. Lange, C. Vredendaal, van, M. Wakker

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

## 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. Link Resolver TU/e(opens in a new window)|View at Publisher| Export | Download | More... Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Volume 8968, 2015, Pages 104-121 13th International Conference on Smart Card Research and Advanced Applications, CARDIS 2014; Paris; France; 5 November 2014 through 7 November 2014; Code 115579 Kangaroos in Side-Channel Attacks (Conference Paper) Lange, T.a , Vredendaal, C.V.ab , Wakker, M.b a Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, Eindhoven, MB, Netherlands b Brightsight B.V, Delftechpark 1, Delft, XJ, Netherlands View references (20) 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-logarithmbased systems significantly more unknown bits can be handled by using Pollard’s kangaroo method: if b bits are unknown then the attack runs in 2b/2 instead of 2b. 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 2b/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 ¿-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. © Springer International Publishing Switzerland 2015. Keywords: Discrete logarithms; Key enumeration; Pollard-kangaroo method; Precomputation; Rank estimation; Side-channel attacks; Template attacks
Original language English Smart Card Research and Advanced Applications 13th International Conference, CARDIS 2014, Paris, France, November 5-7, 2014. Revised Selected Papers M. Joye, A. Moradi Berlin Springer 104-121 978-331916762-6 https://doi.org/10.1007/978-3-319-16763-3_7 Published - 2015 13th Smart Card Research and Advanced Application Conference (CARDIS 2014), November 5-7, 2014, Paris, France - Paris, FranceDuration: 5 Nov 2014 → 7 Nov 2014

### Publication series

Name Lecture Notes in Computer Science 8968 0302-9743

### Conference

Conference 13th Smart Card Research and Advanced Application Conference (CARDIS 2014), November 5-7, 2014, Paris, France CARDIS 2014 France Paris 5/11/14 → 7/11/14