Paper 2020/1241

DAPA: Differential Analysis aided Power Attack on (Non-)Linear Feedback Shift Registers (Extended version)

Siang Meng Sim, Dirmanto Jap, and Shivam Bhasin


Differential power analysis (DPA) is a form of side-channel analysis (SCA) that performs statistical analysis on the power traces of cryptographic computations. DPA is applicable to many cryptographic primitives, including block ciphers, stream ciphers and even hash-based message authentication code (HMAC). At COSADE 2017, Dobraunig~et~al. presented a DPA on the fresh re-keying scheme Keymill to extract the bit relations of neighbouring bits in its shift registers, reducing the internal state guessing space from 128 to 4 bits. In this work, we generalise their methodology and combine with differential analysis, we called it differential analysis aided power attack (DAPA), to uncover more bit relations and take into account the linear or non-linear functions that feedback to the shift registers (i.e. LFSRs or NLFSRs). Next, we apply our DAPA on LR-Keymill, the improved version of Keymill designed to resist the aforementioned DPA, and breaks its 67.9-bit security claim with a 4-bit internal state guessing. We experimentally verified our analysis. In addition, we improve the previous DPA on Keymill by halving the amount of data resources needed for the attack. We also applied our DAPA to Trivium, a hardware-oriented stream cipher from the eSTREAM portfolio and reduces the key guessing space from 80 to 14 bits.

Note: This is the extended version of the same title work published at TCHES 2021 volume 1.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in TCHES 2021
SCADPALFSRNLFSRFresh re-keying schemeKeymillLR-KeymillStream cipherTrivium
Contact author(s)
crypto s m sim @ gmail com
djap @ ntu edu sg
sbhasin @ ntu edu sg
2020-10-09: received
Short URL
Creative Commons Attribution


      author = {Siang Meng Sim and Dirmanto Jap and Shivam Bhasin},
      title = {DAPA: Differential Analysis aided Power Attack on (Non-)Linear Feedback Shift Registers (Extended version)},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1241},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.