A statistical estimation algorithm of the weight distribution of a linear code is shown, based on using its generator matrix as a compression function on random bit strings.
Lee and Brickell observed @cite_3 that the best cryptanalytic attack consisted in choosing a set @math of @math random elements of @math , selecting the corresponding columns of @math as a @math matrix @math , and computing @math . If @math , this procedure returns the correct @math . They also observe that not only is it costly to invert a random @math matrix, there is also a cost associated with checking that the result is correct: if @math , then @math . One would therefore also have to compute @math to be able to claim that @math .
@cite_3
2765992693
In this paper, we propose an algorithm for constructing guess-and-determine attacks on keystream generators and apply it to the cryptanalysis of the alternating step generator (ASG) and two its modifications (MASG and MASG0). In a guess-and-determine attack, we first “guess” some part of an initial state and then apply some procedure to determine, if the guess was correct and we can use the guessed information to solve the problem, thus performing an exhaustive search over all possible assignments of bits forming a chosen part of an initial state. We propose to use in the “determine” part the algorithms for solving Boolean satisfiability problem (SAT). It allows us to consider sets of bits with nontrivial structure. For each such set it is possible to estimate the runtime of a corresponding guess-and-determine attack via the Monte-Carlo method, so we can search for a set of bits yielding the best attack via a black-box optimization algorithm augmented with several SAT-specific features. We constructed and implemented such attacks on ASG, MASG, and MASG0 to prove that the constructed runtime estimations are reliable. We show, that the constructed attacks are better than the trivial ones, which imply exhaustive search over all possible states of the control register, and present the results of experiments on cryptanalysis of ASG and MASG MASG0 with total registers length of 72 and 96, which have not been previously published in the literature.