# HOLLA: DIGITAL LOGIC AND THE PROGRAM ENCRYPTION TOOLKIT

HOLLA: DIGITAL LOGIC AND THE PROGRAM ENCRYPTION TOOLKIT Dr. Todd McDonald Professor of Computer Science School of Computing University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing 2 The material in this HOLLA has been supported by funds from the National Science Foundation. Sponsored by NSF Grants DUE-1303384 and DGE-1303384 University of South Alabama CFITS (Center for Forensics, Information Technology, and Security)

School of Computing What is Logic? 3 Logic: systematic study of the form of valid arguments Based on statements which can be proven true or false Assume that you can drive a car IF you have a valid license AND the car has enough gas. Let A represent: Has a valid license Let B represent: The gas tank is not empty You have a valid license: : You can drive the car: University of South Alabama A = ???? TRUE

B = ???? FALSE A AND B = FALSE CFITS (Center for Forensics, Information Technology, and Security) School of Computing What is Logic? 4 You intuitively know the meaning of the 3 most basic logic functions NOT: true if input is false NOT (It is raining) = NOT (It is daylight outside) =

You can build any circuit based on these 3 functions! AND: true if all values must be true AND (You are 16, You are in the 11th grade) = AND ( 1+1 = 2, 1+2 = 3, 2+1 = 4 ) = OR: true if any value is true OR (You are 16, You are in the 11th grade) = University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing What is Digital Logic? 5 Digital logic: electronic circuits that handle information

encoded in binary form (deal with signals that have only two values, 0 and 1 or false and true) Computers are built from digital logic components The number system that has two values is the binary number system University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Understanding Logic Components Gate Symbol Electrical View 6 Physical Hardware Functional View

Q = A B Q = AND(A, B) University of South Alabama A B Q = AND(A,B) 0 0 0 0 1 0 1

0 0 1 1 1 CFITS (Center for Forensics, Information Technology, and Security) School of Computing Understanding Digital Logic Functions 7 1) Represented as an equation A A B A B A B

= not A = NOT (A) = A * B = A and B = AND (A,B) = A + B = A or B = OR (A,B) = A B = A xor B = XOR (A,B) 2) Represented as a truth table A 0 0 1 1 B 0 1 0 1 University of South Alabama A

B 1 1 1 0 0 1 0 0 A and B 0 0 0 1

A or B 0 1 1 1 A xor B 0 1 1 0 CFITS (Center for Forensics, Information Technology, and Security) (A and B) ?? ?? ?? ?? School of Computing Basic Logic Gates (Single Input)

A A BUFFER University of South Alabama 8 A A INVERTER CFITS (Center for Forensics, Information Technology, and Security) School of Computing Basic Logic Gates (Dual Input) Y = AND (A,B)) Y = NOT (AND (A,B) )

AND NAND OR NOR XOR University of South Alabama 9 NXOR CFITS (Center for Forensics, Information Technology, and Security) School of Computing Logic Programs Representing circuits as a program

# = comment INPUTS: At least 1 OUTPUTS: At least 1 INTERMEDIATE GATES: # 3 inputs # 2 outputs INPUT(A) INPUT(B) INPUT(C) OUTPUT(D) OUTPUT(E) A distinguished intermediate GATE-ID D = NAND(A, B) E = OR(C, D)

We use *.bench.txt for all file BENCH file extensions University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Program Encryption Toolkit Significant Technology Investment in Reconfigurable and Embedded Hardware Devices Manipulate Clone Subvert / DoS 11 Recover lost design information for legal, economical, and defensive purposes

Shortens technological advantage and costs \$\$\$\$\$ Reverse Engineering: Reconstructing schematic or netlist to understand the design University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Program Encryption Toolkit Traditional Attacks Piracy / cloning entire circuit 12 Protection Techniques

Watermarking / fingerprinting Copy or reuse parts of a circuit Obfuscation Insert malicious logic / trojans into circuit Tamper-proofing Subvert cryptography to discover hidden keys or data University of South Alabama CFITS (Center for Forensics, Information Technology, and Security)

School of Computing Program Encryption Toolkit 13 PET = Program Encryption Toolkit Supports basic research into adversarial analysis and protection of logic circuits Around 10 years of Masters thesis research Provides visualization support for experiments and studies in polymorphic variation Provides basic functionality for logic circuit design and analysis University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing

Hands On 14 Lets build an AND gate using a BENCH file 1) 2) 3) 4) 5) 6) Rules: 2 inputs 1 output 1 intermediate gate University of South Alabama File -> New -> Bench File Pick File Name Edit

File -> Save BENCH-> Compile Combinational BENCH-> View Graph CFITS (Center for Forensics, Information Technology, and Security) School of Computing Hands On 15 Lets build a HALF ADDER using the circuit builder # One bit adder INPUT(A) INPUT(B) OUTPUT(SUM) OUTPUT(CARRY) SUM = XOR(A,B) CARRY = AND(A,B) University of South Alabama

CFITS (Center for Forensics, Information Technology, and Security) School of Computing Hands On 16 Lets analyze the half adder: Truth Table Boolean Expression Tree Implicants/Terms MROBDD Simulate University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Hands On 17

Lets do some transformations: Product of Sums Sum of Products University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Hands On 18 Lets compare the half-adder variants University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing

Hands On 19 Lets create a FULL ADDER from our component library University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Working Definitions 20 Polymorphism = an alternate version Functionally equivalent (white-box) Functionally recoverable (black-box) Variation = the process of applying polymorphism to some original program Obfuscation = A measurable loss of

abstract information relative to the original University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Structural Polymorphism 21 Structural Polymorphic generation is easy ONE FUNCTION, MANY FORMS Combinational logic = straight-line program code / basic blocks P1 P P2 P3

P5 University of South Alabama P4 CFITS (Center for Forensics, Information Technology, and Security) School of Computing Hands On 22 Lets generate some polymorphic variants of our full adder! 1 5 5 University of South Alabama

CFITS (Center for Forensics, Information Technology, and Security) School of Computing Hands On University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) 23 School of Computing Hands On 24 Compare the original full-adder with one of your variants University of South Alabama CFITS (Center for Forensics, Information Technology, and Security)

School of Computing Hands On 25 Lets build a small circuit using circuit builder Rules: 4 inputs 5 outputs 7 gates AND OR XOR NAND NOR NXOR mycomponent.bench.txt University of South Alabama CFITS (Center for Forensics, Information Technology, and Security)

School of Computing Hands On 26 Lets build a component-based circuit: using concat 5 c17 2 5 10 YOUR COMPONENT 5 c17 University of South Alabama

2 CFITS (Center for Forensics, Information Technology, and Security) School of Computing Hands On 27 Lets build a component-based circuit: using concat Lets call this circuit our P P mynewcircuit.bench.txt University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing

Hands On 28 Lets build a component-based circuit: using concat University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Component Identification 29 What if you wanted to prevent someone from knowing how this circuit was constructed? ???? Given this starting point.

University of South Alabama Can someone recover this? CFITS (Center for Forensics, Information Technology, and Security) School of Computing Hands On 30 Lets see if we can identify the c17 components in our circuit University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Hands On

University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) 31 School of Computing Variation Techniques 32 Some variation techniques are geared at hiding components Iterative Selection/Replacement Boundary Blurring Component Fusion Component Encryption Some variation techniques can hide the full function of a circuit, if the circuit input size is small enough Program Encryption

Polygate Transformation University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Hands On 33 Lets perform program encryption transformation on our circuit P University of South Alabama Number of inputs: 10 Number of outputs: 5 Number of constant1: 0 Number of constant0: 0

Intermediate gates: 21 ANDs: 2 ORs: 2 XORs: 2 NANDs: 13 NORs: 1 NXORs: 1 BUFFERs: 0 NOTs: 0 DFF: 0 JKFF: 0 TFF: 0 SRFF: 0 Circuit Depth: 7 Size of Largest Level: 10 Size of Largest Intermediate Level: 4 Maximum Fan-In: 2 Maximum Fan-Out: 3 Average Fan-In: 1.3 Average Fan-Out: 1.3 CFITS (Center for Forensics, Information Technology, and Security) School of Computing

Hands On 34 Lets perform program encryption transformation on our circuit 10 INPUTS P + EK 5 OUTPUTS P fP P

Canonical Form (SOP/ POS) QM Minimization University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Hands On 35 Lets the run the component identifier on our P University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Summary of Program Encryption

36 f P P P + Ek P University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Summary of Program Encryption 37

A legitimate user of P can reproduce the functionality of P with the decryption circuit D: P D fP University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Whats the relationship between P and P? 38 Some things about P There is no seam ( P + E ) There are no components related to P or E There is no topology related to P or E

There is nothing directly tied to the structure/configuration of P or E There is ONLY the information necessary to compute: P(x) = EK(P(x)), x University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing Some Things You Learned Today 39 How to write a logic circuit program How to analyze a circuits function or structure Why circuit protection is a problem Key Concepts Evaluating logic statements Digital logic components Logic functions and truth tables

Canonical circuit forms Circuit protection techniques Polymorphism / obfuscation Program encryption University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing 40 Thank You for Coming! University of South Alabama CFITS (Center for Forensics, Information Technology, and Security) School of Computing

## Recently Viewed Presentations

• You can QUOTE me on that A quote is the exact wording of a statement from a source. That statement may be a fact or it may be opinion. Quotes make a story more lively and more bel
• The judge articulated the rules that we live by today The legal process - Tort negligence The defendant owed a duty of care to the claimant That duty was breached The breach caused harm In medical practice we need to...
• We suggest that patients with initially equivocal or non-diagnostic test results or a strong discrepancy between clinical impression and test results be considered for further testing using a complementary, non-invasive modality ) Conditional. Low quality
• DESIGN OF COMPLEX AMALGAM PREPARATION 嘉泉醫大 吉病院 齒科 主任 敎授 金 滿 龍 STANDARD PRINCIPLES Margins 90° (perpendicular) to tangent to carvosurface Proper clearance: 0.25mm - 0.5mm Occlusal, axial and gingival walls in dentin EXTENSIONS BEYOND IDEAL Pulpal and axial...
• VOCABULARY (2.3) STAGE 2: MITOSIS. prophase: chromosomes . condense/become smaller. and turn into shapes that you. can see under a microscope. One copy of each chromatid will move into the daughter cell in the last phase of mitosis. When the...
• Cistern of lamina terminalis / Pericallosal Cistern. The cistern of lamina terminalis is the superior extension of suprasellar and chiasmatic cisterns that extend to the superior surface of corpus callosum as the pericallosal (supracallosal) cistern. Pericallosal cistern is continuous posteriorly...
• An Engineering Design Process Prototype and Test. You may need to incrementally test features of your design as you build. Develop testing procedures and a data collection plan. Qualitative - Does our design solve the problem?
• Submit PAF/ePAR timely for benefits & COBRA. Retiring employees should meet with a Benefits Administrator for benefits eligibility & enrollment. Submit FTE Changes timely . Wellness Update - Nora Pena. Wellness Updates. UT Physical Activity Challenge.