臺灣博碩士論文加值系統

在當今的日常生活中，使用電子裝置儲存個人秘密資料的方式日漸普及。隨之而來的是，資訊安全日益受到重視。當使用者必須經由不可信任之通道傳遞秘密資訊時，人們總是使用密碼系統保障資訊安全。然而，當密碼系統被應用於開放式的環境中時，即使是使用密碼系統保護資訊，任何人皆無法完全地保證系統的安全性。
私密金鑰加密器標準DES自西元1977年被採用至今，已超過二十年。面對各種新式攻擊法，DES在某些應用上已不堪使用。因此，在西元2000年十月，美國國家標準暨技術局(NIST)選定Rijndael為新式私密金鑰加密器標準AES。而在近幾年，物理攻擊法自成一門新的研究領域，並且對現有的各式密碼演算法造成極大的威脅。在本論文中將探討AES是否能有效地防禦物理攻擊法，特別是錯誤攻擊法，以及能量攻擊法。
基於Biham與Shamir所發表之差分錯誤攻擊法的原理，一種應用於Rijndael的差分錯誤攻擊法將在第四章中提出。接著，將探討此攻擊法的效率，並以不同的假設條件觀察攻擊複雜度的消長與可行性。另一方面，為了防禦差分錯誤攻擊法，將對Rijndael進行弱點分析，並且提出了改進ShiftRow運算及新增ShiftColumn運算的方法，使攻擊複雜度提昇至少一千倍以上。
以現階段技術而言，差分能量攻擊法是目前最有效且最可行的物理攻擊法。同樣地，差分能量攻擊法也可應用於攻擊Rijndael。本論文第五章將在不同的前提條件之下，提出兩種攻擊Rijndael的差分能量攻擊法，分別是以KeyAddition以及ShiftRow之運算結果為攻擊對象。接著，將討論兩種攻擊法的優缺點、改進的方法以及時間校正等相關問題。

Nowadays, digital information grows extremely in our daily life, and the importance of information security increases correspondingly. People always protects information transferred in the untrusted channel from leakage by cryptographic algorithms. However, when these cryptosystems are operated in the open environment, no one can ensure the ecurity of information even information is protected by cryptosystems.

The Advanced Encryption Standard (AES) selected by NIST of the United States will become the most widespread block cipher standard. In this thesis, its strength against physical cryptanalyses, specially the power analysis and the differential fault analysis will be discussed.

In Chapter 4, an application of the differential fault analysis on the AES are considered. In order to defend the AES from this attack, the
weakness of the AES are analyzed, and some mprovement of the AES structures are proposed. Finally, in order to defend the AES against the timing attack, possible countermeasure is also discussed.

Power analysis attacks are the most useful cryptanalyses at present, and it is also practicable on the AES. In Chapter 5, two types of power analyses attack on the AES are proposed. Similarly, in order to defend against power analyses, some countermeasures are considered, and some problems about the countermeasures are also discussed.

1 Introduction
1.1 Motivation
1.2 Introduction to Physical Attacks
1.2.1 Fault-based attack
1.2.2 Timing attack
1.2.3 Power analysis attack
1.2.4 Electromagnetic attack
1.3 Overview of the thesis

2 Review of Power Analysis attacks and Fault-based Attacks
2.1 Fault-based Attacks
2.1.1 Bellcore attack
2.1.2 Differential fault analysis
2.2 Power Analysis Attacks
2.2.1 Simple power analysis-SPA
2.2.2 Differential power analysis-DPA

3 Review of Rijndael Cipher
3.1 Historical Review
3.2 Preliminaries
3.2.1 The field GF(2^8)
3.2.2 Addition
3.2.3 Multiplication
3.2.4 Polynomials with coefficients in GF(2^8)
3.3 Specification and Notations
3.3.1 Round transformation

4 A Differential Fault Attack on Rijndael
4.1 Motivation
4.1.1 Brief review of Rijndael
4.1.2 Brief review of differential fault attack
4.2 The DFA on Rijndael
4.2.1 Assumptions
4.2.2 Cryptanalysis procedures
4.2.3 Statistics
4.2.4 Countermeasures with conventional and expensive approaches
4.3 Improvement of ShiftRow on Rijndael
4.3.1 Analysis of rotation operations
4.3.2 Improvement of ShiftRow
4.3.3 An additional operation - ShiftColumn
4.3.4 Countermeasure against timing attack
4.4 Remarks and Discussions

5 Differential Power attacks on Rijndael
5.1 Motivation
5.2 A DPA on the Initial KeyAddition
5.2.1 Preliminaries
5.2.2 Assumptions
5.2.3 Notations
5.2.4 Cryptanalysis procedures
5.2.5 Further explanation
5.3 A DPA on the ShiftRow in Final Round
5.3.1 Assumptions
5.3.2 Notations
5.3.3 Cryptanalysis procedures
5.3.4 Further explanation
5.4 Discussions
5.4.1 Comparisons
5.4.2 Enhanced by attacking multiple bits
5.4.3 Effect of timing delay
5.4.4 Countermeasures
5.5 Remarks and Discussions

6 Conclusions
6.1 Brief Review of Main Contributions
6.2 Further Research Topics and Directions

National Bureau of Standards, "Data Encryption Standard," Federal Information Processing Standards Publication 46, Jan. 1977.J. Daemen, V. Rijmen, "AES Proposal : Rijndael," The First Advanced Encryption Standard Candidate Conference, N.I.S.T., 1998.NIST, "FIPS-197: Advanced Encryption Standard," Federal Information Processing Standard, FIPS-197, 2001D. Boneh, R.A. Demillo and R.J. Lipton, "On the Importance of Checking Cryptographic Protocols for Faults," Advances in Cryptology - EUROCRYPT''97, Lecture Notes in Computer Science, Springer-Verlag, 1997, pp. 37-51E. Biham and A. Shamir, "A New Cryptanalytic Attack on DES: Differential Fault Analysis," Oct. 1996E. Biham and A. Shamir, "Differential Fault Analysis of Secret Key Cryptosystems," Advances in Cryptology - CRYPT0''97, Lecture Notes in Computer Science vol. 1249, Springer-Verlag, 1997, pp. 513-525R. Anderson and M. Kuhn, "Improved Differential Fault Analysis," 1996, ftp://ftp.cl.cam.ac.uk/users/rja14/dfaP. Kocher, "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems," Advances in Cryptology - CRYPTO''96, Lecture Notes in Computer Science, Springer-Verlag, 1996, pp. 104-113P. Kocher, J. Jaffe and B. Jun, "Introduction to Differential Power Analysis and Related Attacks," 1998, http://www.cryptography.com/dpa/technicalP. Kocher, J. Jaffe and B. Jun, "Differential Power Analysis," Advances in Cryptology - CRYPTO''99, Springer-Verlag, 1999, pp. 388-397W.van Eck, "Electromagnetic Radiation from Video Display Units: An Evasdropping Risk," Computers and Security, v. 4, 1985, pp. 269-286K. Gandolfi, C. Mourtel and F. Olivier, "Electromagnetic Analysis: Concrete Results," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''01, Lecture Notes in Computer Science, Springer-Verlag, May 2001T.S. Messerges, "Using 2nd-Order Power Analysis to Attack DPA Resistant Software," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''00, Lecture Notes in Computer Science vol. 1965, Springer-Verlag, Aug. 2000, pp. 238-251P. Fahn and P. Pearson, "IPA: A New Class of Power Attacks," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''99, Lecture Notes in Computer Science vol. 1717, Springer-Verlag, Aug. 1999, pp. 173-186F. Koeune and J.-J. Quisquater, "A Timing Attack against Rijndael," Crypto Group Technical Report Series CG-1999/1, Uinversit''e Catholique de Louvain., 1999E. 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. 1999D. Boneh, R.A. Demillo and R.J. Lipton, "On the Importance of Checking Cryptographic Protocols for Faults," Advances in Cryptology - EUROCRYPT''97, Lecture Notes in Computer Science, Springer-Verlag, 1997, pp. 37-51J. Daemen, L.R. Knudsen and V. Rijmen, "The block cipher Square," Proceedings of Fast Software Encryption Workshop 1997, Lecture Notes in Computer Science, Springer-Verlag, 1267, pp. 149-165J.-S. Coron and L. Goubin, "On Boolean and Arithmetic Masking against Differential Power Analysis," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''00, Lecture Notes in Computer Science vol. 1965, Springer-Verlag, Aug. 2000, pp. 231-237J.-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, 1998S.E. Eldridge and C.D. Walter, "Hardware Implementation of Montgomery''s Modular Multiplication Algorithm," IEEE Trans. on computers, V. 42, n. 6, pp. 6693-699, Jun. 1993M.L-. 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, Springer-Verlag, 2000, pp. 489-502G. Hachez, F. Koeune, J.-J. Quisquater, "Timing Attack: What Can Be Achieved By A Powerful Adversary?," Proceedings of the 20th symposium on Information Theory in the Benelux, May 1999, pp. 63-70H. Handschuh, "A Timing Attack on RC5," Proceedings of the Workshop on Selected Areas in Cryptography - SAC''98, Springer-Verlag, Aug. 1998J. Kelsey, B. Schneier, D. Wagner and C. Hall, "Side Channel Cryptanalysis of Product Ciphers," Computer Security-ESORICS''98, Lecture Notes in Computer Science vol. 1485, Springer-Verlag, 1998M. Kuhn, "Cipher Instruction Search Attack on the Bus-Encryption Security Microcontroller DS5002fp," IEEE Trans. on computers, V. 47, n. 10, pp. 1153-1157, Oct. 1998T.S. Messerges, "Securing the AES Finalists against Power Analysis Attacks," Proceedings of Fast Software Encryption Workshop 2000, Lecture Notes in Computer Science, Springer-Verlag, Apr. 2000, pp. 150-164T.S. Messerges, E.A. Dabbish and R.H. Sloan, "Investigations of Power Analysis Attacks on Smartcards," Proceedings of USENIX Workshop on Smartcard Technology, May 1999, pp. 151-161S.-M. Yen and M. Joye, "Checking Before Output May not Be Enough Against Fault-Based Cryptanalysis," IEEE Trans. on computers, V. 49, n. 9, pp. 967-970, Sep. 2000T.S. Messerges, E.A. Dabbish and R.H. Sloan, "Power Analysis Attacks of Modular Exponentiation in Smartcards," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''99, Lecture Notes in Computer Science vol. 1717, Springer-Verlag, Aug. 1999, pp. 144-157J.-S. Coron, "Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''99, Lecture Notes in Computer Science vol. 1717, Springer-Verlag, Aug. 1999, pp. 292-302L. Goubin and J. Patarin, "DES and Differential Power Analysis - the Duplication Method," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''99, Lecture Notes in Computer Science vol. 1717, Springer-Verlag, Aug. 1999, pp. 158-172S. 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, 1999, pp. 398-412J. Daemen, M. Peeters and G.V. Assche, "Bitslice Ciphers and Power Analysis Attacks," Proceedings of Fast Software Encryption Workshop 2000, Lecture Notes in Computer Science, Springer-Verlag, Apr. 2000J. Kessels, "Applying Asynchronous Circuits in Contactless Smartcards," Proceedings of ACiD-WG Workshop, Grenoble, Feb.2000J.-S. Coron, P. Kocher and D.Naccache, "Statistics and Secret Leakage," Proceedings of Financial Cryptography, Springer-Verlag, Feb.2000J.Daemen and V.Rijmen, "Resistant against Implementation Attacks: A Comparative Study of the AES Proposals," Proceedings of the Second Advanced Encryption Standard (AES) Candidate Conference, Mar. 1999A. 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, Springer-Verlag, Aug. 2000, pp. 71-77 R. Mayer-Sommer, "Smartly Analyzing the Simplicity and the Power of Simple Power Analysis on Smartcards," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''00, Lecture Notes in Computer Science vol. 1965, Springer-Verlag, Aug. 2000, pp. 78-92M.A. Hasan, "Power Analysis Attacks and Algorithmic Approaches to Their Countermeasures for Koblitz Curve Cryptosystems," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''00, Lecture Notes in Computer Science vol. 1965, Springer-Verlag, Aug. 2000, pp. 93-108W. Schindler, "A Timing Attack against RSA with the Chinese Remainder Theorem," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''00, Lecture Notes in Computer Science vol. 1965, Springer-Verlag, Aug. 2000, pp. 109-124C. 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, Springer-Verlag, Aug. 2000, pp. 252-263S.H. Weingart, "Physical Security Devices for Computer Subsystems: A Survey of Attacks and Defenses," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''00, Lecture Notes in Computer Science vol. 1965, Springer-Verlag, Aug. 2000, pp. 302-317L. Goubin, "A Sound Method for Switching Between Boolean and Arithmetic Masking," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''01, Lecture Notes in Computer Science, Springer-Verlag, May 2001E. 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 ''01, Lecture Notes in Computer Science, Springer-Verlag, May 2001D. May, H.L. Muller and N.P. Smart, "Random Register Renaming to Foil DPA," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''01, Lecture Notes in Computer Science, Springer-Verlag, May 2001E. Oswald and M. Aigner, "Randomized Addition-Subtraction Chains As a Countermeasure against Power Attacks," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''01, Lecture Notes in Computer Science, Springer-Verlag, May 2001C.D. Walter, "Sliding Windows Succumbs to Big Mac Attack," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''01, Lecture Notes in Computer Science, Springer-Verlag, May 2001C. Clavier and M. Joye, "Universal Exponentiation Algorithm: A First Step Towards Provable SPA-Resistance," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''01, Lecture Notes in Computer Science, Springer-Verlag, May 2001M. Akkar and C. Giraud, "An Implementation of DES and AES, Secure against Some Attacks," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''01, Lecture Notes in Computer Science, Springer-Verlag, May 2001P.-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 ''01, Lecture Notes in Computer Science, Springer-Verlag, May 2001M. Joye and C. Tymen, "Protections against Differential Analysis for Elliptic Curve Cryptography: An Algebraic Approach," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''01, Lecture Notes in Computer Science, Springer-Verlag, May 2001T.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. 2000H. Handschuh, P. Paillier and J. Stern, "Probing Attacks on Tamper-Resistant Devices," Proceedings of Workshop on Cryptographic Hardware and Embedded Systems ''99, Lecture Notes in Computer Science vol. 1717, Springer-Verlag, Aug. 1999R. Anderson and M. Kuhn, "Tamper Resistance - A Cautionary Note," Proceedings of the 2nd Workshop on Electronic Commerce, 1996, pp. 1-11