BSC - Bloom based stream cipher

Abstract

A Linear Feedback Shift Register (LFSR) is a building block that is frequently used to build fast, hardware-based stream ciphers. However, the fact that an LFSR is bit oriented makes it inefficient when implemented by microprocessors. On the other hand, LFSR’s have a very well-defined internal behavior, defined by a carefully chosen (primitive) feedback polynomial, which facilitates the evaluation of their quality using mathematical tools but also their cryptanalysis. This work consisted on creating a generalized LFSR where the information stored in each stage of the shift register is a 64-bit word, instead of a single bit. Furthermore, a variable feedback polynomial is used instead of a fixed one, for making cryptanalysis harder. The variability of the feedback polynomial is given by the state of a Bloom filter. A Bloom filter is a well defined construction used to detect a possible repetition of a value observed in the past, and was used in our stream generator to provide a hard-to-model, always changing state. The evolution of the Bloom filter state is cyclic, in the sense that during some iterations it accumulates ones (1’s), while in other iterations it accumulates zeros (0’s). The number of iterations in each case is not fixed, it is given by an accumulated number of collisions in the Bloom filter itself.

Um Linear Feedback Shift Register (LFSR) é um elemento base usado frequentemente para desenvolver cifras contínuas, baseadas em hardware, de forma rápida. Contudo, pelo facto de serem orientados ao bit tornam-se ineficientes quando implementadas em microprocessadores. Por outro lado, os LFSRs têm um comportamento bem conhecido, definido pelo seu polinómio de realimentação, o que facilita a análise das suas propriedades com recurso a ferramentas matemáticas mas também a sua cripto análise. Este trabalho consistiu na criação de um LFSR generalizado cujos registos possuem palavras de 64 bits em vez de um único. Utiliza-se também um polinómio de realimentação variável, com vista a dificultar a sua criptanalise. A variabilidade do gerador é definida por um filtro de Bloom. Um filtro de Bloom é um método bem conhecido para detetar possı́veis repetições de um valor e é utilizado neste gerador com vista a torná-lo difı́cil de analisar devido ao seu estado em constante modificação. O estado do filtro é cı́clico, visto que em algumas iterações acumula uns (1’s) enquanto que nas seguintes acumula zeros (0’s). O número de iterações em cada caso varia com o número de colisões detetados pelo próprio filtro.