以非確定式軟體與遮罩分割對策
防禦能量攻擊之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：9

、訪客IP：3.144.17.45

姓名

郭乃綺(Nai-Chi Kuo) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

以非確定式軟體與遮罩分割對策防禦能量攻擊之研究
(Non-deterministic Software and Mask Splitting Method Against Power Analysis Attacks )

相關論文

★ 多種數位代理簽章之設計	★ 小額電子支付系統之研究
★ 實體密碼攻擊法之研究	★ 商業性金鑰恢復與金鑰託管機制之研究
★ AES資料加密標準之實體密碼分析研究	★ 電子競標系統之研究
★ 針對堆疊滿溢攻擊之動態程式區段保護機制	★ 通用型數域篩選因數分解法之參數探討
★ 於8051單晶片上實作可防禦DPA攻擊之AES加密器	★ 遮罩保護機制防禦差分能量攻擊之研究
★ AES資料加密標準之能量密碼分析研究	★ 小額電子付費系統之設計與密碼分析
★ 公平電子現金系統之研究	★ RSA公開金鑰系統之實體密碼分析研究
★ 保護行動代理人所收集資料之研究	★ 選擇密文攻擊法之研究與實作

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

資訊安全的議題已經受到愈來愈多的重視，並且成為在設計資訊
系統時之一項重要考量。由於智慧卡之可攜性與防偽性，智慧卡可有
多種應用。然而，近年來學者提出之物理攻擊法，可藉由觀測防偽性
裝置於進行計算時，所產生之物理特徵值，來推測與破解密碼系統。
因此，倘若密碼系統之實作未能多此層面之考量，仍極有可能被物理
攻擊法所破解。
物理攻擊法的其中一類為能量攻擊法，本論文提出兩種防禦對
策，用以防禦此種能量攻擊法，期能增加智慧卡之安全性。第二章將
介紹於物理攻擊法中，最常被探討之能量攻擊法。第三章回顧能量攻
擊法之防禦對策。
在第四章中，本論文提出非確定式軟體技術，作為一種防禦能量
攻擊法之對策。我們運用程式軟體穿插交錯實作技巧，與非確定性之
程式執行方式，促使防偽性裝置於進行計算時，所產生之物理特徵值
呈現不規則之狀態，經由實驗證實，非確定式軟體技術之應用，可促
使能量攻擊法於執行時所需要收集之能量消耗波形數量增加，進而達
到使能量攻擊法更形困難之目標。
第五章提出遮罩分割對策。我們根據秘密分享之觀念，引入遮罩
分割技術，加強之前學者所提出的布林遮罩轉換算術遮罩機制，用更
為複雜的方式遮蔽原來能量消耗波形之物理特徵值，為使能量攻擊法
之實行更加繁瑣困難。並且，經由實驗證實，應用遮罩分割技術，確
可成功達到防制能量攻擊法之效果。

摘要(英)

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.

關鍵字(中)

★ 非確定性軟體
★ 能量攻擊
★ 遮罩

關鍵字(英)

★ Mask
★ Non-deterministic Software
★ Power Analysis A

論文目次

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

參考文獻

[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
.
[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 .
[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 ="" 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 ="" 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 ="" informatik="" pi4="" projects="" crypto="" rgp="" dfa="" dfa2.html="">.
[12] E. Biham and A. Shamir, “Improved differential fault analysis,” 1996,
available at URL ="" pi4="" projects="" crypto="" rgp="" dfa="">.
[13] E. Biham and A. Shamir, “A new cryptanalytic attack on DES,”
1996, available at URL ="" 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 .
[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
.
[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.

指導教授

顏嵩銘(Yen-Sung Ming)

審核日期

2004-6-21

推文