Stream Ciphers: Edon80

Seguridad de la Información y Criptografía
Homework 7 - Report 3

Edon80 is a stream cypher algorithm designed by Danilo Gligoroski, Smile Markovski, Ljupco Kocarev, and Marjan Gusev. [1]

Has some strengths: [2]

1. If the needs for security bits have to be increased to arbitrary value, the speed of the cipher would not be affected at all (except initialization phases).
2. If the size of IV change, it would not affect the speed of the cipher.
3. It is easily paralelizable.
4. For achieving high speeds, it is appropriate only for a hardware realization to utilize its more then 80 pipeline and parallel operations.

Edon80 is a hardware binary additive synchronous stream cipher. It belongs to a family of stream ciphers that in hardware can have a constant speed of one bit per clock cycle, but in software implementation on popular modern CPUs can be made as slow as needed.

Since its first description in 2005, it has been analyzed by several cryptographers, have been implemented in a more compact way and a MAC functionality have been added. [3]

How it works?

Edon80 is a binary stream cipher. The keystream in Edon80 is generated as a row of a certain in fnite matrix whose elements are defi ned iteratively using quasigroup operations.

The stream cipher Edon80 uses four fixed quasigroups of order 4. The four quasigroups are the next:

But, why use only that quasigroups or are the unique. In fact, we can generate a different quasigroup if we want, but a quasigroup has a special way to be created, and there are some that are not good for generate a random stream in our case.

In Edon80 we use a quasigroup with a dimension of 4x4, so every row and col need to have a 0, 1, 2 and 3, filled in a table like when we play sudoku. We only need four quasigroups, so the crucial part of this method, was select that quasigroups of a set of 576 options. There are 192 quasigroups and are called fractal quasigroups, since they produce highly regular strings.

Some of the rest 384 after every application of an e-transformation increase the period of the transformed string with smaller coefficient, and other by higher coefficient, and those was discarded. We give a list of 64 quasigroups that increase the period of the transformed string at least 2 times, after every application of an e-transformation by them. For select the four quasigroups of the set of the 64 remaining, each one of them was tested and was found the best four options.

Now we have the general model of the stream cipher Edon80. A key and a Input Vector are required for generate a output stream.

For its proper work Edon80 has the following additional inputs:

1. One register key of 80 bits to store the actual secret key.
2. One register IV of 80 bits to store padded initialization vector.
3. One internal 2-bit counter as a feeder of Edon80 Core in keystream mode.
4. One 7 bit SetupCounter that is used in IVSetup mode.
5. One 4 × 4 = 16 bytes ROM bank where 4 quasigroups of order 4 are stored.

In the first row of that table we placed a periodic string that has shape: 01230123[...]0123. The next 80 rows in the table describe 80 e-transformations of that string by using the obtained values of $a_i$ in input vector mode and by the quasigroups $∗i$. The recurrence equations for this transformations are:

The output of the stream cipher is every second value of the last e-transformation so the keystream can be described as:

Using the source code of the official web page of Edon80, I executed a simple example, but I reduced the length of the keystreams:

Generated Key = 04000000000000000000
Generated IV = 0000000000000000
Keystreams generated (3x20 bytes)
s[1]=4E3E5646183CDB17561B8536812775D95D713E69
s[2]=8C67697FD96A249D5E794242413EBEA6B552CC08
s[3]=C61DABCB6AA8E0E50FC5B6392B8549C2F7CBF07B

Encryption of 20 bytes
Plaintext = F4604512C52C03158686A84DF32139B143755F04
Ciphertext = 4E3E5646183CDB17561B8536812775D95D713E69

Decryption of 20 bytes
Ciphertext = 4E3E5646183CDB17561B8536812775D95D713E69
Plaintext = F4604512C52C03158686A84DF32139B143755F04

Attacks and vulnerabilities

Is difficult to attack this kind of stream cipher. Experts found that the complexity of the attack is around 2^69 simple operations for a keystream of similar length. So if we want to attack we have a possibility to found the keystream, but with a brutal force algorithm it will take a very long time.

Another attack and a vulnerability is founded like in others types of encryption and is about the base of explore some periodicy inside the generator.

Using the fact that some elements will repeat with large probability, we can build a kind of test to find out the correct value of the key bits used at the end of the concatenation. We can use it to find a part of the keystream, and is why this kind of stream cipher has a vulnerability.

References:
[1] - Edon80 - Wikipedia
[2] - The eSTREAM Project
[3] - Edon80 Properties
A Key Recovery Attack Of Edon80