Двое исследователей взломали протокол шифрования, который многие считали многообещающей защитой от мощи квантовых вычислений. Комментарий Сохранить статью Прочитать позже
Введение
Если бы сегодняшние протоколы криптографии вышли из строя, было бы невозможно обеспечить безопасность онлайн-соединений — отправлять конфиденциальные сообщения, совершать безопасные финансовые транзакции или аутентифицировать данные. Любой мог бы получить доступ к чему угодно; любой мог бы выдать себя за кого угодно. Цифровая экономика рухнула бы.
Когда (или если) полностью функциональный квантовый компьютер станет доступным, это именно то, что может произойти. В результате в 2017 году Национальный институт стандартов и технологий правительства США (NIST) запустил международный конкурс, чтобы найти лучшие способы достижения «постквантовой» криптографии.
В прошлом месяце агентство выбрало первую группу победителей: четыре протокола, которые с некоторой доработкой будут развернуты в качестве квантового щита. Оно также объявило о четырех дополнительных кандидатах, которые все еще находятся на рассмотрении.
Затем 30 июля пара исследователей показала, что они взломали одного из этих кандидатов за час на ноутбуке. (С тех пор другие сделали атаку еще быстрее, взломав протокол за считанные минуты.) «Такая драматичная и мощная атака… была настоящим шоком», — сказал Стивен Гэлбрейт, математик и компьютерный ученый из Оклендского университета в Новой Зеландии. Мало того, что математика, лежащая в основе атаки, была удивительной, так она еще и сократила (столь необходимое) разнообразие постквантовой криптографии — исключив протокол шифрования, который работал совсем не так, как подавляющее большинство схем в конкурсе NIST.
«Это немного обидно», — сказал Кристофер Пейкерт, криптограф из Мичиганского университета.
Результаты потрясли и воодушевили сообщество постквантовой криптографии. Потрясли, потому что эта атака (и еще одна из предыдущего раунда конкурса) внезапно превратили то, что выглядело как цифровая стальная дверь, в мокрую газету. «Это произошло как гром среди ясного неба», — сказал Дастин Муди, один из математиков, возглавляющих усилия по стандартизации NIST. Но если криптографическая схема должна быть взломана, лучше всего, если это произойдет задолго до того, как она будет использована в реальных условиях. «В вас пронзает множество эмоций», — сказал Дэвид Джао, математик из Университета Ватерлоо в Канаде, который вместе с исследователем IBM Лукой Де Фео предложил протокол в 2011 году. Конечно, среди них есть удивление и разочарование. «Но также», — добавил Джао, «по крайней мере, теперь она взломана».
Секретные прогулки среди изгибов
Джао и Де Фео увидели возможность для криптографической системы, которая была бы и похожа, и соответственно отличалась от известных протоколов. Их схема, названная суперсингулярным изогенным протоколом Диффи-Хеллмана (SIDH), имела дело с эллиптическими кривыми — теми же математическими объектами, которые используются в одном из самых распространенных типов криптографии, используемых сегодня. Но она использовала их совершенно по-другому. Это была также самая компактная схема, которую рассматривал NIST (с тем компромиссом, что она была медленнее, чем многие другие кандидаты).
И «математически это действительно элегантно», — сказал Джао. «В то время это казалось прекрасной идеей».
Допустим, две стороны, Алиса и Боб, хотят тайно обменяться сообщением, даже под пристальным взглядом потенциального злоумышленника. Они начинают с набора точек, соединенных ребрами, называемого графом. Каждая точка представляет собой отдельную эллиптическую кривую. Если вы можете преобразовать одну кривую в другую определенным образом (с помощью карты, называемой изогенией), нарисуйте ребро между парой точек. Полученный граф огромен и в нем легко заблудиться: если вы совершите относительно короткую прогулку по его ребрам, вы окажетесь где-то, что выглядит совершенно случайным.
Графы Алисы и Боба имеют все те же точки, но ребра разные — они определяются разными изогениями. Алиса и Боб начинают в одной и той же точке, и каждый из них прыгает по случайным ребрам на своем собственном графе, отслеживая свой путь из одной точки в другую. Затем каждый публикует свое конечное местоположение, но держит свой путь в секрете.
Теперь они меняются местами: Алиса идет в конечную точку Боба, а Боб — в конечную точку Алисы. Каждый повторяет свой секретный ход. Они делают это таким образом, что оба оказываются в одной и той же точке.
Это местоположение было найдено в тайне, поэтому Алиса и Боб могут использовать его в качестве своего секретного ключа — информации, которая позволяет им безопасно шифровать и расшифровывать сообщения друг друга. Даже если злоумышленник видит промежуточные точки, которые Алиса и Боб отправляют друг другу, он не знает секретный путь Алисы или Боба, поэтому он не может вычислить эту конечную точку.
Но чтобы SIDH заработал, Алисе и Бобу также нужно обменяться дополнительной информацией о своих прогулках. Эта дополнительная информация и привела к краху SIDH.
Новый взгляд на старую математику
Томас Декру не собирался ломать SIDH. Он пытался построить на нем — обобщить метод для улучшения другого типа криптографии. Это не сработало, но породило идею: его подход может быть полезен для атаки на SIDH. И поэтому он обратился к Воутеру Кастрику, своему коллеге из Католического университета Лёвена в Бельгии и одному из его бывших научных руководителей, и они вдвоем погрузились в соответствующую литературу.
Они наткнулись на статью, опубликованную математиком Эрнстом Кани в 1997 году. В ней была теорема, которая «почти сразу же была применима к SIDH», сказал Кастрик. «Я думаю, как только мы это поняли… атака произошла довольно быстро, за один или два дня».
В конечном итоге, чтобы восстановить секретный путь Алисы (и, следовательно, общий ключ), Кастрик и Декру исследовали произведение двух эллиптических кривых — начальной кривой Алисы и кривой, которую она публично отправила Бобу. Эта комбинация создает своего рода поверхность, называемую абелевой поверхностью. Затем они использовали эти абелевы поверхности, теорему Кани (которая связывает абелевы поверхности с эллиптическими кривыми) и дополнительную информацию, которую Алиса дала Бобу, чтобы раскрыть каждый сделанный Алисой шаг.
«Это почти как сигнал самонаведения, который позволяет вам зафиксироваться на [определенных абелевых поверхностях]», — сказал Джао. «И этот сигнал говорит вам, что это путь, по которому вы должны пойти, чтобы сделать следующий шаг, чтобы найти правильный [секретный путь]». Что привело их прямо к общему ключу Алисы и Боба.
«Это очень неожиданный подход — обращаться к более сложным объектам, чтобы получить результаты о более простых объектах», — сказал Джао.
«Я была очень рада увидеть, как эта техника используется», — сказала Кристин Лаутер, математик и криптограф из Meta AI Research, которая не только помогла разработать криптографию на основе изогении, но и работала над абелевыми поверхностями. «Так что мне стыдно, что я не подумала об этом как о способе взлома».
Атака Кастрика и Декру взломала версию протокола SIDH с самой низкой степенью безопасности за 62 минуты, а версию с самой высокой степенью безопасности — всего за день. Затем, вскоре после этого, другой эксперт подправил атаку так, что для взлома версии с низкой степенью безопасности потребовалось всего 10 минут, а для взлома версии с высокой степенью безопасности — пара часов. Более общие атаки, опубликованные за последние несколько недель, делают маловероятным, что SIDH можно будет спасти.
«Это было особое чувство», — сказал Кастрик, хотя и горько-сладкое. «Мы убили одну из наших любимых систем».
Переломный момент
Невозможно гарантировать, что система безусловно безопасна. Вместо этого криптографы полагаются на достаточное количество времени и достаточное количество людей, пытающихся решить проблему, чтобы чувствовать себя уверенно. «Это не значит, что вы не проснетесь завтра и не обнаружите, что кто-то нашел новый алгоритм, чтобы сделать это», — сказал Джеффри Хоффштейн, математик из Университета Брауна.
Вот почему соревнования, подобные NIST, так важны. В предыдущем раунде соревнований NIST Уорд Бейлленс, криптограф из IBM, разработал атаку, которая взломала схему под названием Rainbow за выходные. Как Кастрик и Декру, он смог провести свою атаку только после того, как рассмотрел лежащую в основе математическую проблему под другим углом. И как и атака на SIDH, эта взломала систему, которая опиралась на другую математику, чем большинство предложенных постквантовых протоколов.
«Недавние атаки стали переломным моментом», — сказал Томас Прест, криптограф стартапа PQShield. Они подчеркивают, насколько сложна постквантовая криптография и сколько анализа может потребоваться для изучения безопасности различных систем. «Математический объект может не иметь очевидной структуры с одной точки зрения и иметь эксплуатационную структуру с другой», — сказал он. «Самое сложное — определить правильную новую точку зрения».
Источник: www.quantamagazine.org
