11 WRTLT pptx 最近の更新履歴 Hideo Fujiwara

WAGSR:

Web Application for

Generalized Feed Forward Shift Registers

Katsuya Fujiwara* and Hideo Fujiwara**

* Akita University

** Osaka Gakuin University

2

Background and Motivation

2

Quality 

scan

reset Scan-in



Combinational Logic Circuit   (Kernel)

x

Testability: Good Scan design makes testing easier

Scan Design

Security: Bad Scan chains can be used to steal important information such as secret keys of

cryptographic chips.

There exists an inherent contradiction between testability and security. There is a need for an efficient solution that satisfies both testability and security.

3

Our Previous Works

  Proposed a secure scan design approach

(ASP-DAC 2010, 2011, WRTLT 2010, 2011)

◦  Satisfies both testability and security

◦  Replaces original scan chains with modified scan chains using SR-equivalent circuits, e.g. inversion-inserted linear-feed-

forward shift registers (I²LF²SR)

Which leads to:

◦  Little area overhead

◦  No performance overhead

◦  No need to change traditional ATPG algorithm

y₁ y₂ y₃

x z

I²LF²SR

4

In This Work

  Introduce a new class of extended SR called generalized feed- forward SR (GF²SR) which is an extension of I²LF²SR.

◦  Still satisfy both testability and security

◦  Much wider than I²LF²SR

Which leads to:

◦  Higher cardinality than I²LF²SR

◦  More secure than I²LF²SR _y

1 ^y2 ^y3

x z

I²LF²SR

y1 y2 y3

x
z

GF²SR

5

Replacement of scan chain by modified scan chain

Scan Chain Secret Register

Secret Register

Standard Scan Chain

Standard Scan Chain Modified Scan

Chain

Our Secure Scan Design

6

Generalized Feed Forward Shift Registers (GF

SR)

y1 y2 y3

x
z

y1 y2 y3

x
z

y1 y2 y3

x
z

7

Generalized Feed Forward Shift Registers (GF

SR)

y1 y2 y3

x
z

y1 y2 y3

x
z

y1 y2 y3

x
z

Our objective is to show that GF

SR satisfies both

testability and security .

Let us first consider the testability.

! ^!_! ^!_! ^!! !

!_{(!) !}

!^{(!) !}!^{(!) !!(!)}

!_{(! + 1)}

!_{(! + 2)}

!_{(! + 3)}

8

How to Control/Observe (by Symbolic Simulation)

y1 y2 y3

x
z

Input sequence

Initial state

! ^!! ^!! ^!! !

!_{(!) !}

!^{(!) !}!^{(!) !!(!) !!}(!)

!_{(! + 1)} !_{(!) !}

!(!) ^!!(!) ⊕ ! ! ⋅ !!(!) ^!!(!) ⊕ ! ! ⋅ !!(!)

!_{(! + 2)} !_{(! + 1)} !_{(!) !}

!(!) ⊕ ! ! + 1 ⋅ ! ! ^!_!(!) ⊕ ! ! + 1 ⋅ ! !

!_{(! + 3)} ! ! +₂ !_{(! + 1)} ! ! ⊕ ! ! + 2 ⋅ ! ! + 1 ^{! !} ⊕ ! ! + 2 ⋅ ! ! + 1

9

How to Control/Observe (by Symbolic Simulation)

y1 y2 y3

x
z

Final state

Output sequence

10

How to Control/Observe (by Symbolic Simulation)

y1 y2 y3

x
z

! ^!! ^!! ^!! !

!_{(!) !}

!^{(!) !}!^{(!) !!(!) !(!) = !!(!)}

!_{(! + 1)} !_{(!) !}

!^{(!) !}!(!) ⊕ ! ! ⋅ !_!(!) !(! + 1) = !_!(!) ⊕ ! ! ⋅ !_!(!)

!_{(! + 2)} !_{(! + 1)} !_{(!) !}

!(!) ⊕ ! ! + 1 ⋅ ! ! !(! + 2) = !_!(!) ⊕ ! ! + 1 ⋅ ! !

!_{(! + 3)} ! ! +₂

= !!(! + 3)

!_{(! + 1)}

= !!(! + 3)

! ! ⊕ ! ! + 2 ⋅ ! ! + 1

= !^!(! + 3)

! ! + 3 = ! ! ⊕ ! ! + 2 ⋅ ! ! + 1

!_{(!) = !!}(! + 3) ⊕ !_!(! + 3) ⋅ !!(! + 3)

!(! + 1) = !!^{(! + 3)}

!(! + 2) = !!(! + 3)

!_!(!) = !(! + 2) ⊕ !(! + 1) ⋅ !(!)

!_!(!) = !(! + 1) ⊕ !(!) ⋅ !_!(!)

= !(! + 1) ⊕ !(!) ⋅ !(! + 2) ⊕ !(! + 1) ⋅ !(!)

!!(!) = !(!)

State justification

(Scan in) State identification

(Scan out)

The transfer sequence is expressed by the final state only, independently of the initial state.

Hence, state-justification is easy, i.e., easy to scan-in.

11

How to Control/Observe (by Symbolic Simulation)

y1 y2 y3

x
z

! ^!! ^!! ^!! !

!_{(!) !}

!^{(!) !}!^{(!) !!(!) !(!) = !!(!)}

!_{(! + 1)} !_{(!) !}

!^{(!) !}!(!) ⊕ ! ! ⋅ !_!(!) !(! + 1) = !_!(!) ⊕ ! ! ⋅ !_!(!)

!_{(! + 2)} !_{(! + 1)} !_{(!) !}

!(!) ⊕ ! ! + 1 ⋅ ! ! !(! + 2) = !_!(!) ⊕ ! ! + 1 ⋅ ! !

!_{(! + 3)} ! ! +₂

= !!(! + 3)

!_{(! + 1)}

= !!(! + 3)

! ! ⊕ ! ! + 2 ⋅ ! ! + 1

= !^!(! + 3)

! ! + 3 = ! ! ⊕ ! ! + 2 ⋅ ! ! + 1

!_{(!) = !!}(! + 3) ⊕ !_!(! + 3) ⋅ !!(! + 3)

!(! + 1) = !!^{(! + 3)}

!(! + 2) = !!(! + 3)

!_!(!) = !(! + 2) ⊕ !(! + 1) ⋅ !(!)

!_!(!) = !(! + 1) ⊕ !(!) ⋅ !_!(!)

= !(! + 1) ⊕ !(!) ⋅ !(! + 2) ⊕ !(! + 1) ⋅ !(!)

!!(!) = !(!)

State justification

(Scan in) State identification

(Scan out)

Any initial state can be identified from the input-output sequence and the circuit information, where the input sequence is arbitrary.

Hence, state-identification is easy.

12

How to Control/Observe (by Symbolic Simulation)

y1 y2 y3

x
z

! ^!_! ^!_! ^!! !

!_{(!) !}

!^{(!) !}!^{(!) !!(!) !(!) = !!(!)}

!_{(! + 1)} !_{(!) !}

!(!) ^!!(!) ⊕ ! ! ⋅ !!(!) !(! + 1) = !_!(!) ⊕ ! ! ⋅ !!(!)

!_{(! + 2)} !_{(! + 1)} !_{(!) !}

!(!) ⊕ ! ! + 1 ⋅ ! ! !(! + 2) = !_!(!) ⊕ ! ! + 1 ⋅ ! !

!_{(! + 3)} ! ! +₂

= !_!(! + 3)

!_{(! + 1)}

= !_!(! + 3)

! ! ⊕ ! ! + 2 ⋅ ! ! + 1

= !^!(! + 3)

! ! + 3 = ! ! ⊕ ! ! + 2 ⋅ ! ! + 1

!_{(!) = !!}(! + 3) ⊕ !_!(! + 3) ⋅ !_!(! + 3)

!(! + 1) = !_!(! + 3)

!(! + 2) = !_!(! + 3)

!_!(!) = !(! + 2) ⊕ !(! + 1) ⋅ !(!)

!_!(!) = !(! + 1) ⊕ !(!) ⋅ !_!(!)

= !(! + 1) ⊕ !(!) ⋅ !(! + 2) ⊕ !(! + 1) ⋅ !(!)

!!(!) = !(!)

State justification

(Scan in) State identification

(Scan out)

However, it is hard to derive those equations and to solve the solutions if the circuit size becomes large.

As an alternative method, logic simulation can be considered instead of symbolic simulation.

!"#$ _{! !}

! ^!! ^{!! !}

! !" _{⊕ !}

! + _{1 !} !" _{⊕ !}

! + _{2 ! !} !" _{⊕ !}

! + 3 _{! ! !}

13

How to Control ESR (by Implication Operation)

y1 y2 y3

x
z

How to derive transfer sequence for final state Final state

!"#$ _{! !}

! ^!! ^{!! !}

! !" _{⊕ !}

! + _{1 !} !" _{⊕ !}

! + _{2 ! !} !" _{⊕ !}

! + 3 _{! ! !}

14

How to Control ESR (by Implication Operation)

y1 y2 y3

x
z

How to derive transfer sequence for final state

!"#$ _{! !}

! ^!! ^{!! !}

! !" _{⊕ !}

! + _{1 !} !" _{⊕ !}

! + _{2 ! !} !" _{⊕ !}

! + 3 _{! ! !}

15

How to Control ESR (by Implication Operation)

y1 y2 y3

x
z

How to derive transfer sequence for final state

!"#$ _{! !}

! ^!! ^{!! !}

! !" _{⊕ !}

! + _{1 !} !" _{⊕ !}

! + _{2 ! !} !" _{⊕ !}

! + 3 _{! ! !}

16

How to Control ESR (by Implication Operation)

y1 y2 y3

x
z

How to derive transfer sequence for final state

!"#$ _{! !}

! ^!! ^{!! !}

! !" _{⊕ !}

! + _{1 !} !" _{⊕ !}

! + _{2 ! !} !" _{⊕ !}

! + 3 _{! ! !}

17

How to Control ESR (by Implication Operation)

y1 y2 y3

x
z

The transfer sequence can be uniquely obtained very fast and easily only by logic simulation of implication

18

How to Control ESR

y1 y2 y3

x
z
^{x y1 y2 y3 z}

x y1 y2 y3 z

1 1 0

x y1 y2 y3 z

1 1 0

19

How to Control ESR (After Implication)

y1 y2 y3

x
z
^{x y1 y2 y3 z}

x y1 y2 y3 z

1 1 1

1

1 1

1 1 0

x y1 y2 y3 z

0 1 1

0

1 0

1 1 0

Since the attacker does not know the structure of ESR,

he/she cannot find out the transfer sequence for final state (1, 1, 0).

!"#$ _{! !}

! ^!! ^{!! !}

! _! !" _{⊕ !} !(!" ⊕ !) ⊕ ! ^! _!

! + _{1 ! !} !" _{⊕ ! ! !}

! + ₂ ! _{! ! ! !}

20

How to Observe ESR (by Implication Operation)

y1 y2 y3

x
z

How to identify the initial state from input/output sequence

!"#$ _{! !}

! ^!! ^{!! !}

! _! !" _{⊕ !} !(!" ⊕ !) ⊕ ! ^! _!

! + _{1 ! !} !" _{⊕ ! ! !}

! + ₂ ! _{! ! ! !}

21

How to Observe ESR (by Implication Operation)

y1 y2 y3

x
z

How to identify the initial state from input/output sequence

!"#$ _{! !}

! ^!! ^{!! !}

! _! !" _{⊕ !} !(!" ⊕ !) ⊕ ! ^! _!

! + _{1 ! !} !" _{⊕ ! ! !}

! + ₂ ! _{! ! ! !}

22

How to Observe ESR (by Implication Operation)

y1 y2 y3

x
z

How to identify the initial state from input/output sequence

!"#$ _{! !}

! ^!! ^{!! !}

! _! !" _{⊕ !} !(!" ⊕ !) ⊕ ! ^! _!

! + _{1 ! !} !" _{⊕ ! ! !}

! + ₂ ! _{! ! ! !}

23

How to Observe ESR (by Implication Operation)

y1 y2 y3

x
z

How to identify the initial state from input/output sequence

!"#$ _{! !}

! ^!! ^{!! !}

! _! !" _{⊕ !} !(!" ⊕ !) ⊕ ! ^! _!

! + _{1 ! !} !" _{⊕ ! ! !}

! + ₂ ! _{! ! ! !}

24

How to Observe ESR (by Implication Operation)

y1 y2 y3

x
z

The initial state can be uniquely identified only from input- output sequence by logic simulation of implication

25

How to Observe ESR

y1 y2 y3

x
z
^{x y1 y2 y3 z}

x y1 y2 y3 ^z

1 1 0

0 1 1

x y1 y2 y3 ^z

1 1 0

0 1 1

26

How to Observe ESR (After Implication)

y1 y2 y3

x
z
^{x y1 y2 y3 z}

x y1 y2 y3 ^z

1 1 0

0 1 0 1 0 1

1 1 1

0 1 1

x y1 y2 y3 ^z

1 1 0

1 1 0 1 1 1

1 1 1

0 1 1

Since the attacker does not know the structure of ESR, he/she cannot identify the initial state as (0, 1, 0).

27

Security Level of Proposed Scan Design

The security level of the secure scan architecture is determined by the probability that an attacker can guess right the structure of the GF²SR circuit.

Hence the attack probability approximates to the reciprocal of the cardinality of the class of GF²SRs.

28

Cardinality of Each Class of Extended SRs

(2

-1)(2

-1)

The complexity of identifying the structure of GF²SR is proportional to the cardinality of the class of GF²SR.

So, it is very hard and intractable to identify the structure of a given extended SR from the information on input/output relation only.

GF

SR

I²SR LF²SR

I

LF

SR

(2 - 1) ²

29

WAGSR (Web Application for GF

SR)

Design of GF²SR by means of logic expression

As a tool to assist design and analysis of GF²SR, we implemented a web application program called WAGSR.

30

WAGSR (Web Application for GF

SR)

Symbolic simulation

31

WAGSR (Web Application for GF

SR)

State-justification by implication

32

WAGSR (Web Application for GF

SR)

State-identification by implication

33

Conclusion

  Introduced a new class of extended SR called generalized feed-forward SR (GF²SR) which is an extension of I²LF²SR.

◦ Still satisfy both testability and security

◦ Much wider than ^I2LF2SR Which leads to:

◦ Higher cardinality than ^I2LF2SR

◦ More secure than ^I2LF2SR

  A web application called WAGSR was introduced to assist design and analysis of GF²SR

  The proposed approach:

◦ Little area overhead

◦ No performance overhead

◦ No need to change traditional ATPG algorithm

34

Thank you