[ISN] Cryptanalysis of Frog, an AES Candidate

From: schneier@counterpane.com (Bruce Schneier)

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. 

Bruce


-o-
Subscribe: mail majordomo@sekurity.org with "subscribe isn".
Today's ISN Sponsor: New Dimensions International [www.newdimensions.net]