臺灣博碩士論文加值系統

遮罩防護需要使用亂數產生器。於此研究中，我們研究線性同餘法生成的亂 數用於遮罩防禦時，是否和其他密碼學應用上安全的亂數產生器有同等強度的效 果，以及可能的旁道分析攻擊方法，並且為這些可能的攻擊提出解決方法。我們 發現遮罩防護不需要用到密碼學應用上安全的亂數產生器，一個加上旁通道防護 的線性同餘亂數產生器就已經足夠安全。 另外，我們也根據實作二階差分能量分 析攻擊的經驗，提出一個可以抵擋二階差分能量分析攻擊的特化遮罩防護方法。

Masking countermeasures need random number generators. In this research, we study about whether it is at the same secure level to use linear congruential generators to generate masks compared to other cryptographically secure pseudo random number generators. After analyzing some possible kinds of side channel analysis on linear congruential generators and finding out some countermeasures against them, we find that it is not necessary to use cryptographically secure pseudo random number generators in a masking countermeasure, and a linear congruential generator with countermeasures are secure enough. Besides, with the experience of performing second order differential power analysis, we provide a specialized masking countermeasure strategy to resist second order differential power analysis.

1 Introduction................................................................. 1
1.1 Motivation............................................................. 1
1.2 Our Contributions...................................................... 2
1.3 Chapters Introduction.................................................. 3

2 Preliminaries................................................................ 4
2.1 Linear Congruential Generator.......................................... 4
2.1.1 Lehmer Generator................................................. 4
2.2 Side Channel Analysis and Power Analysis............................... 5
2.2.1 Timing Attack.................................................... 6
2.2.2  Differential Power Analysis...................................... 7
2.2.3 Vertical and Horizontal Power Analysis........................... 8
2.3 Countermeasures against SCA............................................ 9
2.3.1 Avoid Conditional Statement...................................... 9
2.3.2 Countermeasures against DPA...................................... 9 


3 Attacks on Masking.......................................................... 11
3.1 Second-Order DPA...................................................... 11
3.1.1 Types of 2O-DPA................................................. 12
3.1.2 Combination..................................................... 13
3.1.3 Search Space of 2O-DPA.......................................... 13
3.1.4 Countermeasures of 2O-DPA....................................... 14
3.2  Two-Stage Attack...................................................... 15 


4  Security Issues of LCG in Masking Countermeasure............................ 16
4.1  Statistic Issues...................................................... 16
4.2  Cryptographic Security Issues......................................... 16
4.3  Side Channel Issues................................................... 17
4.3.1 Leakage in Masking Preprocessing................................ 18
4.3.2 Leakage Attached on the Intermediate Values..................... 18

5  LCG Countermeasures against Timing Attacks.................................. 19
5.1  Timing Leakage of LCG................................................. 19
5.1.1 Two Sizes of Intervals.......................................... 19
5.1.2 Timing Leakage in AVR Division.................................. 20
5.2  Attacks by Timing Leakage............................................. 22
5.3  A Revised LCG without Timing Leakage.................................. 24
5.3.1  Remove Redundant Part 1......................................... 24
5.3.2  Using Shift to Rewrite the Division in Part 2................... 25
5.3.3  Using MSB to Choose Output in Part 3............................ 26
5.3.4  Result.......................................................... 26

6  LCG Countermeasures against DPA............................................. 28
6.1 The Dilemma........................................................... 28
6.2 Difference of Means Attack on LCG..................................... 29
6.3 Possible Countermeasures.............................................. 30 


7  LCG Masking against Second-Order DPA........................................ 32
7.1 Simulations........................................................... 32
7.1.1 Conditions of the Simulations................................... 32
7.1.2  Key Recovering in Masked AES-128................................ 33 

7.1.3  Key Recovering in Masked AES-128 with Random Shuffling.......... 33 

7.2  Real Experiment....................................................... 36 


8  Suggestions against Second-Order DPA........................................ 38
8.1  Random Shuffling...................................................... 38 

8.2  Fix the Hamming Weight of Masks....................................... 38
8.2.1 Using Subsets of Masks.......................................... 38
8.2.2 Biased Masks Attack Issue....................................... 39
8.2.3 2O-DPA Results.................................................. 40 


9  Conclusion.................................................................. 42 


Bibliography................................................................... 43

Appendix A. Results of Second-Order DPA........................................ 47

Appendix B. Poor Shuffling Examples............................................ 50

[1] Avr crypto library. https://git.cryptolib.org/avr-crypto-lib.git.
[2] Avr libc home page. http://www.nongnu.org/avr-libc/.
[3] Avr libc reference manual toolchain overview, gcc. http://www.atmel.com/webdoc/avrlibcreferencemanual/overview_1overview_gcc.html.
[4] Chipwhisperer. https://newae.com/tools/chipwhisperer/.
[5] Mihir Bellare, Shafi Goldwasser, and Daniele Micciancio. “pseudo-random” number generation within cryptographic algorithms: The dds case. Advances in Cryptology—CRYPTO’97, pages 277–291, 1997.
[6] Eric Brier, Christophe Clavier, and Francis Olivier. Correlation power analysis with a leakage model. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 16–29. Springer, 2004.
[7] Suresh Chari, Charanjit S Jutla, Josyula R Rao, and Pankaj Rohatgi. Towards sound approaches to counteract power-analysis attacks. In Annual International Cryptology Conference, pages 398–412. Springer, 1999.
[8] Christophe Clavier, Jean-Sébastien Coron, and Nora Dabbous. Differential power analysis in the presence of hardware countermeasures. In Cryptographic Hardware and Embedded Systems—CHES 2000, pages 13–48. Springer, 2000.
[9] Christophe Clavier, Benoit Feix, Georges Gagnerot, Mylène Roussellet, and Vincent Verneuil. Horizontal correlation analysis on exponentiation. In International Conference on Information and Communications Security, pages 46–61. Springer, 2010.
[10] Joan Daemen and Vincent Rijmen. The design of Rijndael: AES-the advanced encryption standard. Springer Science & Business Media, 2013.
[11] Benedikt Gierlichs, Lejla Batina, Pim Tuyls, and Bart Preneel. Mutual information analysis. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 426–442. Springer, 2008.
[12] Louis Goubin and Jacques Patarin. Des and differential power analysis the “duplication” method. In Cryptographic Hardware and Embedded Systems, pages 728–728. Springer, 1999.
[13] Christoph Herbst, Elisabeth Oswald, and Stefan Mangard. An aes smart card implementation resistant to power analysis attacks. In International Conference on Applied Cryptography and Network Security, pages 239–252. Springer, 2006.
[14] Joshua Jaffe. More differential power analysis: Selected dpa attacks. Summer School on Cryptographic Hardware, Side-Channel and Fault Attacks, 2006.
[15] Marc Joye and Sung-Ming Yen. The montgomery powering ladder. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 291–302. Springer, 2002.
[16] Paul Kocher. Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems. In Advances in Cryptology—CRYPTO’96, pages 104–113. Springer, 1996.
[17] Paul Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In Advances in cryptology—CRYPTO’99, pages 789–789. Springer, 1999.
[18] Derrick H. Lehmer. Mathematical methods in large-scale computing units. In Proceedings of the Second Symposium on Large Scale Digital Computing Machinery, pages 141–146, Cambridge, United Kingdom, 1951. Harvard University Press.
[19] Houssem Maghrebi, Olivier Rioul, Sylvain Guilley, and Jean-Luc Danger. Comparison between side-channel analysis distinguishers. In International Conference on Information and Communications Security, pages 331–340. Springer, 2012.
[20] Thomas Messerges. Using second-order power analysis to attack dpa resistant software. In Cryptographic Hardware and Embedded Systems—CHES 2000, pages 27–78. Springer, 2000.
[21] Colin O’Flynn and Zhizhang David Chen. Chipwhisperer: An open-source platform for hardware embedded security research. In International Workshop on Constructive Side-Channel Analysis and Secure Design, pages 243–260. Springer, 2014.
[22] Stephen K. Park and Keith W. Miller. Random number generators: good ones are hard to find. Communications of the ACM, 31(10):1192–1201, 1988.
[23] Emmanuel Prouff, Matthieu Rivain, and Régis Bevan. Statistical analysis of second order differential power analysis. IEEE Transactions on computers, 58(6):799–811, 2009.
[24] Matthieu Rivain and Emmanuel Prouff. Provably secure higher-order masking of aes. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 413–427. Springer, 2010.
[25] Matthieu Rivain, Emmanuel Prouff, and Julien Doget. Higher-order masking and shuffling for software implementations of block ciphers. In Cryptographic Hardware and Embedded Systems-CHES 2009, pages 171–188. Springer, 2009.
[26] Werner Schindler, Kerstin Lemke, and Christof Paar. A stochastic model for differential side channel cryptanalysis. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 30–46. Springer, 2005.
[27] Kai Schramm and Christof Paar. Higher order masking of the aes. In Cryptographers’ Track at the RSA Conference, pages 208–225. Springer, 2006.
[28] Jacques Stern. Secret linear congruential generators are not cryptographically secure. In Foundations of Computer Science, 1987., 28th Annual Symposium on, pages 421–426. IEEE, 1987.
[29] Michael Tunstall, Carolyn Whitnall, and Elisabeth Oswald. Masking tables — an underestimated security risk. In International Workshop on Fast Software Encryption, pages 425–444. Springer, 2013.