A time-memory trade-off attack to bit search generator and its variants

In 2004, A. Gouget and H. Sibert proposed a new keystream generator called the Bit Search Generator (BSG), to provide high resistance against algebraic attacks. BSG has a very simple algorithm and attractive properties. However it has been cryptanalyzed in different studies by using the fact that output of BSG can be uniquely expressed by differential of the input sequence. Recently, Gouget et. al introduced two modified versions of BSG, named as MBSG and ABSG, to increase its security and also presented their security analysis in the same paper. The best attack that they give against ABSG and MBSG has complexity O(2(L/2)) and requires O(L2(L/2)) bits of keystream. In this study, we have shown that BSG, MBSG and ABSG can be cryptanalyzed with a time complexity O(2(L/3)) by using a time-memory trade-off attack. The method requires 2(2L/3) words of memory and O(2L + 2(L/3)) bits of keystream. According to computer simulation results, we have found out that MBSG is the most vulnerable generator among BSG and variants to proposed attack. Moreover, ABSG doesn't bring any additional security to original BSG for proposed time-memory trade-off attack.