[Back to Results | New Search]

Student Number 91522066 Author Yuan-Han Kuo(³¢»·¿«) Author's Email Address No Public. Statistics This thesis had been viewed 2103 times. Download 774 times. Department Computer Science and Information Engineering Year 2003 Semester 2 Degree Master Type of Document Master's Thesis Language English Title The Research of Power Analysis against AES Date of Defense 2004-06-07 Page Count 80 Keyword AES DPA Physical cryptanalysis Power analysis attack Smart cards SPA Abstract Nowadays, digital information grows extremely in our daily life, and the requirement of tamper-resistant device that endowed with executing the procedures of cryptosystems or storing the ersonal

secret information increases correspondingly. The smart cards are becoming the representative of tamper-resistant device. However, when these cryptosystems are operated in the open environment, no one can ensure the security of information even information is protected by cryptosystems. Physical cryptanalysis is a modern and increasingly potent threat to the security of information held on smart cards. By measuring physical features such as power consumption, time spending or electromagnetic emission, the attackers can infer secret information from smart cards with naive implementations of cryptosystems.

The Advanced Encryption Standard (AES) is the next generation standard block cipher selected by NIST to replace DES in 2000. AES will become the most widespread block cipher standard. Power

analysis attack is the most useful cryptanalysis at present, and it is also practicable on the AES. In this thesis, the power analysis against AES will be discussed.

The simple power analysis (SPA) is easy to realize in real world. In order to defend the AES against SPA, the weakness of existence SPA-resistant countermeasures are analyzed, and an

improvement is proposed. Second, the DPA-resistant algorithms of AES suffer from high-order differential power analysis (HODPA). To

this end, possible countermeasure is also discussed.

The balanced Hamming weight scheme is one of the effective ways to prevent from power analysis attack. We found that even involving the balanced Hamming weight to protect AES, it may not secure enough under some careless implementations. The weaknesses of balanced Hamming weight scheme will be analyzed and the procedure of the proposed flipping DPA attack is described to derive the secret key of AES.

In this thesis, the experiments will be shown at the end of each proposed method to confirm our contentions. Some experiments, especially the SPA-based attack, the power trace will be pre-process before analyzing. At the end of this thesis, the

pre-process technique will be described.Table of Content {1}Introduction{1}

{1.1}Motivation{1}

{1.2}Power Analysis on AES{2}

{1.3}Overview of the Thesis{4}

{2}Review of Power Analysis Attack and AES{6}

{2.1}Review of Power Analysis Attack{6}

{2.1.1}Simple power analysis{6}

{2.1.2}Differential power analysis{7}

{2.1.3}High-order differential power analysis{9}

{2.2}Review of AES: the Rijndeal Cipher{10}

{2.2.1}Round transformation{11}

{2.2.2}Key expansion of Rijndael{12}

{2.3}Examinations of Power Analysis against AES{14}

{2.3.1}Experimental setup{14}

{2.3.2}DPA against AES{14}

{3}Improvements of AES against Power Analysis Attack{17}

{3.1}Motivation{17}

{3.2}An Improvement of MixColumn against SPA{18}

{3.2.1}SPA attack on MixColumn operation{18}

{3.2.2}Possible countermeasures{19}

{3.2.3}Experimental results{21}

{3.3}An Improvement of Masking Method against High-Order DPA{22}

{3.3.1}Review of masking method on AES{24}

{3.3.2}Proposed algorithm against HODPA{28}

{3.3.3}Discussion{31}

{3.4}Summary{33}

{4}Flipping DPA Attack against AES{35}

{4.1}Motivation{35}

{4.2}Software Balanced Hamming Weight Schemes{36}

{4.3}Analyses of Flipping Model{37}

{4.3.1}Akkar's flipping model{38}

{4.3.2}Analysis of KeyAddition on flipping model{38}

{4.4}Flipping DPA Attack Procedures{39}

{4.5}Experimental Results{43}

{4.6}Discussions{44}

{4.6.1}The disadvantage of balanced Hamming weight scheme{44}

{4.6.2}Hamming weight leakage from loading the secret key{44}

{5}Enhancement of Power Analysis Attack{48}

{5.1}Motivation{48}

{5.2}Frequency Domain Analysis{49}

{5.3}Basic Idea of Digital Filter Design{52}

{5.3.1}Digital transfer functions{53}

{5.3.2}Digital filter implementations{55}

{5.4}Applications of DSP on Power Analysis Attack{56}

{5.4.1}Frequency domain analysis of power trace{57}

{5.4.2}Filtering technique on power analysis{57}

{5.4.3}Design an appropriate filter for DPA{59}

{6}Conclusions{63}

{6.1}Brief Review of Main Contributions{63}

{6.2}Further Research Topics and Directions{64}Reference [1]

The ATMEL, Inc., <http://www.atmel.com>

[2]

The MathWorks, Inc., {<http://www.mathworks.com>

[3]

The Tektronix, Inc., {<http://www.tektronix.com>

[4]

National Bureau of Standards, ``Data Encryption Standard,'

Federal Information Processing Standards Publication 46,

Jan. 1977.

[5]

M. Akkar, R. Bevan, P. Dischamp and D. Moyart, ``Power Analysis,

What Is Now Possible,' Advances in Cryptology - ASIACRYPT

2000, Lecture Notes in Computer Science vol.1976, pp.489-502,

Springer-Verlag, 2000.

[6]

M. Akkar and C. Giraud, ``An Implementation of DES and AES, Secure

against Some Attacks,' Proceedings of Workshop on

Cryptographic Hardware and Embedded Systems - CHES 2001, Lecture

Notes in Computer Science vol.2162, pp.309-318, Springer-Verlag,

2001.

[7]

M. Akkar and C. Giraud, ``A Generic Protection against High-Order

Differential Power Analaysis,' Proceedings of Fast

Software Encryption - FSE 2003, Lecture Notes in Computer Science

vol.2887, pp.192-205, Springer-Verlag, 2003.

[8]

M. Akkar, R. Bevan and L. Goubin, ``Two Power Analysis Attacks

against One-Mask Methods,' Proceedings of Fast Software

Encryption - FSE 2004, Lecture Notes in Computer Science

vol.3017, Springer-Verlag, 2004.

[9]

E. Biham and A. Shamir, ``A New Cryptanalytic Attack on DES:

Differential Fault Analysis,' Oct. 1996

[10]

E. Biham and A. Shamir, ``Differential Fault Analysis of Secret

Key Cryptosystems,' Advances in Cryptology - CRYPT0'97,

Lecture Notes in Computer Science vol.1249, pp.513-525,

Springer-Verlag, 1997.

[11]

E. Biham and A. Shamir, ``Power Analysis of the Key Scheduling of

the AES Candidates,' Proceedings of the Second Advanced

Encryption Standard (AES) Candidate Conference, Mar. 1999

[12]

J.Blomer and J.P. Seifert, ``Fault based cryptanalysis of the

Advanced Encryption Standard (AES),' Cryptology ePrint

Archive of IACR, No.075, 2002,

available at URL <http://eprint.iacr.org/2002/075>.

[13]

E. Brier, H. Handschuh and C. Tymen, ``Fast Primitives for

Internal Data Scrambling in Tamper Resistant Hardware,"

Proceedings of Workshop on Cryptographic Hardware and

Embedded Systems - CHES 2001, Lecture Notes in Computer Science

vol.2162, pp.16-27, Springer-Verlag, 2001.

[14]

S. Chari, C.S. Jutla, J.R. Rao and P.J. Rohatgi, ``Towards Sound

Approaches to Counteract Power-Analysis Attacks,'

Advances in Cryptology - CRYPTO'99, Springer-Verlag,

pp.398-412, 1999.

[15]

C. Clavier, J.S. Coron and N.Dabbous, ``Differential Power

Analysis in the Presence of Hardware Countermeasures,'

Proceedings of Workshop on Cryptographic Hardware and

Embedded Systems '00, Lecture Notes in Computer Science vol.1965,

pp.252-263, Springer-Verlag, 2000.

[16]

C. Clavier and M. Joye, ``Universal Exponentiation Algorithm: A

First Step Towards Provable SPA-Resistance,' Proceedings

of Workshop on Cryptographic Hardware and Embedded Systems - CHES

2001, Lecture Notes in Computer Science vol.2162, pp.300-308,

Springer-Verlag, 2001.

[17]

J.S. Coron, ``Resistance against Differential Power Analysis for

Elliptic Curve Cryptosystems,' Proceedings of Workshop on

Cryptographic Hardware and Embedded Systems - CHES 1999, Lecture

Notes in Computer Science vol.1717, pp.292-302, Springer-Verlag,

1999.

[18]

J.S. Coron and L. Goubin, ``On Boolean and Arithmetic Masking

against Differential Power Analysis,' Proceedings of

Workshop on Cryptographic Hardware and Embedded Systems - CHES

2000, Lecture Notes in Computer Science vol.1965, pp.231-237,

Springer-Verlag, 2000.

[19]

J.S. Coron and L. Goubin, ``New switch of Boolean and Arithmetic

Masking against Differential Power Analysis,' Proceedings

of Workshop on Cryptographic Hardware and Embedded Systems - CHES

2003, Lecture Notes in Computer Science vol.2779, pp.89-97,

Springer-Verlag, 2003.

[20]

J. Daemen, L.R. Knudsen and V. Rijmen, ``The block cipher

Square,' Proceedings of Fast Software Encryption Workshop

- 1997, Lecture Notes in Computer Science vol.1267, pp.149-165,

Springer-Verlag, 1997.

[21]

J. Daemen and V. Rijmen, ``AES Proposal : Rijndael,' The

First Advanced Encryption Standard Candidate Conference,

N.I.S.T., 1998.

[22]

J. Daemen, M. Peeters and G.V. Assche, ``Bitslice Ciphers and

Power Analysis Attacks,' Proceedings of Fast Software

Encryption - FSE 2000, Lecture Notes in Computer Science vol.

1978, pp.134-149, Springer-Verlag, 2000.

[23]

J.F. Dhem, F. Koeune, P.A. Leroux, P. Mestre, J.J. Quisquater and

J.L. Willems, ``A Practical Implementation of the Timing Attack,"

Crypto Group Technical Report Series CG-1998/1,

Universit'e Catholique de Louvain and Proceedings of the CARDIS

1998, 1998.

[24]

D.M. Etter, ``Engineering Problem Solving with MATLAB,'

Prentice-Hall, 1997.

[25]

P. Fahn and P. Pearson, ``IPA: A New Class of Power Attacks,'

Proceedings of Workshop on Cryptographic Hardware and

Embedded Systems - CHES 1999, Lecture Notes in Computer Science

vol.1717, pp.173-186, Springer-Verlag, 1999.

[26]

K. Gandolfi, C. Mourtel and F. Olivier, ``Electromagnetic

Analysis: Concrete Results,' Proceedings of Workshop on

Cryptographic Hardware and Embedded Systems - CHES 2001, Lecture

Notes in Computer Science vol.2162, pp.251-272, Springer-Verlag,

2001.

[27]

L. Goubin and J. Patarin, ``DES and Differential Power Analysis -

the Duplication Method,' Proceedings of Workshop on

Cryptographic Hardware and Embedded Systems - CHES 1999, Lecture

Notes in Computer Science vol.1717, pp.158-172, Springer-Verlag,

1999.

[28]

J.D. Golic and C. Tymen, ``Multiplicative Masking and Power

Analysis of AES,' Proceedings of Workshop on

Cryptographic Hardware and Embedded Systems - CHES 2002, Lecture

Notes in Computer Science vol.2523, pp.198-212, Springer-Verlag,

2002.

[29]

L. Goubin, ``A Sound Method for Switching Between Boolean and

Arithmetic Masking," Proceedings of Workshop on

Cryptographic Hardware and Embedded Systems - CHES 2001, Lecture

Notes in Computer Science vol.2162, pp.3-15, Springer-Verlag,

2001.

[30]

M. Gomulkiewicz and M. Kutylowski, ``Hamming Weight Attacks on

Crytopraphic Hardware - Breaking Masking Defense,'

European Symposium on Research in Computer Security -

ESORICS 2002, Lecture Notes in Computer Science vol.2502,

pp.90-103, Springer-Verlag, 2002.

[31]

K. Itoh, M. Takenaka and N. Torii, ``DPA Countermeasure Based on

the ``Masking Method',' Information Security and

Cryptology - ICISC 2001, Lecture Notes in Computer Science

vol.2288, pp.440-456, Springer-Verlag, 2002.

[32]

K. Itoh, M. Takenaka and N. Torii, ``Address-Bit Differential

Power Analysis of Cryptographic Schemes OK-ECDH and OK-ECDSA,'

Proceedings of Workshop on Cryptographic Hardware and

Embedded Systems - CHES 2002, Lecture Notes in Computer Science

vol.2523, pp.129-143, Springer-Verlag, 2002.

[33]

K. Itoh, M. Takenaka and N. Torii, ``A Practical Countermeasure

against Address-Bit Differential Power Analysis,'

Proceedings of Workshop on Cryptographic Hardware and

Embedded Systems - CHES 2003, Lecture Notes in Computer Science

vol.2779, pp.382-396, Springer-Verlag, 2003.

[34]

J. Wiley and Sons, ``Programs for Digital Signal Processing,'

IEEE Press, 1979.

[35]

M. Joye and C. Tymen, ``Protections against Differential Analysis

for Elliptic Curve Cryptography: An Algebraic Approach,"

Proceedings of Workshop on Cryptographic Hardware and

Embedded Systems - CHES 2001, Lecture Notes in Computer Science

vol.2162, pp.377-390, Springer-Verlag, 2001.

[36]

M. Joye and S.M. Yen, ``The Montgomery Powering Ladder,'

Proceedings of Workshop on Cryptographic Hardware and

Embedded Systems - CHES 2002, Lecture Notes in Computer Science

vol.2523, pp.291-302, Springer-Verlag, 2003.

[37]

J. Kelsey, B. Schneier, D. Wagner and C. Hall, ``Side Channel

Cryptanalysis of Product Ciphers,' European Symposium on

Research in Computer Security - ESORICS 1998, Lecture Notes in

Computer Science vol.1485, Springer-Verlag, 1998.

[38]

J. Kessels, ``Applying Asynchronous Circuits in Contactless

Smartcards,' Proceedings of ACiD-WG Workshop, Grenoble,

Feb. 2000.

[39]

P. Kocher, ``Timing Attacks on Implementations of Diffie-Hellman,

RSA, DSS, and Other Systems,' Advances in Cryptology -

CRYPTO'96, Lecture Notes in Computer Science, pp.104-113,

Springer-Verlag, 1996.

[40]

P. Kocher, J. Jaffe and B. Jun, ``Introduction to Differential

Power Analysis and Related Attacks,' 1998,

available at URL

<http://www.cryptography.com/dpa/technical>

[41]

P. Kocher, J. Jaffe and B. Jun, ``Differential Power Analysis,'

Advances in Cryptology - CRYPTO'99, pp.388-397,

Springer-Verlag, 1999.

[42]

F. Koeune and J.J. Quisquater, ``A Timing Attack against

Rijndael,' Crypto Group Technical Report Series

CG-1999/1, Uinversit'e Catholique de Louvain, 1999.

[43]

P.Y. Liardet and N.P. Smart, ``Preventing SPA/DPA in ECC Systems

Using the Jacobi form,' Proceedings of Workshop on

Cryptographic Hardware and Embedded Systems - CHES 2001, Lecture

Notes in Computer Science vol.2162, pp.391-401, Springer-Verlag,

2001.

[44]

D. May, H.L. Muller and N.P. Smart, ``Random Register Renaming to

Foil DPA,' Proceedings of Workshop on Cryptographic

Hardware and Embedded Systems - CHES 2001, Lecture Notes in

Computer Science vol.2162, pp.28-38, Springer-Verlag, 2001.

[45]

T.S. Messerges, E.A. Dabbish and R.H. Sloan, ``Power Analysis

Attacks of Modular Exponentiation in Smartcards,'

extit{Proceedings of Workshop on Cryptographic Hardware and

Embedded Systems - CHES 1999, Lecture Notes in Computer Science

vol.1717, pp.144-157, Springer-Verlag, 1999.

[46]

T.S. Messerges, ``Power Analysis Attacks And Countermeasures For

Cryptographic Algorithms,' Ph.D. Dissertation, Dept. of

Electrical Engineering and Computer Science at the University of

Illinois at Chicago, Aug. 2000.

[47]

T.S. Messerges, ``Securing the AES Finalists against Power

Analysis Attacks,' Proceedings of Fast Software

Encryption - FSE 2000, Lecture Notes in Computer Science

vol.1978, pp.150-164, Springer-Verlag, 2000.

[48]

T.S. Messerges, ``Using 2nd-Order Power Analysis to Attack DPA

Resistant Software,' Proceedings of Workshop on

Cryptographic Hardware and Embedded Systems - CHES 2000, Lecture

Notes in Computer Science vol.1965, pp.238-251, Springer-Verlag,

2000.

[49]

T.S. Messerges, E.A. Dabbish, R.H. Sloan, ``Examining Smart-Card

Security under the Threat of Power Analysis Attacks,'

IEEE Transactions on Computers, Vol.51, No.4, April 2002.

[50]

S.W. Moore, R. Anderson and M. Kuhn, ``Self-timed Technology to

Reduce Smartcard Fraud,' in proceedings of ACiD-WG

Workshop, Grenoble, February 2000.

[51]

S.W. Moore, R. Anderson, P. Cunnungham, R. Mullins and G. Taylor,

``Improving Smart Card Security using Self-timed Circuits,'

ASYNC 2002, The Eighth IEEE International Symposium on

Asynchronous Circuits and Systems, 2002.

[52]

S.W. Moore, R. Anderson, R. Mullins and G. Taylor, ``Balanced

Self-Checking Asynchronous Logic for Smart Card Applications,'

Journal of Microprocessors and Microsystems Journal,

27(9):421430, October 2003.

[53]

E. Oswald and M. Aigner, ``Randomized Addition-Subtraction Chains

As a Countermeasure against Power Attacks,' Proceedings

of Workshop on Cryptographic Hardware and Embedded Systems - CHES

2001, Lecture Notes in Computer Science vol. 2162, pp.39-50,

Springer-Verlag, 2001.

[54]

F. Sano, M. Koike, S. Kawamura, and M. Shiba, ``Performance

evaluation of AES finalists on the high-end smart card,'

In Proceedings of the Third Advanced Encryption Standard

(AES) Candidate Conference, pp. 82-93, April 13-14, 2000.

[55]

A. Shamir, ``Protecting Smart Cards from Passive Power Analysis

with Detached Power Supplies,' Proceedings of Workshop on

Cryptographic Hardware and Embedded Systems '00, Lecture Notes in

Computer Science vol.1965, pp.71-77, Springer-Verlag, 2000.

[56]

E. Trichina, D.D. Seta and L. Germani, ``Simplified Adaptive

Multiplicative Masking for AES,' Proceedings of Workshop

on Cryptographic Hardware and Embedded Systems - CHES 2002,

Lecture Notes in Computer Science vol.2523, pp.187-192,

Springer-Verlag, 2003.

[57]

W.van Eck, ``Electromagnetic Radiation from Video Display Units:

An Evasdropping Risk,' Computers and Security, v4,

pp.269-286, 1985.

[58]

C.D. Walter, ``Sliding Windows Succumbs to Big Mac Attack,'

Proceedings of Workshop on Cryptographic Hardware and

Embedded Systems - CHES 2001, Lecture Notes in Computer Science

vol. 2162, pp.286-299, Springer-Verlag, 2001.

[59]

S.M. Yen, S. Kim, S. Lim and S. Moon, ``A Countermeasure against

One Physical Cryptanalysis May Benfit Another Attack,'

Information Security and Cryptology - ICISC 2001, Lecture

Notes in Computer Science vol.2288, pp.414-427, Springer-Verlag,

2002.

[60]

S.M. Yen, ``Amplified Differential Power Cryptanalysis on Rijndael

Implementations with Exponentially Fewer Power Traces,'

Information Security and Privacy - ACISP 2003, Lecture

Notes in Computer Science vol.2727, pp.106-117, Springer-Verlag,

2003.Advisor Sung-Ming Yen(ÃC·C»Ê)

Files approve in 1 year

91522066.pdf Date of Submission 2004-06-23

Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.