Generic cryptographic weakness of k-normal Boolean functions in certain stream ciphers and cryptanalysis of grain-128

This paper considers security implications of k-normal Boolean functions when they are employed in certain stream ciphers. A generic algorithm is proposed for cryptanalysis of the considered class of stream ciphers based on a security weakness of k-normal Boolean functions. The proposed algorithm yields a framework for mounting cryptanalysis against particular stream ciphers within the considered class. Also, the proposed algorithm for cryptanalysis implies certain design guidelines for avoiding certain weak stream cipher constructions. A particular objective of this paper is security evaluation of stream cipher Grain-128 employing the developed generic algorithm. Contrary to the best known attacks against Grain-128 which provide complexity of a secret key recovery lower than exhaustive search only over a subset of secret keys which is just a fraction (up to 5%) of all possible secret keys, the cryptanalysis proposed in this paper provides significantly lower complexity than exhaustive search for any secret key. The proposed approach for cryptanalysis primarily depends on the order of normality of the employed Boolean function in Grain-128. Accordingly, in addition to the security evaluation insights of Grain-128, the results of this paper are also an evidence of the cryptographic significance of the normality criteria of Boolean functions.     

Construction of balanced Boolean functions with high nonlinearity,good local and global avalanche characteristics

Boolean functions possessing multiple cryptographic criteria play an important role in the design of symmetric cryptosystems. The following criteria for cryptographic Boolean functions are often considered: high nonlinearity, balancedness, strict avalanche criterion, and global avalanche characteristics. The trade-off among these criteria is a difficult problem and has attracted many researchers. In this paper, two construction methods are provided to obtain balanced Boolean functions with high nonlinearity. Besides, the constructed functions satisfy strict avalanche criterion and have good global avalanche characteristics property. The algebraic immunity of the constructed functions is also considered.     

Construction of balanced Boolean functions with high nonlinearity and good autocorrelation properties

Boolean functions with high nonlinearity and good autocorrelation properties play an important role in the design of block ciphers and stream ciphers. In this paper, we give a method to construct balanced Boolean functions of n variables, where n ≥ 10 is an even integer, satisfying strict avalanche criterion (SAC), and with high algebraic degree. Compared with the known balanced Boolean functions with SAC property, the constructed functions possess the highest nonlinearity and the best global avalanche characteristics property.     

The autocorrelation properties of single cycle polynomial T-functions

T-functions have been widely used in the design of symmetric ciphers, hash functions, and fast cryptographic primitives. Single cycle polynomial T-functions are a special category. If they are used as state transition functions of stream ciphers, the security of the generated sequences is crucial. In 2008, Kolokotronis proposed a conjecture regarding the autocorrelation function’s values of coordinate sequences generated by single cycle polynomial T-functions. In this paper, we show that the conjecture does not hold in general and prove the conditions under which it holds.     

A note on APN permutations in even dimension

APN permutations in even dimension are vectorial Boolean functions that play a special role in the design of block ciphers. We study their properties, providing some general results and some applications to the low-dimension cases. In particular, we prove that none of their components can be quadratic. For an APN vectorial Boolean function (in even dimension) with all cubic components we prove the existence of a component having a large number of balanced derivatives. Using these restrictions, we obtain the first theoretical proof of the non-existence of APN permutations in dimension 4. Moreover, we derive some constraints on APN permutations in dimension 6.     

Proof of a conjecture about rotation symmetric functions

Rotation symmetric Boolean functions have important applications in the design of cryptographic algorithms. We prove the conjecture about rotation symmetric Boolean functions (RSBFs) of degree 3 proposed in Cusick and St?nic? (2002) [2] and its generalization, thus the nonlinearity of such functions is determined.     

幂函数的一些密码学性质

二元域上n数组空间上的非线性置换在分组码，杂凑函数与流密码等密码学领域中有重要应用.域GF（2n）上的幂函数提供了二元域上n数组空间上的一类非线性置换．本文着重研究幂函数的强完全性、完全性与非线性度等密码学性质．作为结果，本文证明了幂函数具有完全性；证明了具有强完全性的函数必有较高的拓扑非线性度；木文找到一类具有强完全性的幂函数；周时也定出了幂函数的代数非线性度．     

Characterizing the Structures of Cryptographic Functions Satisfying the Propagation Criterion for Almost All Vectors

Many practical information authentication techniques are based on such cryptographic means as data encryption algorithms and one-way hash functions. A core component of such algorithms and functions are nonlinear functions. In this paper, we reveal a relationship between nonlinearity and propagation characteristic, two critical indicators of the cryptographic strength of a Boolean function. We also investigate the structures of functions that satisfy the propagation criterion with respect to all but six or less vectors. We show that these functions have close relationships with bent functions, and can be easily constructed from the latter.     

F_2~n上4次正形置换多项式的形式与计数

分组密码是现代密码学中一个重要的研究分支,而置换理论在分组密码中有重要的地位.1995年,美国Teledyne电子技术公司的Lothrop Mittenthal博士提出了一种置换,即正形置换.正形置换是一类完全映射,完全映射是由Mann在1942年研究正交拉丁方的构造时引入的,其具有良好的密码学性质(良好的扩散性和完全平衡性),因此,正形置换常用来构造密码系统的算法,研究正形置换也就非常有必要.本文根据文章[1]的方法讨论了F2n(n=4,5)上的4次正形置换多项式的形式与计数,至于n5的情形我们将在以后的篇章中继续讨论.     

Dirichlet product for boolean functions

Boolean functions play an important role in many symmetric cryptosystems and are crucial for their security. It is important to design boolean functions with reliable cryptographic properties such as balancedness and nonlinearity. Most of these properties are based on specific structures such as Möbius transform and Algebraic Normal Form. In this paper, we introduce the notion of Dirichlet product and use it to study the arithmetical properties of boolean functions. We show that, with the Dirichlet product, the set of boolean functions is an Abelian monoid with interesting algebraic structure. In addition, we apply the Dirichlet product to the sub-family of coincident functions and exhibit many properties satisfied by such functions.     

具有特定非零Walsh谱值个数的布尔函数的研究及构造

布尔函数与其变元的相关性与流密码的相关攻击有紧密联系，Walsh变换则是研究布尔函数相关特性的主要工具，本文研究了非零Walsh谱值个数k=9，10的布尔函数，证明了k=9的函数的不存在性，并构造了所有k=10的函数。     

Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity

Recent research shows that the class of rotation symmetric Boolean functions is potentially rich in functions of cryptographic significance. In this paper, based on the knowledge of compositions of an integer, we present two new kinds of construction of rotation symmetric Boolean functions having optimal algebraic immunity on either odd variables or even variables. Our new functions are of much better nonlinearity than all the existing theoretical constructions of rotation symmetric Boolean functions with optimal algebraic immunity. Further, the algebraic degree of our rotation symmetric Boolean functions are also high enough.     

Linearization of nonlinear filter generators and its application to cryptanalysis of stream ciphers

Nonlinear filter generators are commonly used as keystream generators in stream ciphers. A nonlinear filter generator utilizes a nonlinear filtering function to combine the outputs of a linear feedback shift register (LFSR) to improve the linear complexity of keystream sequences. However, the LFSR-based stream ciphers are still potentially vulnerable to algebraic attacks that recover the key from some keystream bits. Although the known algebraic attacks only require polynomial time complexity of computations, all have their own constraints. This paper uses the linearization of nonlinear filter generators to cryptanalyze LFSR-based stream ciphers. Such a method works for any nonlinear filter generators. Viewing a nonlinear filter generator as a Boolean network that evolves as an automaton through Boolean functions, we first give its linearization representation. Compared to the linearization representation in Limniotis et al. (2008), this representation requires lower spatial complexity of computations in most cases. Based on the representation, the key recoverability is analyzed via the observability of Boolean networks. An algorithm for key recovery is given as well. Compared to the exhaustive search to recover the key, using this linearization representation requires lower time complexity of computations, though it leads to exponential time complexity.     

A new result on irreducible NFSRs with respect to cascade connection

Nonlinear feedback shift registers (NFSRs) are widely used in stream cipher design as building blocks. The cascade connection of NFSRs, known as an important architecture, has been adopted in Grain family of stream ciphers. In this paper, a new sufficient condition under which an NFSR cannot be decomposed into the cascade connection of two smaller NFSRs is presented, which is easy to be verified from the algebraic normal form (ANF) of the characteristic function. In fact, our results are also applicable to nonsingular Boolean functions, which actually improve a previous research of Rhodes [6] where the characteristic functions of NFSRs cannot be contained.     

A systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of the Reed–Muller code

Because of the recent algebraic attacks, optimal algebraic immunity is now an absolutely necessary (but not sufficient) property for Boolean functions used in stream ciphers. In this paper, we firstly determine the concrete coefficients in the linear expression of the column vectors with respect to a given basis of the generator matrix of Reed–Muller code, which is an important tool for constructing Boolean functions with optimal algebraic immunity. Secondly, as applications of the determined coefficients, we provide simpler and direct proofs for two known constructions. Further, we construct new Boolean functions on odd variables with optimal algebraic immunity based on the generator matrix of Reed–Muller code. Most notably, the new constructed functions possess the highest nonlinearity among all the constructions based on the generator matrix of Reed–Muller code, although which is not as good as the nonlinearity of Carlet–Feng function. Besides, the ability of the new constructed functions to resist fast algebraic attacks is also checked for the variable \(n=11,13\) and 15.     

F2^n上4次正形置换多项式的形式与计数

分组峦码是现代密码学中一个重要的研究分支，而置换理论在分组密码中有重要的地位．199j年，美国Tcledyne电子技术公司的Lothrop Mittenthal博士提出了一种置换，即正形置换．止形置换是一类完全映射，完全映射是由Mann在1942年研究正交拉丁方的构造时引入的，其具有良好的密码学性质（良好的扩散性和完令平衡性），因此，正形置换常用来构造密码系统的算法，研究正形置换也就非常订必要．本文根据文章[1]的方法讨论了F2^n（n=4，5）上的4次正形置换多项式的形式与计数，至于n〉5的情形我们将在以后的篇章中继续讨论．     

布尔函数的相关免疫与相对平衡性

平衡性和相关免疫性是函数的两个重要密码特性 ,但目前对两者之间的关系还没有得到很好地研究 .本文拟对布尔函数的平衡性和相关免疫性之间的关系作一些探讨 ,引进相对平衡性的概念 ,讨论相对平衡与通常的平衡概念的关系 ,得到布尔函数的关于相关免疫性和平衡性的一个充要条件     

Impossible differential cryptanalysis using matrix method

The general strategy of impossible differential cryptanalysis is to first find impossible differentials and then exploit them for retrieving subkey material from the outer rounds of block ciphers. Thus, impossible differentials are one of the crucial factors to see how much the underlying block ciphers are resistant to impossible differential cryptanalysis. In this article, we introduce a widely applicable matrix method to find impossible differentials of block cipher structures whose round functions are bijective. Using this method, we find various impossible differentials of known block cipher structures: Nyberg’s generalized Feistel network, a generalized CAST256-like structure, a generalized MARS-like structure, a generalized RC6-like structure, Rijndael structures and generalized Skipjack-like structures. We expect that the matrix method developed in this article will be useful for evaluating the security of block ciphers against impossible differential cryptanalysis, especially when one tries to design a block cipher with a secure structure.     

Vectorial Resilient PC（l） of Order k Boolean Functions from AG-Codes

Propagation criteria and resiliency of vectorial Boolean functions are important for cryptographic purpose (see [1–4, 7, 8, 10, 11, 16]). Kurosawa, Stoh [8] and Carlet [1] gave a construction of Boolean functions satisfying PC(l) of order k from binary linear or nonlinear codes. In this paper, the algebraic-geometric codes over GF(2m) are used to modify the Carlet and Kurosawa-Satoh’s construction for giving vectorial resilient Boolean functions satisfying PC(l) of order k criterion. This new construction is compared with previously known results.     

Rotation symmetric Boolean functions—Count and cryptographic properties

Rotation symmetric (RotS) Boolean functions have been used as components of different cryptosystems. This class of Boolean functions are invariant under circular translation of indices. Using Burnside's lemma it can be seen that the number of n-variable rotation symmetric Boolean functions is 2^g_n, where g_n=(1/n)∑_t|nφ(t)2^n/t, and φ(.) is the Euler phi-function. In this paper, we find the number of short and long cycles of elements in having fixed weight, under the RotS action. As a consequence we obtain the number of homogeneous RotS functions having algebraic degree w. Our results make the search space of RotS functions much reduced and we successfully analyzed important cryptographic properties of such functions by executing computer programs. We study RotS bent functions up to 10 variables and observe (experimentally) that there is no homogeneous rotation symmetric bent function having degree >2. Further, we studied the RotS functions on 5,6,7 variables by computer search for correlation immunity and propagation characteristics and found some functions with very good cryptographic properties which were not known earlier.