Normally a block cipher applies a fixed sequence of primitive mathematical or logical operators on the plaintext and secret key in order to produce the ciphertext. An attacker uses this knowledge to search for weaknesses in the cipher which may allow the recovery of the plaintext. FROG's design philosophy is to hide the exact sequence of primitive operations even though the cipher itself is known. While other ciphers use the secret key only as data, FROG uses the key both as data and as instructions on how to combine these data. In effect an expanded version of the key is used by FROG as a program. FROG itself operates as an interpreter that applies this key-dependent program on the plain text to produce the cipher text. Decryption works by applying the same program in reverse on the cipher text.
Description
The FROG key schedule is 2304 bytes long. It is produced recursively by iteratively applying FROG to an empty plain text. The resulting block is processed to produce a well formatted internal key with 8 records. FROG has 8 rounds, the operations of each round codified by one record in the internal key. All operations are byte-wide and consist of XORs and substitutions. FROG is very easy to implement. Much of the code needed to implement FROG is used to generate the secret internal key; the internal cipher itself is a very short piece of code. It is possible to write an assembly routine of just 22 machine instructions that does full FROG encryption and decryption. The implementation will run well on 8 bit processors because it uses only byte-level instructions. No bit-specific operations are used. Once the internal key has been computed, the algorithm is fairly fast: a version implemented using 8086 assembler achieves processing speeds of over 2.2 megabytes per second when run on a 200 MHz Pentium PC.
Security
FROG's design philosophy is meant to defend against unforeseen/unknown types of attacks. Nevertheless, the very fact that the key is used as the encryption program means that some keys may correspond to weak encryption programs. David Wagner et al. found that 2−33 of the keys are weak and that in these cases the key can be broken with 258 chosen plaintexts. Another flaw of FROG is that the decryption function has a much slower diffusion than the encryption function. Here 2−29 of keys are weak and can be broken using 236 chosen ciphertexts.
