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?

  • 2
    $\begingroup$ This isn't really a cryptography question. It's more reverse engineering. Although the answer is no there isn't. That's why DRM keeps getting broken by anyone willing to put in the effort and risk lawsuits. I would recommend this question be migrated to reverse engineering SE. $\endgroup$ – Serpent27 Oct 2 '20 at 5:50
  • 1
    $\begingroup$ Brecht Wyseur's PHD thesis seems to provide a theoretical model for white box cryptography. Unfortunately, I don't have time to read it and summarize is in an answer at the moment. $\endgroup$ – Vaelus Oct 2 '20 at 16:44
  • $\begingroup$ I am completely unfamiliar with white-box cryptography, but how does it differ from something like hard-coding the key to the algorithm, and then passing the algorithm to an indistinguishability obfuscator? $\endgroup$ – Mark Oct 3 '20 at 5:20
  • 1
    $\begingroup$ You could take a look at the videos/slides from cryptoexperts.com/whibox2016 and cryptoexperts.com/whibox2019 $\endgroup$ – j.p. Oct 3 '20 at 9:37
  • 2
    $\begingroup$ Note that I oppose migrating this question elsewhere as it clearly asks for the formal model used for white-box cryptography. Given that whitebox cryptography is a (more or less) accepted part of cryptography and even has seen some attacks using side-channel techniques, it seems plausible for such a model to exist - if one digs in the contexts. Also note that this question does not ask in any way about the general feasibility (though any potential impossibility results will probably not be unwelcome). $\endgroup$ – SEJPM Oct 5 '20 at 15:37

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.

  • 2
    $\begingroup$ -1: You could try to solve the winning entries of the last White-box competition whibox.cyber-crypt.com (without help from the published solutions) before making such bold claims. Of course, there are crappy solutions out there that are easy to break, and of course, code lifting is always an option. The best one can hope for with an WhiteBox-implementation is to use a symmetric key algorithm as public key algorithm that can be only broken by code lifting. $\endgroup$ – j.p. Oct 3 '20 at 9:35
  • 2
    $\begingroup$ -1: the answer is very misleading (especially since the question is about theory); it is true that current practical implementations are relatively easy to break; it is true that "software obfuscation" techniques provide some weak temporary security layer. However, there is much more on the scientific cryptographic field: there are generic side-channel-style attacks and there are countermeasures against them which started to evolve recently; there are theoretical notions of cryptographic obfuscation which recently had some breakthrough constructions from LWE. $\endgroup$ – Fractalic Oct 4 '20 at 10:32
  • 1
    $\begingroup$ @Fractalic You use the term "generic side-channel-style attacks" like a program can prevent me from reading my own RAM. Debuggers like IDA or Radare2 can't be mitigated, no matter how hard you try to pretend they can be. $\endgroup$ – Serpent27 Oct 5 '20 at 2:09
  • $\begingroup$ @j.p. If the data can't be decrypted there's no use for this anyway - we already have public-key crypto, and I don't need a 49MB program to do it. As soon as you implement the ability to decrypt you allow me to hijack the decryption function and break the security - key or no key. Math gives no shits about the context in which some function is run. If I can create valid decryption inputs I can decrypt. That's why this is a reverse engineering question and not a cryptology question. $\endgroup$ – Serpent27 Oct 5 '20 at 2:10
  • $\begingroup$ @Serpent27 say the program simply multiplies a ton of matrices (matrices depend on the input); this is one of ideas in cryptographic obfuscation. How is IDA or Radare2 going to help you? $\endgroup$ – Fractalic Oct 5 '20 at 8:32

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!

  • 1
    $\begingroup$ WES is a good example to satisfy what is called "weak white-box/unbrekability", but not "strong white-box/onewayness". Weak WB typically comes with incompressibility so that the recovered "equivalent key" is at least worse in size. Here the equivalent key - SHA-256(K) - has the same size. Also note that weak WB of actual AES (i.e. without modifying the key) is much harder. $\endgroup$ – Fractalic Oct 6 '20 at 12:37
  • $\begingroup$ @Fractalic: It would be great if you added definition of Weak/Strong WB in your answer! Note: yes WES-256 is cutting corners, it theoretically looses 0.8272… bit of key! $\endgroup$ – fgrieu Oct 6 '20 at 13:38
  • $\begingroup$ Weak/strong WB are simply synonyms for unbreakability/onewayness, mentioned a few times in the answers linked by @hola, e.g. crypto.stackexchange.com/a/53361/9249 $\endgroup$ – Fractalic Oct 7 '20 at 14:19

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
  • $\begingroup$ Do you have any documents, like research papers, that I can can read more about? $\endgroup$ – hola Oct 5 '20 at 5:46
  • $\begingroup$ @hola added references! $\endgroup$ – Fractalic Oct 5 '20 at 9:13
  • 1
    $\begingroup$ This sounds similar to big-key cryptography, where the ciphers' program itself is not large, but the key is (for essentially the same reason). I'm aware of Bellare's work on this topic (I believe there is at least one other paper precededing that). $\endgroup$ – Mark Oct 9 '20 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.