Главная / Пресс-центр / Статьи
Статьи30 октября 2024
Постквантовые криптосистемы в TLS и не толькоАвтор статьи: Александр Венедюхин, ведущий аналитик ТЦИ ![]() Постквантовые криптосистемы, или криптосистемы с постквантовой стойкостью, - это криптосистемы, которые устойчивы к атаке при помощи алгоритма Шора, исполняемого на универсальном квантовом компьютере. Прикладная постквантовая криптография в TLS развивается неожиданно быстро. Поддержка гибридной криптосистемы обмена ключами X25519Kyber768 с постквантовой стойкостью уже больше года как внедрена в браузер Google Chrome (Chromium). Эта же криптосистема поддерживается современными версиями Mozilla Firefox. А браузер Edge от Microsoft, хоть и базируется на Chromium, поддерживает более экзотический гибрид с постквантовой стойкостью - P384Kyber768. На серверной стороне поддержка есть в таких крупных источниках интернет-трафика, как Google и Cloudflare. Результаты опроса узлов, адресуемых доменами второго уровня в зоне .RU, проведённого в сентябре 2024 года в рамках подготовки настоящей статьи, показали, что поддержка X25519Kyber768 есть на 7,36% уникальных имён, указывающих на работоспособные TLS-серверы (только IPv4). При этом более 95% из них указывают на IP-адреса сервисов Cloudflare и Google (GoogleCloud). Так что гибридные постквантовые криптосистемы уже весьма заметны в вебе. При чём здесь гибриды? Вообще, гибридной криптосистемой традиционно называют сочетание двух (и более) криптосистем, в котором их вывод комбинируется тем или иным способом. Так, гибридной криптосистемой принято называть схему, в которой асимметричная криптосистема (с открытым ключом) используется вместе с симметричной криптосистемой (вместе с шифром). Исторический пример из области TLS: зашифрование симметричного секрета при помощи RSA (то есть при помощи открытого ключа из асимметричной RSA). Такая трактовка термина широко используется и сейчас. Однако в рассматриваемом постквантовом случае речь идёт о другом: здесь комбинируют вывод двух асимметричных криптосистем, одна из них – «классическая», а вторая - с постквантовой стойкостью. В современных реализациях TLS широко используется протокол Диффи-Хеллмана (DH) для согласования сторонами общего секрета через открытый канал. Упомянутая в самом начале в составе гибридного названия криптосистема X25519 - это и есть вариант DH на эллиптической кривой, который много лет используется едва ли не повсеместно в вебе (и не только в вебе). А соответствующий гибрид, X25519Kyber768 (далее - XKyber), - это объединение X25519, которая уязвима для теоретического квантового алгоритма Шора, и Kyber768, для которой быстрых квантовых алгоритмов взлома ещё не найдено. С алгоритмической точки зрения, «гибридизация» этих криптосистем в TLS выполняется самым простым способом: при создании TLS-сессии обе криптосистемы работают независимо, однако результат применения каждой из них, - то есть сессионный секрет, - объединяется в общий массив, который служит для создания симметричных ключей шифров, используемых для защиты полезного трафика. Именно так схема работает в браузерах Chrome/Chromium и Firefox и на серверной стороне. Ошибочным предположением было бы считать, что в гибриде XKyber работа X25519 каким-то образом «подмешивается» внутри Kyber768, чтобы «усилить» последнюю. Это не так: Kyber768 уже сейчас в TLS используется независимо, а стойкость этой криптосистемы, - как классическая, так и постквантовая, - не привязана напрямую к X25519 в гибриде. В этом-то и состоит основной смысл постквантовой «гибридизации» криптосистем: если окажется, что Kyber не обладает достаточной классической стойкостью, то в гибриде такую стойкость обеспечит часть X25519. Это означает, что, взломав Kyber768, атакующая сторона получит только часть секрета, поскольку X25519 осталась невзломанной, то есть трафик всё ещё защищён 256-битным секретом X25519, а этого более чем достаточно. Так что, поскольку X25519 уже широко применяется, то внедрение постквантовых алгоритмов хотя бы не делает ситуацию хуже с практической точки зрения. Если же вдруг случится удивительное событие и появится подходящий квантовый компьютер, с помощью которого взломана X25519, то останется секрет от Kyber768, тоже 256-битный. Тут, конечно, тоже есть оговорки: с точки зрения теоретической криптографии простое объединение криптосистем может ухудшить стойкость в некоторых моделях, применяемых для определения этой самой стойкости. Грубо говоря, присоединение результата работы нестойкой криптосистемы к результату стойкой может дать возможность для построения индекса, по которому результаты работы гибридной криптосистемы окажется возможно отличить от случайной битовой перестановки. Впрочем, магия столь высокого градуса к рядовому TLS применяется редко и внедрению постквантовых гибридов не препятствует. (Тем не менее, считать, что «стойкость» Kyber не отличается для перебора на квантовом и классическом компьютере, тоже не следует.) По только что описанной схеме реализована и гибридная постквантовая криптосистема для TLS под названием P384Kyber768, которую внедрили в браузер Microsoft Edge: это сочетание протокола DH на эллиптической кривой P-384 (угадать этот номер нетрудно) и Kyber768. Полученные независимо секреты, как и в XKyber, комбинируются простым присоединением. Данный метод является весьма распространённым. ML-KEM и бурное развитиеВ 2024 году Kyber, - часть, обеспечивающая постквантовую стойкость в упомянутых гибридах, - была стандартизована NIST и успела сменить название на ML-KEM. Вместе с названием изменились некоторые внутренние детали самой криптосистемы, поэтому имеющиеся в браузерах реализации Kyber несовместимы с реализациями ML-KEM. Поддерживать параллельно две криптосистемы, то есть Kyber и ML-KEM из стандарта, было признано в Google затратным решением, так как используемые ключи слишком велики (требуют много килобитов для записи). Поэтому, хоть эти криптосистемы и аналогичны, в браузерах ML-KEM идёт на смену Kyber. X25519 заменять пока не планируют, поэтому будет – X25519+ML-KEM. Практика постквантовой стойкости в TLS настолько бурная, что развитие уже выходит на третий виток. Третий - потому что несколько лет назад в Chrome уже тестировались, в рамках экспериментов, другие криптосистемы с постквантовой стойкостью (New Hope, SIKE и HRSS). Если снова вспомнить о том, что на серверной стороне постквантовые варианты Kyber для TLS тоже поддерживаются крупнейшими источниками веб-трафика, то получится, что если пользователь просматривает Youtube или поисковую выдачу Google при помощи современной версии Chrome, то трафик его TLS-сессий уже защищён с «постквантовой стойкостью» от возможного раскрытия в будущем. Может даже показаться, что массовый переход на постквантовую криптографию в Интернете уже почти завершился, а вот квантовых компьютеров, из-за которых всё и было затеяно много лет назад, на горизонте пока не видно. Впрочем, это не совсем так. Но, конечно, не в части видимости квантовых компьютеров на горизонте, - их не видно всё так же, как и двадцать лет назад, - а в части внедрения постквантовой криптографии. Несмотря на бесспорные практические успехи и огромнейший отрыв от сугубо теоретических квантовых компьютеров, до всеобъемлющего внедрения всё ещё далеко (если такое внедрение когда-либо вообще потребуется). Так, упомянутая криптосистема ML-KEM (бывшая Kyber), реализованная браузерами для современного TLS, служит в этом протоколе для того, чтобы стороны, устанавливающие соединение, могли безопасно обменяться симметричными ключами. Вообще, TLS позволяет решить пару из базовых задач защиты информации, а именно: обеспечить аутентификацию сторон и реализовать защиту передаваемой между сторонами информации от прослушивания. Вторая задача решается при помощи симметричных шифров, а чтобы такие шифры можно было использовать, нужны общие для сторон соединения симметричные секреты. ML-KEM как раз позволяет серверу передать такой секрет клиенту через открытый канал, защитив значение при помощи криптографических преобразований с постквантовой стойкостью. Без постквантовой стойкости то же самое позволяют проделать и привычная реализация протокола Диффи-Хеллмана (вспомните X25519), и RSA. Но эти криптосистемы уязвимы к чисто теоретическому криптоанализу с помощью квантового алгоритма Шора, а вот ML-KEM, как предполагается, защитит от этого алгоритма. Однако тут ещё остаётся нерешённой первая задача - аутентификация. В TLS для аутентификации сторон традиционно используют TLS-сертификаты. Такое использование целиком полагается на криптосистемы цифровой подписи. Повсеместно применяемые сейчас в TLS-сертификатах криптосистемы уязвимы к атаке при помощи алгоритма Шора. Это относится и к RSA, и к ECDSA (и, соответственно, к ГОСТ-подписи). Почему же тогда постквантовые криптосистемы внедряются для обмена ключами, а не для защиты TLS-сертификатов? Потому что успешная атака на симметричные ключи позволяет раскрыть ранее записанный TLS-трафик. Это важнее в концепции раскрытия записанного ранее трафика. Взлом цифровой подписи, используемой для аутентификации, напротив, позволяет подменить TLS-узел во вновь устанавливаемых сессиях, но атаковать каким-то образом прошлые сессии таким способом невозможно: нет никакого смысла в подмене сторон уже завершившейся сессии. В TLS подписи используются не только в сертификатах, но во всех случаях роль подписей - аутентификация свойств и параметров для той или другой стороны. Естественно, внедрение подписей с постквантовой стойкостью - следующий шаг. Тут есть интересная оговорка, касающаяся RSA: как упоминалось выше, эта криптосистема ранее использовалась в TLS для передачи сессионного секрета, для чего задействовался долговременный ключ из TLS-сертификата сервера. Взлом этого ключа позволит раскрыть записанный трафик из данных сессий (а их достаточно много). Однако в данном случае речь идёт уже не об аутентификации, а о передаче сеансового секрета, то есть как раз о том направлении, которое теперь защищает ML-KEM (но без использования ключей из сертификатов). В спецификации современной версии TLS 1.3 использование RSA для передачи сеансового секрета прямо запрещено, однако защитить старый трафик, если он был записан, уже не получится - остаётся надеяться на то, что до момента появления компьютера, способного эффективно выполнять алгоритм Шора, данные в записанном трафике успеют хорошенько устареть. Вес ключейИтак, постквантовые криптосистемы в TLS прежде всего внедряются из соображений защиты современного трафика от возможного раскрытия в будущем, когда и если квантовые компьютеры всё же появятся. При этом считается, что угроза непосредственно для симметричных шифров не велика. Только такое допущение и позволяет мотивировать внедрение гибридов из X25519 и ML-KEM. Потому что если схема получения общих симметричных сессионных ключей защищена, то и TLS-трафик, зашифрованный симметричным шифром, который считается стойким, в безопасности. Что же касается самих симметричных шифров, то известные универсальные квантовые алгоритмы на этом направлении сводятся к простому поиску, то есть к перебору, а тут прирост ожидается не более «квадратичного». Иными словами, если стойкость некоторого идеального шифра эквивалентна 256-битному ключу, то универсальный квантовый поиск даст тут ухудшение лишь до 128-битного эквивалента. Но и 128-битный ключ, с точки зрения полного перебора, это более чем достаточная стойкость. Однако оценки стойкости симметричных шифров, применительно к гипотетическим квантовым вычислениям, дают довольно богатый источник содержательных обобщений. Например, в случае полного «квантового перебора» (поиска) речь идёт лишь о некотором универсальном алгоритме, который работал бы для каждого и любого шифра, как некоторой «перестановки битов» (обычно упоминают алгоритм Гровера и какие-то похожие варианты). Это почти такая же универсальность, как и в алгоритме Шора, который применим для большого класса криптосистем. Но неизвестно запретов, которые мешали бы предложить квантовые алгоритмы для взлома конкретных симметричных шифров. Дело в том, что в конкретном шифре могут скрываться оптимизации, доступные квантовым компьютерам. Да, пусть этот квантовый алгоритм не сможет взламывать произвольный шифр, но уже и успешная атака на тот или иной распространённый в TLS шифр (предположим, AES или ChaCha20 - выбор тут не слишком велик) позволит раскрыть записанный трафик без всякой необходимости реализации алгоритма Шора и вне зависимости от применения постквантовой криптосистемы типа ML-KEM для обмена сессионными ключами. Впрочем, так как симметричные шифры имеют другую математическую природу, нежели асимметричные криптосистемы обмена ключами, считается, что найти подобные алгоритмы сложнее - этому мешает комбинаторная суть шифров. С другой стороны, разобрав допущение, что симметричные шифры с «короткими ключами» сохраняют стойкость к универсальному квантовому криптоанализу, можно построить предположение, что возможны и быстрые практические постквантовые асимметричные криптосистемы с короткими ключами. Этот момент, про большие ключи, имеет практическое значение в TLS (и не только): предложенные сейчас постквантовые криптосистемы требуют очень много байтов для записи ключей (или значений подписи, если речь про цифровые подписи). Да, такая длина ключей отчасти обусловлена желанием придать приемлемые значения скорости выполнения операций криптосистем. Но открытый ключ ML-KEM (Kyber768) требует для передачи более килобайта (1184 байта). И это, как говорится, далеко не рекорд, что и составляет весьма заметную проблему для TLS. Очень большие ключи мешают передавать сразу несколько вариантов в начальном сообщении при установлении TLS-соединения. Эффект особенно заметен, если сравнивать с привычными «классическими» криптосистемами на эллиптических кривых: постквантовые схемы требуют в сотню раз больше байтов; показатели для разных криптосистем и наборов параметров заметно различаются, но есть рост на пару десятичных порядков. Так, стандартизованная вместе с ML-KEM цифровая подпись SLH-DSA в «минимальном» варианте записывается в 7856 байтов (сравните с 64 байтами подписи ECDSA на кривой P-256). Предположим, что на упомянутые постквантовые криптосистемы переведены подписи в TLS-сертификатах. Тогда на запись только значения подписи и открытого ключа потребуется, предположим, восемь килобайтов. Даже если прочие необходимые поля сертификата займут только два килобайта, то получится десять килобайт в сумме. А два сертификата в таком случае выходят за максимальный размер так называемой TLS-записи - элементарного элемента в TLS-потоке. Спецификация TLS позволяет произвольно разделять сообщения по TLS-записям, поэтому всё же можно будет передать сертификаты в нескольких записях, но потребуется излишняя фрагментация течения протокола, которая легко может привести к проблемам. Интересно, что TLS-сертификаты для веба, - то есть для использования в распространённых веб-браузерах, - сейчас требуют наличия SCT-меток, подтверждающих, что тот или иной доверенный лог Certificate Transparency видел соответствующий пресертификат. Такое подтверждение реализуется с помощью цифровой подписи, так что для постквантовых криптосистем SCT-метки тоже должны заметно разрастись в объёмах, а тогда TLS-сертификаты станут весить около пятидесяти килобайт каждый. А ведь есть ещё и значение дополнительной, относительно сертификатов, «постквантовой» подписи, которое передаётся для аутентификации параметров соединения и сторон этого соединения. Впрочем, нельзя не отметить тот факт, что большая длина ключей постквантовых криптосистем меркнет на фоне того, что единственным широко известным эффективным алгоритмом квантового криптоанализа был и всё так же остаётся алгоритм Шора, свойства которого, кроме прочего, задают и длины ключей. Квант стойкостиСчитается, что квантовая реализация алгоритма Шора позволяет за обозримое время найти простые делители произвольного большого числа, а это, как минимум, ломает одну из распространённых сейчас криптосистем - RSA. Несомненно, именно алгоритму Шора идея квантовых компьютеров обязана своей массовой популярностью. Тут уместно обратить внимание на то, что даже в случае алгоритма Шора квантовая часть оказывается абсолютно бесполезна без классического, обычного компьютера, поскольку фактический поиск делителей должен осуществить именно он. А результаты гипотетических аналоговых преобразований, которые мог бы выполнить квантовый вычислитель, только дают входные данные, сводящие сложность классического вычислительного процесса к достижимому уровню. Алгоритм Шора может быть применён и к ECDSA, и к другим криптосистемам, основанным на подходящих математических задачах. Более того, в части традиционной, для алгоритма Шора, задачи факторизации, - то есть разложения числа на простые множители, - совсем недавно, в 2023 году, для квантовых алгоритмов были предложены заметные улучшения: алгоритм Регева требует меньше операций, чем алгоритм Шора, но больше «квантовой памяти». Так что развивается не только постквантовая криптография, но и квантовые алгоритмы. Отличие тут в том, что постквантовая криптография развивается уже вполне практически, а квантовые алгоритмы - чисто теоретически. Уровень технологического развития темы квантовых компьютеров сейчас таков, что не только всё ещё можно легко запутаться в интерпретациях определений «кубитов» (среди которых встречается много разных цветов и оттенков: «логические», «физические», «исправляющие ошибки» и так далее), но и непросто дать определение тому, что же такое этот «квантовый компьютер», который должен сломать «всю мировую криптографию». Одним из хороших компактных определений является следующее: квантовый компьютер - это гипотетическое устройство, эффективно выполняющее квантовые алгоритмы. Для целей настоящей статьи такое определение подходит как нельзя лучше, ведь работу всякого квантового алгоритма можно реализовать на классическом компьютере, вот только времени вычислителя этот алгоритм затратит экспоненциально больше (если вообще завершится). Постквантовая стойкость упомянутых выше криптосистем тоже определяется относительно известных квантовых алгоритмов, а если точнее, то относительно одного алгоритма - алгоритма Шора. Когда говорят, что некоторая криптосистема обладает постквантовой стойкостью, то имеют в виду, что эту криптосистему не позволяет взломать алгоритм Шора (и его варианты), исполняемый на гипотетическом универсальном квантовом компьютере. Да, для специалиста не составит труда тут же придумать различные смысловые уточнения, но одно можно сказать точно - постквантовая стойкость, обсуждавшаяся выше, вовсе не подразумевает доказательства того, что в принципе не может быть алгоритмов для квантового компьютера, которые ломают ту или иную криптосистему. Доказать отсутствие алгоритма с некоторыми свойствами вообще весьма и весьма непросто, даже если речь идёт про теоретическую криптографию и классический компьютер, что уж говорить про квантовый. Вот алгоритм Шора - известен. Этот алгоритм сработает для целого класса используемых криптосистем, найти бы лишь подходящий квантовый компьютер. Нет никаких теоретических гарантий, что для математической задачи, на которой основана стойкость, например, ML-KEM, невозможно найти быстрый квантовый алгоритм. Более того, даже для классического алгоритма нет таких гарантий. Это свойство не только ML-KEM и не только постквантовых криптосистем. Стойкость практических криптосистем вообще оценивается лишь в рамках некоторой модели и ряда допущений, типа количества памяти с произвольным доступом на единицу площади, количества битовых операций в единицу времени и тому подобных. Есть основания считать, что хорошо проверенные классические криптосистемы устойчивы к классическим атакам, а вот насчёт новых постквантовых криптосистем оснований так считать сильно меньше. Атаки на криптосистемы постоянно улучшаются. Криптосистемы, основанные на новых задачах, обычно более уязвимы. Да, с математической точки зрения задачи, обеспечивающие стойкость той же ML-KEM, не слишком-то новые. Например, концептуально сходная (с математической точки зрения) криптосистема с постквантовой стойкостью McEliece была предложена ещё в 1978 году (намного раньше алгоритма Шора!). Но для практической криптографии, а тем более для TLS, такие криптосистемы являются новыми, и особые риски связаны с их конкретными реализациями. Наверное, особенно обидно было бы не получить квантовый компьютер, но получить постквантовую криптосистему, уязвимую к атакам на классическом. Поэтому в TLS и используют гибридные схемы: всего лишь 32 байта дополнительно, и килобайт ключа ML-KEM становится безопаснее. |
Постквантовые криптосистемы в TLS и не только |