FROG
FROG is a block cipher, and its core idea breaks the usual rules of how a cipher works. Most ciphers keep their procedure fixed and treat the secret key purely as data. FROG does something stranger. It treats the key as a set of instructions, a small program that tells the cipher how to scramble a message. In 1998, a Costa Rican software company called TecApro submitted FROG to a worldwide contest to choose the Advanced Encryption Standard. The cipher carried the names of three authors: Georgoudis, Leroux, and Chaves. It could stretch to fit blocks of data anywhere from 8 to 128 bytes, and accept keys from 5 to 125 bytes. How does a key become a program? What happens when that program turns out to be a bad one? And why did a design built to resist the unknown fail against the very experts who came to test it?
Picture a normal block cipher as a recipe. It applies a fixed sequence of primitive operations, things like additions and XORs, to the plaintext and the secret key, and out comes the ciphertext. The danger is that everyone can read the recipe. An attacker studies that known sequence and hunts for a weakness that lets the original message be recovered. FROG tries to take that recipe away. Its design philosophy is to hide the exact sequence of primitive operations, even while the cipher itself remains public knowledge. The trick lies in how the key is used. In other ciphers the key is only data, combined with the plaintext to produce the ciphertext. In FROG the key is both data and instructions on how to combine that data. An expanded version of the key becomes, in effect, a program. FROG itself acts as an interpreter. It runs that key-dependent program on the plaintext to produce the ciphertext, and decryption simply runs the same program in reverse on the ciphertext. This was meant to defend against attacks no one had thought of yet, threats unforeseen and unknown at the time of design.
The internal key that FROG builds is 2304 bytes long, a much larger object than the key a user supplies. It is produced recursively, by iteratively applying FROG to an empty plaintext. The resulting block is then processed into a well formatted internal key holding 8 records. Those records map directly onto the cipher's structure. FROG has 8 rounds, and the operations of each round are codified by one record in the internal key. Every operation is byte-wide. The whole scheme consists only of XORs and substitutions, with no bit-specific operations anywhere. That byte-level discipline shapes how small the cipher can become in practice, which is where its design takes a surprising turn.
The reference C version of FROG runs to only about 150 lines of code, and most of that work goes into generating the secret internal key. The internal cipher itself is a very short piece of code. Stripped down, full FROG encryption and decryption can be written as an assembly routine of just 22 machine instructions. Because it uses only byte-level instructions and avoids bit-specific operations, the implementation runs well even on 8 bit processors. Speed follows once the setup is done. After the internal key has been computed, the algorithm is fairly fast. A version written in 8086 assembler reached processing speeds of over 2.2 megabytes per second on a 200 MHz Pentium PC. The catch was that getting to that point was costly, since the key setup itself was very slow.
David Wagner and his colleagues turned their attention to FROG in 1999, and they found the fault line running straight through its central idea. Because the key is used as the encryption program, some keys correspond to weak encryption programs. Wagner and his co-authors found that 2 to the power of minus 33 of the keys are weak. In those cases the key can be broken with 258 chosen plaintexts. The decryption side proved even more fragile. The decryption function has much slower diffusion than the encryption function. There, 2 to the power of minus 29 of keys are weak, and they can be broken using 236 chosen ciphertexts. The cipher that hoped to hide its procedure had handed attackers a class of keys that exposed it.
FROG entered the contest to become the Advanced Encryption Standard as one of many candidates, and the weak key classes Wagner's team uncovered were only part of its troubles. The cipher also suffered from very slow key setup and relatively slow encryption. Taken together, those problems decided its fate. FROG was not selected as a finalist. The idea that made it distinctive, a key that doubled as a program run by an interpreter, also created the keys that brought it down, leaving the cipher as a record of a bold approach that the competition declined to advance.
Common questions
What is the FROG block cipher?
FROG is a block cipher authored by Georgoudis, Leroux, and Chaves. It can work with any block size between 8 and 128 bytes, supports key sizes between 5 and 125 bytes, and consists of 8 rounds with a very complicated key schedule.
Who created the FROG cipher and when was it submitted?
FROG was authored by Georgoudis, Leroux, and Chaves. It was submitted in 1998 by TecApro, a Costa Rican software company, to the AES competition as a candidate to become the Advanced Encryption Standard.
What makes the FROG cipher's design philosophy unusual?
FROG hides the exact sequence of primitive operations even though the cipher itself is known. It uses the key both as data and as instructions on how to combine that data, so an expanded version of the key works as a program that FROG interprets to encrypt the plaintext.
How does the FROG key schedule work?
The FROG key schedule, or internal key, is 2304 bytes long. It is produced recursively by iteratively applying FROG to an empty plaintext, then processed into a well formatted internal key with 8 records, one for each of FROG's 8 rounds. All operations are byte-wide and consist of XORs and substitutions.
Why was the FROG cipher not selected as an AES finalist?
FROG was not selected as a finalist because Wagner and colleagues found a number of weak key classes in 1999, and the cipher also had very slow key setup and relatively slow encryption.
What weaknesses did David Wagner find in the FROG cipher?
David Wagner and colleagues found that 2 to the power of minus 33 of FROG's keys are weak and can be broken with 258 chosen plaintexts. They also found that the decryption function has much slower diffusion, with 2 to the power of minus 29 of keys weak and breakable using 236 chosen ciphertexts.
How fast and how small is the FROG cipher implementation?
The reference C version of FROG has only about 150 lines of code, and full encryption and decryption can be written in just 22 machine instructions. Once the internal key is computed it is fairly fast, with an 8086 assembler version reaching over 2.2 megabytes per second on a 200 MHz Pentium PC.