Paper 2017/761

Anti-SAT: Mitigating SAT Attack on Logic Locking

Yang Xie and Ankur Srivastava

Abstract

Logic locking is a technique that's proposed to protect outsourced IC designs from piracy and counterfeiting by untrusted foundries. A locked IC preserves the correct functionality only when a correct key is provided. Recently, the security of logic locking is threatened by a new attack called SAT attack, which can decipher the correct key of most logic locking techniques within a few hours even for a reasonably large key-size. This attack iteratively solves SAT formulas which progressively eliminate the incorrect keys till the circuit is unlocked. In this paper, we present a circuit block (referred to as Anti-SAT block) to enhance the security of existing logic locking techniques against the SAT attack. We show using a mathematical proof that the number of SAT attack iterations to reveal the correct key in a circuit comprising an Anti-SAT block is an exponential function of the key-size thereby making the SAT attack computationally infeasible. Besides, we address the vulnerability of the Anti-SAT block to various removal attacks and investigate obfuscation techniques to prevent these removal attacks. More importantly, we provide a proof showing that these obfuscation techniques for making Anti-SAT un-removable would not weaken the Anti-SAT block's resistance to SAT attack. Through our experiments, we illustrate the effectiveness of our approach to securing modern chips fabricated in untrusted foundries.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
A major revision of an IACR publication in CHES 2016
Keywords
boolean functionslogic locking
Contact author(s)
yangxie @ umd edu
History
2017-08-08: received
Short URL
https://ia.cr/2017/761
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/761,
      author = {Yang Xie and Ankur Srivastava},
      title = {Anti-{SAT}: Mitigating {SAT} Attack on Logic Locking},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/761},
      year = {2017},
      url = {https://eprint.iacr.org/2017/761}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.