Frog

Frog
Frog
Creator	D. Georgoudis, D. Leroux and B. Shave
Created by	1998
Key size	128/192/256 bits
Block size	128 bits
Number of rounds	eight
Type of	Own

This is an article about the encryption algorithm. On the method of measuring the envelope and phase of ultrashort laser pulses, see the article Frequency-resolved optical gating .

FROG is a symmetric block encryption algorithm with an unorthodox structure, one of the participants of the American AES competition, the development of the Costa Rican company TecApro Internacional.

Content

Creation History

The FROG algorithm was created in 1998 by three specialists from the Tecnologia Apropriada company (TesArgo) from the small Latin American state of Costa Rica (previously unknown with its cryptographic works), Dianelos Georgoudis, Damian Jlepy (Damian Leroux), who wen’ted Simon Chaves)

The announced version of the cipher complies with the AES requirements, having a block equal to 128 bits and a key 128, 192 or 256 bits long. The algorithm itself, in theory, allows keys from 40 to 1000 bits in length.

AES Competition

The FROG cipher was put up for the competition by the international company TecApro Internacional, registered in Costa Rica. The developers of the algorithm are D. Georgoudis, D. Leroux and B. Chaves - people, to put it mildly, little known in the cryptographic world. According to the authors, FROG is “a new cipher with an unorthodox structure”. The basis of the cipher strength is the secret internal key of a complex structure, and the encryption / decryption operations themselves are extremely simple.

In August, the TWOFISH team (Wagner, Ferguson and Schneier) showed that the FROG cipher key can be opened with about 2 ⁵⁷ labor costs.

As for the strength of ciphers, this indicator is much more difficult to verify. During the preliminary assessment stage of the first round, a significant number of cryptanalytic results were presented on the NIST website and directly at the AES2 conference, one way or another “staining” the reputation of almost all candidate ciphers. However, if we don’t speak about the obvious outsiders LOKI , FROG, MAGENTA and HPC , then no obvious weaknesses in the algorithms were found.

Key features and structure of the algorithm

The AES competition established for the algorithms participating in the competition the obligation to support 128-bit block size of encrypted data, as well as 128-, 192- and 256-bit encryption keys. However, the developers of the FROG algorithm proposed a wider set of values for these parameters:

it is acceptable to use keys from 5 to 125 bytes in size (that is, from 40 to 1000 bits);
the block size can vary from 8 to 128 bytes, that is, from 64 to 1024 bits (however, in the author's description of the algorithm, in accordance with the requirements of AES, there is a 16-byte block size).

Regardless of the size of the key and block, encryption is performed in 8 rounds. In each round, the following actions are performed on each byte of the block being encrypted (assuming that the blocks are 16 bytes in size):

The value of the current (Nth) byte is added modulo 2 with the value of the same byte of the 1st part of the round key (the key expansion procedure is described below).
The second part of the key round is a permutation table. From this table, a byte is selected, the sequence number of which is equal to the value calculated in the first step. The value of the selected byte replaces the value of the current byte of the data block to be encrypted.
The value of the next byte (N + 1 is shifted modulo 2 with the value selected in step 2. The result replaces the old value of N + 1 byte of the encrypted data block.
The third part of the key round is an index table. The value of the Nth byte of the index table defines another modified byte of the encrypted data block, which changes completely the same as the N + 1 th byte (that is, it is added modulo 2 to the value obtained in step 2).

Key Expansion Procedure

This procedure should receive 8 round keys from the encryption key - one for each round of the algorithm. The round key consists of three subkeys:

16-byte 1st part;
256-byte permutation table;
16-byte index table.

Thus, for the algorithm to work, it is necessary to generate 2304 bytes of key information.

By “replicating” the encryption key (that is, the encryption key value is repeated as many times as necessary, and the encryption key of this algorithm, as mentioned above, is 5 to 125 bytes in size), the first 2304-byte temporary data array is generated. The bytes of the last of the “duplicated” copies of the key that go beyond the required 2304-byte array (for example, the last 71 bytes of the 125-byte key — the key of the maximum size) are discarded.
By a similar “reproduction” of a 251-byte master key fragment, a second 2304-byte temporary data array is formed. The master key is a specially selected constant of 251 bytes in size. The byte value of the master key (starting from the low byte) is given in the table.

Table
By applying the modulo 2 addition operation to the corresponding bits of the two arrays produced in steps 1 and 2, a temporary extended key is obtained.
Formatting the key obtained in step 3 (that is, dividing it into 8 segments — by the number of rounds — 16 + 256 + 16 bytes in size, as well as additional processing, which will be described later), gives a preliminary extended algorithm key.
The advanced advanced key is used to encrypt a 2304-byte array filled with zeros. Encryption is performed in the cipher block concatenation mode, where the initial 16 bytes of the original encryption key are used as the initialization vector (IV), the very first of which is also folded modulo 2 with a number equal to the size of the encryption key in bytes (this is necessary to obtain various IVs). for keys of different sizes, but with the same first 16 bytes). The result of the operation is an extended key filled with pseudo-random information.
Similar to step 4, the extended key is formatted to produce eight round keys with the required structure.

Key Formatting

Steps 4 and 6 of the key expansion algorithm are formatting a 2304-byte pseudo-random sequence in order to obtain 8 round keys. If the 1st part of a round key used for modulo 2 addition can have a completely random structure, then the correct permutation table should consist of 256 non-repeating values from 0 to 255, and to the 16-byte index table, in addition, there are additional requirements .

Thus, the following actions are performed during formatting:

Splitting a 2304-byte array into 8 fragments of 16 + 256 + 16 bytes.
The first 16 bytes of the fragment become the first part of the round key, unchanged.
The following 256 bytes (we denote this fragment A) are processed by a special procedure in order to obtain the correct permutation table. This procedure looks like this:

creates a 256-byte array t /, containing successive values from 0 to 255;
in the cycle from 0 to 255 / -th byte of the permutation table T is determined by the formula:

T[i]=U[(index[i-1]+A[i])modL]

${\ displaystyle T [i] = U [(index [i-1] + A [i]) modL]}$

index [il] is the element number of the array t / used in the previous step (for the zero step is taken equal to 0), a L is the current size of the array U \
the used byte of the U array is discarded, and the elements of the U array located after it are shifted by 1 byte to the beginning of the array; thus, the value of L in each pass of this cycle is reduced by 1;

if the permutation table is created for the decryption operation, then it is inverted.

Similarly to step 3, a 16-byte index table is created.
An analysis of the reference chains of the index table is performed; if the table consists of several chains, the table is modified to obtain a single link chain, the length of which will be equal to the size of the table.
The table is analyzed again in order to find indexes that satisfy the following condition:

$I[i]=i+1$ ${\ displaystyle I [i] = i + 1}$

if such table elements exist, their value changes to

$I[i]=i+2$ ${\ displaystyle I [i] = i + 2}$

Steps 3-5 of the formatting procedure are worth a look at an example. Suppose a 6-byte index table is created from the following 6-byte fragment of a pseudo-random sequence:

21,247,199,108,66,239

In the cycle from 0 to 5 (step 4) / -th byte of the table of indices I is determined by the formula:

$I[i]=U[(index[i-1]+A[i])modL]$ {\ displaystyle I [i] = U [(index [i-1] + A [i]) modL]}

that the example of the above sequence looks as shown in the table:

The result is a table of indices:

3,2,5,1,0,4

3,0,5,1,2,4

Analysis of the table (step 5) allows you to find out that this table consists of two chains of links:

3 → 1 → 2 → 5 → 4 → 2 → 0 → 3

3 → 1 → 0 → 3 and 5 → 4 → 2 → 5

However, to achieve maximum algorithm robustness, the index table must contain one chain of maximum size. The algorithm performed in step 5 allows you to combine several chains into one.

Advantages and disadvantages of the algorithm

Like many other algorithms, such as AES (Rijndael) or SAFER +, FROG is byte-oriented. However, unlike the explanations explained and explained by the authors of Rijndael and SAFER + transformations used in these algorithms, the authors of the FROG algorithm limited themselves to explaining that such an unusual round structure was chosen in order to ensure the fastest possible dispersion of the input data (i.e. ciphertext bit within a block).

However, FROG was recognized as one of the weakest participants in the AES competition; it was found many flaws, in particular:

a rather large part of the set of possible algorithm keys turned out to be weak (due to a very complicated key expansion procedure) to various types of attacks;
the algorithm was slow, even compared to algorithms known before the AES competition, for example, Blowfish and RC5;
the FROG algorithm turned out to be very demanding of RAM - it needs about 2500 bytes if the round keys are formed in advance, and for the operation of a full-featured algorithm, including the key expansion procedure, about 5000 bytes are needed; these requirements are very high (especially in comparison with other algorithms - participants of the AES competition) for the implementation of this algorithm in smart cards;
There are a number of weak keys for this algorithm. The key installation procedure is relatively slow due to the complicated mechanism for generating transformation tables. The cipher itself has a relatively low performance, although after installing the key, 8 rounds of conversion are performed fairly quickly - implemented on the 8086 FROG assembler runs at a speed of 2.2 MB / s on a PC with a Pentium 200 processor;
cryptanalysts also drew attention to the vulnerability of the decryption function and its rather slow diffusion ;
other AES participants showed that the Frog cipher key is opened using 2 ⁵⁷ operations.

Thus, the FROG algorithm did not reach the AES final.

Literature

Course "Information Security", Department of Radio Engineering, Moscow Institute of Physics and Technology (MIPT), essay "Review of AES Candidates", Lipatiev, 2004
http://crypto.pp.ua/2010/12/algoritm-frog/