›› 2017, Vol. 32 ›› Issue (2): 386-395.doi: 10.1007/s11390-017-1727-x

• Regular Paper • Previous Articles     Next Articles

A New Feistel-Type White-Box Encryption Scheme

Ting-Ting Lin1,2, Xue-Jia Lai1,*, Wei-Jia Xue1, Yin Jia1   

  1. 1 Cryptography and Information Security Laboratory, Department of Computer Science, Shanghai Jiao Tong University Shanghai 200240, China;
    2 Irdeto Canada, Ottawa, Ontario, K2K 3G5, Canada
  • Received:2015-12-01 Revised:2016-12-01 Online:2017-03-05 Published:2017-03-05
  • Contact: Xue-Jia Lai E-mail:lai-xj@cs.sjtu.edu.cn
  • About author:Ting-Ting Lin received her Ph.D. degree in computer science from Shanghai Jiao Tong University, Shanghai, in 2016. Her research interests are theory and techniques of white-box cryptography, block cipher, software security, and obfuscation. Text
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61272440, 61472251, and U1536101, and China Postdoctoral Science Foundation under Grant Nos. 2013M531174 and 2014T70417.

The white-box attack is a new attack context in which it is assumed that cryptographic software is implemented on an un-trusted platform and all the implementation details are controlled by the attackers. So far, almost all white-box solutions have been broken. In this study, we propose a white-box encryption scheme that is not a variant of obfuscating existing ciphers but a completely new solution. The new scheme is based on the unbalanced Feistel network as well as the ASASASA (where "A" means affine, and "S" means substitution) structure. It has an optional input block size and is suitable for saving space compared with other solutions because the space requirement grows slowly (linearly) with the growth of block size. Moreover, our scheme not only has huge white-box diversity and white-box ambiguity but also has a particular construction to bypass public white-box cryptanalysis techniques, including attacks aimed at white-box variants of existing ciphers and attacks specific to the ASASASA structure. More precisely, we present a definition of white-box security with regard to equivalent key, and prove that our scheme satisfies such security requirement.

[1] Shannon C E. A mathematical theory of communication. ACM SIGMOBILE Mobile Computing and Communications Review, 2001, 5(1):3-55.

[2] Kocher P C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In Proc. the 16th Annual International Cryptology Conference on Advances in Cryptology, August 1996, pp.104-113.

[3] Kocher P, Jaffe J, Jun B. Differential power analysis. In Proc. the 19th Annual International Cryptology Conference, August 1999, pp.388-397.

[4] Quisquater J J, Samyde D. Electromagnetic analysis (EMA):Measures and counter-measures for smart cards. In Proc. the International Conference on Research in Smart Cards:Smart Card Programming and Security, September 2001, pp.200-210.

[5] Wang H. Privacy-preserving data sharing in cloud computing. Journal of Computer Science and Technology, 2010, 25(3):401-414.

[6] Mi H B, Wang H M, Zhou Y F, Lyu M R, Cai H. Localizing root causes of performance anomalies in cloud computing systems by analyzing request trace logs. Science China Information Sciences, 2012, 55(12):2757-2773.

[7] Wang X M, He Z B, Zhao X Q, Lin C, Pan Y, Cai Z P. Reaction-diffusion modeling of malware propagation in mobile wireless sensor networks. Science China Information Sciences, 2013, 56(9):1-18.

[8] Ma X L, Hu H F, Li S F, Xiao H M, Luo Q, Yang D Q, Tang SW. DHC:Distributed, hierarchical clustering in sensor networks. Journal of Computer Science and Technology, 2011, 26(4):643-662.

[9] Zhou C, Sun Y Q. SPMH:A solution to the problem of malicious hosts. Journal of Computer Science and Technology, 2002, 17(6):738-748.

[10] Chow S, Eisen P, Johnson H, van Oorschot P C. A whitebox DES implementation for DRM applications. In Lecture Notes in Computer Science 2696, Feigenbaum J (ed.), Springer, 2003, pp.1-15.

[11] Chow S, Eisen P, Johnson H, van Oorschot P C. Whitebox cryptography and an AES implementation. In Lecture Notes in Computer Science 2595, Nyberg K, Heys H (eds.), Springer, 2003, pp.250-270.

[12] Jacob M, Boneh D, Felten E. Attacking an obfuscated cipher by injecting faults. In Lecture Notes in Computer Science 2696, Feigenbaum J (ed.), Springer, 2003, pp.16-31.

[13] Link H E, Neumann W D. Clarifying obfuscation:Improving the security of whitebox DES. In Proc. International Conference on Information Technology:Coding and Computing, April 2005, pp.679-684.

[14] Wyseur B, Michiels W, Gorissen P, Preneel B. Cryptanalysis of white-box DES implementations with arbitrary external encodings. In Proc. the 14th International Conference on Selected Areas in Cryptography, August 2007, pp.264-277.

[15] Goubin L, Masereel J M, Quisquater M. Cryptanalysis of white box DES implementations. In Proc. the 14th International Conference on Selected Areas in Cryptography, August 2007, pp.278-295.

[16] Billet O, Gilbert H, Ech-Chatbi C. Cryptanalysis of a white box AES implementation. In Proc. the 11th International Conference on Selected Areas in Cryptography, August 2005, pp.227-240.

[17] Michiels W, Gorissen P, Hollmann H D L. Cryptanalysis of a generic class of white-box implementations. In Lecture Notes in Computer Science 5381, Avanzi R M, Keliher L, Sica F (eds.), Springer, 2009, pp.414-428.

[18] Lepoint T, Rivain M, De Mulder Y, Roelse P, Preneel B. Two attacks on a white-box AES implementation. In Lecture Notes in Computer Science 8282, Lange T, Lauter K, Lisoněk P (eds.), Springer, 2014, pp.265-285.

[19] Xiao Y Y, Lai X J. A secure implementation of white-box AES. In Proc. the 2nd International Conference on Computer Science and its Applications, December 2009, pp.153-158.

[20] De Mulder Y, Roelse P, Preneel B. Cryptanalysis of the Xiao-Lai white-box AES Implementation. In Lecture Notes in Computer Science 7707, Knudsen L R, Wu H P (eds.), Springer, 2013, pp.34-49

[21] Biryukov A, De Cannière C, Braeken A, Preneel B. A toolbox for cryptanalysis:Linear and affine equivalence algorithms. In Lecture Notes in Computer Science 2656, Biham E (ed.), Springer, 2003, pp.33-50.

[22] Karroumi M. Protecting white-box AES with dual ciphers. In Lecture Notes in Computer Science 6829, Rhee K H, Nyang D (eds.), Springer, 2011, pp.278-291.

[23] Bringer J, Chabanne H, Dottax E. White box cryptography:Another attempt. IACR Cryptology ePrint Archive, 2006.

[24] De Mulder Y, Wyseur B, Preneel B. Cryptanalysis of a perturbated white-box AES implementation. In Lecture Notes in Computer Science 6498, Gong G, Gupta K C (eds.), Springer, 2010, pp.292-310.

[25] Xiao Y Y.White-Box cryptography and implementations of AES SMS4. In Proc. the Chaincrypto, Nov. 2009, pp.24-34. (in Chinese)

[26] Lin T T, Lai X J. Efficient attack to white-box SMS4 implementation. Journal of Software, 2013, 24(9):2238-2249. (in Chinese)

[27] Biryukov A, Bouillaguet C, Khovratovich D. Cryptographic schemes based on the ASASA structure:Black-box, whitebox, and public-key (Extended Abstract). In Lecture Notes in Computer Science 8873, Sarkar P, Iwata T (eds.), Springer, 2014, pp.63-84.

[28] Minaud B, Derbez P, Fouque P A, Karpman P. Keyrecovery attacks on ASASA. In Lecture Notes in Computer Science 9453, Iwata T, Cheon J H (eds.), Springer, 2015, pp.3-27.

[29] Dinur I, Dunkelman O, Kranz T, Leander G. Decomposing the ASASA block cipher construction. Cryptology ePrint Archive, Report 2015/507, 2015. http://eprint.iacr.org/2015/507, Jan. 2017.

[30] Biryukov A, Khovratovich D. Decomposition attack on SASASASAS. https://eprint.iacr.org/2015/646.pdf, Jan. 2017.

[31] Bogdanov A, Isobe T. White-box cryptography revisited:Space-hard ciphers. In Proc. the 22nd ACM SIGSAC Conference on Computer and Communications Security, October 2015, pp.1058-1069.

[32] Feistel H. Cryptography and computer privacy. Scientific American, 1973, 228(5):15-23.

[33] Data Encryption Standard, Federal Information Processing Standard (FIPS). National Bureau of Standards, U.S. Department of Commerce, Washington D. C., Jan. 1977.

[34] Rivest R L, Robshaw M J B, Sidney R, Yin Y L. The RC6TM block cipher. In Proc. the 1st Advanced Encryption Standard (AES) Conference, August 1998, pp.82-104.

[35] Schneier B, Kelsey J, Whiting D, Wagner D, Hall C, Ferguson N. Twofish:A 128-bit block cipher. NIST AES Proposal, 1998. https://www.schneier.com/academic/archives/1998/06/twofish a 128-bit bl.html, Jan. 2017.

[36] Patarin J, Goubin L. Asymmetric cryptography with Sboxes:Is it easier than expected to design efficient asymmetric cryptosystems? In Lecture Notes in Computer Science 1334, Han Y F, Okamoto T, Qing S H (eds.), Springer, 1997, pp.369-380.

[37] Biham E. Cryptanalysis of Patarin's 2-round public key system with S boxes (2R). In Lecture Notes in Computer Science 1807, Preneel B (ed), Springer, 2000, pp.408-416.

[38] Biryukov A, Shamir A. Structural cryptanalysis of SASAS. Journal of Cryptology, 2010, 23(4):505-518.

[39] Biryukov A, Shamir A. Structural cryptanalysis of SASAS. In Lecture Notes in Computer Science 2045, Pfitzmann B (ed.), Springer, 2001, pp.395-405.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2] Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3] Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4] Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[5] Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[6] Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[7] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[8] Zhao Jinghai; Liu Shenquan;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .
[9] Shang Lujun; Xu Lihui;. Notes on the Design of an Integrated Object-Oriented DBMS Family[J]. , 1991, 6(4): 389 -394 .
[10] Xu Jianguo; Gou Yuchai; Lin Zongkai;. HEPAPS:A PCB Automatic Placement System[J]. , 1992, 7(1): 39 -46 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved