Novel tests for the security examination of pseudorandom bit generators

Abstract

The cryptographical security of a stream cipher technique for information protection based on a class of the pseudorandom bit generators (PRBG's) is considered. In structure of the considered class of PRBG's certain internal binary sequences exist, such that the following is valid: each internal sequence depends of the secret key part only, and the generator output sequence is a transformation of these sequences. A statistical testing approach for the resistance examination of the PRBG's on certain cryptanalytic correlation attacks is proposed. Two novel statistical tests are presented and discussed. The test functions based on the sequence comparison concept, and corresponding relevant probability distributions are given. Each test is designed so that its satisfaction implies that the corresponding cryptanalytic attack is not feasible. The PRBG is examined by testing the hypotheses that transformation of a certain internal sequence into the PRBG output can not be described by the underlying models for the attacks. Realization of the tests is an extremely fewer complex problem than trying to apply any one of the attacks, because each test realization is a nonexponential complex problem whereas the corresponding cryptanalytic attack needs examination of 2η hypotheses where η is dimension of the relevant key part.