Re: White-Box Cryptography

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

  • Next message: Andrew Swallow: "Re: Erasing an OTP file on a SD card."
    Date: 27 Jul 2004 08:53:13 -0700
    
    

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

    > 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.

    Several points:
     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
        real cleverness.

     
    >>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
    lookups).

    Stanley Chow


  • Next message: Andrew Swallow: "Re: Erasing an OTP file on a SD card."

    Relevant Pages

    • Re: New RSA attack
      ... It's another example of a long line of papers that shows that ... In practice, with today's commodity operating systems, if an attacker can ... Have you seen Microsoft's 10 Immutable Laws of Security? ... recommend to clients that if you have sensitive information, ...
      (sci.crypt)
    • Re: New RSA attack
      ... James S. Singleton wrote: ... It's another example of a long line of papers that shows that ... In practice, with today's commodity operating systems, if an attacker can ... but their first rule seems relevant here: ...
      (sci.crypt)