Universidade de AveiroDepartamento deElectronica, Telecomunicacoes e Informatica,

2018

Nicolasdos Santos Neto

Cifra Contınua baseada no filtro de BloomBSC - Bloom based Stream Cipher

“A winner is just a loser who tried one more time.”

— George Augustus Moore

Universidade de AveiroDepartamento deElectronica, Telecomunicacoes e Informatica,

2018

Nicolasdos Santos Neto

Cifra Contınua baseada no filtro de BloomBSC - Bloom based Stream Cipher

Universidade de AveiroDepartamento deElectronica, Telecomunicacoes e Informatica,

2018

Nicolasdos Santos Neto

Cifra Contınua baseada no filtro de BloomBSC - Bloom based Stream Cipher

Dissertacao apresentada a Universidade de Aveiro para cumprimento dosrequesitos necessarios a obtencao do grau de Mestre em Engenharia deComputadores e Telematica, realizada sob a orientacao cientıfica do DoutorAndre Zuquete, e co-orientacao cientıfica do Doutor Tomas Silva, Profes-sores do Departamento de Eletronica, Telecomunicacoes e Informatica daUniversidade de Aveiro

o juri / the jury

presidente / president Joao Paulo Silva BarracaProfessor auxiliar da Universidade de Aveiro

vogais / examiners committee Andre Ventura da Cruz Marnoto ZuqueteProfessor auxiliar da Universidade de Aveiro (orientador)

Ricardo Jorge Fernandes ChavesProfessor associado do Instituto Superior Tecnico

agradecimentos /acknowledgements

O final desta etapa e, obviamente, um marco na vida de qualquer estudanteque so e possıvel alcancar com apoio das pessoas que nos ajudam a crescerao longo da vida.

Quero por isso agradecer aos meus pais por esta possibilidade, de estudar, epor sempre me apoiaram nas minhas decisoes. Quero ainda agradecer-lhespor todos os ensinamentos que me transmitiram. Ao meu irmao, agradecoa motivacao e acompanhamento que me foi dando ao longo deste trajeto.

Aos meus orientadores, quero tambem deixar o meu obrigado pela ajuda,amizade e paciencia, no que se refere a obtencao do grau de mestre econclusao deste trabalho.

A todos os restantes familiares e amigos, agradeco a compreensao pelaminha ausencia em alguns eventos, mas foi, de facto, por uma causa nobre.

Resumo Um Linear Feedback Shift Register (LFSR) e um elemento base usado fre-quentemente para desenvolver cifras contınuas, baseadas em hardware, deforma rapida. Contudo, pelo facto de serem orientados ao bit tornam-se ine-ficientes quando implementadas em microprocessadores. Por outro lado, osLFSRs tem um comportamento bem conhecido, definido pelo seu polinomiode realimentacao, o que facilita a analise das suas propriedades com recursoa ferramentas matematicas mas tambem a sua cripto anaalise.

Este trabalho consistiu na criacao de um LFSR generalizado cujos registospossuem palavras de 64 bits em vez de um unico. Utiliza-se tambem umpolinomio de realimentacao variavel, com vista a dificultar a sua criptanalise.A variabilidade do gerador e definida por um filtro de Bloom.

Um filtro de Bloom e um metodo bem conhecido para detetar possıveisrepeticoes de um valor e e utilizado neste gerador com vista a torna-lo difıcilde analisar devido ao seu estado em constante modificacao. O estado dofiltro e cıclico, visto que em algumas iteracoes acumula uns (1’s) enquantoque nas seguintes acumula zeros (0’s). O numero de iteracoes em cadacaso varia com o numero de colisoes detetados pelo proprio filtro.

Abstract A Linear Feedback Shift Register (LFSR) is a building block that is fre-quently used to build fast, hardware-based stream ciphers. However, thefact that an LFSR is bit-oriented makes it inefficient when implemented bymicroprocessors. On the other hand, LFSR’s have a very well-defined inter-nal behavior, defined by a carefully chosen (primitive) feedback polynomial,which facilitates the evaluation of their quality using mathematical toolsbut also their cryptanalysis.

This work consisted on creating a generalized LFSR where the informationstored in each stage of the shift register is a 64-bit word, instead of asingle bit. Furthermore, a variable feedback polynomial is used instead of afixed one, for making cryptanalysis harder. The variability of the feedbackpolynomial is given by the state of a Bloom filter.

A Bloom filter is a well defined construction used to detect a possible repe-tition of a value observed in the past, and was used in our stream generatorto provide a hard-to-model, always changing state. The evolution of theBloom filter state is cyclic, in the sense that during some iterations it accu-mulates ones (1’s), while in other iterations it accumulates zeros (0’s). Thenumber of iterations in each case is not fixed, it is given by an accumulatednumber of collisions in the Bloom filter itself.

Contents

Contents i

List of Figures iii

List of Tables v

Acronyms vii

1 Introduction 1

1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Related Work 3

2.1 Some bits of History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Stream Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.3 Pseudo-Random Number Generators . . . . . . . . . . . . . . . . . . . . . . . 5

2.4 LFSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.4.1 Xorshift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.5 Bloom Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.6 Attacks to stream generators . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.6.1 Side channel attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.6.2 Correlation attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.6.3 Distinguishing attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.6.4 Exhaustive Key Search and Time Memory Trade-off . . . . . . . . . . 11

3 Bloom-based Stream Cipher 13

3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2.1 Auxiliary registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.2.2 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.2.3 Bloom filter update function . . . . . . . . . . . . . . . . . . . . . . . 17

3.2.4 Substitution Box . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4 Analysis 21

4.1 Theoretical security analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.2 Statistical evaluation of the generator . . . . . . . . . . . . . . . . . . . . . . 22

i

4.2.1 Selection of N (consecutive collisions) . . . . . . . . . . . . . . . . . . 224.2.2 Evaluation of alternatives for the

⊙function . . . . . . . . . . . . . . 23

4.2.3 Impact of the toggling frequency of the Bloom filter reference bit . . . 254.2.4 Substitution Box (S-Box) analysis . . . . . . . . . . . . . . . . . . . . 264.2.5 Bloom filter statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.2.6 Output correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.2.7 Resistance to side-channel attacks . . . . . . . . . . . . . . . . . . . . 304.2.8 Pseudo random statistical properties . . . . . . . . . . . . . . . . . . . 304.2.9 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5 Conclusion 335.1 Work overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335.2 Further work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Bibliography 35

A Appendix 37A.1 Substitution Box . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

A.1.1 S Box source code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37A.1.2 Resultant Substitution Box . . . . . . . . . . . . . . . . . . . . . . . . 44

A.2 Correlation source code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45A.3 Statistical test results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

A.3.1 Dieharder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

ii

List of Figures

2.1 Scytale example - credits to 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Caesar disk - credits to 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.3 Generic diagram of a stream cipher . . . . . . . . . . . . . . . . . . . . . . . . 52.4 Example of an Linear Feedback Shift Register (LFSR) implemented in hard-

ware [10] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.5 Fibonacci implementation of an LFSR . . . . . . . . . . . . . . . . . . . . . . 72.6 Galois implementation of an LFSR . . . . . . . . . . . . . . . . . . . . . . . . 72.7 Example of a combination of LFSRs as a generator . . . . . . . . . . . . . . . 8

3.1 Detail of registers and operations . . . . . . . . . . . . . . . . . . . . . . . . . 143.2 Overview of the registers and operations. H, F and O are variable coefficients

and S-box is a substitution box that affects different bytes in different S registers. 153.3 Description of the Bloom filter areas where the values are taken for coefficients

F, O and H, as well as the event that triggers their update. . . . . . . . . . . 163.4 Key setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.5 Histogram of H coefficient values. The expected probability for each value, for

a uniform distribution, is 1/128 (7.8125× 10−3). . . . . . . . . . . . . . . . . 183.6 S-Box . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4.1 Distance between collisions, regarding the F coefficient update. . . . . . . . . 234.2 Distance between collisions, regarding the update function of the Bloom filter. 244.3 Distance between each N collisions, when updating the reference bit upon B

collision, ranging from 1 to 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.4 Distance between each N collisions, when updating the reference bit upon 10

collisions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.5 Influence of repeated values on S-Box . . . . . . . . . . . . . . . . . . . . . . 274.6 Histogram of bytes in the Bloom filter after each iteration, for 1× 106 iterations. 274.7 Histogram of values in the filter by its number of bits . . . . . . . . . . . . . 284.8 Distribution of the probability of values in the filter by its number of bits . . 28

iii

iv

List of Tables

4.1 Correlation of 10 keystream with 1KByte length . . . . . . . . . . . . . . . . 294.2 Correlation of 10 keystream with 2KBytes length . . . . . . . . . . . . . . . . 294.3 Performance figures obtained with the openssl speed test. The values represent

the data encryption speed (in MBytes/s) for different buffer sizes. . . . . . . . 31

v

vi

Acronyms

LFSR Linear Feedback Shift Register

FSR Feedback Shift Register

NLFSR Non-Linear Feedback Shift Register

BSC Bloom based Stream Cipher

S-Box Substitution Box

IV Initialization Vector

PRNG Pseudo-random number generator

PRBG Pseudo-random bit generator

TMTO Time Memory Trade-off

SCA Side channel attack

FPGA Field-programmable gate array

vii

viii

Chapter 1

Introduction

Since the beginning of human history, people have explored many ways to exchange secretmessages that can only be read by authorized receptors. This need for secrecy allowed thegrow of cryptography (from Greek kripthos - hidden and graphein - to write) as the science ofsharing information, limited to those who are qualified, even in the presence of third parties.

Historically, there are numerous examples of strategies used to send secrets, mainly inmilitary or diplomatic context. The basis of the first ciphers was the secrecy of the algorithm.This strategy is extremely insecure, as if the algorithm is revealed, is quite easy to a thirdparty to get the all the messages encrypted in the past.

The art of exploration of a cryptogram or encrypted information is named cryptanalysis.The development of new encryption techniques resulted in a parallel development of newcryptanalysis techniques, motivated by the existence of the first ones. These techniques aimto discover the original information hidden, by the means of many processes to find how ithas been transformed and details about it, e.g., algorithms, keys, etc [19].

Over time, both processes have been improved according to the new tools available tousers. Until the 19th century, cipher algorithms where limited to manual systems, but afterthe end of the 1st World War, mechanical substitution machines were developed. (EnigmaLorenz and M-209 Converter). In order to break them, also cryptanalysis machines weredeveloped (as the Colossus), but as stated in [5] ”although it is been used for centuries,cryptography systematic study only became more expressive in the last decades, with thetechnological evolution”.

With the evolution of computers or electronic systems in general, older algorithms becameuseless because of their low combinatorial complexity, as computers were able to exploreexhaustive searches in useful time. But this computational power also brings the possibilityto implement and develop more complex algorithms, adapted to the computer world, werethe information consists on streams of bits or bit blocks.

Concerning the exploitation of cryptographic keys there are two methods to build cryp-tosystems.

One is asymmetric ciphering, also know as public key ciphering, which uses a pair of keys,one private and one public. The first public key cryptography systems was proposed by Diffieand Hellman in 1976. With asymmetric encryption, the public key is known publicly, so it isused to encrypt a message to its owner and only its owner can decipher it using its privatekey. This method is also quite often used to validate the producer of a message, by encryptingit with its private key. Everyone can decipher the message, so it is not confidential, but we

1

can be sure that only owner of a given public key could have encrypted it.The other concept is symmetric ciphering with a secret key, shared by the interested parts,

that is used to do encryption and decryption. The stream cipher, discussed in this thesis is acipher of this kind.

Stream ciphers are mainly used in wireless communications systems, such as GSM, Wi-Fi,or GPS [13,19].

1.1 Motivation

LFSRs are widely known and there are numerous approaches to use them to build streamciphers. Most of them are in hardware, due to its high speed and simple design, but alsobecause the LFSRs are bit-oriented, which means that they are inefficient when implementedon microprocessors (as they are byte oriented). As its internal behavior is well-defined by apolynomial feedback function, its evaluation and cryptanalysis are also a problem, due to itssimplicity and to a periodic behavior.

1.2 Contribution

In this thesis we propose a new stream cipher that should be efficient both in softwareand hardware, based on a generalized LFSR using bit blocks instead of single bits, but toavoid create confusion, and create uncertainty about its periodic behavior, a Bloom filter isused to detect possibly repeated internal states. While the original proposal of these filtersonly use ones (1’s) to test if an element belongs to the set (we define a collision when theelement is found), our approach change it behavior with the collisions along the runs, i.e.,some iterations it accumulates ones (1’s) just like the original proposal, while in some otheriterations it accumulates zeros (0’s). This prevents the need of re-initialization of the filterwhen it is full and brings a more seamless behavior along time.

Although we’ve made some researches on the state of the art, we found no related workon stream ciphers, combining a single LFSR with a filter and none using the Bloom filters atall, as this proposal is a truly new concept design.

This work was presented at the Portuguese Math Society meeting, which took place from9th to 11th of July in Braganca, Portugal.

1.3 Structure

This document is divided in five chapters.The first, this one, aims to introduce an overview of what is cryptography and describe

the proposed work.In the second one, important marks of the history of the stream ciphers are described

chronologically. Then, there are the definitions of each area related to this work.The third chapter start with an overview of whole work, while the next sections are

dedicated to a detailed description of the architecture and all of its components.Latter, in the fourth chapter, we will present the results from the work as also the studies

done so far, in order to achieve the final solution.The conclusions related to this work, the work done and further tasks are debated on the

chapter five.

2

Chapter 2

Related Work

2.1 Some bits of History

Apparently, the history of cryptography started in the old Egypt, circa 1900 BC, by thearchitect Khnumhotep II; Amenemhet II was the actual Pharaoh. The idea of KhnumhotepII was to replace important words and parts of the original documents with symbols toconfuse the treasures thieves [7]. Techniques like this are known as substitution ciphers,where characters, or symbols are replaced by different ones. There are other concepts suchas transposition, where symbols are shuffled between them, such as anagrams, but with aprecise algorithm in order to revert [19].

Some centuries later, other methods were found each one with different transformations.At this time, most of the used techniques were based on steganography. This art differs fromcryptography since it does not need to transform the message. Instead, the message is hiddenby the mean of other support, as the ”Wax tablet”, where the message was marked on thehood and then a new wax is used to hide it. In fact this technique provides secrecy, instead ofsecurity, because when using cryptography, it is obvious to an interceptor that a message ishidden, while, in this last case, the secret is the interceptor cannot understand that a messageis flowing.

Figure 2.1: Scytale example- credits to 1

Probably, the first military cryptographic system has beenthe Scytale, used by Pasanius, a spartan general in 475 BC. Thescytale consists on writing the message on a leather strip, rolledup on a wood bastion. When the strip is removed, the messageis encrypted and to decipher it is need the bastion or anotherone with exactly the same diameter and form. This kind ofcipher is a transposition cipher. An example of the scytale canbe seen on Figure 2.1.

According to Paulo Almeida [7], the classic Kama Sutra hassupposed to been written, in the 4th century BC, by Vatsayana

mentioning the cryptography is an art, or yoga, that every people should know. But Vatsayanarefers to his work as a compilation of earlier works, which makes the dating of cryptographymore difficult [14].

Later, in India, in the years of 300 BC, the first cryptoanalisys methods were presentedon a book called Artha-sastra. This book is assigned to Kautilya and its processes are rec-

1https://commons.wikimedia.org/w/index.php?curid=1698345

3

ommended to diplomats [7].

Figure 2.2: Caesar disk -credits to 2

Some years latter Julius Caesar created a cipher that con-sists on replacing each letter by the 3rd ahead in the alphabet.This cipher, known as Caeser’s cipher, became one of the widelyknown ciphers of all times.

Until the 19th century, ciphers were conceived regardingtheir secrecy and also their usability by the users.

By the end of the 19th century, mechanical machines startedto be used to implement more complex and fast ciphers. TheEnigma, designed in 1918 by the German Arthur Scherbius, isan example. This machine was extensively used by Germansalong the WWII [19].

Parallel to this mechanical machines, electromechanical cryptanalisys machines were alsohas developed. Examples are the Colossus and the Turing Bombe, developed in BletchleyPark, UK, where Alan Turing worked [19].

More recently, with the computers being present everywhere, other techniques have beendeveloped and ciphers are now much faster, complex and hard to break.

To a much more detailed description about evolution of cryptography along time andcivilizations, the book of Richard Molli [14] tells about the way cryptography was developed.

2.2 Stream Ciphers

Menezes et al. [2] classify stream ciphers as an important topic of encryption algorithms.They are used to encrypt plaintext contents, bitwise, i.e., one bit at a time, by using atransformation that changes with time. On the other side, there are the block ciphers, whichtransform blocks of plaintext bytes based on a fixed encryption transformation.

Also on [2] is stated that stream ciphers are, in general, faster than block ciphers, whenimplemented in hardware, and that they have less complex hardware circuitry. This featuremakes stream ciphers a preference, and sometimes a demand, when using limited systems astelecommunication devices. Another advantage of stream ciphers is that they have limited orno error propagation, which makes them suitable in situations where transmission errors arehighly probable.

In [9] it is stated that ”a stream cipher, formally, is a symmetric cipher which generatesa sequence of cryptographically secure bits called the key stream”. It is also stated that the”basic topology of a stream cipher consists of a register to store the key and an InitializationVector (IV) together with a function for its update (typically some sort of feedback shiftregister)”.

Stream ciphers are a practical approach to the Vernam cipher. In order to achieve apractical implementation, the idea was to replace the Vernam’s one-time-pad by a keystreamproduced by a pseudo-random generator. This type of generator is initialized by a key andits output is mixed with the text (plain or ciphered) in a reversible operation, typically theXOR operation. The key and IV define the initial state of the generator. Figure 2.3 showshow practical stream ciphers operate.

2https://www.cryptomuseum.com/crypto/caesar/linge.htm

4

Figure 2.3: Generic diagram of a stream cipher

The majority of stream ciphers are synchronous, i.e., the generator is independent fromboth the plaintext and ciphertext. This implies that both encryption and decryption end-points need to manage the synchronization of both transformation operations [19].

2.3 Pseudo-Random Number Generators

A sequence of numbers . . . , x(-1), x(0), x(1), . . . , is called a pseudo-random sequencewhen it is generated using a mathematical formula and has the statistical properties that areexpected to be found in a random sequence. Mattsson [13] says that a ”random bit sequencer = {ri}∞i=0 is a sequence such that every bit ri follows a Bernoulli distribution with p = 0.5,and all the bits are independent of each other”. He also refers that ”the goal of every streamcipher is to be computationally indistinguishable from such sequence.”

P(n) =

{1− p for n = 0

p for n = 1(2.1)

2.1: Bernoulli distribution

In [15] Pseudo-random number generators (PRNGs) as said to ”generate sequences whichare computed from an initial seed value. Often they are computed recursively in the followingway:

s0 = seed

si+1 = f(si), i = 0, 1, . . .(2.2)

A popular example is the linear congruential generator :

s0 = seed

si+1 = asi + b mod m, i = 0, 1, . . .(2.3)

where a,b,m are integer constants.

A generalization of this are generators of the form si+1 = f(si,si−1,. . . ,si−t), where t is afixed integer.

5

Note that PRNGs are not random in a true sense, because they can be computed and are,thus, completely deterministic.”

PRNGs are implemented by finite state machines. An LFSR is an example of a Pseudo-random bit generator usually used when hardware-based implementation favor performanceand energy saving.

2.4 LFSR

According to Paar and Pelzl [15], LFSRs are ”an elegant way of realizing long pseudo-random sequences” and many of stream ciphers are based on LFSRs, due to its simplicity inimplementation [17] [13].

An LFSR consists on a deterministic state machine mostly used on hardware implemen-tations and mainly based on flip-flops to store its internal state. As each flip-flop stores onebit, combining multiple ones is possible to get the 2n bits, where n is the number of flip-flops,numbered from F0, F1, ..., Fn.

Also, according to Texas Instruments [10], an ”LFSR is a shift register that, when clocked,advances the signal through the register from one bit to the next most-significant bit. Someof the outputs are combined in exclusive-OR configuration to form a feedback mechanism.A linear feedback shift register can be formed by performing exclusive-OR on the outputs oftwo or more of the flip-flops together and feeding those outputs back into the input of one ofthe flip-flops”, as shown in Fig. 2.4.

Figure 2.4: Example of an LFSR implemented in hardware [10]

The feedback function gives the next state of the first flip-flop, resulting in a mathematicalsequence represented by the equation 2.4:

ai = F (ai−1, ..., ai−n), i, n ∈ N (2.4)

where ai represents the output of the first flip-flop on the i-th iteration. There are twotypes of strategies when implementing the feedback on LFSRs. The first one is the externalfeedback, or the Fibonacci implementation of an LFSR, and the internal feedback, or theGalois implementation, as shown of the Figures 2.5 and 2.6.

6

Figure 2.5: Fibonacci implementation of an LFSR

Figure 2.6: Galois implementation of an LFSR

In both drawings the states of the LFSR are represented by the letters ’F’ with theassociated index. The ’C’ letters represent the coefficients of the feedback polynomial andthe circles represent some mathematical formulas, where the symbol represent the ANDoperation, that defines if the coefficient will act on the feedback, and the symbol representsXOR, typically. Of course, any other operations could be chosen.

Also, the name Linear Feedback Shift Register should only be applied to polynomials thatare really linear. If the feedback function is not a linear one, the generator is a Non-LinearFeedback Shift Register or only Feedback Shift Register (FSR).

LFSR cannot be used directly, as generators of stream ciphers because its state (initiallyset by the key and the IV) is revealed by the output. Thus, a common practice is to combinemultiple LFSRs and then use a mechanism that manages which one is selected to generatethe keystream. Figure 2.7 shows a combination of LFSRs as a generator.

According to Schneier [17], ”LFSRs are slow in software, but they are faster in assemblylanguage than C. One solution is to run 16 LFSRs (or 32, depending on computer’s word size)in parallel. This scheme uses an array of words that is the length of the LFSR, with each bitposition in the words representing a different LFSR. Assuming all the feedback polynomialsare the same, this can run pretty quickly.”

7

Figure 2.7: Example of a combination of LFSRs as a generator

The main advantage of using LFSRs is its speed, as is hardware implemented, resulting ona very efficient system. One disadvantage of LFSRs is that they are very easy to analyze usingmathematical tools. This makes it easier to cryptoanalyze LFSR-based ciphers. Furthermore,typically LFSRs used in cryptographic algorithms use fixed polynomials and use the key andthe IV to set their initial state. Thus, the knowledge of the polynomials makes it easierto cryptoanalyze LFSR-based generators. The main reason for using fixed polynomials isto guarantee that LFSRs do not enter on a fixed state and produce the maximum possibleoutput sequence before starting to cycle.

2.4.1 Xorshift

An alternative implementation of LFSR generators was proposed by George Marsaglia:the Xorshift [12]. The Xorshift consists on the ”exclusive-or (xor) a computer word with ashifted version of itself” [12].

Marsaglia defines his discover as an ”extremely fast random number generator with periods2k − 1 for k = 32, 64, 128, 160, 192”. The seed could not be zero, as it is a blocking stateon this generator. In fact, on his proposal, Marsaglia presents the possible combinations andnumber of choices that guaranties the maximum period for 32 and 64 bits, which are 648 and2200, respectively.

The algorithm is, in fact, very simple as it uses exactly three XORs of shifted values(xorshifts). An implementation example, for a 64-bits generator, retrieved from [12]:

1 unsigned long long xorshift()2 {3 static unsigned long long y = 2463534242;4 y ˆ= (y<<13);5 y ˆ= (y>>17);6 return (y ˆ= (y<<5));7 }

Higher periods are considered feasible by the author, although it becomes less efficient.

8

2.5 Bloom Filters

The Bloom Filter was proposed by Burton Howard Bloom, in 1970, to test whether anelement is a member of a set or not. The filter is a space-efficient probabilistic data-structureto query connected elements. In other words, it is a way of check if a given value belongs toa data-set without the need to search all elements.

Burton’s proposal [6] had not the intent of replacing any other hash coding techniques,but to fulfill its flaws. The major definition of applications of Bloom Filters is to check if anelement belongs to a data structure. In conventional hash coding, to test if a given element isin the data structure, first an address is generated, based on a message, and then the contentof the cell must be compared with the message. If there’s a match, the item already belongsto the set, otherwise, it does not and a new address must be generated. The inconvenienceof this solution is the time to find a message and the space needed to store all the messages.

The Bloom filter, on the other hand, consists of a vector of m bits, initially set to all zeros,and k hash functions. To query if an element e belongs to the set, the algorithm checks thepositions mapped by h1(e) to hk(e). If all positions are ”1”, the element is probably in theset, but if at least one is ”0”, the element is not in the set, definitely. In this case, all thepositions mapped are set to ”1”, to update the filter value.

This leads us to conclude that, as each iteration is the set of n bits, the time complexityto update a Bloom filter depends only on the number of hash functions k, i.e., O(k). In fact,to query if a given element is in the set, the time complexity is exactly the same.

In [6], Burton also considers a third computational factor: the allowable fraction of errors.What a Bloom Filter can guarantee, faster than any other solution, is that the elementsearched in the structure is not there. Otherwise, it may be there or be a false positive.

The false positive rate depends of the size of the filter and the number of inserted elements,but is independent from the hash functions used. Also the speed of each query depends onthe number of hash functions k. An interactive example can be found at 3.

Mathematically, and according to the author [1], the probability of finding a 0 or 1, afterinserting n elements on a vector of size m are defined by equations 2.5 and 2.6:

P0 =(

1− 1

m

)kn(2.5)

P1 =(

1− eknm

)k(2.6)

The advantage in order to use a Bloom filter on an LFSR is to detect a repeated internalstate and, increase the period, leading to a different output sequence thereafter changing thefeedback function. In the worst case, to detect a repeated state, as the Bloom filter matchescould be false positives, a state could not be repeated as the sequence change earlier.

In our work, we started to use the traditional implementation described of the Bloomfilter, but latter, for reasons explained in next chapters we will implement a modification tofulfill our needs.

3https://www.jasondavies.com/bloomfilter

9

2.6 Attacks to stream generators

On his thesis, John Mattsson [13] presents a full chapter about the generic attacks onstream ciphers and refers that ”the methods for attacking a stream cipher can be classifiedaccording to the information available to the cryptanalyst, the aim of the attack, or the waythe attack is done. It is often assumed that the attacker has knowledge of the cryptographicalgorithm, but not the key.”

As it has been referenced in literature for a long time, Jonsson [11] (qtd. in Mattsson [13])describe the generic classification of the stream cipher attacks in four categories, accordingto the information available to the attacker:

• The first one is ciphertext-only attack, which is the worst case to a cryptanalyst. Inthis scenario, only the ciphertext is given and the attacker tries to recover the key orthe plaintext. If the plaintext has redundancies it could be able to the attacker to havesuccess.

• The second case is a known-plaintext, where the attacker knows the ciphertext and allor part of the plaintext and tries to deduce the key or the rest of the plaintext. Inthis case, is also possible to know the keystream as both the s possible to encrypt anychosen plaintexts. The aim is to deduce the key.ciphertext and (part of) the plaintextare known.

• The third category is the chosen-plaintext. In this attack, the access to an encryptionunit is given and is possible to encrypt any chosen plaintexts. The aim is to deduce thekey.

• Analogously to the previous case, in the chosen-ciphertext, the attacker can chose anyciphertext and decrypt it on a decryption unit. The objective is the same: deduce thekey.

Mattsson [13] also explains the most known attacks. Those attacks are the exhaustivekey search, time memory trade-offs, distinguishing attacks, guess-and-determine, correlationattack, algebraic and side-channel attacks.

2.6.1 Side channel attack

A special mention to the Side channel attack (SCA) is given due to its difference. Whilethe other attacks focus on the information produced by the cipher, SCA are based on indirectinformation, i.e., information that can be retrieved during the processes of encryption anddecryption [4] and that are dependent of the information used by the stream cipher, such asthe plaintext, key and IV. This information could be based on any variations between rounds,such as time and power variations.

The side channel techniques could be what an attacker’s imagination allows and could beprepared quickly, sometimes with easy-to-get equipments. According [4], the time of a SCAdepends on the type of attack, as it could be a Differential Power Analysis, a Simple PowerAnalysis, Timing, or any other.

The timing attacks consists on measuring the time a unit takes to perform operations. Itis also stated in [4] that cryptosystems often take small different amounts of time to process

10

different inputs and its reason include branching and conditional statements, RAM cache hitsand variations on processor instruction timing (such as multiplication and division).

A most complex kind of attack are the power consumption attacks. This ones are basedthe analysis of the power consumption of the device while it performs the operations andthen combine with other techniques to learn about the what it is occurring inside the unit.Some more advanced attacks combine statistical analysis of multiple data retrieved of thedevice and can be automated, but the main requirement is that the target implementation inneeded [4].

In Mattson thesis [13], other example of SCA includes leaked electromagnetic radiationand sound. An example of one of these attacks has been demonstrated by authors like Genkin,Shamir and Tromer [8] (qtd. in Mattsson [13]) and has shown that it is possible to performa time based attack based on the hamming noise of the CPU.

2.6.2 Correlation attacks

Other significant, and considered by Mattson [13] as probably the most important, attackon stream ciphers is the correlation attack.

This attack consists on using a much simpler device internal configuration, and thencorrelate both the keystream (k1, k2,. . . ) and the output sequence of the simpler device(s1, s2,. . . ). If both the sequences have probability P (ki = ai) 6= 0.5 they are correlated andthe attacker could recover the initial state of the LFSR [13].

2.6.3 Distinguishing attacks

The distiguishing attacks consists on distinguishing a keystream from a truly randomsequence [13]. This attacks are very generic as each one is designed to a specific cipher.

These attacks are typically efficient to distinguish the keystream on ciphers that fail onordinary statistical tests, that cannot find weaknesses in new stream ciphers. Its downside isthat requires large amounts of keystream.

2.6.4 Exhaustive Key Search and Time Memory Trade-off

The exhaustive key search is a brute force attack, where all the combinations of keys aretried until the correct one is found. This is the most simple attack, compatible with all streamciphers.

In order to decrease the time complexity, a Time Memory Trade-off (TMTO) could beconsidered. This strategy consists on using of large amount of precomputed data. Obviously,the quantity of data (memory used) and time of computation are a trade-off of resources.

The first TMTO attack on stream ciphers was used to break the A5 cipher used in GSMstandard [13] and was a birthday attack - not known until it happen. This attack wasperformed by Golic, due to the work of Steve Babbage [3]. The mathematical formulation ofthis attacks is described on his work and are represented by (n+m)×2m of space to save thepre-computed data and (n + m2)× 2n−m of time to perform the attack, where m representsthe amount of keystreams samples and n the maximum length period of the stream cipherbegin attacked.

11

12

Chapter 3

Bloom-based Stream Cipher

3.1 Overview

The typical design of FSR-based ciphers explores single bit registers, which makes themfast and easy to implement in hardware but not in software. Our goal was, then, to followthe fundamental construction of FSRs but to use longer values on registers, namely 64-bitvalues. This allows the generator to produce 64 more bits on each shifting iteration.

As referenced before, there are some security inconveniences when using LFSRs. Namely,their output reveal their inner state and the normal strategy of using a fixed feedback functionmakes them more prone to cryptanalytic attacks. Our approach to tackle the second of theseproblems was to use a secret feedback function, i.e., a function whose coefficients dependon a secret key. However, this strategy may be dangerous if one could not ensure that thegenerator cannot enter in short-length cycles.

The solution that we envisioned to deal both with the direct exposure of the generator’soutput and the entering on a (short) cyclic behavior was to use a Bloom filter. With theBloom filter we are able to detect repeated register states, and modify the feedback functionin order to avoid short cycles. With the inner state of the Bloom filter, which evolves in acomplex way, we are also able to mask the generator’s output value, thus hiding the exactvalues held by registers.

The fact of using 64-bit values in registers, instead of single bit values, enables us to addto extra sources of cryptographic complexity without compromising performance. As a basicprinciple, we looked for a way create an avalanche effect in the feedback function. This way,using the same feedback coefficients we could produce very different values from very similarregister values. The way we achieved this was not by placing complexity of the feedbackfunction, but rather to use different S-Boxes along the register shifting.

Recalling the two fundamental principles of cryptographic design due to Claude Shannon(confusion and diffusion [18]), the use of the Bloom filter to control the evolution of the FSRfeedback function and to mask its output adds confusion, while S-Box modifications alongthe register shifting adds diffusion.

3.2 Architecture

The Bloom based Stream Cipher (BSC) is a cryptographic pseudo-random number gen-erator based on a FSR. As described, an FSR consists on values shifting from one register

13

to the next and a feedback function (of some) of those values to update the first register. Inthis proposal, the FSR is based on four 64-bit registers, designated by S, that are used inthe feedback function, combined with an equal number of the F coefficients. Also a modifiedBloom filter of 512 bits, is used to detect repeated states and trigger modifications in theFSR internal state, namely the F coefficients, among others. The filter is segmented in fourparcels, each one addressed by one S register. The update of the Bloom filter depends on theoffset function, represented by

⊙, will be explained in 3.2.3.

Furthermore, after each S register exists an S-Box to replace two bytes throughout theshifting, until the output. The changed bytes are, in the first register, the first and the fifthbytes, on the second register, the second and the sixth, and so on until the last register, seeFigure 3.6. A detailed description of the S-Box will be done later in the section 3.2.4.

The Figure 3.1 show detailed information of each S register, as the size of the operandsbefore each operation and where they influence the behavior of the generator.

Figure 3.1: Detail of registers and operations

As already mentioned, the feedback function depends on all S registers values, after mod-ified by the S-Boxes and the F coefficients, associated to each register. The value of thefeedback is given by:

S0 =n∑

i=0S′i⊕

Fi

where the S′i represents the output of each register after being modified by the S-Boxes, Fi

represents a feedback coefficient, the⊕

represents the XOR operation and the summationrepresents the arithmetic sum; n is the depth of the FSR, which in our case is 4.

On the other side, on the output, after the last S-Box modification there is a coefficient,

14

O, used to hide the last value, and the rest of the S registers, through an XOR operation.A complete overview of the design and the operations of the BSC is shown in Figure 3.2.

Figure 3.2: Overview of the registers and operations. H, F and O are variable coefficients andS-box is a substitution box that affects different bytes in different S registers.

In order to achieve a better performance, we have done some modifications to the originalproposal of Bloom filter. The Bloom filter evolution depends on the state of the FSR, as ineach state iteration are generated several indexes of bits of the Bloom filter to be tested (4in our case). These bits are compared with a reference bit, which toggles from time to time.We say we have a collision when all 4 bits equal the reference one. Upon a collision, possiblydue to a repeated state, some modifications are triggered to prevent the generator to stay ona loop.

Other advantage of the implementation of the toggling bit is there is no need of resettingthe filter to zeros, as it never gets saturated.

3.2.1 Auxiliary registers

As referenced before, and shown in Figure 3.2 and Figure 3.1, there are three types ofcoefficients to update the registers and also the Bloom filter. All these registers are views ofparcels of the Bloom filter.

The H coefficients are used to select the bit to test on the filter. Although being abyte, they can only address 128 bits of the filter. The function that computes the address,represented by

⊙, will be described on section 3.2.3. After the update of the filter, each H

coefficient takes as value the byte of the filter that contains the bit analyzed.The F coefficients are an important member of the feedback function, as they are mixed

with the values of S registers, after modified by S-Boxes, by a XOR operation, adding con-fusion on the generation of the next state value. Those coefficients are pointers to twoalternating 64-bit words within 128-bit parcels of the Bloom filter. These pointers alternateeach N collisions between the 64 MSBit and 64 LSBit of their Bloom filter parcel. In our casewe used N=4, but it can be customized.

The other coefficient, O, is also a pointer to a 64-bit word of the filter. Its address isupdated on each collision; the update is a 64 bit right shift, modulus the size of the filter.

15

Another important feature to highlight is the fact that, although the H coefficient couldbe pointers or not, both F and O must be, to take advantage of the fact that the filter is inconstant evolution. So, even the pointers are fixed to a location, as the content of the filteris dynamic, its values also updates and create influence on the feedback value.

Figure 3.3: Description of the Bloom filter areas where the values are taken for coefficientsF, O and H, as well as the event that triggers their update.

In the Figure 3.3 is shown how pointers of the coefficients work, based on collisions (Fand O) and on iterations (H). Each box in the figure represent the parcel of the filter thateach pointer can address, except to the O coefficient which address all the Bloom filter.

3.2.2 Initialization

It is useful when using stream ciphers to require an IV, also known in some ciphers as anonce, i.e., a value (like a counter), that is not repeated while using the same key. The use ofthe IV is useful as the sharing of the keys could be hard to achieve. The IV does not need tobe secret, as it does not affect the security of the stream cipher, and allows to encrypt severalmessages using the same key.

To initialize the BSC, a 768-bit key is required to fill the Bloom filter and the S registersof the FSR. 512 bits are copied into the filter and the remaining 256 bits are copied to theshift registers. Then, a 64-bit IV is XORed with all S registers. H coefficients take the lowestbyte of their parcel of the Bloom filter, and all F coefficients take the lowest address of theirparcel of the Bloom filter. The O coefficient takes the lowest address of the entire Bloomfilter. The collision counter is initialized with 0. Finally, the Bloom filter reference bit is setto 1 (i.e., in the beginning the generator will look for collisions using 1’s instead of 0’s).

16

Figure 3.4: Key setup

When the initialization is concluded, a shuffle operation is run to create some confusion,i.e., in order to generate very different keystreams when using the same key and different IVs.This operation consists on doing 8 iteration rounds with all the registers being updated asnormally, until producing a total of 512 output bits. These bits are then used to update theBloom filter with an XOR operation between them.

3.2.3 Bloom filter update function

The Bloom filter has a very important role on the behavior of the generator as it is respon-sible for its good statistical properties. One of our concerns was its update and management.

In the previous sections we mentioned that the update function depends on the H coef-ficients and the S register, but we did not specified how they relate. In order to achieve thebest possible solution, we studied the behavior of different mathematical operations betweenthe operands and studied the statistics of bit offsets for checking bits on Bloom filter parcels.The operations we chose to study on this function were addition, XOR and multiplication.The study of them is on 4.2.2.

The resulting formula to generate the offset of each bit to be tested is given by:

bit offset =

{(S mod 127)

⊕HL if HH = 0

(S mod 127)⊕¬HL if HH = 1

(3.1)

where HH represents the high order bit of H and HL are the lower order 7 bits of H. Afterthe update of the bit, the H register takes for its value the byte where the bit was changed.Experimental evaluations with random key setups show that the frequency of the values onH registers approaches a uniform distribution, as shown the histogram on Figure 3.5

17

Figure 3.5: Histogram of H coefficient values. The expected probability for each value, for auniform distribution, is 1/128 (7.8125× 10−3).

3.2.4 Substitution Box

As mentioned before, the output of an S register is modified prior to be used; a Substitu-tion Box replaces two bytes by other two bytes, and keeps the others unchanged. For this wecreated a one-byte S-Box, which is used in all the four different 64-bit S-Boxes (see Figure3.6). This S-Box was created by a deterministic algorithm. In order to replace bytes withoutcreating bias, it has the following properties:

• s[i + j mod 256] 6= s[i] + s[j] mod 256

• s[i⊕

j] 6= s[i]⊕

s[j]

• s[i] 6= i

• if i 6= j in 1 bit, s[i] differs from s[j] in 4 bits, on average.

The first two properties gives us the guaranty that there is no isomorphism between thevalue that gets in the S-Box and the value that gets out. The importance of this rules is toprevent correlation attacks.

The third rule is also important for this prevention as it guarantees that all values on Sregisters change in each shift, independently of Bloom filter collisions. This means that eachstate is always different from, at least, the previous.

At last, the fourth rule, creates the avalanche effect, if we consider the parallelism of the64 FSRs. This is a very good practice according Schneier [17], as a single bit modified on theentrance affects a significant quantity of bits on the output, creating diffusion.

The resultant S-Box can be found at A.1.2 and the source code at A.1.1. The source codeuses the rand() pseudo-random function, starting from a constant seed, but it can producedifferent S-Boxes for different implementations of rand().

18

Figure 3.6: S-Box

As shown, each 64-bit S-Box affects different bytes on each S register. This configurationensures that all bytes in a 64 bits range are affected until the end of the overall shift (4 registershifts).

19

20

Chapter 4

Analysis

4.1 Theoretical security analysis

Since the BSC is based on an FSR, one of the major concerns is its primary limitation, itsperiod. Considering all its components, we have the following number of bits for representingits state:

• 4 × 64 for S registers;

• 512 for the Bloom filter;

• 4 × 4 for H coefficients;

• 4 for F coefficients;

• 3 for the O coefficient;

• 2 for the collision counter that toggles F coefficients;

• 1 for the Bloom filter reference bit;

Thus, the complete state of the generator is given by 794 bits. Since, unlike for LFSRs,we do not have an absorbing state (a state from which one cannot move away). In theory,the BSC has a maximum length period of 2794 bits.

With these values and considering the work of Steve Babbage [3], a Time Memory Trade-off attack to BSC is not feasible due to its period. Remembering the formula of time requiredto perform an attack:

(n + m)× 2m (4.1)

supposing we have a set of m=700 samples of n-bits = 794, which is the period of BSC, thespace needed to store all the data is:

(1494)× 2700 bits (4.2)

As this value is so huge we can say that the BSC is immune to these attacks.

21

In order to define a lower bound of the period, the S0 register was monitored in a seriesof generated keystreams. Due to its dimension, count all its values to find those that repeat,would require a lot of memory. Our solution was to use another Bloom filter, in order tocatch the first value that would be repeated and the number of iterations before it happen.

To update the Bloom filter, we used a similar function to the offset function: the indexis generated by the S register value modulus 65521 (the biggest prime represented with 16bits). Running the cipher with this new feature, the only result we’ve achieved was all theexperiments gave different values for the S0 register, as also different distances between itscollisions, i.e., all results were false positives.

With this, we decided to store a list of S0 states until a collision and then check if thevalue was in that list. The test was repeated for more than 30000 experiments and in all ofthem the value that triggered the collision was not in the list of saved states, which gives noinformation about the BSC period.

In all of the tests, the key and IV were initialized by a random value.

4.2 Statistical evaluation of the generator

4.2.1 Selection of N (consecutive collisions)

As described so far, the collisions in the Bloom filter are responsible for the update of thepointers of the coefficients. As we needed to know how was its behavior, we used a randomgenerator to seed the initial status of the generator and feed the offsets, on each iteration.Then, we counted the number of iterations between collisions. In all these tests, the referencebit used in the Bloom filter was 1 and the result is shown on Figure 4.1.

With this results it was considered that a distance of 4 collisions is enough to update theF coefficients and yet, prevent the generator to enter in a short cyclic loop. Although, thisdistance parameter could be customized.

22

Figure 4.1: Distance between collisions, regarding the F coefficient update.

4.2.2 Evaluation of alternatives for the⊙

function

As referenced in the previous chapter, we have considered three operations to computethe offset function,

⊙, to update the Bloom filter. This function is responsible to create the

index of the bit that each register will update on the filter, combining both the H coefficientvalue and the S register value, modulus 127. The functions we decided that could fit on anoperation as described were: addition, xor and multiplication, which are given by the nextfunctions:

• Multiplication:

bit offset =

{(S mod 127)×HL if HH = 0

(S mod 127)× ¬HL if HH = 1(4.3)

23

• Addition:

bit offset =

{(S mod 127) + HL if HH = 0

(S mod 127) + ¬HL if HH = 1(4.4)

• XOR:

bit offset =

{(S mod 127)

⊕HL if HH = 0

(S mod 127)⊕¬HL if HH = 1

(4.5)

In order to understand how which one affect the numbers and distance between 4 collisions,we registered the values and the resultant distributions are shown in Figure 4.2.

Figure 4.2: Distance between collisions, regarding the update function of the Bloom filter.

In all of the three cases, the experiments were made with an accumulator (”acc”) andwithout it (”no acc”). The function of using the accumulator, using the XOR operation, isgiven by:

bit offset +=

{(S mod 127)

⊕HL if HH = 0

(S mod 127)⊕¬HL if HH = 1

(4.6)

where the last index value is added to the new index calculated.As shown, the multiplication operation, with and without the accumulator, will reduce

the distance between the 4 collisions.Although, for the three operators, the values seems to have a good Gaussian distributions,

the use of an accumulator does not affect the behavior in a significant way. So, choosing

24

between the addition or XOR operations, we decided by the last, as it provides a larger setof values without compromising the performance.

As in the previous study, all the tests used random values for the S registers and Hcoefficients, and the number of iterations was 1× 106.

4.2.3 Impact of the toggling frequency of the Bloom filter reference bit

As we saw before, F coefficients are updated upon N=4 collisions in the Bloom filter,regardless of the value of its reference bit. However, the toggling frequency of this bit can affectthe distribution of distances between those N collisions. Figure 4.3 shows the distributionthat we achieved with a toggling after a given number of collisions, ranging from 1 to 10.

Figure 4.3: Distance between each N collisions, when updating the reference bit upon Bcollision, ranging from 1 to 5.

The result shows that, toggling the reference bit upon more collisions (higher values ofB), reduces the spreading of the distance between N consecutive collisions.

For values of B>5, the results have a less normal distribution, as shown for B=10 in Figure4.4.

25

Figure 4.4: Distance between each N collisions, when updating the reference bit upon 10collisions.

Given this distributions, we decided to toggle the bit after 4 collisions, as the collisionspresent the best approximation to a Gaussian distribution.

4.2.4 S-Box analysis

The S-Boxes are critical to the behavior of the generator. In this section we will showthe influence of their transformation in the overall quality of the generator by producing twoequal values from two different outputs. This should not happen, by design, but it happenby mistake during the early experiments with the chosen one-byte S-Box. The mistake wasdetected due to strange statistical deviations, as we will see.

Using the S-Box presented in A.1.2, the histogram of the bytes in output of the generatoris uniform, as expected on a Pseudo-random bit generator, as shows the blue line in thegraphic. Then, we modified the S-Box to replace the value 0x80 (12810) by 0x40 (6410), andthe histogram of the bytes in the output of the generator started to exhibit a set of spikesmatching exactly the values suppressed and repeated in the S-Box output, represented by theorange line.

26

Figure 4.5: Influence of repeated values on S-Box

4.2.5 Bloom filter statistics

An important factor of the quality and security of the generator is the Bloom filter statis-tics. In order to understand its evolution over iterations, we did an histogram of its bytes,result of the

⊙operations, updated after each iteration, and the results are the ones presented

in Figure 4.6.

Figure 4.6: Histogram of bytes in the Bloom filter after each iteration, for 1× 106 iterations.

The graphic exhibits a symmetry related to its center values, 127 and 128. This effecthappens due to the proportion of bits in each byte value and the influence of toggling thereference bit.

27

In fact, the more frequent values are exactly 0 (all zeros) and 255 (all ones). The secondmore frequent values, there are the ones with only one bit equals to 1, in the left side of thegraphic, or only one bit equals to 0, on the right side of it. This relation is the same in thenext frequencies to values with two, three and four bits different on each byte.

Then, with this results, we have computed the distribution of the values, by the numberof bits and the result is shown on 4.7.

Figure 4.7: Histogram of values in the filter by its number of bits

As expected, the values with more difference of bits are the ones with higher frequency.This could also be seen in the Figure 4.8, that shows the probability distribution of each setof bits.

Figure 4.8: Distribution of the probability of values in the filter by its number of bits

4.2.6 Output correlation

As the correlation attacks are some of the most significant attacks against stream ciphers,we developed some tests in order to guarantee the value of the key and IV remains secret,even in the first bytes of the keystream.

The tests consist on generate multiple keystreams with 1KByte, with the same key anddifferent IVs, and then compute the correlation between them. This IVs have an Hammingdistance between them of 1bit. The correlation factor of two sequences is a value between 0and 1(considering absolute values), where 0 means there is no linear relation and 1 means aperfect linear relation between them.

28

To compute this correlations, we used the source code in the appendix A.2. The idea wasto count the number of bits that are different in both sequences, to give weights of -1 for theseones and +1 to those that are equal.

One output of this test is shown in Table 4.1, for 10 sequences. The results are quitesatisfactory, as there the correlation factor is really close to 0 and less than 2%, for differentsequences. In fact, the minimum value is 0, i.e., there is no linear relation between thosesequences and the maximum is 1,8% between the first sequence and the last one.

Table 4.1: Correlation of 10 keystream with 1KByte length

1 2 3 4 5 6 7 8 9 10

1 1.0002 0.012 1.0003 0.006 0.010 1.0004 0.004 0.009 0.000 1.0005 0.009 0.004 0.006 0.004 1.0006 0.014 0.000 0.006 0.000 0.007 1.0007 0.010 0.000 0.002 0.010 0.008 0.002 1.0008 0.005 0.009 0.000 0.001 0.009 0.001 0.003 1.0009 0.003 0.015 0.009 0.005 0.011 0.001 0.005 0.014 1.00010 0.018 0.012 0.011 0.009 0.009 0.010 0.000 0.011 0.007 1.000

With some good results, we decided to repeat the test to bigger sequences, in order tounderstand how the correlation factor behaviors. In average the values are lower, than theprevious experiment, which means the generator has enough randomness, independent of theinput, even in the first bytes of the keysteams. The results are in the Table 4.2.

Table 4.2: Correlation of 10 keystream with 2KBytes length

1 2 3 4 5 6 7 8 9 10

1 1.0002 0.006 1.0003 0.008 0.010 1.0004 0.018 0.005 0.004 1.0005 0.010 0.017 0.005 0.003 1.0006 0.004 0.003 0.001 0.011 0.001 1.0007 0.005 0.008 0.005 0.005 0.005 0.003 1.0008 0.009 0.005 0.000 0.002 0.011 0.009 0.005 1.0009 0.007 0.003 0.006 0.007 0.002 0.007 0.003 0.009 1.00010 0.001 0.006 0.011 0.001 0.005 0.000 0.003 0.004 0.005 1.000

29

4.2.7 Resistance to side-channel attacks

To avoid these attacks, it is important to preserve the secrecy of the internal state and donot allow the possibility of identifying when a collision occurs on the Bloom filter. This willprevent to discover when the H, F and O are updated and, possibly, the key.

But not only the collisions make differences on the behavior of the cipher. Anotherprevention method to consider is to minimize the different number of instructions executedcreated by the conditional instructions. For example, some iterations will not result oncollision, so some registers does not need to be updated. This reduces timings and instructionsexecutions in some iterations. So, in order to avoid an increase of instructions when a collisionoccurs, the registers are updated every cycle, even when the update is with the same value.

Nevertheless, to optimize the code, we used the tool GCOV 1 to profile and improve thesolution so far. With its outputs, some of the instructions have been reordered in order toequalize the time of each iteration. This is an important measure to keep the behavior of thegenerator as linear as possible to the outside.

No improvements or analysis have been made regarding the power consumption, as itshould be done as a future work.

4.2.8 Pseudo random statistical properties

Stream cipher generators need to be cryptographically strong pseudo-random bit genera-tor. Thus, the statistical quality of their output keystream should be evaluated by tools thattest it against a wide set of statistical randomness tests. For this, we used a very populartool: the dieharder [16]. This tool integrates numerous tests and algorithms to evaluate therandomness of the bit sequences. Its current version, 3.31.3, now includes some of the testsof the National Institute for Standards and Technology (NIST) 2.

It is important to highlight that this tools does not evaluate the security of the streamcipher.

One example of the output is available on the A.3.1. In this tests we used the configurationsdefined until now: update of the F coefficients and bit toggling in N=4 collisions, the XORoperation with no accumulator in

⊙function and the Bloom filter toggling bit.

The results were very satisfactory as all tests reported an average of two weak assessmentsper sequence. The best result has 0 weaks and the worst had a maximum of 4, always indifferent tests. Then we tried some more specific initializations: with a key and IV of all 0’s,there are no weaks and with all 1’s, the result was two weaks.

With these good statistical properties and as our feedback function is non-linear, we cansay BSC is immune to distinguish attacks.

4.2.9 Performance

After all the analysis, our concern was, at this point, the performance of the BSC. Toevaluate our stream cipher we used, as a benchmark, a real scenario: the openssl tool 3. Tobe able to compare with referenced stream ciphers, used by openssl, we embedded our code(with manual loop unrolling) in its source and executed the tests.

1https://gcc.gnu.org/onlinedocs/gcc/Gcov.html2https://nist.gov3https://www.openssl.org/

30

The results, in the Table 4.3, revealed to be quite acceptable, as when compared to RC4,this one is 5 times faster than BSC, but AES is only 1.7 times faster then BSC.

To this test was executed in a machine with a core i7-2620M 2.7 GHz.

Table 4.3: Performance figures obtained with the openssl speed test. The values representthe data encryption speed (in MBytes/s) for different buffer sizes.

Cipher 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes 16384 bytes

RC4 372,80 587,91 690,66 713,01 726,64 725,50AES-128 CBC 93,95 101,36 103,87 244,83 246,91 246,95AES-192 CBC 78,62 84,42 86,84 208,23 208,96 207,32AES-256 CBC 68,66 72,90 73,51 178,85 179,55 178,54BSC 137,16 142,32 143,17 143,09 144,28 143,09

31

32

Chapter 5

Conclusion

5.1 Work overview

With this work we aimed to present a new software efficient stream cipher. Due to theBloom filter technique, we were able to build an FSR with only four stages that proved tohave the desired randomness properties, high period length and high efficiency in memoryspace and time.

In general, there is a complete description of the BSC architecture and of its evolution oneach iteration, considering the limitations of the FSR to enter on short cyclic behavior andthe false positive triggers from the filter. Also the implementation details and considerationswere described with the related studies and results, that led us to the final implementation.Also the S-Boxes that were also a point of intense study, as they are the BSC best defenseagainst correlation attacks and a major influence in the diffusion of the keystream, have beenexplained in high detail.

By the results of the tests, BSC shows that there is no correlation between the input key(and IV) and its output, even for differences of 1-bit on the input, as the amount of modifiedbits on the output between both sequences is half of their size.

As the architecture, the S-Boxes and all update functions are known, the only secret onthis stream cipher is, in fact, the initialization state, which seems to being kept secret, evenon short sequences and to the most known attacks.

Also in questions of performance, BSC presents itself with good results when comparedwith the some of the most used stream ciphers actually.

5.2 Further work

Until the BSC could be released as a public stream cipher, there is some work that couldbe done. One of the most important is to perform the attacks to validate the robustness ofthe cipher.

Other interesting work to be done, is the development of the BSC on a Field-programmablegate array (FPGA), tacking advantage of the parallelism of operations and measure its per-formance.

Also an idea of a reduced version of BSC, could be adapted to work on microcontrollersusing 32-bit words, instead of 64-bit, with special care on the prevention of Time MemoryTrade-off attacks.

33

34

Bibliography

[1] Bloom filters - the math. http://pages.cs.wisc.edu/˜cao/papers/summary-cache/node8.html.

[2] A. Menezes, P. van Oorschot, and S. Vanstone. Handbook of applied cryptography.chapter 6 - Stream Ciphers. CRC Press, 1996.

[3] S. H. Babbage. Improved exhaustive search attacks on stream ciphers, November 2016.

[4] Hagai Bar-El. Introduction to side channel attacks. http://gauss.ececs.uc.edu/Courses/c653/lectures/SideC/intro.pdf.

[5] Red Hat Security Blog. A brief history of cryptography. https://access.redhat.com/blogs/766093/posts/1976023, 2013.

[6] Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commu-nications of the ACM, 13(7):422–426, July 1970.

[7] Diefo Napp, Paulo J. Almeida. Criptografia e Seguranca. Engebook, 2017.

[8] Daniel Genkin, Adi Shamir, and Eran Tromer. Acoustic cryptanalysis. Journal of Cryp-tology, 30(2):392–443, Apr 2017.

[9] Tim Good and Mohammed Benaissa. ASIC Hardware Performance. In New StreamCipher Designs, pages 267–293. Spring, 2008.

[10] Texas Instruments. What’s an LFSR? http://www.ti.com/lit/an/scta036a/scta036a.pdf.

[11] Fredrik Jonsson. Some results on fast correlation attacks. PhD thesis, Lund University,2002.

[12] George Marsaglia. Xorshift RNGs. Journal of Statistical Software. 8 (14), July 2003.

[13] John Mattsson. Stream Cipher Design An evaluation of the eSTREAM candidate PolarBear. Master’s thesis, KTH Royal Institute of Technology, 2006.

[14] Richard A. Mollin. CODES - The Guide To Secrecy From Ancient to Modern Times.Chapman and Hall, 2005.

[15] Christof Paar and Jan Pelzl. Understanding Cryptography. A Textbook for Students andPractitioners. Springer, Heidelberg Dordrecht London New York , 2010.

35

[16] David Bauer Robert G. Brown, Dirk Eddelbuettel. Dieharder: A random number testsuite. https://webhome.phy.duke.edu/˜rgb/General/dieharder.php. Ver-sion 3.31.1.

[17] Bruce Schneier. Applied cryptography : Protocols, Algorithms and Source Code in C.John Wiley and Sons, Inc, 2nd edition, 1996.

[18] C.E. Shannon. Communication theory of secrecy systems. Bell System Technical Journal,28(656-715), 1949.

[19] Andre Zuquete. Seguranca em Redes Informaticas. FCA, Lisbon, 2018.

36

Appendix A

Appendix

A.1 Substitution Box

A.1.1 S Box source code

1 #inc lude <s t d i o . h>2 #inc lude <s t d i n t . h>3 #inc lude <s t d l i b . h>4 #inc lude <memory . h>5 #inc lude <uni s td . h>6

7 u i n t 8 t sbox [ 2 5 6 ] ;8 i n t min non l in xor = 1000 ;9 i n t min non l in sum = 1000 ;

10

11 u i n t 8 t rnd ( )12 {13 s t a t i c i n t i n i t = 0 ;14 u i n t 3 2 t r ;15 u i n t 8 t ∗ r = ( u i n t 8 t ∗) & r ;16

17 i f ( i n i t == 0) {18 srandom ( 0 ) ;19 i n i t = 1 ;20 }21

22 r = random ( ) ;23 re turn r [ 0 ] ˆ ˜ r [ 1 ] ˆ r [ 2 ] ˆ ˜ r [ 3 ] ;24 }25

26 u i n t 8 t ∗27 c lone ( u i n t 8 t ∗ s )28 {29 u i n t 8 t ∗ new = mal loc ( 256 ) ;30 memcpy( new , s , 256 ) ;31

32 re turn new ;33 }

37

34

35 i n t36 ones ( u i n t 8 t x )37 {38 i n t i , sum ;39

40 f o r (sum = i = 0 ; i < 8 ; i++) {41 sum += ( x >> i ) & 1 ;42 }43

44 re turn sum ;45 }46

47 i n t48 notEqual ( u i n t 8 t ∗ s )49 {50 i n t i ;51

52 f o r ( i = 0 ; i < 256 ; i++) {53 i f ( i == s [ i ] ) r e turn 0 ;54 }55 re turn 1 ;56 }57

58 i n t59 bitEntropy ( u i n t 8 t ∗ s )60 {61 i n t i , j , sum ;62

63 f o r (sum = 0 , i = 0 ; i < 256 ; i++) {64 f o r ( j = 0 ; j < 8 ; j++) {65 u i n t 8 t x = s [ i ] ;66 u i n t 8 t y = s [ i ˆ (1 << j ) ] ;67

68 sum += ones ( x ˆ y ) ;69 }70 }71

72 re turn sum == 4 ∗ 8 ∗ 256 ;73 }74

75 i n t76 goodXor ( u i n t 8 t ∗ s )77 {78 i n t i , j , sum ;79

80 f o r (sum = 0 , i = 0 ; i < 256 − 1 ; i++) {81 f o r ( j = i + 1 ; j < 256 ; j++) {82 i f ( s [ i ˆ j ] == ( s [ i ] ˆ s [ j ] ) ) {83 sum++;84 }85 }86 }

38

87

88 re turn sum ;89 }90

91 i n t92 goodSum( u i n t 8 t ∗ s )93 {94 i n t i , j , sum ;95

96 f o r (sum = 0 , i = 0 ; i < 256 − 1 ; i++) {97 f o r ( j = i + 1 ; j < 256 ; j++) {98 i f ( s [ ( i+j ) & 0xFF ] == ( ( s [ i ] + s [ j ] ) & 0xFF) ) {99 sum++;

100 }101 }102 }103

104 re turn sum ;105 }106

107 i n t108 improveBoth ( u i n t 8 t ∗ s )109 {110 i n t i , j ;111 i n t problems [ 2 5 6 ] = { 0 } ;112 i n t max = 0 ;113 i n t max index = −1;114

115 f o r ( i = 0 ; i < 256 − 1 ; i++) {116 f o r ( j = i + 1 ; j < 256 ; j++) {117 i f ( s [ i ˆ j ] == ( s [ i ] ˆ s [ j ] ) ) {118 problems [ i ]++;119 problems [ j ]++;120 i f ( problems [ i ] > max) {121 max = problems [ i ] ;122 max index = i ;123 }124 i f ( problems [ j ] > max) {125 max = problems [ j ] ;126 max index = j ;127 }128 }129 i f ( s [ ( i+j ) & 0xFF ] == ( ( s [ i ] + s [ j ] ) & 0xFF) ) {130 problems [ i ]++;131 problems [ j ]++;132 i f ( problems [ i ] > max) {133 max = problems [ i ] ;134 max index = i ;135 }136 i f ( problems [ j ] > max) {137 max = problems [ j ] ;138 max index = j ;139 }

39

140 }141 }142 }143

144 // p r i n t f ( ”\n\tB %3d %3d\ t ” , max index , max ) ;145

146 max = goodXor ( s ) + goodSum ( s ) ;147 u i n t 8 t new [ 2 5 6 ] ;148 i n t bes t = −1;149

150 f o r ( i = 0 ; i < 256 ; i++) {151 i f ( i == max index ) cont inue ;152

153 memcpy ( new , s , 256 ) ;154 u i n t 8 t tmp = new [ max index ] ;155 new [ max index ] = new [ i ] ;156 new [ i ] = tmp ;157

158 i f ( goodXor ( new ) + goodSum ( new ) < max) {159 max = goodXor ( new ) + goodSum ( new ) ;160 best = i ;161 }162 }163

164 i f ( bes t == −1) re turn 0 ;165

166 u i n t 8 t tmp = s [ max index ] ;167 s [ max index ] = s [ bes t ] ;168 s [ bes t ] = tmp ;169

170 // p r i n t f ( ”\n\tB %3d\ t ” , max ) ;171

172 re turn 1 ;173 }174

175 void176 improveXor ( u i n t 8 t ∗ s )177 {178 i n t i , j ;179 i n t problems [ 2 5 6 ] = { 0 } ;180 i n t max = 0 ;181 i n t max index = −1;182

183 f o r ( i = 0 ; i < 256 − 1 ; i++) {184 f o r ( j = i + 1 ; j < 256 ; j++) {185 i f ( s [ i ˆ j ] == ( s [ i ] ˆ s [ j ] ) ) {186 problems [ i ]++;187 problems [ j ]++;188 i f ( problems [ i ] > max) {189 max = problems [ i ] ;190 max index = i ;191 }192 i f ( problems [ j ] > max) {

40

193 max = problems [ j ] ;194 max index = j ;195 }196 }197 }198 }199

200 u i n t 8 t tmp = s [ max index ] ;201 do {202 i = rnd ( ) ;203 } whi le ( i == max index ) ;204

205 tmp = s [ max index ] ;206 s [ max index ] = s [ i ] ;207 s [ i ] = tmp ;208

209 // p r i n t f ( ”\n\ tx %3d %3d %3d\ t ” , max index , i , max ) ;210 }211

212 void213 improveSum ( u i n t 8 t ∗ s )214 {215 i n t i , j ;216 i n t problems [ 2 5 6 ] = { 0 } ;217 i n t max = 0 ;218 i n t max index = −1;219

220 f o r ( i = 0 ; i < 256 − 1 ; i++) {221 f o r ( j = i + 1 ; j < 256 ; j++) {222 i f ( s [ ( i+j ) & 0xFF ] == ( ( s [ i ] + s [ j ] ) & 0xFF) ) {223 problems [ i ]++;224 problems [ j ]++;225 i f ( problems [ i ] > max) {226 max = problems [ i ] ;227 max index = i ;228 }229 i f ( problems [ j ] > max) {230 max = problems [ j ] ;231 max index = j ;232 }233 }234 }235 }236

237 u i n t 8 t tmp = s [ max index ] ;238 do {239 i = rnd ( ) ;240 } whi le ( i == max index ) ;241

242 tmp = s [ max index ] ;243 s [ max index ] = s [ i ] ;244 s [ i ] = tmp ;245

41

246 // p r i n t f ( ”\n\ t s %3d %3d %3d\ t ” , max index , i , max ) ;247 }248

249 void250 dump ( u i n t 8 t ∗ s )251 {252 i n t i ;253

254 p r i n t f ( ” u i n t 8 t sbox [ 2 5 6 ] = {” ) ;255 f o r ( i = 0 ; i < 256 ; i++) {256 i f ( i % 16 == 0) p r i n t f ( ”\n” ) ;257 i f ( i == 0) p r i n t f ( ”0x%x” , s [ i ] ) ;258 e l s e p r i n t f ( ” ,0 x%x” , s [ i ] ) ;259 }260 p r i n t f ( ” } ;\n” ) ;261 f f l u s h ( stdout ) ;262 }263

264

265 void266 improve ( u i n t 8 t ∗ s )267 {268 i n t i ;269 i n t gx , gs ;270

271 gx = goodXor ( s ) ;272 gs = goodSum( s ) ;273 p r i n t f ( ”X %3d S %3d\ t ” , gx , gs ) ;274

275 f o r ( i = 0 ; i < 1024 && ( gx != 0 | | gs != 0) ; ) {276 i f ( gx != 0 && gs != 0) {277 i f ( improveBoth ( s ) == 0) {278 break ;279 }280 }281 e l s e i f ( gx != 0) {282 improveXor ( s ) ;283 i f ( goodXor ( s ) >= gx ) i ++;284 }285 e l s e i f ( gs != 0) {286 improveSum ( s ) ;287 i f ( goodSum ( s ) >= gs ) i ++;288 }289 gx = goodXor ( s ) ;290 gs = goodSum( s ) ;291 }292

293 p r i n t f ( ”X %3d S %3d\n” , gx , gs ) ;294

295 i f ( gx == 0 && gs == 0) {296 i f ( bitEntropy ( s ) == 1 && notEqual ( s ) == 1) {297 dump ( s ) ;298 e x i t ( 0 ) ;

42

299 }300 }301

302 f r e e ( s ) ;303

304 re turn ;305 }306

307 i n t308 main ( )309 {310 i n t i ;311

312 f o r ( ; ; ) {313

314 // F i l l SBOX with the i n i t i a l ( non−random ) sequence o f a l l 0−255va lue s

315

316 f o r ( i = 0 ; i < s i z e o f ( sbox ) ; i++) {317 sbox [ i ] = ( u i n t 8 t ) i ;318 }319

320 // Randomize SBOX321

322 f o r ( i = 0 ; i < s i z e o f ( sbox ) ; i++) {323 u i n t 8 t o f f s e t , tmp ;324

325 o f f s e t = rnd ( ) ;326 o f f s e t %= 256 − i ;327

328 tmp = sbox [256 − i − 1 ] ;329 sbox [256 − i − 1 ] = sbox [ o f f s e t ] ;330 sbox [ o f f s e t ] = tmp ;331 }332

333 // Improve i t s q u a l i t y334

335 improve ( c l one ( sbox ) ) ;336 }337 }

43

A.1.2 Resultant Substitution Box

1 u i n t 8 t sbox [ 2 5 6 ] = {2 0xDB, 0 x20 , 0 xE6 , 0xCF, 0 x8A , 0 xB2 , 0 x43 , 0 x26 , 0xBC, 0 xA5 , 0 x91 , 0 x6B , 0xCA, 0xCC,3 0x37 , 0 x46 , 0 xE0 , 0 x5F , 0 x6F , 0 x1E , 0 xA7 , 0 x6C , 0 x56 , 0xFA, 0 xF7 , 0 x6D , 0 x07 , 0xBF,4 0x77 , 0xAB, 0 x49 , 0 x2A , 0 x66 , 0xEB, 0 x00 , 0 xB1 , 0 xA4 , 0 xB4 , 0 x21 , 0xAA, 0 x93 , 0 xD3 ,5 0x11 , 0 x02 , 0 x65 , 0 x92 , 0 x96 , 0 x1C , 0 x29 , 0 x98 , 0 x9F , 0 x9C , 0 xC7 , 0 xE5 , 0xDE, 0 x25 ,6 0x5E , 0 xA0 , 0 x34 , 0 x0C , 0 x0A , 0 x13 , 0 x1F , 0 xE4 , 0 x85 , 0 xD4 , 0xFF, 0 xA9 , 0 x17 , 0 x5A ,7 0x8F , 0 xC2 , 0 x5C , 0 xB0 , 0 xE8 , 0 xA6 , 0 x8C , 0 x84 , 0 x9A , 0 x1B , 0 x83 , 0 x71 , 0xDA, 0 xF4 ,8 0xD7 , 0 x23 , 0xFB, 0 xB5 , 0 x38 , 0xBA, 0 x87 , 0 xE9 , 0 x04 , 0 xA8 , 0 x18 , 0xFE, 0 x2D , 0 x1D ,9 0x32 , 0 x5B , 0 x55 , 0xAE, 0 xD1 , 0 x62 , 0 x2E , 0 x2B , 0 x0B , 0 x7C , 0 x8B , 0 x0F , 0 x63 , 0 xA2 ,

10 0xBB, 0 x54 , 0 xE7 , 0xFC, 0 x33 , 0 x08 , 0xEF, 0xAD, 0 x3B , 0 x09 , 0 x67 , 0xDD, 0 x16 , 0xDF,11 0x3E , 0 xB8 , 0 xC9 , 0 xB9 , 0 x7D , 0 x2F , 0xCD, 0 x9E , 0 xF5 , 0 xC5 , 0 xB6 , 0xAC, 0 x53 , 0 x4C ,12 0x6E , 0 x69 , 0 xC6 , 0 xF1 , 0 x7F , 0 x97 , 0 x80 , 0 x7E , 0 x81 , 0 x7B , 0 xA1 , 0 xA3 , 0 x39 , 0 x72 ,13 0x3F , 0 x68 , 0 x70 , 0 x05 , 0 x60 , 0 x5D , 0 xC1 , 0 xD5 , 0 xD0 , 0 x47 , 0 x64 , 0 x14 , 0 x79 , 0 x94 ,14 0x30 , 0 x28 , 0 xC4 , 0 xD8 , 0 x3C , 0 x15 , 0xED, 0 x42 , 0 x2C , 0 x36 , 0 xD2 , 0 x61 , 0 x73 , 0xBD,15 0x35 , 0 xC0 , 0 xF6 , 0 xF3 , 0 xD9 , 0 x12 , 0 x7A , 0 x59 , 0 x8D , 0 x3A , 0 x51 , 0 x1A , 0 x4F , 0 x0D ,16 0xF8 , 0 xF2 , 0 xB3 , 0 x95 , 0 xF0 , 0 x52 , 0 x82 , 0 x4D , 0 x27 , 0 x88 , 0 x10 , 0 x75 , 0 xD6 , 0 x78 ,17 0xCE, 0 x01 , 0 x89 , 0 x41 , 0 xB7 , 0 x45 , 0 xF9 , 0 xC3 , 0 x57 , 0 xE3 , 0 x4E , 0xAF, 0 x06 , 0xDC,18 0xCB, 0 x31 , 0 x6A , 0 x99 , 0xFD, 0 x24 , 0 x8E , 0 x22 , 0 x3D , 0 x48 , 0 x9D , 0 x50 , 0 x0E , 0 x74 ,19 0xBE, 0 x58 , 0 x86 , 0 x19 , 0 xE2 , 0xEE, 0 x90 , 0 xC8 , 0 x4B , 0 x03 , 0 x44 , 0 x4A , 0xEC, 0 xE1 ,20 0x40 , 0 x9B , 0xEA, 0 x76 } ;

44

A.2 Correlation source code

1 #inc lude <s t d i o . h>2

3 i n t main ( i n t argc , char ∗∗ argv )4 {5 #d e f i n e N 10246 unsigned char f [ argc ] [ N ] ;7 i n t i , j , k , c ,m;8 FILE ∗ fp ;9 f o r ( i = 1 ; i < argc ; i++)

10 {11 fp = fopen ( argv [ i ] , ” rb” ) ;12 i f ( f r ead ( f [ i ] , 1 ,N, fp ) != N)13 re turn 1 ;14 f c l o s e ( fp ) ;15 }16

17 p r i n t f ( ” | ” ) ;18 f o r ( i = 1 ; i < argc ; i++)19 p r i n t f ( ” %6d” , i ) ;20 p r i n t f ( ”\n” ) ;21 p r i n t f ( ”−− +” ) ;22 f o r ( i = 1 ; i < argc ; i++)23 p r i n t f ( ” −−−−−−” ) ;24 p r i n t f ( ”\n” ) ;25 f o r ( i = 1 ; i < argc ; i++)26 {27 p r i n t f ( ”%2d | ” , i ) ;28 f o r ( j = 1 ; j < argc ; j++)29 {30 c = 0 ;31 f o r ( k = 0 ; k < N; k++)32 f o r (m = ( f [ i ] [ k ] ˆ f [ j ] [ k ] ) & 255 ;m != 0 ;m &= m − 1)33 c++;34 // n i g u a i s = 8∗N−c −> peso +135 // n d i f e r e n t e s = c −> peso −136 // (8 ∗ N − c ) ∗ (+1) + c ∗ (−1) = 8 ∗ N − 2 ∗ c37 p r i n t f ( ” %6.3 f ” , ( double ) (8 ∗ N − 2 ∗ c ) / ( double ) (8 ∗ N) ) ;38 }39 p r i n t f ( ”\n” ) ;40 }41 }

45

A.3 Statistical test results

A.3.1 Dieharder

#=============================================================================## dieharder ve r s i on 3 . 3 1 . 1 Copyright 2003 Robert G. Brown ##=============================================================================#

rng name | f i l ename | rands / second |mt19937 | bsc | 1 .10 e+08 |

#=============================================================================#test name | ntup | tsamples | psamples | p−value | Assessment

#=============================================================================#diehard b i r thdays | 0 | 100 | 100 |0 .65824784 | PASSED

diehard operm5 | 0 | 1000000 | 100 |0 .02955276 | PASSEDdiehard rank 32x32 | 0 | 40000 | 100 |0 .53419246 | PASSED

diehard rank 6x8 | 0 | 100000 | 100 |0 .63520508 | PASSEDdiehard b i t s t r eam | 0 | 2097152 | 100 |0 .48494204 | PASSED

diehard opso | 0 | 2097152 | 100 |0 .69318365 | PASSEDdiehard oqso | 0 | 2097152 | 100 |0 .66419526 | PASSEDdiehard dna | 0 | 2097152 | 100 |0 .05506192 | PASSED

d i eha rd c oun t 1 s s t r | 0 | 256000 | 100 |0 .93276661 | PASSEDdiehard count 1 s byt | 0 | 256000 | 100 |0 .80317024 | PASSEDd i eha rd pa rk i ng l o t | 0 | 12000 | 100 |0 .63055103 | PASSED

diehard 2dsphere | 2 | 8000 | 100 |0 .69045753 | PASSEDdiehard 3dsphere | 3 | 4000 | 100 |0 .99651599 | WEAKdiehard squeeze | 0 | 100000 | 100 |0 .98699753 | PASSED

diehard sums | 0 | 100 | 100 |0 .02504065 | PASSEDdiehard runs | 0 | 100000 | 100 |0 .65959675 | PASSEDdiehard runs | 0 | 100000 | 100 |0 .28273906 | PASSED

diehard c raps | 0 | 200000 | 100 |0 .42626904 | PASSEDdiehard c raps | 0 | 200000 | 100 |0 .94050041 | PASSED

marsag l i a t sang gcd | 0 | 10000000 | 100 |0 .66543045 | PASSEDmarsag l i a t sang gcd | 0 | 10000000 | 100 |0 .43759852 | PASSED

sts monobit | 1 | 100000 | 100 |0 .85130608 | PASSEDs t s r un s | 2 | 100000 | 100 |0 .43534495 | PASSED

s t s s e r i a l | 1 | 100000 | 100 |0 .83811328 | PASSEDs t s s e r i a l | 2 | 100000 | 100 |0 .80327843 | PASSEDs t s s e r i a l | 3 | 100000 | 100 |0 .17620232 | PASSEDs t s s e r i a l | 3 | 100000 | 100 |0 .23594699 | PASSEDs t s s e r i a l | 4 | 100000 | 100 |0 .52408778 | PASSEDs t s s e r i a l | 4 | 100000 | 100 |0 .38892856 | PASSEDs t s s e r i a l | 5 | 100000 | 100 |0 .48560753 | PASSEDs t s s e r i a l | 5 | 100000 | 100 |0 .93766933 | PASSEDs t s s e r i a l | 6 | 100000 | 100 |0 .69165187 | PASSEDs t s s e r i a l | 6 | 100000 | 100 |0 .24254628 | PASSEDs t s s e r i a l | 7 | 100000 | 100 |0 .91508246 | PASSEDs t s s e r i a l | 7 | 100000 | 100 |0 .76439209 | PASSEDs t s s e r i a l | 8 | 100000 | 100 |0 .48991189 | PASSEDs t s s e r i a l | 8 | 100000 | 100 |0 .86620977 | PASSEDs t s s e r i a l | 9 | 100000 | 100 |0 .46435450 | PASSEDs t s s e r i a l | 9 | 100000 | 100 |0 .85001005 | PASSEDs t s s e r i a l | 10 | 100000 | 100 |0 .38273328 | PASSEDs t s s e r i a l | 10 | 100000 | 100 |0 .99339158 | PASSEDs t s s e r i a l | 11 | 100000 | 100 |0 .95050676 | PASSEDs t s s e r i a l | 11 | 100000 | 100 |0 .81840634 | PASSEDs t s s e r i a l | 12 | 100000 | 100 |0 .70716926 | PASSEDs t s s e r i a l | 12 | 100000 | 100 |0 .78207039 | PASSEDs t s s e r i a l | 13 | 100000 | 100 |0 .82188694 | PASSEDs t s s e r i a l | 13 | 100000 | 100 |0 .56530908 | PASSEDs t s s e r i a l | 14 | 100000 | 100 |0 .78638269 | PASSEDs t s s e r i a l | 14 | 100000 | 100 |0 .21571955 | PASSEDs t s s e r i a l | 15 | 100000 | 100 |0 .98655906 | PASSEDs t s s e r i a l | 15 | 100000 | 100 |0 .96262452 | PASSEDs t s s e r i a l | 16 | 100000 | 100 |0 .65719482 | PASSEDs t s s e r i a l | 16 | 100000 | 100 |0 .66999784 | PASSED

r gb b i t d i s t | 1 | 100000 | 100 |0 .30971398 | PASSEDr gb b i t d i s t | 2 | 100000 | 100 |0 .91383895 | PASSEDr gb b i t d i s t | 3 | 100000 | 100 |0 .05462643 | PASSEDr gb b i t d i s t | 4 | 100000 | 100 |0 .29646545 | PASSEDr gb b i t d i s t | 5 | 100000 | 100 |0 .83591600 | PASSEDr gb b i t d i s t | 6 | 100000 | 100 |0 .77226805 | PASSEDr gb b i t d i s t | 7 | 100000 | 100 |0 .60459703 | PASSEDr gb b i t d i s t | 8 | 100000 | 100 |0 .43941350 | PASSEDr gb b i t d i s t | 9 | 100000 | 100 |0 .14452602 | PASSEDr gb b i t d i s t | 10 | 100000 | 100 |0 .08224741 | PASSEDr gb b i t d i s t | 11 | 100000 | 100 |0 .49268850 | PASSEDr gb b i t d i s t | 12 | 100000 | 100 |0 .35574111 | PASSED

rgb minimum distance | 2 | 10000 | 1000 |0 .02898202 | PASSEDrgb minimum distance | 3 | 10000 | 1000 |0 .81079113 | PASSEDrgb minimum distance | 4 | 10000 | 1000 |0 .28035144 | PASSEDrgb minimum distance | 5 | 10000 | 1000 |0 .84416335 | PASSED

rgb permutat ions | 2 | 100000 | 100 |0 .93569515 | PASSEDrgb permutat ions | 3 | 100000 | 100 |0 .49013350 | PASSEDrgb permutat ions | 4 | 100000 | 100 |0 .46959042 | PASSEDrgb permutat ions | 5 | 100000 | 100 |0 .72625156 | PASSED

rgb lagged sum | 0 | 1000000 | 100 |0 .37522549 | PASSEDrgb lagged sum | 1 | 1000000 | 100 |0 .85800287 | PASSEDrgb lagged sum | 2 | 1000000 | 100 |0 .02720481 | PASSED

46

rgb lagged sum | 3 | 1000000 | 100 |0 .47793556 | PASSEDrgb lagged sum | 4 | 1000000 | 100 |0 .26524540 | PASSEDrgb lagged sum | 5 | 1000000 | 100 |0 .28845818 | PASSEDrgb lagged sum | 6 | 1000000 | 100 |0 .49417201 | PASSEDrgb lagged sum | 7 | 1000000 | 100 |0 .46487869 | PASSEDrgb lagged sum | 8 | 1000000 | 100 |0 .59981674 | PASSEDrgb lagged sum | 9 | 1000000 | 100 |0 .45791953 | PASSEDrgb lagged sum | 10 | 1000000 | 100 |0 .57389510 | PASSEDrgb lagged sum | 11 | 1000000 | 100 |0 .79621146 | PASSEDrgb lagged sum | 12 | 1000000 | 100 |0 .74881471 | PASSEDrgb lagged sum | 13 | 1000000 | 100 |0 .42387648 | PASSEDrgb lagged sum | 14 | 1000000 | 100 |0 .76995497 | PASSEDrgb lagged sum | 15 | 1000000 | 100 |0 .92828655 | PASSEDrgb lagged sum | 16 | 1000000 | 100 |0 .82128349 | PASSEDrgb lagged sum | 17 | 1000000 | 100 |0 .98276114 | PASSEDrgb lagged sum | 18 | 1000000 | 100 |0 .32851196 | PASSEDrgb lagged sum | 19 | 1000000 | 100 |0 .92393051 | PASSEDrgb lagged sum | 20 | 1000000 | 100 |0 .15805439 | PASSEDrgb lagged sum | 21 | 1000000 | 100 |0 .98188483 | PASSEDrgb lagged sum | 22 | 1000000 | 100 |0 .25532516 | PASSEDrgb lagged sum | 23 | 1000000 | 100 |0 .66896563 | PASSEDrgb lagged sum | 24 | 1000000 | 100 |0 .91806031 | PASSEDrgb lagged sum | 25 | 1000000 | 100 |0 .84337164 | PASSEDrgb lagged sum | 26 | 1000000 | 100 |0 .36564850 | PASSEDrgb lagged sum | 27 | 1000000 | 100 |0 .40148954 | PASSEDrgb lagged sum | 28 | 1000000 | 100 |0 .74480305 | PASSEDrgb lagged sum | 29 | 1000000 | 100 |0 .20766941 | PASSEDrgb lagged sum | 30 | 1000000 | 100 |0 .98712281 | PASSEDrgb lagged sum | 31 | 1000000 | 100 |0 .85345620 | PASSEDrgb lagged sum | 32 | 1000000 | 100 |0 .41682525 | PASSED

r g b k s t e s t t e s t | 0 | 10000 | 1000 |0 .49503861 | PASSEDdab byt ed i s t r i b | 0 | 51200000 | 1 |0 . 37525219 | PASSED

dab dct | 256 | 50000 | 1 |0 . 68351224 | PASSEDPreparing to run t e s t 207 . ntuple = 0

d a b f i l l t r e e | 32 | 15000000 | 1 |0 . 72901193 | PASSEDd a b f i l l t r e e | 32 | 15000000 | 1 |0 . 30514018 | PASSED

Preparing to run t e s t 208 . ntuple = 0d a b f i l l t r e e 2 | 0 | 5000000 | 1 |0 . 25254913 | PASSEDd a b f i l l t r e e 2 | 1 | 5000000 | 1 |0 . 71651136 | PASSED

Preparing to run t e s t 209 . ntuple = 0dab monobit2 | 12 | 65000000 | 1 |0 . 13716598 | PASSED

47

48