Re: White-Box Cryptography
From: Stanley Chow (stanley.chow_at_pobox.com)
Date: 27 Jul 2004 08:53:13 -0700
firstname.lastname@example.org (David Wagner) wrote in message news:<email@example.com>...
> Stanley Chow wrote:
>>Ok, I assumed a qualifier, so let me be explicit:
>> Implementations of symmetric cyphers, if secure in the White-Box
>> sense, are effectively PK (in the White-box sense, which implies
>> the Black-box sense).
> I don't see it. Perhaps you can show us your preferred definition of
> White-Box security, and then maybe we'll be able to see whether the
> above claim follows? I must admit I have never been able to find any
> definition that was precise enough for me. (The definition of Barak et
> al. might be a nice model to follow.)
I would also love to see a formal definition, especially one that
balances nice theoretical properties with measures that are useful
for practitioners. The definition of Barak et al. is nice for a
number of reasons, but the bar is way too high. Many people are
willing (in fact, desperate) to settle for any extra strength.
For this discussion, let me use these definitions:
"White-Box Attack Context" - the attacker has total control over
the machine, is able to use advanced debugging hardware,
emulators. The attacker also has sufficiently large resources
of computing power, disk space, etc. It is always assumed
the attacker has access to all patents, papers, etc. including
any code/generator used to generate instances. The attacker
only lacks the key and the random numbers consumed.
"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) even with
all the attack tools. We can informally refer to the strength
of the obfuscation by the amount of work it takes to extract K
(or use K is some unintended way).
"Executable E is secure in the White-box sense" -
in this usage, the attacker wins if he modifies E to do *anything*
different that is somehow "useful". This is what many people
want and is a much stronger requirement than "E obfuscates K" in
that every aspect of E must also be secure. We can also refer to
the strength the same way. Our AES and DES papers only allure to
this, but that is the ultimate goal. I won't go into this but
mention it only for completeness.
As I said, I would love to see someone formalize these operational
definitions; but cryptography (the "normal" black-box flavour) has
thrived with similar definitions. One particular difficulty is the
concept of "useful" (or "otherwise use K" for only obfuscating K)
seems to be hard to capture formally.
>>This pretty much follows immediately from the definition of White-Box
>>in that having the WAES-encrypt code and WK-encrypt key *does not*
>>let you have K (the real key), which means you cannot decrypt.
> I don't believe it. The public-key property does not follow from
> the simple requirement that WAES and WK do not reveal K. That simple
> requirement is not enough. With the published constructions, if you give
> me WAES and WK, I can run the thing backwards and do an AES decryption
> without ever learning the key K. You claim that not learning the key K
> implies not being able to decrypt, but that is incorrect; it is possible
> to decrypt without ever learning the key K.
1) my definition of "E obfuscates K in the white-box sense" includes
preventing any use of K in any unauthorized way. So running the
code backward to decrypt is, by definition, a breach in the
security. This is analagos to the usual requirements on cyphers
and signature schemes. The definitions in our papers did not
explicitly address this (but the discussions of attacks clearly
had this in mind).
2) We intended White-Box to be a new "context" of attacks and
implementions. Our two implementions were just initial attempts
in this field. Whether our initial attempts turn out to be
insecure, a (possibly hypothetical) secure White-Box
implementation is effectively PK.
3) The implementations in our two papers cannot be run backwards
(at least not in any simple way). There are many places where
tables are many-to-one, so it is not possible to run backwards.
It may be possible to keep track of all possible back-paths
but the number of back-paths grows exponentially so it requires
>>Alternatively, a secure implementation means that having WK-encrypt
>>does not let you derive WK-decrypt [...]
> Well, that's a different definition.
It is a deficiency in our published definition. The intent has
always been that any indirect use of K qualifies as a break.
> The published schemes might be
> secure in the previous sense that they don't reveal K, but they are not
> secure in this second sense. It is totally trivial to run them backwards.
> In the published construction, WAES is a circuit consisting only of
> 32-bit to 32-bit invertible functions and bit re-ordering operations.
> Both elements are trivially invertible, so running the circuit backwards
> is straightforward.
Hmm, our paper must have been unclear. The actual code does many 8-bit
to 4-bit lookups (the type IV xor tables as well as the optimized vector
add tables). This is true for both the DES and the AES papers. (I would
have to check, but I think both do many more 8-to-4 lookups than 8-to-8