key: cord-0058874-61iym3li
authors: Martin-Navarro, Jose Luis; Fúster-Sabater, Amparo
title: Folding-BSD Algorithm for Binary Sequence Decomposition
date: 2020-08-24
journal: Computational Science and Its Applications - ICCSA 2020
DOI: 10.1007/978-3-030-58799-4_26
sha: 2a4a12d2fe43dd4e4e1f1bb73d3bbb6bfd5fc2bb
doc_id: 58874
cord_uid: 61iym3li

The IoT revolution leads to a range of critical services which rely on IoT devices. Nevertheless, they often lack proper security, becoming the gateway to attack the whole system. IoT security protocols often rely on stream ciphers, where PRNGs are an essential part of them. In this article, a family of ciphers with strong characteristics that make them difficult to be analyzed by standard methods is described. In addition, we will discuss an innovative technique of sequence decomposition and present a novel algorithm to evaluate the strength of binary sequences, key part of the IoT security stack.

This is the reason why general research [5] , 5G related research [6] or specific calls such as that of NIST for lightweight cryptography primitives [7] , are addressing this concerning topic. Although different protocols of communication and orchestration are being proposed [8] , lightweight cryptography in general and stream ciphers in particular are the stepping stones on which such protocols are built to guarantee both device and network security.

In this work, first we will introduce Linear Feedback Shift Registers (LFSR), key components in stream ciphers, often used as Pseudo Random Number Generators (PRNG). Next, we will present the generalized shelf shrinking generator, a particular family of ciphers with strong cryptographic characteristics which remain strong to the standard Berlekamp-Massey Algorithm [9] . Then, we will analyze an innovative sequence decomposition introduced by Cardell et al. in [10] and will show how it can be used to analyze the properties of binary sequences. Finally, we will propose a novel algorithm based on the symmetry of the Binomial Sequences (BS) and discuss the comparison among algorithms.

The study of the generalized shelf shrinking generator is not a random choice. Indeed, it produces not only sequences that are hard to analyzed by the Berlekamp-Massey algorithm, but also it has been implemented in hardware [11] along on RFID devices [12] . Studying the robustness of these sequences could prevent vulnerabilities on the IoT devices and the services built on them.

Linear Feedback Shift Registers (LFSRs) [13] are linear structures currently used in the generation of pseudorandom sequences. The LFSRs are electronic devices included in most of the sequence generators proposed in the literature. Main reasons for a so generalized use are: LFSRs provide high performance when used for sequence generation, they are particularly well-suited to hardware implementations and such registers can be readily analysed by means of algebraic techniques. According to Fig. 1 , a LFSR consists of L interconnected stages numbered (0, 1, . . . , L − 1) (from left to right) able to store one bit, the feedback or connection polynomial

with binary coefficients c i and the initial state (stage contents at the initial instant). In addition, a clock controls the data shift. LFSRs generate sequences by means of shifts and linear feedbacks.

The output of an LFSR with nonzero initial state is a binary sequence notated {a n } (n = 0, 1, 2, . . . ). If the polynomial p(x) is primitive [13] , then the output sequence is called PN-sequence (pseudo-noise sequence). Moreover, a PNsequence has period T = 2 L − 1 bits with 2 L−1 ones and 2 L−1 − 1 zeros. On the other hand, linear complexity (LC) of a sequence is a parameter closely related to the LFSR. In fact, LC is defined as the length of the shortest LFSR able to generate such a sequence.

Although an LFSR in itself is an excellent generator of pseudorandom sequence, nevertheless it has undesirable linearity properties which reduce the security of its use. In practice, the introduction of any type of nonlinearity in the process of generation of the pseudorandom sequence is needed. The irregular decimation of PN-sequences is one of the most popular techniques to destroy the inherent linearity of the LFSRs [14, 15] .

Inside the type of irregularly decimated generators, we can enumerate: a) the shrinking generator introduced in [16] that includes two LFSRs, b) the selfshrinking generator [17] that involves just one LFSR and c) the generalized self-shrinking generator proposed in [18] that is considered as a generalization of the self-shrinking generator as well as a simplification of the shrinking generator. In this work, we focus on the last type of generator that is the generalized selfshrinking generator.

The generalized self-shrinking generator can be described as follows:

1. It makes use of two PN-sequences: {a n } a PN-sequence produced by an LFSR with L stages and a shifted version of such a sequence denoted by {v n }. In fact, {v n } = {a n+p } corresponds to the own sequence {a n } but rotated cyclically p positions to the left with (p = 0, 1, . . . , 2 L − 2). 2. It relates both sequences by means of a simple decimation rule to generate the output sequence. For n ≥ 0, we define the decimation rule as follows:

If a n = 1 then v n is output, If a n = 0 then v n is discarded and there is no output bit.

Thus, for each value of p an output sequence {s n } p = {s 0 s 1 s 2 . . .} p is generated. Such a sequence is called the p generalized self-shrunken sequence (GSSsequence) or simply generalized sequence associated with the shift p. Recall that Since the PN-sequence has 2 L−1 ones, the period of any generalized sequence will be 2 L−1 of divisors, that is a power of 2. Next a simple example is introduced.

For an LFSR with primitive polynomial p(x) = x 4 +x+1 and initial state (1 1 1 1), we generate the generalized sequences depicted in Table 1 . The bits in bold in the different sequences {v n } are the digits of the corresponding GSS-sequences associated to their corresponding shifts p. The PN-sequence {a n } with period T = 2 4 − 1 is written at the bottom of the table.

There are two particular facts that differentiate the GSS-sequences from the PN-sequences generated by LFSRs:

-The period of the GSS-sequences is a power of 2, in contrast to PN-sequences whose period is 2 L − 1. This difference arises from the fact that PN-sequences cannot have a run of zeros of the length of its internal state. -The LC of PN-sequences equals L while that of the GSS-sequences is 2 L−1 .

This property is desirable because such sequences exhibit a great LC with low resources. As a result, the Berlekamp-Massey algorithm would need to process 2 L bits with a computational complexity of O(2 2 * L ).

In this section, we introduce a new representation of the binary sequences whose period is a power of 2 in terms of the binomial sequences. Next, the close relationship among binomial sequences and the Sierpinski's triangle is also analyzed.

The binomial number n i is the coefficient of the power x i in the polynomial expansion of (1 + x) n . For every non-negative integer n, it is a well-known fact that n 0 = 1 as well as n i = 0 for i > n. 

The binomial coefficients reduced modulo 2 allow us to define the concept of binomial sequence.

Given an integer i ≥ 0, the sequence {b n } i (n = 0, 1, 2, . . .) whose elements are binomial coefficients reduced modulo 2, that is b n = n i mod 2, is called the i-th binomial sequence. Table 2 shows the eight first binomial sequences { n i }, i = 0, 1, . . . , 7, see [19] , with their corresponding periods and linear complexities, denoted by T i and LC i , respectively.

Next, different properties of the binomial sequences are introduced. b) The first period of such a binomial sequence has the following structure:

2. The linear complexity of the sequence n

3. Every binary sequence whose period is a power of 2 can be written as a linear combination of a finite number of binomial sequences [10, Theorem 1] . Such a combination is called the Binomial Sequence Decomposition. 4. Given a sequence with binomial representation t k=0 n i k , where i 0 < i 1 < · · · < i t are integer indexes, then its linear complexity is given by LC = i t +1, see [19] . 5. Given a sequence with binomial representation t k=0 n i k , where i 0 < i 1 < · · · < i t are integer indexes, then its period T is that of the binomial sequence n it , see [19] .

Notice that the generalized sequences are binary sequences whose period is a power of 2. Consequently, they can be written in terms of binomial sequences satisfying all the previous properties.

When the binomial coefficients are arranged into rows for the successive values of n = 0, 1, 2, . . ., then the generated structure is the Pascal's triangle (see Fig. 2a ). If we color the odd numbers and shade the even ones in such a triangle, then we get the Sierpinski's triangle whose version reduced mod 2 is depicted in Fig. 2b .

Recall that the successive diagonals of the Sierpinski's triangle in Fig. 2a correspond to the successive binomial sequences n i , (i = 0, 1, 2, . . .) starting at the first 1. That is, the binomial sequences can be found inside the Sierpinski's triangle mod 2, and also are related to certain cellular automata [10] .

NOTATION: For the sake of simplicity, in this section the binomial coefficient n k will denote the corresponding k−th binomial sequence. Then, the term n k i,j stands for the binary sub-sequence of n k between the bits i and j − 1 while n k j is just for the case i = 0. The general method of computing the linear complexity of any sequence is the Berlekamp-Massey algorithm [9] . In order to work, this algorithm needs to process 2 * n bits of the sequence with a computational complexity of O(n 2 ) [20] .

This section first introduces in detail the basic Binomial Sequence Decomposition algorithm (b-BSD) as well as an improvement on the algorithm implementation.

Second, a new approach to the Binomial Sequence Decomposition is developed, giving rise to the folding Binomial Sequence Decomposition algorithm (f-BSD). Such an algorithm improves the throughput of previous methods thanks to the symmetry of the binomial sequences.

Finally, a comparison among Berlekamp-Massey, b-BSD and f-BSD algorithms is presented. Such a comparison allows us to discuss the improvement of the f-BSD algorithm presented in this article.

Based on the mathematical results provided in the previous section, a basic Binomial Sequence Decomposition algorithm (b-BSD) can be designed in order to calculate the LC of a given sequence. In particular, two facts are used:

-A sequence of length n can be decomposed in t + 1 binomial sequences (third item in 3.1):

-The lineal complexity of a sequence can be calculated from the maximum binomial sequence of its BSD (second item in Sect. 3.1). Since the binomial sequences are in order, then LC satisfies the following expression:

The resulting algorithm can be seen in Algorithm 1. It takes the sequence to be analyzed as input and checks for every bit equal to 1. When bit i == 1, it sums the sequence with the corresponding binomial sequence (seq+ n i ) stopping when all the binomial sequences have been found. A step-by-step example of the algorithm decomposing a sequence of length 16 can be seen in Table 3 . Thus, the b-BSD algorithm is able to calculate the LC, as the Berlekamp-Massey algorithm does, but with only n bits of the sequence instead of 2 * n. The complexity of b-BSD algorithm, which performs the sum of two sequences of n bits (n additions) for every binomial sequence, is O(t * n), t being the number of binomial sequences in which the main sequence is decomposed with t n. Moreover, the logic of the algorithm can be improved by avoiding the sum of the sub-sequence that are zero. On the one hand, thanks to the characteristic 1.b) of Sect. 3.1, we know that n k = 0 ∀n < k. On the other hand, at each step of the b-BSD algorithm the sequence begins with zeros. That is, at step i the k i first terms of the sequence are zeros.

If these two facts are combined, then the number of algorithm operations can be reduced. When the algorithm detects the first 1 in the i − th position of seq, instead of performing the sum of two sequences of n bits (seq n + n i ), it just sums both sequences between the i − th and (n − 1) − th bits (seq i,n + n i i,n ), as the head of both sequences ([0, i − 1]) is made up of zeros.

Compared with t * n, the number of operations is reduced as follows:

In addition, we do not need to perform the sum of any bit after the max binomial. The reason is that, for every binary sequence produced by the generalized self-shrinking generator, the maximum binomial sequence can be calculated as k max = n − log n. The final number of operations will be:

To upgrade the code in Algorithm 1 only the sum of both sequences is changed, which will be now seq = seq i,max + n i i,max , with max = n − log n. Summing it up, for a sequence with a characteristic polynomial of degree σ, with length n = 2 σ−1 , the b-BSD algorithm will require n − log n bits of the sequence to calculate the LC with a complexity of O(t * n).

Despite the improvement in both complexity and length requirements between b-BSD and Berlekamp-Massey, there is still room for enhancing the decomposition mechanism.

In the next sub-section a new algorithm design is explained, improving the results of the b-BSD algorithm by taking advantage of the symmetry of the binomial sequences.

In order to fully understand the f-BSD algorithm, a particular matrix representation of the decomposition, based on the symmetric properties of binomial sequences, is presented. Symmetry of n k : There are two properties regarding the symmetric structure of binomial sequences and their relation to the powers of 2 that are explained in the next sub-section.

In all the binomial sequences ( n k with k < n 2 and n being the length of the sequence), it is possible to observe the following structure:

In Table 4 , where n 2 = 8, this phenomenon is observable on binomial sequences n 2 , n 3 , n 5 and n 6 , where the eight first bits repeat themselves. In fact, this is a simplification of a stronger result, defined in Theorem 1.

For every binomial sequence n k there exists an integer l ∈ N such that 2 l is the period of the binomial sequence as well as satisfies the inequality

The result follows directly from item 1 in 3.1. On the other hand, recall that the binomial sequences n k with n 2 ≤ k ≤ n start with k zeros, so they can be divided in the following way: n k = zeros + seq = zeros 0, n 2 , n k n From the item 1.b in Subsect. 3.1 there is an interesting characteristic of the sub-sequence n k n 2 ,n , which can be converted in another binomial sequence with the following expression: n k n 2 ,n = n k− n 2 n 2 . Taking into consideration the period of the sequence, the Theorem 2 arises: Theorem 2. Every binomial sequence n k n , k ≤ n with period 2 l , 2 l−1 < k ≤ 2 l , can be divided into two binomial sequences of length n 2 as follows:

In particular, as the sequences analyzed have a length of n a power of 2 bits, they can be divided into two sequences of length n 2 . Again, it can be observed in Table 4 on the binomial sequences n 8 , n 9 and n 10 . Putting together the facts regarding the symmetry of the binomial sequences, they can be classified in two groups depending on their division. It is explained in Algorithm 2. (1).

Three important characteristics about the matrix representation shown in (1) form the core of the folding BSD algorithm.

-As the length of the sequences is n = 2 σ−1 , the matrix representation can be extended in a recursive way, taking M 3 and repeating the same process until it cannot be divided more (length = 1).

The following expression (3) is an example of the matrix representation of the sequence decomposition of Table 4 .

0011 0011 0011 0011 0001 0001 0001 0001 0000 0101 0000 0101 0000 0011 0000 0011 0000 0000 1111 1111 0000 0000 0101 0101 0000 0000 0011 0011

(3) In order to calculate the LC of the given sequence, only the highest binomial sequence of its decomposition is needed. Thus, the f-BSD algorithm will benefit from the symmetry of the binomial sequences by reducing recursively the length of the sequence to analyze, as depicted in the matrix expression (2).

The previous subsection described all the elements needed by the f-BSD algorithm. In fact, the algorithm locates the maximum binomial sequence to calculate LC. At every step, it sums the first half of the sequence with the second half. If the result is different from zero, then it continues with the second half of the sequence. Otherwise, it continues with the first half, finishing when only one bit is left.

At every step, the folding mechanism reduces the length of the studied sequence by 2. It performs a sum of half the length of the sequence too, with a total of log n steps. Given a sequence seq with length n, the number of operations of the algorithm can be calculated as follows:

The final pseudo-code of the algorithm, for a given binary sequence of length n (although we can reduce it to n−log n as explained in Sect. 4.1) and complexity O(n), can be found in Algorithm 3. The way this algorithm searches for the maximum binomial sequence is similar to that of the binary search algorithm. The difference results in that the binary search only performs one comparison in each step, while our algorithms needs to sum length(n) As aux = 0 0,1 , then seq = aux = 1 1 and k = 8 + 2.

-Step 4:

As aux = 0, then seq = aux = 0.

-End: the maximum binomial sequence is n 10 → LC = k + 1 = 10 + 1 = 11.

When putting together the three algorithms that can calculate the complexity of a sequence (Berlekamp-Massey, b-BSD and f-BSD), it is interesting to compare the computational complexity and length requirements of each of them as shown in Table 5 .

Although the Berlekamp-Massey algorithm is able to calculate the linear complexity of any sequence, it is not the best choice for particular sequences as the GSS-sequences O(n 2 ). It is in that situation where the Binomial Sequence Decomposition can be really useful, in particular the folding algorithm presented in this part of the work. A particular difference between b-BSD and f-BSD is that the later performance does not depend on the number of binomial sequences in the decomposition. That means that in general its performance will be better, but it could depend on the particular sequence under study.

Although it is not the purpose of this work, it is worth saying that the f-BSD algorithm can be parallelized in the calculus of the LC of a given sequence, while b-BSD performs the calculus in a sequential way.

In this work, the folding-BSD algorithm has been introduced. It exhibits much better performance on sequences particularly hard to be decomposed by the Berlekamp-Massey algorithm. This is a big step in the study of binary sequences with period a power of two, and makes it easier to find vulnerabilities in this kind of sequences. Detecting such vulnerabilities in a cipher implemented in practical applications could compromise the corresponding IoT devices and the services behind them.

Moreover, the binomial decomposition of sequences as a way to extract information from a given sequence is an innovative but powerful tool, and it is left for future work its application to other kind of binary sequences. Also, there is still room for improvement on how the fractal structure of the binomial sequences can be profited to decompose a binary sequence without handling the whole sequence.

About the f-BSD algorithm presented in this article, it shows a better theoretical characteristics in both complexity and length of the sequence required. Future works may study the algorithm performance in real world scenarios by applying it to different binary sequences, taking advantage of the parallel capabilities of the algorithm.

Energy big data security threats in IOT-based smart grid communications

New attack vectors for building automation and IOT

Internet of things as an attack vector to critical infrastructures of cities

Security and privacy vulnerabilities of in-car wireless networks: a tire pressure monitoring system case study

Security protocols for IoT

Internet of Things (IoT) in 5G Mobile Technologies. MOST

Solutions for internet of things security challenges: trust and authentication

Shift-register synthesis and BCH decoding

Binomial representation of cryptographic binary sequences and its relation to cellular automata

Method and apparatus for generating keystream

Apparatus and method for protecting RFID data

Shift Register Sequences

The modified self-shrinking generator?

Cryptography with Shrinking Generators. SM

The shrinking generator

The self-shrinking generator

Generalized self-shrinking generator

Generation of cryptographic sequences by means of difference equations

Cryptographic Boolean Functions and Applications