Theoretical notion of white-box

Question

Is there any theoretically safe notion of white-box?

I have been reading about white-box [1, 2, 3] recently. It seems white-box deals with code obfuscation and its not known whether a perfect white-box exists.

I am curios about theoretical notion behind this. For a stream cipher, the theoretical notion is PRF. For block cipher it is PRP. For a hash function, it is one-way function. Is there anything comparable for white-box?

I am looking for something which is not necessarily practical, but we can actually show this achieves perfect white-box, like a really scrambled code or something.

UPDATE. I vaguely remember reading something on the line of

White-box would be possible if a super-huge memory exists. The memory could be loaded as a look-up table with the plaintexts as the look-up-keys and the ciphertexts the look-up-values. Since the encryption-key is not involved in the look-up table (it has been used previously to create the look-up table), it cannot be recovered but encryption would be still possible.

But I could not retrieve the source. Does anybody know anything about it?

Answer 1

Since I guess we're entertaining this as a crypto question, and not reverse engineering, I'll provide a formal answer.

The purpose of white-box crypto, as generally accepted, is to hide the key used to perform some cryptographic operation. The issue with such a system is that the algorithm itself must know the key; it's pretty difficult to successfully encrypt or decrypt something with a key you don't know.

In any instance where the algorithm knows the key it uses to perform cryptographic operations, a reverse engineer can simply grab the key from the algorithm's memory. You can try to hinder the reverse engineer's attempt to do so, but reverse engineering isn't an NP-complete problem; it's actually quite easy for someone with the necessary skills.

Maybe you don't load the key, but some one-way operation based on the key... Congratulations! You're simply using a different key, and have changed no security properties whatsoever.

Let's say you use some input, perform some indecipherable calculations on it, and use the resulting value as the key... Congratulations! You've also done nothing, since a reverse engineer's entire job is to decipher seemingly "indecipherable" code, and they tend to be quite good at it.

Also, there's nothing stopping them from simply running the calculations themselves. They don't need to understand code to run it. You can try various techniques to prevent them from doing so, and that's called anti-reverse-engineering. But it's neither theoretically, nor practically, able to stop any decent reverse engineer.

Just a couple days ago I was tasked with reverse engineering a malware sample that tried to use such a white-box system to prevent me from understanding what it does. I decrypted every encrypted string within the sample and am currently pending approval to upload the reverse-engineered sample to my public GitHub.

In short, White-box crypto doesn't work.

Answer 2

Caution: White Box Cryptography is out of my comfort zone, and I have not been following the latest developments in the field. The following is my current opinion, which I present in hope of seeing it challenged, and learning in the process.

---

As I see it, the traditional goal of White Box Cryptography (and the one the industry would like most) is to design software that computes a standard public keyed cryptographic transformation (such as a keyed PRP, ideally AES) with a particular instance of the secret key embedded in the software, such that leaking the software does not leak the key.

I know no serious claim that this is even close to be achieved. On the contrary, WBC competitions that focused on the above goal with AES as the PRP have AFAIK all ended with quick key extraction.

With respect to that goal, it seems we do not even have practically secure WBC, and thus much less theoretically secure WBC. Contrast with the better situation in symmetric crypto, where we have practically secure PRPs and PRFs, but arguably no theoretically secure construction from first principles.

---

Yet a variant of WBC as defined above is practically feasible if we allow to construct the keyed transformation with WBC in mind: for example it's trivial to make a practically secure WBC implementation of the AES-256 lookalike WES-256, defined as: $$\begin{align} \text{WES-256}:\quad&\{0,1\}^{256}\times\{0,1\}^{128}\to\{0,1\}^{128}\\ &P\mapsto\text{WES-256}(K,P)\underset{\text{def}}=\text{AES-256}(\text{SHA-256}(K),P) \end{align}$$

If we take that variant definition, security of WBC follows from that of more traditional constructs.

---

My conclusion is that I know no good definition of the theoretical goal of WBC, thus can't answer the question!

Answer 3

Not the main answer, but something useful.

There is a notion of incompressibility, which requires that it is hard to meaningfully compress an intentionally large white-box implementation. While hard to achieve for existing ciphers, it is easy to design new symmetric ciphers with incompressible implementations.

Why? The main idea probably is to prevent code-lifting attacks: extracting say, 1GB from a mobile phone is much harder than 128 bit of the secret key. Especially, in a massive attack, say, by malware. Of course, on practice, industry is reluctant to use such implementations, as nobody wants to eat 1GB of storage for nothing.

How? For example, consider a Feistel Network where Feistel functions are truncated AES instances (using the master key, or better deriving from it). In the incompressible implementation, we'll put this function as a look-up table (we truncate it to have any desired size). It is not hard to show that compressing the scheme implies non-randomness of AES, so the incompressibility is reduced to the AES security.

Some references:

1. Delerablée et al. White-box security notions for symmetric encryption schemes. https://ia.cr/2013/523
2. Biryukov et al. Cryptographic Schemes Based on the ASASA Structure: Black-box, White-box, and Public-key https://ia.cr/2014/474
3. Bogdanov et al. White-box cryptography revisited: Space-hard ciphers.
4. Bogdanov et al. Towards Practical Whitebox Cryptography: Optimizing Efficiency and Space Hardness. https://www.iacr.org/archive/asiacrypt2016/10031190/10031190.pdf
5. Fouque et al. Efficient and Provable White-Box Primitives. https://ia.cr/2019/329
6. Cho et al. WEM: A New Family of White-box Block Ciphers Based on the Even-Mansour Construction http://www.cs.haifa.ac.il/~orrd/crypt/WEM.pdf
7. Bock et al. Doubly half-injective PRGs for incompressible white-box cryptography https://ia.cr/2019/329
8. Koike et al. Galaxy: A Family of Stream-Cipher-Based Space-Hard Ciphers

Answer 4

White-box cryptography says that any side-channel attack is impossible. Looking at the intermediate computation is no better than looking at input and output of the algorithm.

There is a theoretical "perfect" white-box cryptography notion, when the algorithm is represented as a huge table of (input, output) pairs. With this representation, nothing is known about the internals of the algorithm, only the inputs and outputs are visible. This of course becomes impractical for any input longer than 16 bits.

This is the white-box analogy of the one time pad from symmetric ciphers.