Если бы сегодняшние криптографические протоколы вышли из строя, было бы невозможно защитить онлайн-соединения — отправлять конфиденциальные сообщения, совершать безопасные финансовые транзакции или аутентифицировать данные. Любой мог получить доступ ко всему; любой мог притвориться кем угодно. Цифровая экономика рухнет.
Когда (или if) станет доступен полностью функциональный квантовый компьютер, именно это и может произойти. В результате в 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, разработал атаку, которая сломал схему под названием Радуга в выходные. Подобно Кастрику и Декру, он смог организовать свою атаку только после того, как рассмотрел основную математическую проблему под другим углом. Как и атака на SIDH, эта атака разрушила систему, основанную на математике, отличной от большинства предлагаемых постквантовых протоколов.
«Недавние нападения стали переломным моментом», — сказал Томас Перст, криптограф стартапа PQShield. Они подчеркивают, насколько сложна постквантовая криптография и сколько анализа может потребоваться для изучения безопасности различных систем. «Математический объект может не иметь очевидной структуры с одной точки зрения и иметь пригодную для использования структуру с другой», — сказал он. «Самое сложное — определить правильную новую перспективу».
