Why Spritz has become so popular over the past few weeks

Hello dear cryptographers and mathematicians!

For me, not a professional mathematician or a cryptographer, it can be difficult to immediately understand how the encryption algorithm works. Here is an attempt to deal with individual functions of one algorithm. And also, understand why the Spritz algorithm is now more discussed by specialists than, for example, Keccak . There were several articles on Habré that described the Sponge function , or, in Russian, a sponge ( one , two) This function can be used in several ways: as a cryptor / decryptor, as a hash, as a hash with separate domains, generate a message authenticity code (MAC) or an insert code, work as a stream cipher and as a stream cipher with random access, for authentication with associated data (Authenticated Encryption with Associated Data), as a pseudo-random number generator and for generating symmetric keys from passwords.

To understand, I used the original article and presentation , as well as the source code from GitHub ( C , JS ).

Since I am not an expert, I will begin to understand with examples. In particular, with the function hash (M, r).

M is the input byte array.
r is the length of the output hash of the array in bytes.

As you can see from the example, the input array has a length of 3 bytes, and the output is 32 bytes. Thus, the length of the array is increased by 29 bytes.

Let's see how this happens.

Initially, variables and an array of permutations are initialized.

i = j = k = z = a = 0;
w is 1;

i, j are the positions of two elements.
k is the key
z is the last calculated value.
a - the number of nibbles (nibbles) used

All these values ​​are initially zero And the permutation array initially has ordered values ​​from 1 to N. In our example, N is 256.

w - the hop width is 1, but can vary depending on the greatest common factor with N.

Soak up

Next, the absorb (M) function is called - absorption, as we recall the array M in the example consists of 3 bytes. For definiteness, let it be bytes 'A', 'B', and 'C'. The sponge has a rather large size of 256 bytes, for our 3 bytes that need to be absorbed. For each byte, we call the absorbByte ('A') function, similarly for 'B' and 'C'.

We break each byte into two nibbles - the senior and the least, and for each of them we call the absorbNibble function ('the lower 4 bits'), the same for the high 4 bits of the byte.
How is the absorption of the current nibble? The absorbNibble function takes the first byte from the permutation array (it is equal to 1) and hinders it by a position equal to the middle of the array
permutations plus the value of the nibble itself. Since code A is 65. Then the lowest nibble is 1. Then the new position for the first element is 128 + 1 = 129.
And in the first position, we will have the number 129.

Next, we increase the counter of used nibbles by 1 (a = 2).

We do the same for the older nibble and for the remaining 2 bytes. In total, in our example, 6 permutations should be carried out, according to the number of nibbles used.

Shuffle

After that, run the shuffle () function - shuffle.

Here's what it looks like:

     /*
         Shuffle()
         1 Whip(2N)
         2 Crush()
         3 Whip(2N)
         4 Crush()
         5 Whip(2N)
         6 a=0
       */
       function shuffle() {
         whip(TWO_N);
         crush();
         whip(TWO_N);
         crush();
         whip(TWO_N);
         a = 0;
       }

First, the update () function is launched - updating 2N times. It is in this function that Spritz differs from RC4 ( presentation , analysis ).

Compare operations with RC4

RC4:

1: i = i + 1
2: j = j + S[i]
3: SWAP(S[i];S[j])
4: z = S[S[i] + S[j]]
5: Return z

Spritz:

1: i = i + w
2: j = k + S[j + S[i]]
2a: k = i + k + S[j]
3: SWAP(S[i];S[j])
4: z = S[j + S[i + S[z + k]]]
5: Return z

Spritz with my modification for a better understanding:

1: i = i + w
2: j = j + S[i]
2a: j = k + S[j]
2b: k = i + j
3: SWAP(S[i];S[j])
4a: i = i + S[k+z]   // z=S[j] c предыдущего шага
4b: j = j + S[i]
4c: z = S[j]
5: Return z

4 operation can be represented as follows: Ez = S [j + S [i + S [k + z]]] = kzpSipSjpS.

Shake and crush

There was a parameter w - which should be an odd number. In RC4, it is always equal to 1.
Another dependent parameter k has appeared - the key.
The name of the Whip (2N) function can be translated as shake, and Crush () how to crush.

The Whip function performs operations 1,2,2a, 3. Then it increases the parameter w by one as many times as the largest common factor for w and N. will be found.

I runs through all values ​​from 1 to 512. Suppose that k = 0. So it is set during initialization. Then, before the first iteration, j will be 0. And after the first iteration, j = S [S [1]], but S [1] = 129, and if the absorbed elements first and 129 were rearranged only once, then j = 1. Then k in step 2a will take the value k = 129.

The Crush () function changes values ​​that are symmetric with respect to the center of the array of permutations, if the value on the right side is greater than the value on the left side.

Squeeze

This is the final squeeze (r) operation. In our output array \ hash, we need to get r bytes. After calling drip () and update (), the final operation output () is performed:

  /*
  Output()
    1 z = S[j+S[i+S[z+k]]]
    2 return z
  */
  function output() {
    z = S[
      madd(j, S[
        madd(i, S[
          madd(z, k)
        ])
      ])
    ];
    return z;
  } 

As you can see, unlike RC4, this operation depends on the z value calculated in the previous step. It turns out a somewhat fractal algorithm.

Notice

This is a completely new cipher, it will be time before a real analysis appears. As a result of viewing the code, I turned to the following features.

  /*
    addition modulo N
  */
  function madd(a, b) {
    return (a + b) % N;
    // return (a + b) & 0xff;      // when N = 256, 0xff = N - 1
  }
  /*
    subtraction modulo N. assumes a and b are in N-value range
  */
  function msub(a, b) {
    return madd(N, a - b);
  }

All summation and subtraction are done on a circular buffer with size N (this is specified in the article). This is probably a feature of this particular implementation, but it seemed to me that in some simple summation or difference is enough. If I understand correctly, the size of the buffer can be different.

The code is sensitive to the initial value of w. During initialization, this parameter is set to 1. But what happens if it is set to N?

The permutation array S is initialized with values ​​from 1 to N, therefore S [i] = i, if the length of the input buffer is small, then this will be true in subsequent rounds.

With a special selection of the key and initialization vector (IV), it is possible that some operations will be greatly simplified. And they will have low algebraic complexity in general. For example, 2a may be equivalent to j = k + (i + j) << 1.

Total

A very interesting approach to encryption is developed at Spritz. In my opinion, existing implementations require significant refinement. Also, it will take time before this cipher becomes clearly reliable or not. It is already visible that it is slower than RC4. This cipher is publicly available and does not have any licensing restrictions.

Spritz is likely to become popular as it implements the following Sponge functions: AbsorbStop function, Encryption, Hash function, Domain separation hash function, Message Authentication Code (MAC), Authentication Encryption with Associated Data (AEAD), Deterministic Random Bit Generator (DRBG )

Perhaps these functions can be used for distributed databases, for transmitting audio and video over the Internet, etc.

Also, if respected specialists are pleased, I can write the following article, where I will show how to use AEAD to make a one-time digital key that works only for a certain time. This can be used, in particular, for the remote rental of a car, motel, yacht or apartment, or for managing IoT facilities in a hotel or guest house.

PS Thank you Ivan_83 for the link. Low algebraic complexity Keccak / Keyak facilitates cubic attacks.