Алгебраические атаки на некоторые низкоресурсные шифры на основе функций с малым числом выходных бит

Вводится новый класс атак, применимых к низкоресурсным функциям симметричной криптографии. Основная идея атак основана на использовании специальных функций, получаемых из оригинальных за счёт рассмотрения малого числа выходных бит. Задачи обращения специальных функций существенно более просты для используемых в алгебраическом криптоанализе комбинаторных алгоритмов (SAT-решателей), чем задачи обращения функций, из которых они строятся. Однако для специальной функции, ввиду того, что её выход существенно короче входа, задача обращения имеет не единственное решение. Для достижения единственности по ключу описывается процедура клонирования функции, в рамках которой специальные функции строятся для одного ключа и нескольких различных фрагментов открытых данных. Операция клонирования специальных функций выполняется на And-Inverter-графах (AIG), представляющих данные функции. Во многих случаях размер AIG может быть существенно уменьшен за счёт применения алгоритмов AIG-минимизации. Результатом совместного использования перечисленных техник являются алгебраические атаки, которые для ряда поточных шифров могут быть существенно более эффективными в сравнении с аналогичными атаками на функции, представляющие рассматриваемые шифры стандартным образом.