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. For other uses, see Frog (disambiguation).

FROG
General
Designers	Dianelos Georgoudis, Damian Leroux, and Billy Simón Chaves
First published	1998
Cipher detail
Key sizes	128, 192, or 256 bits
Block sizes	128 bits
Rounds	8
Best public cryptanalysis
Differential and linear attacks against some weak keys

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 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.

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. 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

High level view of FROG

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.^[1]

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 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⁻³³ 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⁻²⁹ of keys are weak and can be broken using 2³⁶ chosen ciphertexts.

Notes

↑ A detailed description of the cipher can be found here.

References

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

External links

256bit Ciphers - FROG Reference implementation and derived code

Block ciphers (security summary)

Common algorithms	AES Blowfish DES (Internal Mechanics, Triple DES) Serpent Twofish

Less common algorithms	Camellia CAST-128 IDEA RC2 RC5 SEED ARIA Skipjack TEA XTEA

Other algorithms	3-Way Akelarre Anubis BaseKing BassOmatic BATON BEAR and LION CAST-256 Chiasmus CIKS-1 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA CMEA Cobra COCONUT98 Crab Cryptomeria/C2 CRYPTON CS-Cipher DEAL DES-X DFC E2 FEAL FEA-M FROG G-DES GOST Grand Cru Hasty Pudding cipher Hierocrypt ICE IDEA NXT Intel Cascade Cipher Iraqi KASUMI KeeLoq KHAZAD Khufu and Khafre KN-Cipher Ladder-DES Libelle LOKI (97, 89/91) Lucifer M6 M8 MacGuffin Madryga MAGENTA MARS Mercy MESH MISTY1 MMB MULTI2 MultiSwap New Data Seal NewDES Nimbus NOEKEON NUSH PRESENT Q RC6 REDOC Red Pike S-1 SAFER SAVILLE SC2000 SHACAL SHARK Simon SMS4 Speck Spectr-H64 Square SXAL/MBAL Threefish Treyfer UES Xenon xmx XXTEA Zodiac

Design	Feistel network Key schedule Lai-Massey scheme Product cipher S-box P-box SPN Avalanche effect Block size Key size Key whitening (Whitening transformation)

Attack (cryptanalysis)	Brute-force (EFF DES cracker) MITM (Biclique attack, 3-subset MITM attack) Linear (Piling-up lemma) Differential (Impossible Truncated Higher-order) Differential-linear Distinguishing (Known-key) Integral/Square Boomerang Mod n Related-key Slide Rotational Timing XSL Interpolation Partitioning Davies' Rebound Weak key Tau Chi-square Time/memory/data tradeoff

Standardization	AES process CRYPTREC NESSIE

Utilization	Initialization vector Mode of operation Padding

Cryptography

History of cryptography Cryptanalysis Outline of cryptography

Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography

Portal

This article is issued from Wikipedia - version of the Sunday, August 30, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.