BESAT

Behavioral SAT-based attack on cyclic logic encryption

Yuanqi Shen, You Li, Amin Rezaei, Shuyu Kong, David Dlott, Hai Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

Cyclic logic encryption is newly proposed in the area of hardware security. It introduces feedback cycles into the circuit to defeat existing logic decryption techniques. To ensure that the circuit is acyclic under the correct key, CycSAT is developed to add the acyclic condition as a CNF formula to the SAT-based attack. However, we found that it is impossible to capture all cycles in any graph with any set of feedback signals as done in the CycSAT algorithm. In this paper, we propose a behavioral SAT-based attack called BeSAT. BeSAT observes the behavior of the encrypted circuit on top of the structural analysis, so the stateful and oscillatory keys missed by CycSAT can still be blocked. The experimental results show that BeSAT successfully overcomes the drawback of CycSAT.

Original languageEnglish (US)
Title of host publicationASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages657-662
Number of pages6
ISBN (Electronic)9781450360074
DOIs
StatePublished - Jan 21 2019
Event24th Asia and South Pacific Design Automation Conference, ASPDAC 2019 - Tokyo, Japan
Duration: Jan 21 2019Jan 24 2019

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Other

Other24th Asia and South Pacific Design Automation Conference, ASPDAC 2019
CountryJapan
CityTokyo
Period1/21/191/24/19

Fingerprint

Cryptography
Networks (circuits)
Feedback
Structural analysis
Hardware security

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Cite this

Shen, Y., Li, Y., Rezaei, A., Kong, S., Dlott, D., & Zhou, H. (2019). BESAT: Behavioral SAT-based attack on cyclic logic encryption. In ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference (pp. 657-662). (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1145/3287624.3287670
Shen, Yuanqi ; Li, You ; Rezaei, Amin ; Kong, Shuyu ; Dlott, David ; Zhou, Hai. / BESAT : Behavioral SAT-based attack on cyclic logic encryption. ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 657-662 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).
@inproceedings{c2117ebf71164cb6b1300761d90e0f55,
title = "BESAT: Behavioral SAT-based attack on cyclic logic encryption",
abstract = "Cyclic logic encryption is newly proposed in the area of hardware security. It introduces feedback cycles into the circuit to defeat existing logic decryption techniques. To ensure that the circuit is acyclic under the correct key, CycSAT is developed to add the acyclic condition as a CNF formula to the SAT-based attack. However, we found that it is impossible to capture all cycles in any graph with any set of feedback signals as done in the CycSAT algorithm. In this paper, we propose a behavioral SAT-based attack called BeSAT. BeSAT observes the behavior of the encrypted circuit on top of the structural analysis, so the stateful and oscillatory keys missed by CycSAT can still be blocked. The experimental results show that BeSAT successfully overcomes the drawback of CycSAT.",
author = "Yuanqi Shen and You Li and Amin Rezaei and Shuyu Kong and David Dlott and Hai Zhou",
year = "2019",
month = "1",
day = "21",
doi = "10.1145/3287624.3287670",
language = "English (US)",
series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "657--662",
booktitle = "ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference",
address = "United States",

}

Shen, Y, Li, Y, Rezaei, A, Kong, S, Dlott, D & Zhou, H 2019, BESAT: Behavioral SAT-based attack on cyclic logic encryption. in ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference. Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, Institute of Electrical and Electronics Engineers Inc., pp. 657-662, 24th Asia and South Pacific Design Automation Conference, ASPDAC 2019, Tokyo, Japan, 1/21/19. https://doi.org/10.1145/3287624.3287670

BESAT : Behavioral SAT-based attack on cyclic logic encryption. / Shen, Yuanqi; Li, You; Rezaei, Amin; Kong, Shuyu; Dlott, David; Zhou, Hai.

ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference. Institute of Electrical and Electronics Engineers Inc., 2019. p. 657-662 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - BESAT

T2 - Behavioral SAT-based attack on cyclic logic encryption

AU - Shen, Yuanqi

AU - Li, You

AU - Rezaei, Amin

AU - Kong, Shuyu

AU - Dlott, David

AU - Zhou, Hai

PY - 2019/1/21

Y1 - 2019/1/21

N2 - Cyclic logic encryption is newly proposed in the area of hardware security. It introduces feedback cycles into the circuit to defeat existing logic decryption techniques. To ensure that the circuit is acyclic under the correct key, CycSAT is developed to add the acyclic condition as a CNF formula to the SAT-based attack. However, we found that it is impossible to capture all cycles in any graph with any set of feedback signals as done in the CycSAT algorithm. In this paper, we propose a behavioral SAT-based attack called BeSAT. BeSAT observes the behavior of the encrypted circuit on top of the structural analysis, so the stateful and oscillatory keys missed by CycSAT can still be blocked. The experimental results show that BeSAT successfully overcomes the drawback of CycSAT.

AB - Cyclic logic encryption is newly proposed in the area of hardware security. It introduces feedback cycles into the circuit to defeat existing logic decryption techniques. To ensure that the circuit is acyclic under the correct key, CycSAT is developed to add the acyclic condition as a CNF formula to the SAT-based attack. However, we found that it is impossible to capture all cycles in any graph with any set of feedback signals as done in the CycSAT algorithm. In this paper, we propose a behavioral SAT-based attack called BeSAT. BeSAT observes the behavior of the encrypted circuit on top of the structural analysis, so the stateful and oscillatory keys missed by CycSAT can still be blocked. The experimental results show that BeSAT successfully overcomes the drawback of CycSAT.

UR - http://www.scopus.com/inward/record.url?scp=85061134170&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85061134170&partnerID=8YFLogxK

U2 - 10.1145/3287624.3287670

DO - 10.1145/3287624.3287670

M3 - Conference contribution

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 657

EP - 662

BT - ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Shen Y, Li Y, Rezaei A, Kong S, Dlott D, Zhou H. BESAT: Behavioral SAT-based attack on cyclic logic encryption. In ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference. Institute of Electrical and Electronics Engineers Inc. 2019. p. 657-662. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1145/3287624.3287670