openPGP в России

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

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

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

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

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

Однако алгебраические атаки всё ещё считались непрактичными, сложными, эвристически-негарантированными по результату, связанными с большим объёмом вычислений, возможно превосходящим атаки грубой силой на AES. Как говорил один из создателей шифра RIJNDAEL в частной переписке: "XSL — это не атака, это всего лишь мечта". "Это мечта, способная стать кошмаром", — отвечал Николя Куртуа.

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

Источник: "openPGP в России"^[link4]