В октябре 2024 года мировые СМИ стали распространять пугающие новости о том, что китайским учёным якобы удалось взломать современные криптографические шифры военного применения с помощью квантового компьютера D-Wave Advantage (на фото вверху).
Эти новости основаны не на пустых словах, а на научной статье от группы исследователей под руководством д-ра Ван Чао (Wang Chao) из Шанхайского университета. Статья опубликована в сентябре 2024 года в журнале Chinese Journal of Computers. Авторы использовали D-Wave Advantage для успешной атаки на три алгоритма — Present, Gift-64 и Rectangle, которые являются критически важными для расширенного стандарта шифрования (AES), используемого для защиты данных в правительственном, военном и финансовом секторах.
Западные эксперты по криптографии изучили статью и оценили достижения китайских коллег.
Авторы научной статьи отмечают, что их успех впервые выявил «реальную и существенную угрозу» взлома вышеперечисленных шифров.
Угроза может распространиться и на AES-256 — шифр, который считался абсолютно безопасным. Исследователи заявили, что им не удалось взломать AES-256, но они подошли к этому «ближе, чем когда-либо прежде».
Квантовый отжиг
Квантовый компьютер Advantage от компании D-Wave Systems для вычислений использует технологию квантовой нормализации (квантового отжига). Согласно Википедии, это «довольно общий метод нахождения глобального минимума некоторой заданной функции среди некоторого набора решений-кандидатов. Преимущественно используется для решения задач, где поиск происходит по дискретному множеству с множеством локальных минимумов».
Метод называют «отжигом» по аналогии с металлургией. Подобно тому, как металлы укрепляются и очищаются путём многократного нагрева и охлаждения, квантовый отжиг проводит систему через различные энергетические состояния, а затем постепенно переводит её в самое низкое, которое представляет собой наилучшее решение проблемы.
Пример расписания отжига двух функций, источник
В некотором смысле, квантовый компьютер для вычислений использует законы физики: «Он обладает уникальным эффектом квантового туннелирования, который позволяет выходить из локальных экстремумов, в которые склонны попадать традиционные алгоритмы», — пишут авторы.
128-кубитный сверхпроводящий адиабатический процессор D-Wave Systems для квантового отжига, источник
Криптография в безопасности
Алгоритмы Present, Gift-64 и Rectangle используют структуру SP-сети (Substitution-Permutation Network, SPN), которая является частью стандарта AES. Но все три — легковесные блочные шифры с ограниченной сферой применения во встроенных системах с ограниченными вычислительными возможностями.
Исследователи из Шанхайского университета предложили новую вычислительную архитектуру для симметричного криптоанализа: Quantum Annealing-Classical Mixed Cryptanalysis (QuCMC), которая сочетает алгоритм квантового отжига с традиционными математическими методами.
Цитата из научной статьи:
«Используя архитектуру QuCMC, мы сначала применили свойство деления для описания правил распространения линейных и нелинейных слоёв в алгоритмах симметричных шифров со структурой SPN.
Затем задачи поиска отличителя структуры SPN были преобразованы в задачи смешанного целочисленного линейного программирования (MILP). Эти MILP-модели были преобразованы в D-Wave ограниченные квадратичные модели (CQM), использующие эффект квантового туннелирования, вызванный квантовыми флуктуациями, для выхода из локальных минимумов и достижения оптимального решения, соответствующего интегральному отличителю (integral distinguisher) для атакуемых алгоритмов шифрования. Эксперименты, провед`нные с использованием квантового компьютера D-Wave Advantage, позволили успешно осуществить атаки на три репрезентативных алгоритма структуры SPN: PRESENT, GIFT-64 и RECTANGLE, и успешно проведён поиск интегральных отличителей до 9 раунда. Результаты экспериментов показывают, что алгоритм квантового отжига превосходит традиционные эвристические алгоритмы глобальной оптимизации, такие как имитационный отжиг, по способности избегать локальных минимумов и по времени решения. Это первая практическая атака на несколько полномасштабных алгоритмов симметричных шифров со структурой SPN с использованием реального квантового компьютера.
Кроме того, это первый случай, когда атаки квантовых вычислений на несколько алгоритмов симметричного шифра со структурой SPN достигли производительности традиционных математических методов».
Реферат научной статьи (abstract) на английском
Как видим, ничего революционного в исследовании нет. Однако результаты научной статьи попали в заголовки СМИ и вызвали беспокойство по поводу уязвимостей современной криптографии. Эксперты говорят, что шумиха раздута.
«Это интригующее исследование, но оно не вызовет квантовый апокалипсис прямо сейчас, — считает Авеста Ходжати (Avesta Hojjati), глава отдела исследований и разработок компании DigiCert. — Хотя здесь демонстрируется потенциальная угроза квантовых вычислений для классического шифрования, но атака проведена на 22-битные ключи».
22-битные ключи представляют собой строку символов с 222 (4 194 304) возможных комбинаций, что намного меньше, чем в 2048- и 4096-битных ключах, широко используемых сегодня.
Таким образом, предположение о том, что атака представляет непосредственную угрозу для широко используемых стандартов шифрования, вводит в заблуждение. AES-256 считается одним из лучших современных шифров и ему пока ничего не угрожает.
Комментарии (20)
Sly_tom_cat
17.11.2024 13:10Одни про атаку на "Present, Gift-64 и Rectangle", а другие про AES-256.....
Кто в лес, кто по дрова.
Опять журналисты натянули сову на глобус.
litalen
17.11.2024 13:10Тут еще всю статью вроде про симметричные шифры типа Rijndael, а потом рраз - и почему-то сравниваются длины ключей симметричных шифров (AES-256 написано) и 2048/4096, характерные для ассиметричных шифров типа RSA.
22-битные ключи представляют собой строку символов с 222 (4 194 304) возможных комбинаций, что намного меньше, чем в 2048- и 4096-битных ключах, широко используемых сегодня.
Chetverh
17.11.2024 13:10Исследователи заявили, что им не удалось взломать AES-256, но они подошли к этому «ближе, чем когда-либо прежде».
Очевидно же, что подошли ближе, чем другие до них - иначе бы и новости не было. Но насколько близко к окончательному результату?
Темнят. Наверняка хотят под это дело с кого-то сколько-то получить.
leon-mbs
17.11.2024 13:10когда китайцы заявляют о очредном своем достидении это внегда надо делить натрое.
могли бы чего то достаигать не воровали бы чцжие технологии сплошь и рядом
tairsu
17.11.2024 13:10Интересно, вы, когда бумажными деньгами расплачивались, всегда мысленно китайцев благодарили за эту технологию или просто пользовались?
CitizenOfDreams
17.11.2024 13:10В некотором смысле, квантовый компьютер для вычислений использует законы физики
А в некотором смысле - законы магии?
ITShchen
Я не думаю, что то кто сломав любой шифр - сразу об этом раструбит на всю округу. Тем более корпорации, тем более с новейшими технологиями. Но в целом, отбросив паранойю - я совершенно спокоен как за AES-256, так и за себя. Ведь очевидно, случись даже реальный прорыв в этом направлении - до рядовых мошенников эти технологии не скоро дойдут.. надеюсь)
vilgeforce
С другой стороны шило в мешке не утаишь и реальные атаки вызовут много подозрений...
Zolg
Секретностью дисциплиной и рядом спецопераций по дезинформации (об источниках данных) англичане утаивали шило с Энигмой почти всю войну
mapnik
Сколько это в днях?
Zolg
По окончании войны надобность в маскировке шила пропала, поэтому для оценки нижней границы возможного срока сокрытия прецедент с Энигмой использовать можно, а вот верхнего - нет.
Ну н нужно помнить об особенностях времени: война диктовала масштаб использования информации, а уровень технологий - немалое количество вовлеченных в процесс людей. И то и то на сохранности тайны положительно не сказывается. Так что если смогли тогда, то сейчас - и подавно (с)могут
qazdro
Тогда возможностей для шпионажа было гораздо меньше, фактически по-настоящему секретные факты получали через агентуру. Среди создателей Энигмы и их ближайшего окружения агентов не было, вот про нее и не узнали. Сейчас же провести такую масштабную работу, скрыв ее итог, практически невозможно. Разве что отдельно создавать территорию с учёными, связь на которой будет полностью отсутствовать, а выезд всем запрещен. Да и то, кто-нибудь из чиновников может разгласить
ifap
Смотря кто сломает. Если какой-нибудь темный гений, то мы узнаем о его успехах скорее по улетучиванию пары ярдов биткоинов в неизвестном направлении, чем по сливу переписки генералов из Пентагона с
полевымикомандирами в поле.wanomgn
/душнила on
битков всего 21 миллион
/душнила off
:)
ifap
Как увидите, что больше - знайте: AES пал! ;)
Infthi
так ужо, в 2010
uranik
Это в оригинальном блокчейне максимум 21 миллион, но эти гении придумали размножить биткойны в виде токенов в других сетях (bsc,eth...), поэтому сколько их уже сейчас никто не знает.
Zolg
Идея спорной гениальности: информация о компрометации криптографической надёжности битка обрушит и его и другие криптовалюты. И если быстро улетучить офиглион биткоинов гипотетически можно, то вот обналичить - увы. И даже с меньшими суммами в момент обналички магия неизвестности направления рассеется