Re: Running White-Box AES backwards

From: John A. Malley (102667.2235_at_compuserve.com)
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
102667.2235@compuserve.com 

--

Relevant Pages

  • Re: White-Box Cryptography
    ... > weaker than that proposed by Barak et al. ... > There are two things an attacker might be able to do with E: ... Barak call it an insecure obfuscation. ... It looks like every scheme that is a secure White-Box ...
    (sci.crypt)
  • Re: White-Box Cryptography
    ... > weaker than that proposed by Barak et al. ... > There are two things an attacker might be able to do with E: ... Barak call it an insecure obfuscation. ... It looks like every scheme that is a secure White-Box ...
    (sci.crypt)
  • Re: White-Box Cryptography
    ... > weaker than that proposed by Barak et al. ... > There are two things an attacker might be able to do with E: ... Barak call it an insecure obfuscation. ... It looks like every scheme that is a secure White-Box ...
    (sci.crypt)
  • Re: White-Box Cryptography
    ... > attacker is given executable E, which has K ... I agree it is a great goal to look for notions of obfuscation that are ... weaker than that proposed by Barak et al. ... It looks like every scheme that is a secure White-Box ...
    (sci.crypt)
  • Re: why we have to do first Encryption and then Authentication in PKCS
    ... At least with CTR which requires that any encryption uses a nonce ... not previously used under this key, I would assume the attacker is not ... the attacker can never perform use the block cipher as ...
    (sci.crypt)