15.11 // Крипто // Осуществлена первая алгебраическая атака на DES

Сенсационный результат был представлен в работе Николя Куртуа и Грегори Барта "Алгебраический криптоанализ стандарта шифрования данных". Им удалось впервые осуществить алгебраическую атаку на блочный шифр, не созданный на основе алгебраических преобразований и считающийся не имеющим алгебраической структуры.

Использовалось свойство небольших размеров S-блоков DES, что позволило создать систему уравнений относительно компактного размера: 2900 переменных, 3056 уравнений и 4331 одночленов. (Напомним, что ближайший аналог DES — российский шифр ГОСТ — имеет ещё более простую структуру. Малые размеры S-блоков используются также в шифре Serpent.)

И хотя атака непрактична — осуществима только против 6 раундов DES на PC, — тем не менее, для её проведения требуется всего одна пара открытого текста (что является безпрецендентным успехом по сравнению с дифференциальным и линейным криптоанализом) и всего несколько секунд времени (полный взлом DES также возможен, но авторы не приводят оценки затрат ресурсов). Атака возможна против DES с любым модифицированным набором S-блоков такого же размера, кроме того, это всего лишь первая алгебраическая атака против шифра без "алгебраической" раундововой функции, что является важным доказательством универсальности этого метода.

AES пока более устойчив к "шестираундовой атаке", так как он описывается системой уравнений с количеством одночленов, равным 27400.

Авторы предупреждают, что дальнейшее развитие этого метода может позволить взламывать хэш-функции, коды аутентификации сообщений (MAC) и, возможно, все существующие шифры, созданные с возможностью компактного аппаратного исполнения и без учёта стойкости к данным атакам.

Источник: http://eprint.iacr.org/2006/402