Cryptanalysis of White Box DES Implementations
Obfuscation is a method consisting in hiding information of some parts of a computer program. According to the Kerckhoffs principle, a cryptographical algorithm should be kept public while the whole security should rely on the secrecy of the key. In some
- PDF / 458,681 Bytes
- 18 Pages / 430 x 660 pts Page_size
- 36 Downloads / 184 Views
Abstract. Obfuscation is a method consisting in hiding information of some parts of a computer program. According to the Kerckhoffs principle, a cryptographical algorithm should be kept public while the whole security should rely on the secrecy of the key. In some contexts, source codes are publicly available, while the key should be kept secret; this is the challenge of code obfuscation. This paper deals with the cryptanalysis of such methods of obfuscation applied to the DES. Such methods, called the “naked-DES” and “nonstandard-DES”, were proposed by Chow et al. [5] in 2002. Some methods for the cryptanalysis of the “naked-DES” were proposed by Chow et al. [5], Jacob et al. [6], and Link and Neuman [7]. In their paper, Link and Neuman [7] proposed another method for the obfuscation of the DES. In this paper, we propose a general method that applies to all schemes. Moreover, we provide a theoretical analysis. We implemented our method with a C code and applied it successfully to thousands of obfuscated implementations of DES (both “naked” and “non-standard” DES). In each case, we recovered enough information to be able to invert the function. Keywords: Obfuscation, cryptanalysis, DES, symmetric cryptography, block cipher.
1
Introduction
In recent years, the possibility of obfuscating programs has been investigated. From a theoretical point of view, Barak et al. [1] have proven impossibility results for the task of obfuscating computer programs. In particular, it turns out that there exists a family of programs such that: on the one hand each program is non learnable (i.e. its execution does not give any information about its original source code), but on the other hand every obfuscator (i.e. the program producing an obfuscation) fails completely when given any program of this family as input. However it has not been proved that specific instances, particularly cryptographic primitives, are impossible to obfuscate.
This work has been supported in part by the French ANR (Agence Nationale de la Recherche), through the CrySCoE project, and by the région Île-de-France.
C. Adams, A. Miri, and M. Wiener (Eds.): SAC 2007, LNCS 4876, pp. 278–295, 2007. c Springer-Verlag Berlin Heidelberg 2007
Cryptanalysis of White Box DES Implementations
279
In 2002, Chow et al. [4,5] suggested two different obfuscations, one for the AES, the other for the DES. The AES obfuscation was cryptanalysed by Billet et al. [2,3] in 2004. Chow et al. [5] also mounted an attack on their first DES obfuscation version (called “naked-DES”). Jacob et al. [6] and Link and Neuman [7], proposed two other attacks on the “naked-DES”. Here, breaking the “nakedDES” means recovering the secret key. A second version of DES obfuscation, called “nonstandard-DES”, was given by Chow et al. [5]. This “nonstandard-DES” is obtained by obfuscating the usual DES composed with initial and final secret permutations. In this context, breaking such a “nonstandard-DES” implementation means recovering the secret key and the secret initial and final permutations. Moreov
Data Loading...
