Paper 2015/033

On the Security of Fresh Re-keying to Counteract Side-Channel and Fault Attacks

Christoph Dobraunig, Maria Eichlseder, Stefan Mangard, and Florian Mendel


At AFRICACRYPT 2010 and CARDIS 2011, fresh re-keying schemes to counter side-channel and fault attacks were introduced. The idea behind those schemes is to shift the main burden of side-channel protection to a re-keying function $g$ that is easier to protect than the main block cipher. This function produces new session keys based on the secret master key and random nonces for every block of message that is encrypted. In this paper, we present a generic chosen-plaintext key-recovery attack on both fresh re-keying schemes. The attack is based on two observations: Since session key collisions for the same message are easy to detect, it is possible to recover one session key with a simple time-memory trade-off strategy; and if the re-keying function is easy to invert (such as the suggested multiplication constructions), the attacker can use the session key to recover the master key. The attack has a complexity of about $2 \cdot 2^{n/2}$ (instead of the expected $2^n$) for an $n$-bit key. For the typically employed block cipher AES-128, this would result in a key-recovery attack complexity of only $2^{65}$. If weaker primitives like 80-bit PRESENT are used, even lower attack complexities are possible.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. CARDIS 2014
side-channel attacksfresh re-keyingkey-recovery attack
Contact author(s)
christoph dobraunig @ iaik tugraz at
2015-01-15: received
Short URL
Creative Commons Attribution


      author = {Christoph Dobraunig and Maria Eichlseder and Stefan Mangard and Florian Mendel},
      title = {On the Security of Fresh Re-keying to Counteract Side-Channel and Fault Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2015/033},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.