FROG
Encyclopedia
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 byte
s, 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 by TecApro, a Costa Rican software company, 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 very slow key setup and relatively slow encryption. FROG was not selected as a finalist.
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 (which are combined with the plain text to produce the cipher text), 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.
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 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 megabyte
s per second when run on a 200 MHz Pentium PC.
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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, FROG is a block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
authored by
Georgoudis, Leroux and Chaves. The algorithm can work with any block size between 8 and 128 byte
Byte
The byte is a unit of digital information in computing and telecommunications that most commonly consists of eight bits. Historically, a byte was the number of bits used to encode a single character of text in a computer and for this reason it is the basic addressable element in many computer...
s, and supports key sizes between 5 and 125 bytes. The algorithm consists of 8 rounds and has a very complicated key schedule
Key schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...
.
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
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
. Wagner et al. (1999) found a number of weak key
Weak key
In cryptography, a weak key is a key, which, used with a specific cipher, makes the cipher behave in some undesirable way. Weak keys usually represent a very small fraction of the overall keyspace, which usually means that, if one generates a random key to encrypt a message, weak keys are very...
classes for FROG. Other problems included very slow key setup and relatively slow encryption. FROG was not selected as a finalist.
Design philosophy
Normally a block cipher applies a fixed sequence of primitive mathematical or logical operators (such as additions, XORs, etc) on the plaintextPlaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
and secret key in order to produce the ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
. 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 (which are combined with the plain text to produce the cipher text), 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 (or internal key) 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 (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 encryption and decryption. The implementation will run well on 8 bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
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 megabyte
Megabyte
The megabyte is a multiple of the unit byte for digital information storage or transmission with two different values depending on context: bytes generally for computer memory; and one million bytes generally for computer storage. The IEEE Standards Board has decided that "Mega will mean 1 000...
s 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.