The Interpose PUF (iPUF): Secure PUF Design against State ... · Arbiter PUF (APUF) x-XOR Arbiter PUF Interpose PUF (iPUF) Precise non-linear model + CRPs + classical ML = impractically - [PDF Document] (2024)

Secure Computation Laboratory

Department of Electrical & Computer Engineering

University of Connecticut

The Interpose PUF (iPUF): Secure PUF Design againstState-of-the-art Machine Learning based Modeling Attacks

Phuong Ha Nguyen,

Durga P. Sahoo, Kaleel Mahmood, Chenglu Jin,

Ulrich Rührmair and Marten van Dijk

ChengluDurga

CHES 2019

Kaleel Uli MartenHa

Content

2

1. Concept - Overview - Motivation

2. Strong PUFs: APUF, XOR APUF and Interpose PUF (iPUF)

3. Short-term Reliability

4. Reliability based modeling attacks on XOR PUF: understanding

5. Interpose PUF – a lightweight PUF which is secure against state-of-the art

modeling attacks

6. Conclusion

1. Concept - Overview - Motivation

3

Concept - Overview – Motivation [1]

4

Hardware

Primitive [Device] Challenge C Response R

Weak PUF - small #CRPs:

RO PUF, SRAM PUF, etc.

Strong PUF – large #CRPs:

Application: device Identification, authentication

and crypto key generation

No Security Proof:

Power Grid PUF,

Clock PUF,

Crossbard PUF

Security Proof:

LPN PUFs - heavy

Broken but lightweight:

APUF, XOR APUF, Feed

Forward PUF,

Lightweight Secure PUF,

Bistable Ring PUF, MPUF

etc.

Nature: process variation – physically unclonability - unique

PUF’s Category:

Concept - Overview – Motivation [2]

5

Hardware

Primitive [Device] Challenge C Response R

Weak PUF - small #CRPs:

RO PUF, SRAM PUF, etc.

Strong PUF – large #CRPs:

Application: device Identification, authentication

and crypto key generation

No Security Proof:

Power Grid PUF,

Clock PUF,

Crossbard PUF

Security Proof:

LPN PUFs - heavy

Broken but lightweight:

APUF, XOR APUF, Feed

Forward PUF,

Lightweight Secure PUF,

Bistable Ring PUF, MPUF

etc.

Nature: process variation – physically unclonability - unique

PUF’s Category:

Concept - Overview – Motivation [3]

6

Hardware

Primitive [Device] Challenge C Response R

Weak PUF - small #CRPs:

RO PUF, SRAM PUF, etc.

Strong PUF – large #CRPs:

PUF’s Modeling Attacks on CRPs only:

No Security Proof:

Power Grid PUF,

Clock PUF,

Crossbard PUF

Security Proof:

LPN PUFs

- heavy

Broken but lightweight:

APUF, XOR APUF, Feed

Forward PUF,

Lightweight Secure PUF,

Bistable Ring PUF, MPUF

etc.

PUF’s Category:

Classical ML attacks

– reliable CRPs:

Support Vector Machine (SVM),

Logistic Regression (LR),

Evolution Strategy (ES),

Covariance Matrix Adaptation

ES (CMA-ES), Perceptron,

Boolean Attacks, Deep Neural

Network Attacks (DNN)

Advanced ML attacks

– noisy CRPs:

CMA-ES + noisy CRPs

Concept - Overview – Motivation [4]

7

Hardware

Primitive [Device] Challenge C Response R

Weak PUF - small #CRPs:

RO PUF, SRAM PUF, etc.

Strong PUF – large #CRPs:

PUF’s Modeling Attacks with CRPs only:

No Security Proof:

Power Grid PUF,

Clock PUF,

Crossbard PUF

Security Proof:

LPN PUFs

- heavy

Broken but lightweight:

APUF, XOR APUF, Feed

Forward PUF,

Lightweight Secure PUF,

Bistable Ring PUF, MPUF

etc.

PUF’s Category:

Classical ML attacks

– reliable CRPs:

Support Vector Machine (SVM),

Logistic Regression (LR),

Evolution Strategy (ES),

Covariance Matrix Adaptation

ES (CMA-ES), Perceptron,

Boolean Attacks, Deep Neural

Network Attacks (DNN)

Advanced ML attacks

– noisy CRPs:

CMA-ES + noisy CRPs

Concept - Overview – Motivation [5]

8

Hardware

Primitive [Device] Challenge C Response R

Weak PUF - small #CRPs:

RO PUF, SRAM PUF, etc.

Strong PUF – large #CRPs:

PUF’s Modeling Attacks with CRPs only:

No Security Proof:

Power Grid PUF,

Clock PUF,

Crossbar PUF

Security Proof:

LPN PUFs

- Large HW

footprint

Broken but lightweight:

Arbiter PUF/APUF, XOR

APUF, Feed Forward

PUF, Lightweight Secure

PUF, Bistable Ring PUF.

PUF’s Category:

Classical ML attacks

– reliable CRPs:

Support Vector Machine (SVM),

Logistic Regression (LR),

Evolution Strategy (ES),

Covariance Matrix Adaptation

ES (CMA-ES), Perceptron,

Boolean Attacks, Deep Neural

Network Attacks (DNN)

Advanced ML attacks

– noisy CRPs:

CMA-ES + noisy CRPs

Concept - Overview – Motivation [6]

9

Hardware

Primitive [Device] Challenge C Response R

Weak PUF - small #CRPs:

RO PUF, SRAM PUF, etc.

Strong PUF – large #CRPs:

PUF’s Modeling Attacks with CRPs only:

Broken but lightweight:

Arbiter PUF/APUF, XOR

APUF, Feed Forward

PUF, Lightweight Secure

PUF, Bistable Ring PUF.

PUF’s Category:

Classical ML attacks

– reliable CRPs:

Advanced ML attacks

– noisy CRPs:

CMA-ES + noisy CRPs

XOR APUF

Security ProofVulnerability

Lightweight,

Precise Math. Model

Concept - Overview – Motivation [7]

10

Hardware

Primitive [Device] Challenge C Response R

Weak PUF - small #CRPs:

RO PUF, SRAM PUF, etc.

Strong PUF – large #CRPs:

PUF’s Modeling Attacks with CRPs only:

Broken but lightweight:

Arbiter PUF/APUF, XOR

APUF, Feed Forward

PUF, Lightweight Secure

PUF, Bistable Ring PUF.

PUF’s Category:

Classical ML attacks

– reliable CRPs:

Advanced ML attacks

– noisy CRPs:

CMA-ES + noisy CRPs

XOR APUF interpose PUF (iPUF)

Security Proof

Lightweight,

Precise Math. Model

Security Proof

Concept - Overview – Motivation [8]

11

Hardware

Primitive [Device] Challenge C Response R

Weak PUF - small #CRPs:

RO PUF, SRAM PUF, etc.

Strong PUF – large #CRPs:

PUF’s Modeling Attacks with CRPs only:

Broken but lightweight:

Arbiter PUF/APUF, XOR

APUF, Feed Forward

PUF, Lightweight Secure

PUF, Bistable Ring PUF.

PUF’s Category:

Classical ML attacks

– reliable CRPs:

Advanced ML attacks

– noisy CRPs:

CMA-ES + noisy CRPs

XOR APUF interpose PUF (iPUF)

Security Proof

Lightweight,

Precise Math. Model

Security ProofSecurity Philosophy

Design Philosophy

2. APUF- XOR APUF -iPUF

12

APUF, XOR APUF and iPUF [1]

Arbiter PUF (APUF) [1]

Interpose PUF (iPUF)x-XOR APUF

- Extremely lightweight and large number of CRPs i.e, 2𝑛 CRPs

- Environmental noises make the PUF’s outputs unreliable sometimes

- Not secure against modeling attacks

APUF, XOR APUF and iPUF [2]

Arbiter PUF (APUF) x-XOR APUF

APUF, XOR APUF and iPUF [3]

15

The Interpose PUF / iPUF

APUF, XOR APUF and iPUF [4]

16

Arbiter PUF (APUF) x-XOR Arbiter PUF Interpose PUF (iPUF)

• Δ > 0 → 𝑟 = 1. 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑟 = 0• Δ = 𝒅𝒖𝒑𝒑𝒆𝒓 − 𝒅𝒍𝒐𝒘𝒆𝒓 = 𝒘 ⋅ 𝚽

• 𝒘 ∶ 𝑢𝑛𝑖𝑞𝑢𝑒 𝑤𝑒𝑖𝑔ℎ𝑡 𝑣𝑒𝑐𝑡𝑜𝑟,𝑑𝑒𝑙𝑎𝑦 𝑟𝑒𝑝𝑟𝑒𝑠𝑒𝑛𝑡𝑎𝑡𝑖𝑜𝑛 𝑓𝑜𝑟 𝑎𝑛𝑦 𝐴𝑃𝑈𝐹 𝑖𝑛𝑠𝑡𝑎𝑛𝑐𝑒

• 𝚽 𝑖𝑠 𝑡ℎ𝑒 𝑝𝑎𝑟𝑖𝑡𝑦 𝑣𝑒𝑐𝑡𝑜𝑟𝚽 𝑖 = 𝑗=𝑖,…,𝑛−1 1 − 𝒄 𝑗 , 𝑖 = 0,… , 𝑛 − 1 , 𝚽 𝑛 = 1

Precise linear model + CRPs + ML

= practically and softwarelly clonable

Precise non-linear model + CRPs + classical ML

= impractically softwarelly clonable

𝑥, 𝑦 − 𝐼𝑃𝑈𝐹

≈ 𝑦 +𝑥

2− 𝑋𝑂𝑅 𝑃𝑈𝐹

if a is inserted at the middle

Precise non-linear model + CRPs + classical ML

= impractically softwarelly clonable

XOR APUF is not Secure against noisy CRPs +

CMA-ES [Advanced ML]! (CHES2015) why?

Why not for IPUF?

APUF, XOR APUF and iPUF [5]

17

Arbiter PUF (APUF) x-XOR Arbiter PUF Interpose PUF (iPUF)

Precise non-linear model + CRPs + classical ML

= impractically softwarelly clonable

𝑥, 𝑦 − 𝐼𝑃𝑈𝐹

≈ 𝑦 +𝑥

2− 𝑋𝑂𝑅 𝑃𝑈𝐹

if a is inserted at the middle

Precise non-linear model + CRPs + classical ML

= impractically softwarelly clonable

XOR APUF is not Secure against noisy CRPs +

CMA-ES [Advanced ML]! (CHES2015) why?

Why not for IPUF?

• Δ > 0 → 𝑟 = 1. 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑟 = 0• Δ = 𝒅𝒖𝒑𝒑𝒆𝒓 − 𝒅𝒍𝒐𝒘𝒆𝒓 = 𝒘 ⋅ 𝚽

• 𝒘 ∶ 𝑢𝑛𝑖𝑞𝑢𝑒 𝑓𝑜𝑟 𝑎𝑛𝑦 𝐴𝑃𝑈𝐹 𝑖𝑛𝑠𝑡𝑎𝑛𝑐𝑒• 𝚽 𝑖𝑠 𝑡ℎ𝑒 𝑝𝑎𝑟𝑖𝑡𝑦 𝑣𝑒𝑐𝑡𝑜𝑟𝚽 𝑖 = 𝑗=𝑖,…,𝑛−1 1 − 𝒄 𝑗 , 𝑖 = 0,… , 𝑛 − 1 , 𝚽 𝑛 = 1

• Precise linear model

• Large CRP space

• Vulnerable to ML attacks

APUF, XOR APUF and iPUF [6]

18

Arbiter PUF (APUF) x-XOR Arbiter PUF Interpose PUF (iPUF)

• Δ > 0 → 𝑟 = 1. 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑟 = 0• Δ = 𝒅𝒖𝒑𝒑𝒆𝒓 − 𝒅𝒍𝒐𝒘𝒆𝒓 = 𝒘 ⋅ 𝚽

• 𝒘 ∶ 𝑢𝑛𝑖𝑞𝑢𝑒 𝑓𝑜𝑟 𝑎𝑛𝑦 𝐴𝑃𝑈𝐹 𝑖𝑛𝑠𝑡𝑎𝑛𝑐𝑒• 𝚽 𝑖𝑠 𝑡ℎ𝑒 𝑝𝑎𝑟𝑖𝑡𝑦 𝑣𝑒𝑐𝑡𝑜𝑟𝚽 𝑖 = 𝑗=𝑖,…,𝑛−1 1 − 𝒄 𝑗 , 𝑖 = 0,… , 𝑛 − 1 , 𝚽 𝑛 = 1

• Precise linear model

• Large CRP space

• Vulnerable to ML attacks

• Precise non-linear model

• Large CRP space

• Secure against classical ML

• Vulnerable to advanced ML

𝑥, 𝑦 − 𝐼𝑃𝑈𝐹

≈ 𝑦 +𝑥

2− 𝑋𝑂𝑅 𝑃𝑈𝐹

if a is inserted at the middle

Precise non-linear model + CRPs + classical ML

= impractically softwarelly clonable

XOR APUF is not Secure against noisy CRPs +

CMA-ES [Advanced ML]! (CHES2015) why?

Why not for IPUF?

[2]

APUF, XOR APUF and iPUF [7]

19

Arbiter PUF (APUF) x-XOR Arbiter PUF Interpose PUF (iPUF)

𝑥, 𝑦 − 𝐼𝑃𝑈𝐹

≈ 𝑦 +𝑥

2− 𝑋𝑂𝑅 𝑃𝑈𝐹

if a is inserted at the middle

Precise non-linear model + CRPs + classical ML

= impractically softwarelly clonable

XOR APUF is not Secure against noisy CRPs +

CMA-ES [Advanced ML]! (CHES2015) why?

Why not for IPUF?

• Δ > 0 → 𝑟 = 1. 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑟 = 0• Δ = 𝒅𝒖𝒑𝒑𝒆𝒓 − 𝒅𝒍𝒐𝒘𝒆𝒓 = 𝒘 ⋅ 𝚽

• 𝒘 ∶ 𝑢𝑛𝑖𝑞𝑢𝑒 𝑓𝑜𝑟 𝑎𝑛𝑦 𝐴𝑃𝑈𝐹 𝑖𝑛𝑠𝑡𝑎𝑛𝑐𝑒• 𝚽 𝑖𝑠 𝑡ℎ𝑒 𝑝𝑎𝑟𝑖𝑡𝑦 𝑣𝑒𝑐𝑡𝑜𝑟𝚽 𝑖 = 𝑗=𝑖,…,𝑛−1 1 − 𝒄 𝑗 , 𝑖 = 0,… , 𝑛 − 1 , 𝚽 𝑛 = 1

• Precise linear model

• Large CRP space

• Vulnerable to ML attacks

• Precise non-linear model

• Large CRP space

• Secure against classical ML

• Vulnerable to advanced ML

APUF, XOR APUF and iPUF [8]

20

Arbiter PUF (APUF) x-XOR Arbiter PUF Interpose PUF (iPUF)

𝑥, 𝑦 − 𝐼𝑃𝑈𝐹

≈ 𝑦 +𝑥

2− 𝑋𝑂𝑅 𝑃𝑈𝐹

if a is inserted at the middle

• Precise non-linear model

• Large CRP

• Secure both classical ML and advanced ML

XOR APUF is not Secure against noisy CRPs +

CMA-ES [Advanced ML]! (CHES2015) why?

Why not for IPUF?

• Δ > 0 → 𝑟 = 1. 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑟 = 0• Δ = 𝒅𝒖𝒑𝒑𝒆𝒓 − 𝒅𝒍𝒐𝒘𝒆𝒓 = 𝒘 ⋅ 𝚽

• 𝒘 ∶ 𝑢𝑛𝑖𝑞𝑢𝑒 𝑓𝑜𝑟 𝑎𝑛𝑦 𝐴𝑃𝑈𝐹 𝑖𝑛𝑠𝑡𝑎𝑛𝑐𝑒• 𝚽 𝑖𝑠 𝑡ℎ𝑒 𝑝𝑎𝑟𝑖𝑡𝑦 𝑣𝑒𝑐𝑡𝑜𝑟𝚽 𝑖 = 𝑗=𝑖,…,𝑛−1 1 − 𝒄 𝑗 , 𝑖 = 0,… , 𝑛 − 1 , 𝚽 𝑛 = 1

• Precise linear model

• Large CRP space

• Vulnerable to ML attacks

• Precise non-linear model

• Large CRP space

• Secure against classical ML

• Vulnerable to advanced ML

3. Short-term Reliability

21

Arbiter: Repeatability – short-term Reliability [1]

22

Challenge C

(C,1),

(C,2),

….

(C,m)

APUF A

Responses

𝑟1, 𝑟2, . . , 𝑟𝑚(𝑟1 = 0),(𝑟2 = 1),

… .(𝑟𝑚 = 0)

𝑅 = (𝑟1+𝑟2 +⋯+ 𝑟𝑚)/𝑚

Reliability

Measurements

Δ1, Δ2, … , Δ𝑚Δ1 < 0,Δ2 > 0,… ,

Δ𝑚 < 0

Δ = 𝑤 ⋅ Φ + noise Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 0

Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 1

𝑤

Arbiter: Repeatability – short-term Reliability [2]

23

Challenge C

(C,1),

(C,2),

….

(C,m)

APUF A

Responses

𝑟1, 𝑟2, . . , 𝑟𝑚(𝑟1 = 0),(𝑟2 = 1),

… .(𝑟𝑚 = 0)

𝑅 = (𝑟1+𝑟2 +⋯+ 𝑟𝑚)/𝑚

Reliability

Measurements

Δ1, Δ2, … , Δ𝑚Δ1 < 0,Δ2 > 0,… ,

Δ𝑚 < 0

Δ = 𝑤 ⋅ Φ + noise Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 0

Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 1

𝑤

Arbiter: Repeatability – short-term Reliability [3]

24

Challenge C

(C,1),

(C,2),

….

(C,m)

APUF A

Responses

𝑟1, 𝑟2, . . , 𝑟𝑚(𝑟1 = 0),(𝑟2 = 1),

… .(𝑟𝑚 = 0)

𝑅 = (𝑟1+𝑟2 +⋯+ 𝑟𝑚)/𝑚

Reliability

Measurements

Δ1, Δ2, … , Δ𝑚Δ1 < 0,Δ2 > 0,… ,

Δ𝑚 < 0

Δ = 𝑤 ⋅ Φ + noise Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 0

Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 1

𝑤

Arbiter: Repeatability – short-term Reliability [4]

25

Challenge C

(C,1),

(C,2),

….

(C,m)

APUF A

Responses

𝑟1, 𝑟2, . . , 𝑟𝑚(𝑟1 = 0),(𝑟2 = 1),

… .(𝑟𝑚 = 0)

𝑅 = (𝑟1+𝑟2 +⋯+ 𝑟𝑚)/𝑚

Reliability

Measurements

Δ1, Δ2, … , Δ𝑚Δ1 < 0,Δ2 > 0,… ,

Δ𝑚 < 0

Δ = 𝑤 ⋅ Φ + noise

Arbiter: Repeatability – short-term Reliability [5]

26

Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 0

Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 1

𝑤Reliable

Δ1

Challenge C

(C,1),

(C,2),

….

(C,m)

APUF A

Responses

𝑟1, 𝑟2, . . , 𝑟𝑚(𝑟1 = 0),(𝑟2 = 1),

… .(𝑟𝑚 = 0)

𝑅 = (𝑟1+𝑟2 +⋯+ 𝑟𝑚)/𝑚

Reliability

Measurements

Δ1, Δ2, … , Δ𝑚Δ1 < 0,Δ2 > 0,… ,

Δ𝑚 < 0

Δ = 𝑤 ⋅ Φ + noise

Δ𝑚

Arbiter: Repeatability – short-term Reliability [6]

27

Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 0

Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 1

𝑤Reliable

Noisy

r1

rmr1 r2

rm

Challenge C

(C,1),

(C,2),

….

(C,m)

APUF A

Responses

𝑟1, 𝑟2, . . , 𝑟𝑚(𝑟1 = 0),(𝑟2 = 1),

… .(𝑟𝑚 = 0)

𝑅 = (𝑟1+𝑟2 +⋯+ 𝑟𝑚)/𝑚

Reliability

Measurements

Δ1, Δ2, … , Δ𝑚Δ1 < 0,Δ2 > 0,… ,

Δ𝑚 < 0

Δ = 𝑤 ⋅ ΦΔ = 𝑤 ⋅ Φ + noise

Arbiter: Repeatability – short-term Reliability [7]

28

Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 0

Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 1

𝑤Reliable

Reliable

Noisy

Noisy

r1

rmr1 r2

rm

Challenge C

(C,1),

(C,2),

….

(C,m)

APUF A

Responses

𝑟1, 𝑟2, . . , 𝑟𝑚(𝑟1 = 0),(𝑟2 = 1),

… .(𝑟𝑚 = 0)

𝑅 = (𝑟1+𝑟2 +⋯+ 𝑟𝑚)/𝑚

Reliability

Measurements

Δ1, Δ2, … , Δ𝑚Δ1 < 0,Δ2 > 0,… ,

Δ𝑚 < 0

Δ = 𝑤 ⋅ ΦΔ = 𝑤 ⋅ Φ + noise

Reliability of C and 𝑤 are related

The Gap Between Promise and Reality: On the Insecurity of XOR Arbiter PUFs CHES, 2015, Georg T. Becker

4. Reliability based Modeling Attacks

29

APUF

30

• Δ > 0 → 𝑟 = 1. 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑟 = 0• Δ = 𝒅𝒖𝒑𝒑𝒆𝒓 − 𝒅𝒍𝒐𝒘𝒆𝒓 = 𝒘 ⋅ 𝚽

Covariance Matrix Adaptation Evolution Strategy (CMA-ES) Algorithm

31

[4]

𝑤

𝑤

𝑤 𝑤

𝑤 𝑤

𝑤

𝑤

𝑤

𝑤𝑤 𝑤

𝑤 = 𝑤

𝑤

𝑤

𝑤: 𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑜𝑟 𝑜𝑟 𝑚𝑜𝑑𝑒𝑙

𝑤: 𝑡𝑎𝑟𝑔𝑒𝑡

Reliability-based modeling attack on APUFs using CMAES [1]

32

Δ = 𝑤 ⋅ Φ > 0, 𝑟 = 0

Δ = 𝑤 ⋅ Φ < 0, 𝑟 = 1

𝑤Reliable

Reliable

Noisy

r1

r2

rmr1 r2

rm

Qn : noisy

challenges

Qr :

reliable

challenges

𝑄,𝑤

𝑄: 𝑠𝑒𝑡 𝑜𝑓 𝐶𝑅𝑃𝑠 ,𝑤: 𝐴𝑃𝑈𝐹

𝑄

Reliability-based modeling attack on APUFs using CMAES [2]

33

Qn : noisy

Qr :

reliable

𝑄,𝑤

Iteration 1

𝑄, 𝜖1, 𝑤1

𝑄 → 𝑐ℎ𝑎𝑙𝑙𝑒𝑛𝑔𝑒 𝑐 → Φ 𝑐 → Δ = 𝑤1 ⋅ Φ 𝑐

Δ ≤ 𝜖1 → 𝑐ℎ𝑎𝑙𝑙𝑒𝑛𝑔𝑒 𝑐 𝑖𝑠 𝑛𝑜𝑖𝑠𝑦

Δ > 𝜖1 → 𝑐ℎ𝑎𝑙𝑙𝑒𝑛𝑔𝑒 𝑐 𝑖𝑠 𝑟𝑒𝑙𝑖𝑎𝑏𝑙𝑒

Qn : noisy

Qr : reliable

ModelTarget

Reliability-based modeling attack on APUFs using CMAES [3]

34

Qn : noisy

Qr :

reliable

𝑄,𝑤

Iteration 1

Qn

Qr

𝑄, 𝜖1, 𝑤1

Qr

Qn

Reliability-based modeling attack on APUFs using CMAES [4]

35

Qn : noisy

Qr :

reliable

𝑄,𝑤

Iteration 1

Qn

Qr

𝑄, 𝜖1, 𝑤1

Qr

Qn

𝐶𝑜𝑚𝑝𝑢𝑡𝑒 𝑡ℎ𝑒 𝑚𝑎𝑡𝑐ℎ𝑖𝑛𝑔 𝑟𝑎𝑡𝑒 𝜌1 𝑏𝑒𝑡𝑤𝑒𝑒𝑛 𝑄, 𝑤 𝑎𝑛𝑑 𝑄, 𝜖1, 𝑤1

matching

not

matching

not

𝜌1

Reliability-based modeling attack on APUFs using CMAES [5]

36

Qn : noisy

Qr :

reliable

𝑄,𝑤

Iteration 1

Qn

Qr

𝑄, 𝜖1, 𝑤1

Qr

Qn

Qn

Qr

Qr

Qn

Qn

Qr

Qr

Qn

Qn

Qr

Qr

Qn

𝑄, 𝜖2, 𝑤2 𝑄, 𝜖𝑖, 𝑤𝑖 𝑄, 𝜖𝑘, 𝑤k

𝜌1 𝜌2 𝜌𝑖 𝜌𝑘

Reliability-based modeling attack on APUFs using CMAES [6]

37

Qn : noisy

Qr :

reliable

𝑄,𝑤

Iteration 1

Qn

Qr

𝑄, 𝜖1, 𝑤1

Qr

Qn

Qn

Qr

Qr

Qn

Qn

Qr

Qr

Qn

Qn

Qr

Qr

Qn

𝑄, 𝜖2, 𝑤2 𝑄, 𝜖𝑖, 𝑤𝑖 𝑄, 𝜖𝑘, 𝑤k

𝜌1 𝜌2 𝜌𝑖 𝜌𝑘

High matching rate: Kept Low matching rate: Discarded

Reliability-based modeling attack on APUFs using CMAES [7]

38

Qn : noisy

Qr :

reliable

𝑄,𝑤

Iteration 2

Qn

Qr

𝑄, 𝜖1, 𝑤1

Qr

Qn

Qn

Qr

Qn

Qr

Qr

Qn

Qn

Qr

r

𝑄, 𝜖2, 𝑤2 𝑄, 𝜖1, 𝑤1 𝑄, 𝜖𝑘, 𝑤k

𝜌1 𝜌2 𝜌1 𝜌𝑘

High matching rate: Kept

generate

Reliability-based modeling attack on APUFs using CMAES [8]

39

Qn : noisy

Qr :

reliable

𝑄,𝑤

Iteration M

Qn

Qr

𝑄, 𝜖1, 𝑤1

Qn

Qr

Qn

Qr

𝑄, 𝜖2, 𝑤2 𝑄, 𝜖1, 𝑤1 𝑄, 𝜖𝑘, 𝑤k

𝜌1 𝜌2 𝜌1 𝜌𝑘

High matching rate: Kept

generate

Qn

Qr

𝑥-XOR APUF

40

Reliability-based modeling attack on XOR APUFs using CMAES [1]

41

Qn : noisy

Qr :

reliable

𝑄,𝑤

Iteration M

Qn

Qr

𝑄, 𝜖1, 𝑤1

Qn

Qr

𝑄, 𝜖2, 𝑤2

The model of

one APUF 𝑖among 𝑥 APUFs

in 𝑥-XOR APUF

𝜌1 𝜌2

High matching rate: Kept

Converge

Qn

Qr

XOR APUF → 𝑄 𝑤1, …., w𝑘 are STILL models of APUF

CMA-ES attack on XOR APUF

APUF 𝑖

Reliability-based modeling attack on XOR APUFs using CMAES [2]

42

Qn : noisy

Qr :

reliable

𝑄,𝑤

Iteration M

Qn

Qr

𝑄, 𝜖1, 𝑤1

Qn

Qr

𝑄, 𝜖2, 𝑤2

The model of

another APUF 𝑗among 𝑥 APUFs

in 𝑥-XOR APUF

𝜌1 𝜌2

High matching rate: Kept

Converge

Qn

Qr

XOR APUF → 𝑄𝑛𝑒𝑤 𝑤1, …., w𝑘 are STILL models of APUF

CMA-ES attack on XOR APUF

APUF 𝑗

Understanding Reliability based modeling attack on XOR PUF

Question 1: How does the attack on XOR PUF work?

Question 2: How can we make the attack on XOR PUF fail?

43

Question 1: How does the attack on XOR PUF work?

44

The noisy and reliable challenges in XOR PUF

45Challenge-Reliability Pairs Training Data

Reliable

Noisy

All PUF

models

Qnoisy

reliable

reliable

Qn

Qr

Q1:

noisy

Q1: reliable

Qn

Qr

Qr

APUF 1

noisy

reliable

Qn

Qr

XOR APUF

noisy

noisy

reliable

/reliable

/reliable

Key idea of the attack on XOR PUF [1]

46Challenge-Reliability Pairs Training Data

Reliable

Noisy

Q10

Q2

Q1

All PUF

models

Qi

Q

Qn

Qr

Qn : noisy

Qr :

reliable

Q10

Qr

Qr

Qn

Qr

Qr

Qn

converge

𝑄, 𝜖𝑖, 𝑤𝑖10-XOR APUF APUF 10

- (1) All the models 𝑤𝑖 in CMA-ES are models of APUF

- (2) 𝑤𝑖 can only converge to an APUF instance

- (3) CMA ES maximizes the matching Q of 𝑤𝑖 and

Q of XOR APUF

- (1)+(2)+(3) CMA ES forces

𝑤𝑖 converges to APUF 10 because Q of APUF 10

is the representative of Q of XOR APUF.

Key idea of the attack on XOR PUF [2]

47Challenge-Reliability Pairs Training Data

Reliable

Noisy

Q10

Q2

Q1

All PUF

models

Qi

Q

Qn

Qr

Qn : noisy

Qr :

reliable

Q10

Qr

Qr

Qn

Qr

Qr

Qn

converge

𝑄, 𝜖𝑖, 𝑤𝑖10-XOR APUF APUF 10

- (1) All the models 𝑤𝑖 in CMA-ES are models of APUF

- (2) 𝑤𝑖 can only converge to an APUF instance

- (3) CMA ES maximizes the matching Q of 𝑤𝑖 and

Q of XOR APUF

- (1)+(2)+(3) CMA ES forces

𝑤𝑖 converges to APUF 10 because Q of APUF 10

is the representative of Q of XOR APUF.

Key idea of the attack on XOR PUF [3]

48Challenge-Reliability Pairs Training Data

Reliable

Noisy

Q10

Q2

Q1

All PUF

models

Qi

Q

Qn

Qr

Qn : noisy

Qr :

reliable

Q10

Qr

Qr

Qn

Qr

Qr

Qn

converge

𝑄, 𝜖𝑖, 𝑤𝑖10-XOR APUF APUF 10

- (1) All the models 𝑤𝑖 in CMA-ES are models of APUF

- (2) 𝑤𝑖 can only converge to an APUF instance

- (3) CMA ES maximizes the matching Q of 𝑤𝑖 and

Q of XOR APUF

- (1)+(2)+(3) CMA ES forces

𝑤𝑖 converges to APUF 10 because Q of APUF 10

is the representative of Q of XOR APUF.

Key idea of the attack on XOR PUF [4]

49Challenge-Reliability Pairs Training Data

Reliable

Noisy

Q10

Q2

Q1

All PUF

models

Qi

Q

Qn

Qr

Qn : noisy

Qr :

reliable

Q10

Qr

Qr

Qn

Qr

Qr

Qn

converge

𝑄, 𝜖𝑖, 𝑤𝑖10-XOR APUF APUF 10

- (1) All the models 𝑤𝑖 in CMA-ES are models of APUF

- (2) 𝑤𝑖 can only converge to an APUF instance

- (3) CMA ES maximizes the matching Q of 𝑤𝑖 and

Q of XOR APUF

- (1)+(2)+(3) CMA ES forces

𝑤𝑖 converges to APUF 10 because Q of APUF 10

is the representative of Q of XOR APUF.

Key idea of the attack on XOR PUF [5]

50Challenge-Reliability Pairs Training Data

Reliable

Noisy

Q3

Q2

Q1

All PUF

models

Qi

Q

Qn

Qr

Qn : noisy

Qr :

reliable

Q3

Qr

Qr

Qn

Qr

Qr

Qn

converge

𝑄, 𝜖𝑖, 𝑤𝑖10-XOR APUF APUF 3

- Changing Q makes Q3 largest

Key idea of the attack on XOR PUF [6]

51Challenge-Reliability Pairs Training Data

Reliable

Noisy

Q3

Q2

Q1

All PUF

models

Qi

Q

Qn

Qr

Qn : noisy

Qr :

reliable

Q3

Qr

Qr

Qn

Qr

Qr

Qn

converge

𝑄, 𝜖𝑖, 𝑤𝑖10-XOR APUF APUF 3

- Changing Q makes Q3 largest

Keep changing Q and applying CMA-ES attack

on Q to get models of all APUF instances

Question 2: How to make the attack on XOR PUF fail?

52

Attack fails

53

A1

Majority

Voting

+c 𝑟

CMA ES never converges to APUF A0

and always converges to APUF A1

when majority voting mechanism in use.

A0

2-XOR APUF with majority voting circuit at A0

5. Interpose PUF ( iPUF) – Reliability based modeling attack resistance

54

Security of iPUF wrt Reliability-based modeling attack [1]

Reason 1: the information of APUF instances in x-XOR PUF presented at the iPUFoutput is less compared to APUF instances in y-XOR PUF. Thus, the reliability based modeling attack never converges to any APUF instance in x-XOR PUF

56

Security of iPUF wrt Reliability-based modeling attack [2]

- Reason 2: to attack APUFs at y-XOR APUF, the adversary needs to compute Δ. But compute Δ is infeasible because the output of x-XOR PUF (a) is not known.

57

Cannot compute Φ 𝑐 𝑜𝑟 Δ

Other Contributions

Theoretical

Enhanced Reliability based Modeling Attacks on APUF and XOR APUFs

Proved Logistic Regression on XOR APUF is the best attack

Proved Logistic Regression on iPUF is not applicable

Engineering

Implemented APUF, XOR, and iPUF on FPGA

Studied good and bad FPGA-implemented APUF based PUF

All source codes available online: https://github.com/scluconn/DA_PUF_Library/

Detailed tutorial online: https://www.youtube.com/playlist?list=PLK5NNs4GceLQw7bOEHSdZOwHlmSF1zvSW

58

6. Conclusion

We explain how the reliability-based modeling attack on XOR PUF works

We propose a new lightweight PUF design (iPUF) which is secure against the state-of-the art of modelling attacks.

59

Literature

1. https://slideplayer.com/slide/3927633/

2. Cryptanalysis of electrical PUFs via machine learning algorithms – Master Thesis of Jan Solter

3. The Gap Between Promise and Reality: On the Insecurity of XOR Arbiter PUFs CHES, September 16 th , 2015, Georg T. Becker

4. https://en.wikipedia.org/wiki/CMA-ES

60

Thank you for your attention!

and any questions?