Guess-and-determine attacks and automatic methods for their construction

In the paper, a brief review of approaches to construction of cryptographic attacks from the class “guess-and-determine” is presented. The main focus is done on recent works, in which some automatic methods for constructing SAT-based guess-and-determine attacks were proposed. With that purpose, the problems of constructing corresponding attacks are stated as optimization problems for specific evaluation functions over Boolean hypercube. To solve the latter, the metaheuristic algorithms widely employed in discrete optimization are used. In the mentioned papers, two types of evaluation functions were formally introduced. Those can be viewed as concretizations of the notions of “UNSAT-immunity” and “SAT-immunity” informally introduced by N. Courtois in 2012. Within the report, several examples of constructing guess-and-determine attacks of the mentioned type on a number of block and stream ciphering algorithms will be given.