Announcement: Cryptanalysis of Frog (an AES Candidate)

Bruce Schneier (schneier@counterpane.com)
Sun, 16 Aug 1998 08:53:28 -0500

• Next message: Bruce Schneier: "Microsoft Electronic Commerce patent: Prior Art?"
• Previous message: Bill Stewart: "Re: Request for information on cryptanalysis"

                                          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

• Next message: Bruce Schneier: "Microsoft Electronic Commerce patent: Prior Art?"
• Previous message: Bill Stewart: "Re: Request for information on cryptanalysis"