The method for constructing uniform planar approximations of the filter generator

L. A. Kuschinskaya

Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 57-68.

Résumé

We study the possibility of constructing an approximation of filter generator to restore initial state $u^* \in V_n$ from its output sequence $z_i=f(A^i(u^*)) \in \{0,1\}$, $i=0,\ldots,N-1$, where $A:V_n\to V_n$ is non-degenerate linear mapping, $f$ is balanced Boolean function. The triple $(m, L_0, \mathbb T )$ is a key element in the construction of the approximation, where $m \in \mathbb{N}$, $L_0$ is coset of the space $V_n$, $\mathbb T = ( t_0, t_1, \ldots, t_m )$, $t_0 = 0$, $t_0 \leqslant t_1 \ldots t_m $. Let $(m, L_0, \mathbb T )$ be a triple and for $b_1, \ldots, b_m\in \{0, 1\}$ the probability that $f(v) {=} b_i$ is greater than $1/2$ for a random equiprobable choice of a vector $v$ from $L_i = A^{ t_i - t_{i-1}}(L_{i-1})$, $i = 1, \ldots, m$. Then a finite number of such triples with pairwise distinct sets $L_0$ makes it possible to restore the key with a complexity that is much less than the complexity of enumerating keys in some cases. In this paper, we study the possibility of constructing approximations of a special form, where all cosets $L_0$ have the same dimension, their union is equal to $V_n$, and the values of $m$ are the same for all described triples. Expressions for the optimal values of the parameters $k$ and $\delta$ are obtained for some enumeration method for constructing the approximations. It is shown that for $k = \left \lceil \log_2 \left ((Q-\sqrt{Q^2-\pi_0 2^{n+2}})/{2\pi_0} \right ) \right \rceil$ and $\delta \approx \lceil t_0 \sqrt \Omega \rceil$ it is possible to achieve the minimum length of the generator output sequence required to construct such approximations for a given value of the upper complexity $Q$ and lower reliability $\pi_0$ of the initial state recovery method, where $ \Omega = 2^k$, $t_0 \approx 1{.}19061 $.

Détail

Mots-clés : cryptanalysis
Keywords: key recovery, filter generator, planar approximation.

Bibliographie

[1] Bluetooth Specification, version 1.2, Bluetooth$^{\mathrm{TM}}$, 2003, 903–948 http://www.bluetooth.org

[2] Briceno M., Goldberg I., and Wagner D., A pedagogical implementation of A5/1, 1999 https://cryptome.org/jya/a51-pi.htm

[3] Ekdahl P. and Johansson T., “A new version of the stream cipher SNOW”, LNCS, 2595, 2003, 47–61 | MR

[4] Hell M., Johansson T., and Meier W., “Grain: stream cipher for constrained environments”, Int. J. Wireless Mobile Computing, 2:1 (2007), 86–93 | DOI

[5] Siegenthaler T., “Decrypting a class of stream cipher using ciphertext only”, IEEE Trans. Comput., C-34:1 (1985), 81–85 | DOI

[6] Meier W. and Staffelbach O., “Fast correlation attacks on certain stream cipher”, J. Cryptology, 1:3 (1989), 159–176 | DOI | MR

[7] Courtois N. and Meier W., “Algebraic attacks on stream ciphers with linear feedback”, LNCS, 2656, 2003, 345–359 | MR

[8] Courtois N., “Fast algebraic attacks on stream ciphers with linear feedback”, LNCS, 2729, 2003, 176–194 | MR

[9] Logachev O. A., Sal'nikov A. A., and Yashchenko V. V., “Correlation immunity and real secrecy”, Matematika i Bezopasnost' Informatsionnykh Tekhnologiy, MCCME Publ., M., 2004, 165–171 (in Russian)

[10] Alekseev E. K. and Kushchinskaya L. A., “Generalization of one method of a filter generator key recovery”, Discrete Math. Appl., 29:2 (2019), 69–87 | DOI | MR

[11] Glukhov M. M., Elizarov V. P., and Nechaev A. A., Algebra, v. 1, Gelios ARV Publ., M., 2003, 416 pp.

[12] Feller V., An Introduction to Probability Theory and its Applications, v. 1, Mir Publ., M., 1984 | MR

[13] Mills J. P., “Table of the ratio: area to bounding ordinate, for any portion of normal curve”, Biometrika, 18:3/4 (1986), 395–400

[14] Gasull A. and Utzet F., “Approximating Mills ratio”, J. Math. Anal. Appl., 420:2 (2014), 1832–1853 | DOI | MR

[15] GOST R 34.12–2015. Information Technology. Information Security. Block Ciphers, Standartinform Publ., M., 2015 (in Russian)