Announcement: Cryptanalysis of Frog (an AES Candidate)

[Bruce Schneier <schneier@counterpane.com>]

                                          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