White-Box Cryptography: Analysis of White-Box AES Implementations

摘要

Cryptographic algorithms are designed to protect data or communication in the presence of an attacker. If these algorithms make use of a secret key, then their security relies on the secrecy of the key. Hence, the primary objective of an attacker typically is to extract the key. In a traditional black-box environment, the attacker has only access to the inputs and outputs of a cryptographic algorithm. However, due to the increasing demand to deploy strong cryptographic algorithms within software applications that are executed on untrusted open platforms owned and controlled by a possibly malicious party, the black-box environment becomes inadequate. Therefore, a new realistic white-box environment is introduced in which an attacker has complete access to a software implementation of a cryptographic algorithm and furthermore has full control over its execution environment. Real-world examples of a white-box environment can be found in digital content protection systems such as Digital Rights Management or Pay-TV systems, where key-instantiated cryptographic algorithms are implemented on e.g. a smartphone, tablet or set-top box. The extraction of the secret key would compromise the content protection.White-box cryptography aims to protect the confidentiality of the secret key of a cryptographic algorithm in a white-box environment. It is a technique to construct software implementations of a cryptographic algorithm that are sufficiently secure against a white-box attacker. In the academic literature, the focus has been mainly on the design of white-box implementations of block ciphers, an important subclass of symmetric-key cryptographic algorithms. In 2002, Chow, Eisen, Johnson and van Oorschot proposed the first published white-box implementation of the Advanced Encryption Standard (AES), one of the most prominent block ciphers at this time. However, two years later, Billet, Gilbert and Ech-Chatbi presented an efficient attack on this implementation, which motivated the design of three new white-box AES implementations offering more resistance against key extraction: the ones by Bringer, Chabanne and Dottax in 2006, by Xiao and Lai in 2009 and by Karroumi in 2010.This doctoral thesis covers the design and analysis of white-box implementations of block ciphers, where the main contributions address the analysis of white-box AES implementations. Starting from the initial improvement of Billet et al.’s attack proposed by Tolhuizen in 2012, we present several additional improvements considerably reducing the overall work factor. Our improved version leads to some useful observations with respect to the design choices made in Chow et al.’s white-box AES implementation. Further, this doctoral thesis describes the analysis of the three newly proposed white-box AES implementations mentioned above. First, we show how to efficiently extract equivalent keys out of Bringer et al.’s white-box AES implementation; these equivalent keys yield functionally equivalent implementations. Second, we present a practical cryptanalysis of the white-box AES implementation proposed by Xiao and Lai. The cryptanalysis uses a modified variant of the linear equivalence algorithm presented by Biryukov, De Cannière, Braeken and Preneel as a building block. Additionally, we consider design generalizations of the Xiao-Lai white-box AES implementation and their impact on our cryptanalytic result. Third, we show that Karroumi’s white-box AES implementation belongs to the class of white-box AES implementations specified by Chow et al. Consequently, Karroumi’s implementation remains vulnerable to the attack it was designed to resist, i.e., Billet et al.’s attack and our improved version of this attack.Based on the cryptanalytic results presented in this doctoral thesis and outlined above, it is shown that in early 2014 there does not exist a practical and secure white-box AES implementation published in the academic literature, even though AES is still considered to be a secure black-box block cipher. However, at the end of this thesis we discuss a new design principle proposed by Michiels and Gorissen that may lead to the construction of secure white-box AES implementations. All white-box AES implementations appeared in the academic literature so far are fixed-key; we present a new dynamic-key white-box technique that allows to update the cryptographic key in a more secure way than the known techniques.