Frog

Encyclopedia : F : FR : FRO : Frog

This article is about the block cipher algorithm. For the ultrafast laser pulse measurement technique, see frequency-resolved optical gating. For the amphibian, see Frog.

In cryptography, FROG is a block cipher authored by Georgoudis, Leroux and Chaves. The algorithm can work with any block size between 8 and 128 bytes, and supports key sizes between 5 and 125 bytes. The algorithm consists of 8 rounds and has a very complicated key schedule.

It was submitted in 1998 to the AES competition as a candidate to become the Advanced Encryption Standard. Wagner et al (1999) found a number of weak key classes for FROG. Other problems included the very slow key setup and the relatively slow encryption. FROG was not selected as a finalist.

Contents

1 Design philosophy
2 Description
3 Security
4 References

Design philosophy

FROG follows an innovative design philosophy. Normally a block cipher applies a fixed sequence of primitive mathematical or logical operators (such as additions, XORs, etc) on the plaintext and secret key in order to produce the ciphertext. This sequence of primitive operations is known to the attacker (unless the cipher itself is secret, which is impossible in the context of an encryption standard meant to be used internationally). 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. When other ciphers use the secret key only as data (which are combined with the plaintext to produce the ciphertext) FROG uses the key both as data and as instructions on how to combine these data. In effect an expanded version of the key (called key schedule) is used by FROG as a program. FROG itself operates as an interpreter that applies this key-dependent program on the plaintext to produce the ciphertext. Decryption works by applying the same program in reverse on the ciphertext.

Description

The FROG key schedule (or internal key) is 2304 bytes long. It is produced recursively by iteratively applying FROG on an empty plaintext. The resulting block is processed to produce a well formatted internal key with 8 records. FROG has 8 iterations the operations of which are codified by one record in the internal key. All operations are byte-wide and consist of XORs and substitutions. A detailed description of the cipher can be found [here].

FROG is very easy to implement (the reference C version has only about 150 lines of code). 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 encryptions 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 Mbytes per second when run on a 200 MHz Pentium PC.

Security

FROG's innovative design philosophy is meant to defend against unforeseen/unknown types of attacks. Nevertheless, that very fact that the key is used as the encryption program means that some keys may correspond to a weak encryption program. David Wagner et al found that 2^-33 of the keys are weak and that in these cases the key can be broken with 2⁵⁸ 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 2³⁶ chosen ciphertexts.

References

David Wagner, Niels Ferguson and Bruce Schneier, Cryptanalysis of FROG, in proceedings of the 2nd AES candidate conference, pp175–181, NIST, 1999 [link].
Dianelos Georgoudis, Damian Leroux and Billy Simón Chaves, The FROG Encryption Algorithm, June 15, 1998 [link].

Block ciphers [edit]

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.