Re: AES and groups

From: Mark Wooding (mdw_at_nsict.org)
Date: 09/04/03

  • Next message: Henrick Hellström: "Re: Complexity/permutation based hash" 
    Date: 4 Sep 2003 15:35:18 GMT

    Mailman <mailman@anonymous.org> wrote:

    > If I recall my Algebra correctly, the conditions enumerated above are for a
    > ring, not for a group.

    You're wrong. A group is a set closed under an associative binary
    operator with identity and inverses. A ring is a set closed under two
    associative binary operators, named addition and multiplication, both
    with distinct identities, additive inverses, with multiplication
    distributive over addition; a field is a commutative ring with
    multiplicative inverses for all elements except the additive identity.

    > Associativity is not a necessary result of closure - try it with a
    > group made of (square) matrices for a counter-example, which may also
    > fail the inverse-element requirement.

    Nonsingular square matrices form a group under multiplication. (Indeed,
    square matrices form a ring. The nonsingular matrices form the
    multiplicative subgroup.)

    > As Mike correctly remarks, closure (1) is the rub: if AES is indeed a
    > group then super-encryption (encrypting cyphertext with a second key)
    > would be useless, as closure would imply that for any two given keys
    > there is another key that is their exact equivalent.

    As has been mentioned (see, e.g., <slrnbidbjt.f12.mdw@tux.nsict.org>),
    the main problem is meet-in-the-middle attacks against a single key.

    > As far as I know neither the property nor its inverse have ever been
    > proven even for DES, let alone AES.

    DES isn't a group, and the group generated by DES contains at least
    10^{2499} elements. See

    <http://www3.sympatico.ca/wienerfamily/Michael/MichaelPapers/desgroup.pdf>

    I am unaware of any similar result for AES.

    -- [mdw]

  • Next message: Henrick Hellström: "Re: Complexity/permutation based hash"

    Relevant Pages