Title page for 90522008


[Back to Results | New Search]

Student Number 90522008
Author Nai-Chi Kuo(³¢¤Dºö)
Author's Email Address cs022008@csie.ncu.edu.tw
Statistics This thesis had been viewed 2041 times. Download 1278 times.
Department Computer Science and Information Engineering
Year 2003
Semester 2
Degree Master
Type of Document Master's Thesis
Language English
Title Non-deterministic Software and Mask Splitting Method Against Power Analysis Attacks
Date of Defense 2004-06-15
Page Count 76
Keyword
  • Mask
  • Non-deterministic Software
  • Power Analysis A
  • Abstract The issue of information security has attracted more and more attention, and
    usually is considered a major factor in the design of an information system. Being
    portable and tamperproof, a smart card can be used to provide additional services.
    However, physical cryptanalysis proposed recently intuitively observes physical
    characteristics leaked from an assumed tamperproof device such as a smart card.
    Therefore, when a cryptosystem is implemented without sufficient care, it may be
    vulnerable to physical cryptanalysis.
    In this thesis, we propose two countermeasures, non-deterministic software and
    the mask splitting technique, for the sake of strengthening the security of a smart
    card. Chapter 2 gives a short introduction on power analysis, that is most used and
    investigated. In chapter 3 we review some of the countermeasures used to prevent
    such attack.
    Chapter 4 proposes a non-deterministic software (NDS) technique as a countermeasure
    against DPA that utilizes the interleaving technique of software implementation
    for the sake of removing any correlation between power traces in the software
    according to non-deterministically executive operations.
    Chapter 5 investigates the mask splitting method (MSM) that is regarded as
    an improved mechanism of transformation from boolean mask to arithmetic mask.
    Detailed security analysis of mask splitting applied is also discussed.
    Table of Content 1 Introduction 1
    1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
    1.2 BriefReview of Physical Cryptanalysis . . . . . . . . . . . . . . . . . 2
    1.3 Thesis Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
    2 PowerAnalysis 6
    2.1 SimplePower Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 6
    2.2 Differential PowerAnalysis . . . . . . . . . . . . . . . . . . . . . . . . 7
    2.3 Higher-order Power Analysis . . . . . . . . . . . . . . . . . . . . . . . 8
    3 Reviews on Countermeasures for Differential Power Analysis on a
    Symmetric Cryptosystem 10
    3.1 Non-deterministicExecution . . . . . . . . . . . . . . . . . . . . . . . 10
    3.1.1 Non-deterministic processor . . . . . . . . . . . . . . . . . . . 12
    3.1.2 Random register renaming . . . . . . . . . . . . . . . . . . . . 12
    3.1.3 Maybe predicate instruction . . . . . . . . . . . . . . . . . . . 13
    3.1.4 Instructionmutation . . . . . . . . . . . . . . . . . . . . . . . 13
    3.1.5 Fetch split jump . . . . . . . . . . . . . . . . . . . . . . . . . . 13
    3.2 Masking Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
    3.2.1 Transformation from boolean to arithmetic masks . . . . . . . 15
    3.2.2 Secret sharing scheme . . . . . . . . . . . . . . . . . . . . . . 15
    3.2.3 Approaches to counteract power analysis attacks . . . . . . . . 16
    3.2.4 Architecture for power analysis resistant smart cards . . . . . 16
    3.2.5 Transformedmasking method . . . . . . . . . . . . . . . . . . 17
    4 Nondeterministic Software 20
    4.1 NDSMethod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
    4.1.1 Data dependency . . . . . . . . . . . . . . . . . . . . . . . . . 21
    4.1.2 Choosing appropriate assembly codes and subroutines . . . . . 21
    4.1.3 Algorithms for scrambling independent subroutines . . . . . . 23
    4.2 Scrambling Instructions . . . . . . . . . . . . . . . . . . . . . . . . . 25
    4.3 Summary of ThisWork . . . . . . . . . . . . . . . . . . . . . . . . . . 31
    5 Mask Splitting Method 41
    5.1 The 2-bit DPA Applied on Former Transformation Method . . . . . . 41
    5.2 Techniques of Mask Splitting Applied, from Boolean Masks to ArithmeticMasks
    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
    5.2.1 MSMdeliberating on 2-bit DPA . . . . . . . . . . . . . . . . . 45
    5.2.2 MSM deliberating on second-order DPA . . . . . . . . . . . . 45
    5.2.3 Performance comparisons . . . . . . . . . . . . . . . . . . . . 46
    5.3 SecurityAnalysis . . . . . . . . . . . . . . . . . . . . . . . . .47
    5.4 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
    6 Conclusions 58
    6.1 BriefReview ofMain Contributions . . . . . . . . . . . . . . . . . . . 58
    6.2 FurtherResearch Topics and Directions . . . . . . . . . . . . . . . . . 59
    A The Program Delivering on an Inspection of Data Dependency 67
    A.1 Scramble.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
    A.2 Templatedef.cpp. . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
    A.3 Treenode.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
    A.4 Sort.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
    4.1 The ratio of decreased power profile . . . . . . . . . . . . . . . . . . . 31
    4.2 The incremental multiple of the number of traces needed under RPIprotected
    and NDS-protected scheme . . . . . . . . . . . . . . . . . . 32
    5.1 The assembly codes needed under MSM, Messerges¡¦s and Goubin¡¦s
    maskingmethod (Part I). . . . . . . . . . . . . . . . . . . . . . . . . 46
    5.2 The assembly codes needed under MSM, Messerges¡¦s and Goubin¡¦s
    maskingmethod (Part II). . . . . . . . . . . . . . . . . . . . . . . . . 47
    5.3 The ratio ofMSMto other maskingmethods . . . . . . . . . . . . . . 47
    5.4 The effect on the power profile when considering DPA attack . . . . . 49
    5.5 Some estimation on the additional line of codes of each subroutine of
    the DES program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
    4.1 The algorithm used to choose independent instructions and subroutines. 25
    4.2 The algorithm used to scramble k subroutines. . . . . . . . . . . . . . 26
    4.3 The algorithm used to scramble three subroutines (Part I). . . . . . . 27
    4.4 The algorithm used to scramble three subroutines (Part II). . . . . . 33
    4.5 The DPA profile produced in original computation with 256 power
    samples (part I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
    4.6 The DPA profile produced in original computation with 256 power
    samples (part II). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
    4.7 The DPA profile produced under the influence of NDS technique with
    2560 power samples (part I). . . . . . . . . . . . . . . . . . . . . . . . 36
    4.8 The DPA profile produced under the influence of NDS technique with
    2560 power samples (part II). . . . . . . . . . . . . . . . . . . . . . . 37
    4.9 The changed power profile under the influence of different percentage
    of right traces remained on a power profile (part I). . . . . . . . . . . 38
    4.10 The changed power profile under the influence of different percentage
    of right traces remained on a power profile (part II). . . . . . . . . . . 39
    5.1 The transformation method proposed byMesserges. . . . . . . . . . . 41
    5.2 The XORmask splittingmethod. . . . . . . . . . . . . . . . . . . . . 44
    5.3 The ADDmask splittingmethod. . . . . . . . . . . . . . . . . . . . . 44
    5.4 The SUBmask splittingmethod. . . . . . . . . . . . . . . . . . . . . 45
    5.5 The DPA profile produced in original computation (part I). . . . . . . 51
    5.6 The DPA profile produced in original computation (part II). . . . . . 52
    5.7 The DPA profile produced under the influence of MSM-I technique
    (part I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
    5.8 The DPA profile produced under the influence of MSM-I technique
    (part II). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
    5.9 The DPA profile produced under the influence of MSM-II technique
    (part I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
    5.10 The DPA profile produced under the influence of MSM-II technique
    (part II). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
    Reference [1] M. Akkar and C. Giraud, ¡§An implementation of DES and AES, secure against
    some attacks,¡¨ In Cryptographic Hardware and Embedded Systems - CHES
    2001, LNCS 2162, pp.309-318, Springer-Verlag, 2001.
    [2] M. Akkar and L. Goubin, ¡§A generic protection against high-order differential
    power analysis,¡¨ In Proceedings of the Fast Software Encryption Workshop -
    FSE 2000, LNCS 2887, pp.192-205, Springer-Verlag, 2003.
    [3] W. Amme, P. Braun, and E. Zehendner, ¡§Data dependence analysis
    of assembly code,¡¨ ISSN 0249-6399, 1999, available at URL
    <http://citeseer.nj.nec.com/395649.html>.
    [4] R. Anderson and M. Kuhn, ¡§Tamper resistance - a cautionary note,¡¨ In
    The Second USENIX Workshop on Electronic Commerce Proceedings, ISBN
    1-880446-83-9, pp. 1-11, 1996.
    [5] R. Anderson and M. Kuhn, ¡§Improved differential fault analysis,¡¨ 1996, available
    at URL <http://www.ftp.cl.cam.ac.uk/ftp/users/rja14/dfa>.
    [6] R. Anderson and M. Kuhn, ¡§Low cost attacks on tamper resistant devices,¡¨ In
    Security Protocols, LNCS 1361, pp. 125-136, Springer-Verlag, 1997.
    [7] C. Aumuller, P. Bier, W. Fischer, P. Hofreiter, and J. Seifert, ¡§Fault attacks
    on RSA with CRT: concrete results and practical countermeasures,¡¨ In Cryptographic
    Hardware and Embedded Systems - CHES 2002, LNCS 2523, pp. 260-
    275, 2003.
    [8] F. Bao, R. Deng, Y. Han, A. Jeng, T. Nagir and D.
    Narasimhalu, ¡§Another new attack to RSA on tamperproof devices,¡¨
    1996, available at URL <http://tirnanog.ls.fi.upm.es/
    Servicios/Alejandria/InfoTecnica/Ataque%20RSA.htm>.
    [9] F. Bao, R. Deng, Y. Han, A. Jeng, D. Narasimhalu, and T. Nagir,
    ¡§New attacks to public key cryptosystems on tamperproof devices,¡¨
    1996, available at URL <http://www.ieee-security.org/Cipher/
    Newsbriefs/1996/961029 sgtamper.html>.
    [10] E. Biham and A. Shamir, ¡§Differential fault analysis of secret key cryptosystems,¡¨
    In Advances in Cryptology - CRYPT0 ¡¦97, LNCS 1249, Springer-Verlag,
    pp. 513-525, 1997.
    [11] E. Biham and A. Shamir, ¡§The next stage of differential fault
    analysis: how to break completely unknown cryptosystems,¡¨ 1996,
    available at URL <http://www.informatik.uni-mannheim.de/
    informatik/pi4/projects/Crypto/rgp/dfa/dfa2.html>.
    [12] E. Biham and A. Shamir, ¡§Improved differential fault analysis,¡¨ 1996,
    available at URL <http://www.informatik.uni-mannheim.de/informatik/
    pi4/projects/Crypto/rgp/dfa/>.
    [13] E. Biham and A. Shamir, ¡§A new cryptanalytic attack on DES,¡¨
    1996, available at URL <http://www.interesting-people.org/archives/
    interesting-people/199610/msg00050.html>.
    [14] J. Bl¨omer 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.pdf>.
    [15] B. Boer, K. Lemke and G. Wicke, ¡§A DPA attack against the modular reduction
    within a CRT implementation of RSA,¡¨ In Cryptographic Hardware and
    Embedded Systems - CHES 2002, LNCS 2523, pp. 229-244, 2003.
    [16] D. Boneh, R.A. Demillo and R.J. Lipton, ¡§On the importance of checking cryptographic
    protocols for faults,¡¨ In Advances in Cryptology - EUROCRYPT¡¦97,
    LNCS 1233, pp. 37-51, Springer-Verlag, 1997.
    [17] N. Borisov and S. Song, ¡§An architecture for power
    analysis resistant smart cards,¡¨ 2000, available at URL
    <http://www.cs.berkeley.edu/ nikitab/papers/>.
    [18] S. Chari, C. Jutla, J. Rao and P. Rohatgi, ¡§Towards sound approaches to
    counteract power-analysis attacks,¡¨ In Advances in Cryptology - CRYPTO ¡¦99,
    LNCS 1666, pp. 398-412, Springer-Verlag, 1999.
    [19] S. Chari, J. Rao and P. Rohatgi, ¡§Template attacks,¡¨ Cryptographic Hardware
    and Embedded Systems - CHES 2002, LNCS 2523, pp. 13-28, Springer-Verlag,
    2002.
    [20] C. Clavier, J.-S. Coron and N. Dabbous, ¡§Differential power analysis in the
    presence of hardware countermeasures,¡¨ In Cryptographic Hardware and Embedded
    Systems - CHES 2000, LNCS 1965, pp. 252-263, Springer-Verlag, 2000.
    [21] J.-S. Coron and L. Goubin, ¡§On boolean and arithmetic masking against differential
    power analysis,¡¨ In Cryptographic Hardware and Embedded Systems -
    CHES 2000, LNCS 1965, pp. 231-237, Springer-Verlag, 2000.
    [22] J. Daemon, M. Peeters and G.V. Assche, ¡§Bitslice ciphers and power analysis
    attacks,¡¨ In Proceedings of the Fast Software Encryption Workshop - FSE 2000,
    LNCS 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,¡¨ In Proceedings
    of CARDIS ¡¦98 - Third Smart Card Research and Advanced Application Conference,
    UCL, Louvain-la-Neuve, Belgium, Sep. 14-16, 1998.
    [24] P. Fahn and P. Pearson, ¡§IPA: a new class of power attacks,¡¨ In Cryptographic
    Hardware and Embedded Systems - CHES ¡¦99, LNCS 1717, pp. 173-186,
    Springer-Verlag, 1999.
    [25] J.J.A. Fournier, S. Moore, H. Li, R. Mullins, and G. Taylor, ¡§Security evaluation
    of asynchronous circuits,¡¨ In Cryptographic Hardware and Embedded
    Systems - CHES 2003, LNCS 2779, pp. 137-151, Springer-Verlag, 2003.
    [26] G. Hachez, F. Koeune, J.J. Quisquater, ¡§Timing attack: what can be achieved
    by a powerful adversary?,¡¨ In Proceedings of the 20th symposium on Information
    Theory in the Benelux, pp. 63-70, 1999.
    [27] H. Handschuh, ¡§A timing attack on RC5,¡¨ Proceedings of the Workshop on
    Selected Areas in Cryptography - SAC ¡¦98, LNCS 1556, pp. 306-320, Springer-
    Verlag, 1999.
    [28] M.A. Hasan, ¡§Power analysis attacks and algorithmic approches to their countermeasures
    for Koblitz curve cryptosystems,¡¨ Cryptographic Hardware and
    Embedded Systems - CHES 2000, LNCS 1965, pp.93-108, Springer-Verlag, 2000.
    [29] A. Hevia and M. Kiwi, ¡§Strength of two data encryption standard implementation
    under timing attacks,¡¨ In Latin American Theoretical Informatics -
    LATIN ¡¦98, LNCS 1380, pp. 192-205, Springer-Verlag, 1998.
    [30] J. Irwin, D. Page, and N.P. Smart, ¡§Instruction stream mutation for nondeterministic
    processors,¡¨ In Proceedings of the IEEE International Conference
    on Application-Specific Systems, Architectures, and Processors -ASAP¡¦02,
    2002.
    [31] J. Irwin, H.L. Muller, D. Page, N.P. Smart, and B. Silverman, ¡§Probabilistic
    Instruction Prediction: The MAYBE Predicate,¡¨ Technical Report CSTR-03-
    005, Department of Computer Science, University of Bristol, 2003.
    [32] K. Itoh, T. Isu and M. Takenaka, ¡§Address-bit differential power analysis of
    cryptographic schemes OK-ECDH and OK-ECDSA,¡¨ In Cryptographic Hardware
    and Embedded Systems - CHES 2002, LNCS 2523, pp. 129-143, Springer-
    Verlag, 2002.
    [33] M. Joye and J.J. Quisquater, ¡§RSA-type signatures in the presence of transient
    faults,¡¨ Technical Report CG-1997/7, Universit´e catholique de Louvain, 1997.
    [34] M. Joye and A. Lenstra, ¡§Chinese remaindering based cryptosystems in the
    presence of faults,¡¨ Journal of Cryptology, vol. 12, no. 4, pp. 241-245, 1999.
    [35] P. Kocher, ¡§Timing attacks on implementations of Diffie-Hellman, RSA, DSS,
    and other systems,¡¨ In Advances in Cryptology - CRYPTO¡¦96, LNCS 1109, pp.
    104-113, Springer-Verlag, 1996.
    [36] P. Kocher, J. Jaffe and B. Jun, ¡§Differential power analysis,¡¨ In Advances in
    Cryptology - CRYPTO¡¦99, LNCS 1109, pp. 388-397, Springer-Verlag, 1999.
    [37] F. Koeune and J.J. Quisquater, ¡§A timing attack against Rijndael,¡¨ Technical
    Report CG-1999/1, Universit´e catholique de Louvain, 1999.
    [38] O. K¨ommerling and M. Kuhn, ¡§Design principles for tamper-resistant smartcard
    processors,¡¨ In Proceedings of the USENIX Workshop on Smartcard Technology
    - Smartcard¡¦99 , ISBN 1-880446-34-0, pp. 9-20, 1999.
    [39] D. May, H.L. Muller and N.P. Smart, ¡§Random register renaming to foil DPA,¡¨
    In Cryptographic Hardware and Embedded Systems - CHES 2001, LNCS 2162,
    pp. 28-38, Springer-Verlag, 2001.
    [40] D. May, H.L. Muller and N.P. Smart, ¡§Non-deterministic processors,¡¨ In The
    6th Australasian Conference on Information Security and Privacy - ACISP
    2001, LNCS 2119, pp. 115-129, Springer-Verlag, 2001.
    [41] R. Mayer-Sommer, ¡§Smartly analyzing the simplicity and the power of simple
    power analysis on smartcards,¡¨ In Cryptographic Hardware and Embedded
    Systems - CHES 2000, LNCS 1965, pp. 78-92, Springer-Verlag, 2000.
    [42] T.S. Messerges, ¡§Securing the AES finalists against power analysis attacks,¡¨
    In Proceedings of the Fast Software Encryption Workshop - FSE 2000, LNCS
    1978, pp. 150-164, Springer-Verlag, 2001.
    [43] T.S. Messerges, E. Dabbish and R. Sloan, ¡§Investigation of Power Analysis
    Attacks on Smartcards,¡¨ In Proceedings of USENIX Workshop on Smartcard
    Technology - Smartcard¡¦99, ISBN 1-880446-34-0, pp. 151-161, 1999.
    [44] T.S. Messerges, ¡§Using 2nd-order power analysis to attack DPA resistant software,¡¨
    In Cryptographic Hardware and Embedded Systems - CHES 2000, LNCS
    1965, pp. 238-251, Springer-Verlag, 2000.
    [45] T.S. Messerges, E. Dabbish and R. Sloan, ¡§Power analysis attacks of modular
    exponentiation in smartcards,¡¨ In Cryptographic Hardware and Embedded
    Systems - CHES¡¦99, LNCS 1717, pp. 144-157, Springer-Verlag, 1999.
    [46] T.S. Messerges, E. Dabbish and R. Sloan, ¡§Examining smart-card security under
    the threat of power analysis attacks,¡¨ IEEE Transactions on computers, v.
    51, n. 5, pp. 541-552, May 2002.
    [47] S. Moore, R. Anderson, P. Cunningham, R. Mullins and G. Taylor, ¡§Improving
    Smart Card Security using Self-timed Circuits,¡¨ In Proceedings of 8th IEEE
    International Symposium on Asynchronous Circuits and Systems -ASYNC ¡¦02
    , pp. 23-58, 2002.
    [48] T. Ogiso, Y. Sakabe, M. Soshi and A. Miyaji, ¡§Software obfuscation on a theoretical
    basis and its implementation,¡¨ IEICE Transactions on Fundamentals,
    vol. E86-A, No. 1, pp.176-186, 2003.
    [49] D. Page and N. Sidwell, ¡§A Fetch Resident Split Jump Mechanism for Non-
    Deterministic Processors,¡¨ Technical Report CSTR-01-007, Department of
    Computer Science, University of Bristol, 2001.
    [50] W. Schindler, F. Koeune, and J.J. Quisquater, ¡§ Unleashing the full power of
    timing attack,¡¨ Technical Report CG-2001/3, Universit´e catholique de Louvain,
    2001.
    [51] W. Schindler, ¡§ A combined timing and power attack,¡¨ In The 5th International
    Workshop on Practice and Theory in Public Key Cryptosystems - PKC 2002,
    LNCS 2274, pp. 263-279, Springer-Verlag, 2002.
    [52] W. Schindler, ¡§ A timing attack against RSA with the chinese remainder theorem,¡¨
    In Cryptographic Hardware and Embedded Systems - CHES 2000, LNCS
    1965, pp. 109-124, Springer-Verlag, 2000.
    [53] A. Shamir, ¡§Protecting smart cards from passive power analysis with detached
    power supplies,¡¨ In Cryptographic Hardware and Embedded Systems - CHES
    2000, LNCS 1965, pp. 71-77, Springer-Verlag, 2000.
    [54] C. Walter, ¡§Some security aspects of the MIST randomized exponentiation
    algorithm,¡¨ In Cryptographic Hardware and Embedded Systems - CHES 2002,
    LNCS 2523, pp. 277-291, Springer-Verlag, 2002.
    [55] S.M. Yen and M. Joye, ¡§Checking before output may not be enough against
    fault-based cryptanalysis,¡¨ IEEE Transactions on computers, v. 49, n. 9, pp.
    967-970, Sept. 2000.
    [56] National Bureau of Standards, ¡§Data encryption standard,¡¨ Federal Information
    Processing Standards Publication 46, Jan. 1977.
    Advisor
  • Yen-Sung Ming(ÃC·C»Ê)
  • Files
  • 90522008.pdf
  • approve in 1 year
    Date of Submission 2004-06-21

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have dissertation-related questions, please contact with the NCU library extension service section.
    Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.