International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 21 July 2014

Tanja Lange, Christine van Vredendaal, Marnix Wakker
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.