16 August 1998

    Date: Sun, 16 Aug 1998 08:53:37 -0500
    To: cypherpunks@toad.com
    From: Bruce Schneier <schneier@counterpane.com>
    Subject: Announcement: Cryptanalysis of Frog (an AES Candidate)

                        Results Announcement:

    D. Wagner, N. Ferguson, and B. Schneier, "Cryptanalysis of Frog,"
    Counterpane Systems Report, Aug 1998.

                             Abstract:
    We examine some attacks on the FROG cipher.  First we give a
    differential attack which uses about $2^{58}$ chosen plaintexts and
    very little time for the analysis; it works for about $2^{-33.0}$ of
    the keyspace.  Then we describe a linear attack which uses $2^{56}$
    known texts and works for $2^{-31.8}$ of the keyspace.  The linear
    attack can also be converted to a ciphertext-only attack using $2^{64}$
    known ciphertexts.  Also, the decryption function of FROG is a lot
    weaker than the encryption function.  We show a differential attack
    on the decryption function that requires $2^{36}$ chosen ciphertexts
    and works on $2^{-29.3}$ of the keyspace.  Using our best attack an
    attacker with a sufficient number of cryptanalytical targets can expect
    to recover his first key after $2^{56.7}$ work.  Taken together, these
    observations suggest that FROG is not a very strong candidate for the
    AES.

    This paper is available at http://www.counterpane.com/publish.html, and
    will be made available at the AES Workshop next week.

    Cheers,
    Bruce
    **********************************************************************
    Bruce Schneier, President, Counterpane Systems     Phone: 612-823-1098
    101 E Minnehaha Parkway, Minneapolis, MN  55419      Fax: 612-823-1590
               Free crypto newsletter.  See:  http://www.counterpane.com