logo

SCIENCE CHINA Information Sciences, Volume 59, Issue 11: 112101(2016) https://doi.org/10.1007/s11432-015-5474-8

Discussion on the theoretical results of white-box cryptography

More info
  • ReceivedJul 13, 2015
  • AcceptedSep 26, 2015
  • PublishedMay 24, 2016

Abstract

White-box cryptography (WBC) aims to resist attacks from attackers who can control all the implementation details of cryptographic schemes. In 2009, Saxena et al. proposed a fundamental of white-box cryptography via the notion ``white-box property'' (WBP). Under this model, they proved that there do not exist obfuscators that can satisfy every security notion for a program (the negative result). On the other hand, they proved that there exists an obfuscator satisfying WBP for some security notion (the positive result). These contributions provide us a general cognition of WBC, which is big progress for the theoretical research. To better understand them, we make discussion on each result and achieve some new results. For the negative result, we prove that insufficiently secure obfuscator is the real cause of the negative result. We point out that the security of a white-box scheme cannot be guaranteed if it is instantiated by a less secure obfuscator, since the obfuscator used in their proof does not satisfy the ``Virtual Black-box Property'' with auxiliary input. From our proof, we also conclude that the notion WBP is equal to ``Virtual Black-box Property with auxiliary input''. For the positive result, we prove that security notion under black-box model should not be used in white-box context without any modification; although the positive result is meaningful, it is unlikely to prove that an obfuscator satisfies WBP for IND-CPA, since the security notion ``IND-CPA'' is under black-box model, which has different adversary with WBP.


Funded by

National Natural Science Foundation of China(61272440)

National Natural Science Foundation of China(61472251)

National Natural Science Foundation of China(U1536101)

China Postdoctoral Science Foundation(2013M531174)

China Postdoctoral Science Foundation(2014T70417)


Acknowledgment

Acknowledgments

This work was supported by National Natural Science Foundation of China (Grant Nos. 61272440, 61472251, U1536101), China Postdoctoral Science Foundation (Grant Nos. 2013M531174, 2014T70417) and Science and Technology on Communication Security Laboratory.


References

[1] Borghoff J, Canteaut A, Gneysu T, et al. {Prince--a low-latency block cipher for pervasive computing applications}. {In: Advances in Cryptology--ASIACRYPT. Berlin: Springer}, 2012. {49--58}. Google Scholar

[2] Wang S B, Zhu Y, Ma D, et al. {Lattice-based key exchange on small integer solution problem}. Sci China Inf Sci, 2014, 57: 112111 Google Scholar

[3] Chen Z X. {Trace representation and linear complexity of binary sequences derived from Fermat quotients}. Sci China Inf Sci, 2014, 57: 112109 Google Scholar

[4] Chow S, Eisen P, Johnson H, et al. White-box cryptography and an AES implementation. In: Selected Areas in Cryptography. Berlin: Springer, 2003. 250--270. Google Scholar

[5] Chow S, Eisen P, Johnson H, et al. A white-box DES implementation for DRM applications. In: Digital Rights Management. Berlin: Springer, 2003. 1--15. Google Scholar

[6] Xiao Y Y, Lai X J. {A secure implementation of white-box AES}. {In: Proceedings of the 2nd International Conference on Computer Science and its Applications}, Jeju, 2009. 1--6. Google Scholar

[7] Karroumi M. Protecting white-box AES with dual ciphers. In: Information Security and Cryptology-ICISC. Berlin: Springer, 2011. 278--291. Google Scholar

[8] Bringer J, Chabanne H, Dottax E. White box cryptography: another attempt. IACR Cryptology ePrint Archive, 2006, 2011: 468 Google Scholar

[9] Xiao Y Y, Lai X J. White-box cryptography and a white-box implementation of the SMS4 algorithm. In: ChinaCrypt, Guangzhou, 2009. 24--34. Google Scholar

[10] Shi Y, Wei W, He Z. A lightweight white-box symmetric encryption algorithm against node capture for WSNs. Sensors, 2015, 15: 11928-11952 CrossRef Google Scholar

[11] Link H E, Neumann W D. Clarifying obfuscation: improving the security of white-box DES. In: Proceedings of IEEE International Conference on Information Technology: Coding and Computing, Las Vegas, 2005, 1: 679--684. Google Scholar

[12] Wyseur B, Michiels W, Gorissen P, et al. Cryptanalysis of white-box DES implementations with arbitrary external encodings. In: Selected Areas in Cryptography. Berlin: Springer, 2007. 264--277. Google Scholar

[13] Goubin L, Masereel J M, Quisquater M. Cryptanalysis of white box DES implementations. In: Selected Areas in Cryptography. Berlin: Springer, 2007. 278--295. Google Scholar

[14] Billet O, Gilbert H, Ech-Chatbi C. Cryptanalysis of a white box AES implementation. In: Selected Areas in Cryptography. Berlin: Springer, 2005. 227--240. Google Scholar

[15] Michiels W, Gorissen P, Hollmann H D L. Cryptanalysis of a generic class of white-box implementations. In: Selected Areas in Cryptography. Berlin: Springer, 2009. 414--428. Google Scholar

[16] De Mulder Y, Roelse P, Preneel B. Cryptanalysis of the Xiao-Lai white-box AES Implementation. In: Selected Areas in Cryptography. Berlin: Springer, 2013. 34--49. Google Scholar

[17] Lepoint T, Rivain M, De Mulder Y, et al. Two attacks on a white-box AES implementation. In: Selected Areas in Cryptography--SAC 2013. Berlin: Springer, 2014. 265--285. Google Scholar

[18] De Mulder Y, Wyseur B, Preneel B. Cryptanalysis of a perturbated white-box AES implementation. In: Progress in Cryptology-INDOCRYPT. Berlin: Springer, 2010. 292--310. Google Scholar

[19] Lin T T, Lai X J. Efficient attack to white-box SMS4 implementation. J Softw, 2013, 24: 2238-2249 Google Scholar

[20] Gilbert H, Plt J, Treger J. Key-recovery attack on the ASASA cryptosystem with expanding S-boxes. In: Advances in Cryptology--CRYPTO 2015. Berlin: Springer, 2015. 475--490. Google Scholar

[21] Herzberg A, Shulman H, Saxena A, et al. Towards a theory of white-box security. In: Emerging Challenges for Security, Privacy and Trust. Berlin: Springer, 2009. 342--352. Google Scholar

[22] Saxena A, Wyseur B, Preneel B. Towards security notions for white-box cryptography. In: Information Security. Berlin: Springer, 2009. 49--58. Google Scholar

[23] Saxena A, Wyseur B, Preneel B. White-box cryptography: formal notions and (im) possibility results. IACR Cryptology ePrint Archive, 2008, 2008: 273-2249 Google Scholar

[24] Valiant L G. A theory of the learnable. Commun ACM, 1984, 27: 1134-1142 CrossRef Google Scholar

[25] Linial N, Mansour Y, Nisan N. Constant depth circuits, fourier transform, and learnability. J ACM (JACM), 1993, 40: 607-620 CrossRef Google Scholar

[26] Lynn B, Prabhakaran M, Sahai A. Positive results and techniques for obfuscation. In: Advances in Cryptology-EUROCRYPT. Berlin: Springer, 2004. 20--39. Google Scholar

[27] Wee H. On obfuscating point functions. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. New York: ACM, 2005. 523--532. Google Scholar

[28] Hada S. Zero-knowledge and code obfuscation. In: Advances in Cryptology A SIACRYPT. Berlin: Springer, 2000. 443--457. Google Scholar

[29] Barak B, Goldreich O, Impagliazzo R, et al. On the (im) possibility of obfuscating programs. In: Advances in cryptology CRYPTO 2001. Berlin: Springer, 2001. 1--18. Google Scholar

[30] Canetti R, Dakdouk R R. Extractable perfectly one-way functions. In: Automata, Languages and Programming. Berlin: Springer, 2008. 449--460. Google Scholar

[31] Canetti R, Rothblum G N, Varia M. Obfuscation of hyperplane membership. In: Theory of Cryptography. Berlin: Springer, 2010, 10: 72--89. Google Scholar

[32] Barak B, Bitansky N, Canetti R, et al. Obfuscation for evasive functions. In: Theory of Cryptography. Berlin: Springer, 2014. 26--51. Google Scholar

[33] Goldwasser S, Kalai Y T. On the impossibility of obfuscation with auxiliary input. In: Proceedings of IEEE 46th Annual Symposium on Foundations of Computer Science, Los Alamitos, 2005. 553--562. Google Scholar

[34] Garg S, Gentry C, Halevi S, et al. Candidate indistinguishability obfuscation and functional encryption for all circuits. In: Proceedings of IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), Berkeley, 2013. 40--49. Google Scholar

[35] Sahai A, Waters B. How to use indistinguishability obfuscation: deniable encryption, and more. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing. New York: ACM, 2014. 475--484. Google Scholar

[36] Hohenberger S, Sahai A, Waters B. Replacing a random oracle: full domain hash from indistinguishability obfuscation. In: Advances in Cryptology-EUROCRYPT. Berlin: Springer, 2014. 201--220. Google Scholar

[37] Pandey O, Prabhakaran M, Sahai A. Obfuscation-based non-black-box simulation and four message concurrent zero knowledge for np. In: Theory of Cryptography. Berlin: Springer, 2015. 638--667. Google Scholar

[38] Goldwasser S, Rothblum G N. On best-possible obfuscation. In: Theory of Cryptography. Berlin: Springer, 2007. 194--213. Google Scholar

[39] Barak B, Goldreich O, Impagliazzo R, et al. On the (im) possibility of obfuscating programs. J ACM (JACM), 2012, 59: 6-620 Google Scholar

[40] Bitansky N, Canetti R, Cohn H, et al. The impossibility of obfuscation with auxiliary input or a universal simulator. In: Advances in Cryptology CRYPTO. Berlin: Springer, 2014. 71--89. Google Scholar

[41] Ananth P, Boneh D, Garg S, et al. Differing-inputs obfuscation and applications. IACR Cryptology ePrint Archive, 2013, 2013: 689-620 Google Scholar

[42] Boyle E, Chung K M, Pass R. On extractability obfuscation. In: Theory of Cryptography. Berlin: Springer, 2014. 52--73. Google Scholar

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1