Abstract 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.
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.
Corresponding Authors: Xue-Jia Lai
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
Cite this article:
Ting-Ting Lin, Xue-Jia Lai, Wei-Jia Xue, Yin Jia.A New Feistel-Type White-Box Encryption Scheme[J] Journal of Computer Science and Technology, 2017,V32(2): 386-395
 Shannon C E. A mathematical theory of communication. ACM SIGMOBILE Mobile Computing and Communications Review, 2001, 5(1):3-55. 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. Kocher P, Jaffe J, Jun B. Differential power analysis. In Proc. the 19th Annual International Cryptology Conference, August 1999, pp.388-397. 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. Wang H. Privacy-preserving data sharing in cloud computing. Journal of Computer Science and Technology, 2010, 25(3):401-414. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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 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. 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. Bringer J, Chabanne H, Dottax E. White box cryptography:Another attempt. IACR Cryptology ePrint Archive, 2006. 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. Xiao Y Y.White-Box cryptography and implementations of AES SMS4. In Proc. the Chaincrypto, Nov. 2009, pp.24-34. (in Chinese) Lin T T, Lai X J. Efficient attack to white-box SMS4 implementation. Journal of Software, 2013, 24(9):2238-2249. (in Chinese) 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. 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. 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. Biryukov A, Khovratovich D. Decomposition attack on SASASASAS. https://eprint.iacr.org/2015/646.pdf, Jan. 2017. 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. Feistel H. Cryptography and computer privacy. Scientific American, 1973, 228(5):15-23. Data Encryption Standard, Federal Information Processing Standard (FIPS). National Bureau of Standards, U.S. Department of Commerce, Washington D. C., Jan. 1977. 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. 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. 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. 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. Biryukov A, Shamir A. Structural cryptanalysis of SASAS. Journal of Cryptology, 2010, 23(4):505-518. Biryukov A, Shamir A. Structural cryptanalysis of SASAS. In Lecture Notes in Computer Science 2045, Pfitzmann B (ed.), Springer, 2001, pp.395-405.
Copyright 2010 by Journal of Computer Science and Technology