Paper 2018/219

On Side-Channel Vulnerabilities of Bit Permutations: Key Recovery and Reverse Engineering

Jakub Breier, Dirmanto Jap, Xiaolu Hou, and Shivam Bhasin

Abstract

Lightweight block ciphers rely on simple operations to allow compact implementation. Thanks to its efficiency, bit permutation has emerged as an optimal choice for state-wise diffusion. It can be implemented by simple wiring or shifts. However, as recently shown by Spectre and Meltdown attacks, efficiency and security often go against each other. In this work, we show how bit permutations introduce a side-channel vulnerability that can be exploited to extract the secret key from the cipher. Such vulnerabilities are specific to bit permutations and do not occur in other state-wise diffusion alternatives. We propose Side-Channel Assisted Differential-Plaintext Attack (SCADPA) which targets this vulnerability in bit permutation operation. SCADPA is experimentally demonstrated on PRESENT-80 on an 8-bit microcontroller, with the best case key recovery in 17 encryptions. The attack is then extended to latest bit-permutation based cipher GIFT, allowing full key recovery in 36 encryptions. We also propose and experimentally verify an automatic threshold method which can be easily applied to SCADPA, allowing automation of the attack. Moreover, SCADPA on bit permutations has other applications. Application for reverse engineering secret sboxes in PRESENT-like proprietary ciphers is shown. We also highlight a special case, where fixing one vulnerability opens another one. This is shown by applying SCADPA on some assembly level fault attack countermeasures, rendering it less secure than unprotected implementations. Lastly, we also provide several different attack scenarios, such as targeting different encryption modes.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
side-channel analysisdifferential plaintext attackSCADPAbit permutations
Contact author(s)
jbreier @ ntu edu sg
History
2018-02-26: received
Short URL
https://ia.cr/2018/219
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/219,
      author = {Jakub Breier and Dirmanto Jap and Xiaolu Hou and Shivam Bhasin},
      title = {On Side-Channel Vulnerabilities of Bit Permutations: Key Recovery and Reverse Engineering},
      howpublished = {Cryptology ePrint Archive, Paper 2018/219},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/219}},
      url = {https://eprint.iacr.org/2018/219}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.