Re: White-Box Cryptography

From: Stanley Chow (stanley.chow_at_pobox.com)
Date: 07/28/04


Date: 27 Jul 2004 22:22:34 -0700

daw@taverner.cs.berkeley.edu (David Wagner) wrote in message news:<ce632k$u83$1@agate.berkeley.edu>...

> Stanley Chow wrote:
>>The definition of Barak et al. is nice for a
>>number of reasons, but the bar is way too high.
>>
>> "Executable E obfuscates K in the White-Box sense" -
>> attacker is given executable E, which has K (a key in this case)
>> embedded inside; the attacker must not be able to extract K
>> (or otherwise use K in anyway not performed by E)
>
> Ok, this is helping me start to understand what you had in mind; thanks
> for taking the time to write this out in more detail.

You are welcome, glad to have someone thinking about this.

> I agree it is a great goal to look for notions of obfuscation that are
> weaker than that proposed by Barak et al. But I'm still not sure I see
> how the White-box definition is any weaker than the Barak definition.
> I think I probably need more explanation before I will understand.
>
> There are two things an attacker might be able to do with E:
> 1) The attacker might be able to learn something about K after
> running E many times without peeking at, or disrupting, the
> execution of E in any way. This is unavoidable. This is what
> Barak formalize as what you can compute given an oracle for E.

This is the normal/usual Black-box apsect. It turns out to be relatively
easy to secure programs against Black-Box attacks. This is, of course,
why people use debuggers and other white-box attack tools, and why people
use DPA, etc. to do gray-box (side-channel) attacks.

> 2) The attacker might be able to learn something else about K by
> using the code of E somehow (other than what is available in
> case 1) above). Presumably this category includes everything
> you had in mind as "using K in any way not performed by E".
> But if the attacker can learn anything not already covered
> by case 1), Barak call it an insecure obfuscation.

I assume you mean the attacker is using White-Box attacks to extract
K-related stuff. In this case, I agree with your conclusion.

But if the attacker learns something un-related to K, I may still
decide that "E obfuscates K". Indeed, even if the attackers learns
K, someone may decide that "E obfuscates K for 3 years" is good
enough for the particular application.

> So I'm having trouble understanding the White-Box definition of
> obfuscation. It looks like every scheme that is a secure White-Box
> obfuscation will also be a secure Barak obfuscation. Can you give me
> any intuition how a scheme might fail to be secure in the Barak sense
> but might nonetheless be secure in the White-Box sense?

A brief answer is:
  Barak et al. requires the Obfuscator to protect any program P inspite
  of P actively leaking information.
  My definition is about programs that want to be protected and will
  jump through hoops to become a little bit more secure.

Some differences that make Barak et al. a tougher standard (from memory
so the details may be wrong):
 - Barak requires an Obfuscator that uniformly protects *any* program
   *automatically* whereas my definition allows people to inject
   intelligence after studying the program, and reject some programs
   as being too hard to protect.
 - Barak requires the protection be total - not a single bit of
   information leaks whereas my definition of "secure" only cares
   about "useful" changes (and our AES, DES papers only care about
   obfuscating K-related things; so lots of other details may leak).
   As mentioned previously, usefullness is not an intrinsic
   property of the program or of the change but is dependent on the
   system design and the usage context, so it is difficult to
   formalize the concept of "useful".
 - Barak defines secure to be a binary value - secure against
   Polynomial time attacks with large resources. I am more interested
   in measuring strength down in (very) low-order polynomials.

There are also some difference that make Barak et al. easier - mainly
that they allow polynomial expansion on execution-time and memory. In
practice, only a small multiple is tolerable (where "small" is clearly
application dependent)

Stanley Chow