Re: Running White-Box AES backwards

From: John A. Malley (
Date: 08/04/04

Date: Tue, 03 Aug 2004 18:01:38 -0700

David Wagner wrote:
> John A. Malley wrote:
>>IIRC, Stanley Chow thought the table mapping block cipher inputs to
>>outputs for any secret key is the existential proof for White Box
>>obfuscation to make a public key cipher out of a private key PRP.
> Are you sure that's what he thought?

Yes, I found the post.

He said,

> Let me pose this question:
> Given K, we construct a table of plaintext to cyphertext, literally
> the ECB of AES(K,x). If we assume AES is secure, then the attacker
> can gain no information about K from this table. Clearly this table
> is huge, but it is only still O(1), and this table can be trivially
> implemented as a circuit (also huge but still O(1)).
> Is this a secure obfuscation of K?
> Note that it is difficult to extract K (any attack using this table
> turns into a Chosen-plaintext attack on AES), so presumably this
> counts as an obfuscation of the key; and serves as an existance
proof. > Also note that the attacker could construct the decryption
table with > 2^128 work; so one could say this obfuscation (of the key
in the
> encryption direction) is no stronger than 2^128 work factor.

I saw this as a claim that such a table is a valid and secure white-box
obfuscated public version of an originally private key PRP, and that it
is as secure as a measure on the order of the Adv^prp for the
private-key block cipher (chosen ciphertext attack on the PRP). I also
took it to mean that inverting the table is just as much work as brute
forcing the key (the 2^128 work factor) but he didn't explicitly say that.

Am I off base here?

John A. Malley