Атаки из класса “угадывай и определяй” и автоматические способы их построения

Представлен краткий обзор подходов к построению криптографических атак, относящихся к классу “угадывай и определяй”. Основной акцент сделан на относительно недавних работах, в которых описаны автоматические способы построения таких атак с ипользованием алгоритмов решения проблемы булевой выполнимости (SAT). С этой целью задачи построения атак из рассматриваемого класса ставятся как задачи оптимизации на булевом гиперкубе специальных оценочных функций. Для решения последних используются метаэвристические алгоритмы, широко применяемые в дискретной оптимизации. В упомянутых работах введены два типа оценочных функций, которые можно рассматривать как конкретизации понятий “UNSAT-иммунность” и “SAT-иммунность”, неформально введённых Н. Куртуа в 2012 г. Приведены примеры построения атак указанного типа для ряда блочных и поточных алгоритмов шифрования.