Avalanche effect and bit independence criterion of perfectly secure Shannon cipher based on matrix power

Matas Levinskas1 , Aleksejus Mihalkovich2

1, 2Department of Applied Mathematics, Kaunas University of Technology, Kaunas, Lithuania

2Corresponding author

Mathematical Models in Engineering, Vol. 7, Issue 3, 2021, p. 50-53. https://doi.org/10.21595/mme.2021.22234
Received 4 August 2021; received in revised form 14 September 2021; accepted 28 September 2021; published 30 September 2021

Copyright © 2021 Matas Levinskas, et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Creative Commons License
Table of Contents Download PDF References
Cite this article
Views 13
Reads 7
Downloads 81
CrossRef Citations 0
Abstract.

In 2020 E. Sakalauskas with coauthors published a paper defining perfectly secure Shannon cipher based on matrix power function, proposing effective parallelization, and ensuring no need for multiple rounds encrypting one data block [1]. In this paper we present computational results with the avalanche effect and bit independence criterion (BIC). These criteria are important when describing the rate of confusion of bits in the ciphertext. It was observed that increasing matrix order and group size enhance BIC and avalanche effect results converging to the desired values. Based on the outputs it is possible to pick appropriate parameters satisfying security needs and available memory in a device where appropriate keys are going to be stored.

Keywords: symmetric cipher, perfect secrecy, block cipher, matrix power function, avalanche effect, bit independence criterion.

1. Introduction

1.1. Avalanche effect and BIC

Cryptography security analysis methods such as avalanche effect and BIC allow us to evaluate block cipher secrecy by computing elements confusion after changing just one bit [2], determine elements confusion and dependance from other elements [3, 4]. The values of these criteria are commonly calculated by considering the avalanche vector Aei, which describes ciphertext bits change after flipping one bit in the plaintext:

(1)
A e i = E n c k , μ E n c k , μ e i = a 1 e i a 2 e i a n e i ,

where vector has all entries equal to 0 except for the i-th one which is equal to 1, entry a1ei0,1 and function Enck,μ is encryption function mapping shared key k and plaintext μ to the ciphertext generally denoted by c.

Using expression defined in Eq. (1), we compute the i-th bit avalanche kAVALi effect as follows:

(2)
k A V A L i = 1 n 2 n j = 1 n W a j e i ,
W a j e i = X 0,1 n a j e i ,

where kAVALi indicates the number of bits changes after flipping i-th bit. The desired value of the avalanche effect is 0.5 for all the bits, meaning that it is infeasible to distinguish which bit changes occur after flipping a random bit of the original message.

The bit independence of the two entries is being calculated by the maximal absolute correlation coefficient between avalanche vector j and k components. According to [2], BIC can be calculated by the formula:

(3)
B I C ( a j , a k ) = m a x 1 i n | c o r r ( a j e i , a k e i ) | .

Furthermore, relying on Eq. (3) we can define the overall BIC for the whole ciphertext block Enck,m as the maximal correlation by checking all available pairs:

(4)
B I C ( E n c ) = m a x 1 k , k n k j B I C ( a j , a k ) .

Ideally, the value of BIC should be close to 0 hence ensuring that all the bit changes occur statistically independently.

1.2. Perfectly secure Shannon cipher based on matrix power function

The matrix power function (MPF) was introduced in [5], as the following mapping acting on the Cartesian product of the space of square matrices of order m with itself:

M a t m R × M a t m S × M a t m R M a t m S .

The general notation for this mapping is as follows:

(5)
    X W Y = E ,

where W,EMatm(S) are matrices with entries from semigroup S and X,YMatm(R) are matrices with entries from a finite ring of integers R. This mapping allows us to raise the base matrix W to the so-called power matrices X and Y.

E. Sakalauskas with co-authors used the MPF in 2020 to propose a perfectly secure Shannon cipher defined over Z3 [1]. This cipher uses a plaintext matrix M, private keys X and Y along with a function f:Z3G3, which maps elements of Z3 to elements of the multiplicative Sylow group G3={1,2,4}, which is a subgroup of Z7*. Note, that actions in G3 are performed modulo 7. A key feature of this mapping is that it does not carry over the addition in Z3 to the multiplication in G3 and hence is not an isomorphism. The encryption function can be expressed in a following way:

(6)
C = E n c X , Y , M = F - 1 F ( X )     X F ( X + M ) Y + X ,

where F:MatmZ3MatmG3 is an entry-wise matrix analogue of the mapping f and F-1 is its inverse. Note that since F is not an isomorphism no cancelations in Eq. (6) are possible. We also use to denote Hadamard product of two matrices.

It is worthy noting that the shared key X,Y consists of 2m2 entries and hence is at least twice the length of the original plaintext given that extra bits may be added at the end message to make it appropriate length. However, the plaintext and ciphertext are roughly the same size.

To decipher the ciphertext, we denote by TH the inverse of matrix T in Hadamard sense i.e., a matrix satisfying the following relation:

T H T = 1 ,

where every entry in the matrix is the unit of the group G3.

Upon receiving the ciphertext its decryption is performed in the reverse order and can be summarized by the following expression:

D e c X , Y , C = F - 1     Y - 1 [ ( F X ) H F C - X ] Y - 1   - X .

Perfect secrecy of the presented block cipher and the statistical independency of the ciphertext C from the plaintext M is proven in [1].

In this paper we investigate the avalanche effect and BIC for the presented block cipher in a more general form i.e., we expand the cardinalities of the algebraic structures considered. In other words, we consider the Sylow group Gq of the multiplicative group Zp* and an additive group Zq. Hence in Eq. (4) we have W,EMatm(Gq) and X,YMat(Zq). Actions in Gq are performed modulo a prime p=2q+1.

2. Computational results

The avalanche effect of perfectly secure Shannon cipher defined in Eq. (6) is calculated using Eq. (2). For each fixed pair of parameters p,q we investigate the relation between avalanche effect and the matrix order m. We executed 1000 experiments and the results averaged for each value of m given the fixed pair p,q. In Table 1 we present the results of our experiments.

Table 1. Avalanche effect with different parameters

p   =   7 , q=3
p   =   23 , q=11
p = 107 , q=53
p = 4079 , q=2039
p   =   33553799 , q=16776899
m = 5
0.4446
0.4615
0.4922
0.5007
0.5001
m = 8
0.4447
0.4638
0.4919
0.5002
0.5004
m = 10
0.4451
0.4626
0.4910
0.4997
0.4999
m = 15
0.4450
0.4627
0.4911
0.4996
0.4998
m = 16
0.4448
0.4625
0.4921
0.5002
0.4995
m = 32
0.4442
0.4628
0.4921
0.4999
0.5000

Analyzing the obtained results, we see that as the parameter q gets larger the avalanche effect increases to 0.5 whereas the matrix order does not have such big of an impact.

We perform the investigation of the BIC in a way similar to the one presented above. As above we performed experiments for each triplet p,q,m and using Eq. (4) obtained the BIC values presented in Table 2.

Table 2. BIC with the different parameters

p   =   7 , q=3
p   =   23 , q=11
p = 107 , q=53
p = 4079 , q=2039
p   =   33553799 , q=16776899
m = 5
1
0.7391
0.4717
0.2508
0.1731
m = 8
1
0.5746
0.4074
0.2035
0.1264
m = 10
1
0.5798
0.3738
0.1555
0.1099
m = 15
1
0.5678
0.3539
0.1214
0.0785
m = 16
1
0.5704
0.3436
0.1171
0.0667
m = 32
1
0.5530
0.3367
0.0782
0.0376

Note that increasing group size reduces BIC value. However, more importantly we see that small values of the parameter p are clearly not suitable for implementation since the value of BIC approaches the worst possible case. Furthermore, we can see that increasing matrix order has some impact as well and it is more noticeable compared to an analogous result of the analysis of the avalanche effect.

3. Conclusions

In this paper we investigated the previously proposed Shannon block cipher which does not require multiple rounds to encrypt a message. Furthermore, we expanded our research of the initial scheme by introducing a pair of parameters {p,q} which makes our cipher more flexible as compared to the original. The obtained results show that even though no information about the plaintext is revealed by the encryption algorithm itself, small values of parameters q cannot be used in practice since the BIC fails even for the largest value of matrix order we considered. However, the avalanche criterion is mostly satisfied and is quite near perfection even for small values of q. Hence, relying on the results presented in Table 1 and Table 2, a good recommendation to choose the system parameters {p,q,m} is to find a balance between q and m keeping them reasonably small while also ensuring that BIC is satisfied. Keeping this in mind a triplet {4079, 2039, 15} can be considered a suitable choice for practical implementation.

References

  1. E. Sakalauskas, L. Dindienė, A. Kilčiauskas, and K. Lukšys, “Perfectly secure Shannon cipher construction based on the matrix power function,” Symmetry, Vol. 12, No. 5, p. 860, May 2020, https://doi.org/10.3390/sym12050860 [Publisher]
  2. Işıl Vergili, “Avalanche and bit independence properties for the ensembles of randomly chosen n × n S-Boxes,” Turkish Journal of Electrical Engineering Computer Sciences, Vol. 9, No. 2, pp. 137–145, 2001. [Search CrossRef]
  3. M. Salman, R. Yugitama, A., and R. F. Sari, “KAMIES: Security optimization of KASUMI algorithm by increasing diffusion level,” International Journal of Security and Its Applications, Vol. 12, No. 3, pp. 29–46, May 2018, https://doi.org/10.14257/ijsia.2018.12.3.04 [Publisher]
  4. L. Liu, “Designing a random S-box with the mixed spatiotemporal chaos,” in Conference series, Vol. 1983, No. 1, 2021, https://doi.org/10.1088/1742-6596/1983/1/012040 [Publisher]
  5. Sakalauskas Eligijus and Lukšys Kęstutis, “The matrix power function and its application to block cipher S-box construction,” International Journal of Innovative Computing, Information and Control, Vol. 8, No. 4, pp. 2655–2663, 2012. [Publisher]