Демонстрация новых возможностей взлома AES

//Демонстрация новых возможностей взлома AES

http://www.cryptosystem.net/aes/
http://ntcourtois.free.fr/quovadis4/
http://security.computerworld.pl/news/91316.html

26 мая 2006 года (незадолго до EUROCRYPT 2006) на конференции Quo Vadis IV
Николя Тадеуш Куртуа (польский криптограф, живущий во Франции) представит практическое доказательство существования алгебраических атак, оптимизированных против шифра AES-RIJNDAEL. За полтора часа на своём ноутбуке он осуществит демовзлом всего лишь по нескольким шифртекстам близкого аналога RIJNDAEL. Хотя это будет модельный шифр, он будет таким же стойким, в нём не будет добавлено существенных слабостей, он будет иметь такие же хорошие диффузионные характеристики и устойчивость ко всем известным до этого видам криптоанализа. Единственным отличием будут изменённые в рамках модели алгебраических атак параметры S-блоков и уменьшенное для наглядности число раундов. Однако этого достаточно, чтобы убедить скептиков в реальности алгебраических атак.

Предыстория вопроса такова.

В своей первой работе, написанной ещё в 2001 году
!!(green) Nicolas T. Courtois и Josef Pieprzyk "Cryptanalysis of Block Ciphers with Overdefined System of Equations" !!
показали принципиально новый метод взлома шифров на основе решения систем уравнений в конечном поле. Главной мишенью послужили шифры SERPENT (из-за малого размера S-блоков) и AES-RIJNDAEL из-за его своебразной алгебраической структуры. Шифр RIJNDAEL может быть представлен в виде простой замкнутой алгебраической функции на полем GF(256), что было рассмотрено в работе
!!(green)
Ferguson N., Schroeppel R. and Whiting D. "A simple algebraic representation of Rijndael"
!!

Выводом из этой работы и работ Николя Куртуа служит то, что стойкость AES-RIJNDAEL опирается только на невозможность на данный момент решить систему уравнений, описывающую алгебраическую структуру шифра. Если такое решение будет найдено, то это будет серьёзным прорывом в криптоанализе, так как такие атаки не используют малозначительные вероятностные отклонения в гигантских объёмах исходных данных (как дифференциальный или линейный криптоанализ) и для их работы будет достаточно небольшого количества пар открытых/шифртекстов.

Сначала XSL-атаки считались невозможными, а работы по ним – ошибочными. Тем не менее авторам удалось частично применить их к модельным шифрам, а против некоторых поточных шифров достичь и практических результатов и получить таким образом признание. Теперь новые шифры стараются проектировать устойчивыми и к алгебраическим атакам.

Однако алгебраические атаки всё ещё считались непрактичными, сложными, эвристически-негарантированными по результату, связанными с большим объёмом вычислений, возможно превосходящим атаки грубой силой на AES.

Как говорил один из создателей шифра RIJNDAEL в частной переписке – "XSL – это не атака, это всего лишь мечта". "Это мечта, способная стать кошмаром" – отвечал Николя Куртуа.

В любом случае это всё пока лишь интересные события в мире теоретической криптографии. Полный взлома шифра и снятие его со стандарта может состоятся не ранее чем через десять-тридцать лет, как оптимистично (со своей позиции давнего противника RIJNDAEL) заявляет Куртуа. Хотя кто может достоверно предсказать будущее? Кто может гарантировать, что AES-RIJNDAEL, SERPENT, CAMELLIA, считающиеся уязвимыми к (несуществующим официально пока) алгебраичесим атакам тайно не взломаны уже сейчас? Хотя это и представляется маловероятным.