### 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.

Available format(s)
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
Short URL
https://ia.cr/2017/761

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},
note = {\url{https://eprint.iacr.org/2017/761}},
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.