Scan based side-channel attacks

A Research on Scan based side-channel attacks

Abstract

The purpose of this research survey paper is to introduce us to a fairly new concept (2005) of scan-based attacks to understand the underlying threats of this attack and how scientists and research scholars have developed secure scan-chains as a countermeasure to this attack. It is a known fact that physical interactions of cryptosystems can be easily monitored. Attackers make use of this side-channel information to break some of the highly secure encryption standards like AES and Stream cipher. The underlying idea of side-channel attacks (SCA) is to look at the way cryptographic algorithms are implemented rather than the algorithm itself. Cryptographic Algorithms like AES and Stream-cipher by itself are highly secure but the methods in which they are implemented may not always be secure. Attackers focus on these types of vulnerabilities to extract useful information. In this research survey, we shall discuss the various scan-based attacks on AES and stream-cipher presented at several reputed symposiums. We will also study some methods to build secure scan chain architecture.

1. Introduction to side-channel attacks

In cryptography, a side channel attack is any attack based on information gained from the physical implementation of a cryptosystem, rather than brute force or theoretical weaknesses in the algorithms [3]. In 1 we see the communication between two users Bob and Alice is intercepted by a third party Eve. Alice has key Ka and Bob has key Kb and the message ‘M' exchanged between the two parties. The attacker Eve utilizes the physical vulnerabilities of the system such as heat, visible light, electromagnetic radiation and sound in A and other factors like time of execution, power consumption. The attacks performs various attacks on basis of these physical characteristics like power attacks, timing attacks, fault injection attacks in order to break the encrypted message ‘M'.

1.1 Some of the known side - channel attacks

The complete capabilities of these attacks have still not being exploited; however there exists several examples of such attacks through time. We can summarize some of the famous attacks as below [1][2]

— Power Analysis Attack -Kocher(1998)

— Timing Attack-Kocher (1996)

— Fault Attack-Boneh(1996)

— EM Attack -Kuhn(1998)

— Acoustic Attack -Shamir(2004)

— Visible Light Attack- Kuhn(2002)

— Error Message Attack - Bleichenbacher. (1998)

— Frequency-based Attack -Liu(2004)

— Scan-based Attack- Yang(2005)

Side-channel attacks are threats to several devices like credit cards, RFID's, smart cards, PDA's etc.

2. Scan - based side channel attacks

In this paper we focus on scan-based side channel attacks, general idea behind the attack, how they are performed and how we can prevent such attacks. With increase in complexity of VLSI systems, the need for better tools for testing and debugging purposes has become increasingly important. Scan-chains were developed for the purpose of testing and debugging. Today we use various debugging tools like JTAG debuggers based on the concept of scan chains. Scan - chain based testing is a very powerful and popular method. We will see how this technique has become a double edged sword opening several side-channels to cryptanalysis.

2.1 Scan chains [1]

Scan chains is the technique used in Design for Test. The objective is to make testing easier by providing a simple way to set and observe every flip-flop in an IC. 3 gives the typical structure of a scan chain. A special signal called scan select/test_select is added to a design. When this signal is asserted, every flip-flop in the design is connected into a long shift register, one input pin provides the data to this chain, and one output pin is connected to the output of the chain scan out. Then using the chip's clock signal, an arbitrary pattern can be entered into the chain of flips flops, and/or the state of every flip flop can be read out (scan out).

2.1 Overview of current research on Scan-based attacks

In [1] Yang, Wu, Karri perform scan-based attacks for hardware implementation of the Data encryption standard. In [2] D. Mukhopadhyay, S. Banerjee, D. RoyChowdhury, and B. Bhattacharya discuss scan-based attacks on stream cipher and provides a secure architecture design for scan chains. Both these papers lay stress on need for new designs for secure scan chains. The basic idea is to provide increased control to authorized users and reduce the controlling capabilities of unauthorized users and ensure these new scan chain designs are non-trivial in nature.

An Attack block cipher was presented at DAC'05 and attack on Stream cipher was presented at the Asian test symposium ATS'05.

Several side-channel attacks on AES and DES have been established. In October 2005, Dag Arne Osvik,Adi Shamirand Eran Tromer presented a paper demonstrating several cache-timing attacks against AES.[3]One attack was able to obtain an entire AES key after only 800 operations triggering encryptions, in a total of 65 milliseconds. This attack requires the attacker to be able to run programs on the same system that is performing AES.

3. Attack on Block cipher - Yang & Karri [1]

In [1] we see how scan chains are used to break DES standard. This can further be extended to break AES Standard. For better understanding of this let us understand DES algorithm.

Phase1: 64 bit plain text is permuted and stored in 32 bit L and R registers.

Phase2: A round operation composed of function f and exclusive-ored is performed 16 times. In the ith round, the 32-bit R and the 48-bit round key Ki are inputs to the f function. The output of the f function is exclusive-ored with L to form R for the round i+1. The R used in round ‘i' becomes the L for round i+1. Function f shaded in 2 performs following operations to generate a 32-bit output.

Phase3: In this phase the two 32-bit outputs of round 16 are concatenated and permuted using the inverse permutation and loaded into the output register.

Round key generation: Since each of the sixteen rounds uses a 48-bit round key, a round key generation algorithm is used to generate the sixteen round keys K1, K2 …K16 from the 56-bit user key. The round key generation uses simple bit-permutation and shift operations. Each round key contains 48 bits of the 56-bit user key.

Breaking the DES Algorithm [1]:

Assumptions: What does the attacker know?

* The attacker knows the DES algorithm as its Public

* Attacker has access to some high level timing information for DES implementation on ASIC by the vendor.

* Attacker is aware of the general implementation structure of the DES algorithm but is not aware of the exact registers used in design.

* Round keys are stored in a secure location. They are not included in the scan-chain.

* The attacker is not aware of the exact structure of the scan-chain

The paper [1] by yang and Karri proposes a two-phase attack on DES algorithm. This is described in a step by step fashion below.

Attack step 1: Determine scan-chain structure.

1. Reset the DES chip and run it in normal operation mode for 1 clock cycle. This way we can load the known plaintext word into the input register

2. The next step is to test mode and scan out the bit stream (pattern 1).

3. Then switch back to the normal mode and run for one more clock cycle this way the plain text gets loaded to registers L and R.

4. Now switch to test mode and scan out bit steam (pattern 2).

5. Steps 1 to 3 are repeated using plaintext with just 1 bit difference in position more the first plaintext. These patterns are saved as pattern 3 and 4.

We can infer the following:

Difference (Pattern 1 and Pattern 3) = 1bit. -> Determines location of input register flip - flop in the scan chain.

Difference (Pattern 3 and Pattern 4) = 2 bit -> 1 bit is from input register and other is from L or R registers.

Repeating step 5 63 times we can determine structure of scan chains (Locations of all the flip-flops of input register, L and R registers)

Attack step2: Recover Round Key 1

Since we now are aware of locations of registers L and R in the scan chain. We can break the DES algorithm by applying 3 known plaintexts by analyzing the DES algorithm.

From 4. We can split DES round implementation into the following operations.

L1=R0 ----------------------------------------->(1)

R1=L0⊕d; ------------------------------------>(2)

d=permutation(c); --------------------------->(3)

a=Expand(r); --------------------------------->(4)

b=a⊕K1;-------------------------------------->(5)

c= S_box(b);---------------------------------->(6)

Load a plaintext word (L0 and R0) and run 3 clock cycles. Switch to test mode and scan out the bit stream.

Now L1 and R1 are known. Is this information enough to discover round key K1?

From equation (2), d is known (=L0⊕R1).

From equation (3), c is known (c = inverse permutation (d)).

From equation (4), a is known (expand (R0)).

From equation 5, if we know b, we can find round key K1 (K1 = a⊕b).

Since we know a, we need to find b the input to the s-boxes, from their output c.

Attack step 3: Recover User Key

We are aware that each round key has 48 bits of the 56 bit user key. By careful analysis of the DES round key generation algorithm shows we find that Round key K1 consists of the following 48 bits of the user key: 45,24,9,32,22,51,8,29,38,44,53,16,39,10,2,1,43,30,31,37,36,3,52,15,54,4,14,27,12,42,21,6,11,26,55,5,33,25,13,35,4 8,56,19,47,18,34,28,7.

* Bits 17, 20, 23, 40, 41, 46, 49 and 50 are missing in Round Key K1.

* Bits 17, 20, 23, 40, 41, 49 and 50 can be obtained from round key K2

* Bit 46 can be obtained from round key K3.

Hence [1] concludes that to find entire user key we need to find round keys K2 and K3 as well. Using an iterative architecture, all sixteen rounds are calculated using the same register L and R. Scan (00000000)16 into L and (00000000)16 into R after the first round as L1 and R1; run one cycle and scan out L2 and R2.Do the same work using L=0 and R= (11111111)16 and then L=0 and R= (22222222)16. From these (L2, R2) pairs, we can retrieve K2. Similarly, we can get K3.
Attack on stream cipher[2] - D. Mukhopadhyay, S. Banerjee, D. RoyChowdhury, and B. Bhattacharya.

This paper proposes a scan- based attack on LFSR -Based stream ciphers and several methods to prevent scan-based attacks by using secure scan -chain techniques.

Let us take a look at the hardware implementation of stream ciphers. Stream cipher cryptography is a classical method of secured information exchange. One of the well known implementation techniques is shown in 5. The outputs of several independent Linear Feedback Shift Registers (LFSR) are combined using a Boolean function F to produce the pseudo random bit stream. At each clock cycle, each of the LFSRs produces a bit of output. These bits are combined by the Boolean function f to produce a pseudo random bit. Thus, one pseudo random bit is produced at each clock cycle and hence the rate of encryption is also one bit per clock cycle. The secret key of the system consists of the initial conditions of all the LFSRs.

In order to explain the scan based attack we consider the stream cipher method where the model is shown in 6, where the LFSRs of 5 are replaced by reconfigurable LFSRs. The re-configurable LFSR shown in 7 consists of a Shift Register (SR) and a Configurable

Register (CR). The CR is loaded with the coefficients of a primitive polynomial from memory.

Attacker's Knowledge:

1. The attackers know the stream cipher algorithm as its open to flag.

2. High level timing information is known from the ASIC vendor.

3. Attacker knows the size of the seed.

4. The attacker does not know the primitive polynomials which are stored in the memory since the memory is not stored in scan-chain.

5. The attacker also does not know the structure of the scan chain.

Attacking the Stream Cipher Using Scan Chains

The prime Objective of the attacker is to obtain the message stream (m1 , m2 ,…, ml) from the stream of ciphertexts (c1 , c2 ,…, cl).In [2] they authors propose a three Stage Attack. The first part is to ascertain the structure of the seeds followed by the positions of the registers. From the data collected by the first two stages, it is possible to decipher the cryptogram.

Ascertain the Structure of the Seed:

The attacker first scans out the state of the SR and CR registers. He is however not aware of the correspondence of the registers with the scan patterns. The next step is to load the seed with all zero values and apply 1 clock cycle.

The Next step is to switch the scanning to test mode and collect the number of one's = s.wt(m(0)). The next step is to set the first bit of seed to 1 and rest of the bits to 0 and again apply 1 clock cycle. The bit with value ‘1' can go either to the memory or to the SRs

If the bit goes to the SR, we have the corresponding no of one's = s.wt(m(0))+1 else the number of one's = s.wt(m(p)). Repeating the same for all the w bits of the seed we can ascertain the structure of the seed.

Deciphering the Cryptogram:

Decoding cl : The attacker knows the values of the SR registers of all the LFSRs: {SR[n],SR[n-1],……SR[2],SR[1]}. The previous state of the LFSRs can be computed as: {SR[n-1],SR[n-2],…,SR[1],SR[n] SR[1]} (as CR[1] is always 1) He sets the message bit of the device to zero and the device in normal mode. One clock cycle is applied and the output is observed. The output is the value of kl. Thus ml = cl kl

Decoding c1,c2,….,cl-1: For decoding cl-1, similarly the attacker computes the previous stage of the SR register of all the LFSRs. Continuing the step for l times leads to the decoding of the entire cryptogram. Thus, the time complexity is O(nsl)

Techniques for Secure scan-chains

As a result of the various scan - chain based attacks cryptologists are proposing secure scan - chain architectures. In this report we discuss three different techniques for secure scan - chains

1. Scrambling Technique [2]

Scrambling Technique proposes dynamic Re-ordering of scan chains

This technique uses separate test key to program the inter-connections. Due to the dynamic reordering of scan chains the wiring complexity increases and proportionally the number of flip flops also increases. One of the demerits of this technique is that even thought we dynamically re-order the scan chains in depth statistical analysis may reveal the ordering.

2. Lock and Key technique[4]

The Lock & Key security measure we are proposing can be used to secure both single and multiple-scan designs. For either case, the scan chain can be divided into smaller equal length sub-chains. Test vectors are not sequentially shifted into each sub-chain but rather a linear feedback shift register (LFSR) randomly selects a sub-chain to be filled. 9 shows general architecture for the Lock & Key method for single-scan design. The aim of this method is to prevent those who do not hold the test key from manipulating the scan chain and revealing vital information about the chip.

In this technique the authorized user holds a test key. The test security controller (TSC) compares the key. If the wrong key is entered the design goes into an unsecured mode unless its reset.

The demerits of this technique are that it introduces large area overhead. The TSC uses flip-flops as well. If an additional key is used there again exists overhead on key exchange.

As a conclusion, we can say that flip-flops related to secret data always lead to attacks as they can be easily exploited. We need to ensure that is area overhead is less hence adding an additional key is definitely not desirable. On-line testing should be made possible.

3. Secure scan by karri[3]

Test and debug crypto chips using general scan based DFT the information obtained from scan chains should not be useful in retrieving the secret key. Two copies of the secret key are maintained the secure key and the Mirror key. Secure key is hardwired or in secure memory location and memory key is used for testing purposes.

Two modes of operation are possible, the first being insecure mode where the secure key is isolated and the mirror key are used for the purpose of debug. The second mode is the secure mode where the secure key is used and debugging is disabled.

The merits of this method are that this ensure a good test speed, hence does not degrade the test speed. The circuit incurred due to secure scan is easy to test and can be easily integrated into the current scan DFT flow. The area overhead incurred is very small as compared to lock and key technique. The demerits of this technique are that on-line testing in not possible and the testing of MKR is not straight-forward.

Conclusion:

Scan chain is the most popular way to achieve high fault coverage in digital circuits. But in the different papers discussed in this report have shown that hardware designs of stream ciphers and DES are insecure if scan-chains are used. Thus scan chains provide a means for side channel attacks against crypto devices. Secure scan-chains must be employed to prevent these attacks.

References

[1]Bo Yang, Kaijie Wu and R. Karri, Scan Based Channel Attack on Dedicated Hardware Implementation of Data Encryption Standard, Proceedings of International Conference (ITC), 26-28 Oct 2004, pp. 334-344.

[2]D. Mukhopadhyay, S. Banerjee, D. RoyChowdhury, and B. Bhattacharya, Cryptoscan: Secured Scan Chain Architecture, Proceedings of 14th IEEE Asian Test Symposium, (ATS), 2005, pp. 348-353.

[3]Bo Yang, Kaijie Wu and R. Karri, Secure scan:A Design-for-test Architecture for Crypto-chips, Proceedings of 42nd Design Automation Conference (DAC), 2005, pp. 135-140

[4]Jeremy Lee, Mohammed Tehranipoor, Chintan Patel, and Jim Plusquellic: Securing Scan Design Using Lock & Key Technique.

[5] P. Kitsos, G. Kostopoulos, N. Sklavos, and O. Koufopavlou, Hardware Implementation of the RC4 Stream Cipher, Proceedings of 46th IEEE Midwest Symposium on Circuits and Systems, December 27-30, Cairo, Egypt, 2003, vol. 3, pp. 1363-1366.

[6] Bo Yang, Kaijie Wu and R. Karri,:A Design-for-test Architecture for Crypto-chips, IEEE Transactions on Computer Aided-Design of Integrated Circuits and Systems, vol 25, no 10, October 2006, pp. 2287-2293.

Please be aware that the free essay that you were just reading was not written by us. This essay, and all of the others available to view on the website, were provided to us by students in exchange for services that we offer. This relationship helps our students to get an even better deal while also contributing to the biggest free essay resource in the UK!