Постквантовая криптография — новый алгоритм «ушел за 60 минут»

Мы писали о PQC, сокращенно постквантовая криптография, ранее несколько раз.

Если вы пропустили весь ажиотаж последних нескольких лет в СМИ о так называемых квантовых вычислениях…

… это (если вы извините то, что некоторые эксперты, вероятно, сочтут безрассудным упрощением) способ создания вычислительных устройств, которые могут отслеживать несколько возможных исходов расчета одновременно.

При должной осторожности и, возможно, долее везения это означает, что вы можете переписать некоторые типы алгоритмов, чтобы найти правильный ответ или, по крайней мере, правильно отбросить целую кучу неправильных ответов, не пытаясь и не проверяя каждый возможный результат. по одному.

Два интересных криптоаналитических ускорения возможны с использованием квантового вычислительного устройства, если предположить, что достаточно мощное и надежное устройство действительно может быть построено:

• Алгоритм квантового поиска Гровера. Обычно, если вы хотите найти случайно упорядоченный набор ответов, чтобы увидеть, есть ли ваш в списке, вы ожидаете, что в худшем случае просмотрите весь список, прежде чем получите окончательный ответ. Например, если вы хотите найти 128-битный ключ дешифрования AES для расшифровки документа, вам потребуется выполнить поиск по списку всех возможных ключей, начиная с 000..001, ..2, ..3и так далее, вплоть до FFF..FFF (16 байтов FF), чтобы быть уверенным в решении проблемы. Другими словами, у вас должен быть бюджет, чтобы попробовать все 2¹²⁸ возможные ключи, прежде чем либо найти правильный ключ, либо определить, что его не было. Алгоритм Гровера, однако, при наличии большого и достаточно мощного квантового компьютера утверждает, что способен совершить тот же подвиг с помощью квадратный корень обычных усилий, таким образом взламывая код, теоретически, всего за 2⁶⁴ пытается вместо этого.
• Алгоритм квантовой факторизации Шора. Некоторые современные алгоритмы шифрования основаны на том факте, что умножение двух больших простых чисел может быть выполнено быстро, в то время как деление их произведения обратно на два числа, с которых вы начали, практически невозможно. Чтобы почувствовать это, попробуйте умножить 59×87 с помощью ручки и бумаги. Это может занять минуту или около того (ответ 5133), но это не так сложно. Теперь попробуй по другому. Разделите, скажем, 4171 обратно на два его множителя. Гораздо сложнее! (Это 43 × 97.) Теперь представьте, что вы делаете это с числом длиной 600 цифр. Грубо говоря, вы пытаетесь разделить 600-значное число на все возможные 300-значные простые числа, пока не сорвете джекпот или не обнаружите, что ответа нет. Алгоритм Шора, однако, обещает решить эту проблему с логарифм обычного усилия. Таким образом, разложение числа из 2048 двоичных цифр должно занимать всего в два раза больше времени, чем разложение 1024-битного числа, а не вдвое больше, чем разложение 2047-битного числа, что представляет собой огромное ускорение.

Противодействие угрозе

Угрозе со стороны алгоритма Гровера можно противостоять, просто увеличив размер используемых вами чисел, возведя их в квадрат, что означает удвоение количества битов в вашем криптографическом хеше или симметричном ключе шифрования. (Другими словами, если вы считаете, что с SHA-256 сейчас все в порядке, использование вместо него SHA-512 обеспечит альтернативу, устойчивую к PQC.)

Но алгоритму Шора не так просто противостоять.

Для открытого ключа в 2048 бит потребуется экспоненциальное увеличение его размера, а не просто возведение в квадрат, так что вместо ключа 2×2048=4096 бит вам понадобится новый ключ с невозможным размером 2²⁰⁴⁸ биты…

…или вам пришлось бы принять совершенно новый тип постквантовой системы шифрования, к которой алгоритм Шора неприменим.

Ну, американский орган по стандартизации NIST проводит ПКК «конкурс» с конца 2017 года.

Процесс был открыт для всех, все участники приветствуются, все алгоритмы открыто публикуются, а общественный контроль не только возможен, но и активно поощряется:

Призыв к предложениям. [Закрыто 2017 ноября 11 г.]. […] Предполагается, что новые стандарты криптографии с открытым ключом будут определять один или несколько дополнительных несекретных, общедоступных алгоритмов цифровой подписи, шифрования с открытым ключом и установления ключа, которые доступны во всем мире и способны защищать конфиденциальную правительственную информацию. в обозримом будущем, в том числе после появления квантовых компьютеров.

После трех раундов представлений и обсуждений, NIST объявил, 2022 июля 07 г., что он выбрал четыре алгоритма, которые считаются «стандартами» с немедленным вступлением в силу, и все с восхитительно звучащими именами: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONкачества SPHINCS+.

Первый (CRYSTALS-KYBER) используется как то, что называется Ключевой механизм соглашения (KEM), где два конца общедоступного канала связи надежно придумывают одноразовый закрытый ключ шифрования для конфиденциального обмена данными сеанса. (Проще говоря: ищейки получают только нашинкованную капусту, чтобы не могли подслушать разговор.)

Остальные три алгоритма используются для Цифровые подписи, благодаря чему вы можете гарантировать, что данные, которые вы получили на своем конце, точно совпадают с тем, что отправитель ввел на другом, тем самым предотвращая подделку и обеспечивая целостность. (Проще говоря: если кто-то попытается испортить или испортить данные, вы узнаете.)

Нужно больше алгоритмов

Одновременно с объявлением о новых стандартах NIST также объявил о четвертый раунд своих конкурентов, выдвигая еще четыре алгоритма в качестве возможных альтернативных KEM. (Помните, что на момент написания у нас уже есть три утвержденных алгоритма цифровой подписи на выбор, но только один официальный KEM.)

Это были: BIKE, Classic McEliece, HQC и SIKE.

Интересно, что Алгоритм МакЭлиса был изобретен еще в 1970-х годах американским криптографом Робертом МакЭлисом, который умер в 2019 году, задолго до того, как конкурс NIST уже начался.

Однако он так и не прижился, потому что требовал огромного количества ключевого материала по сравнению с популярной альтернативой того времени, алгоритмом Диффи-Хеллмана-Меркла (DHM, а иногда и просто DH).

К сожалению, один из трех алгоритмов четвертого раунда, а именно SIKE, кажется, был взломан.

В головокружительной статье под названием ЭФФЕКТИВНАЯ АТАКА С ВОССТАНОВЛЕНИЕМ КЛЮЧЕЙ НА SIDH (ПРЕДВАРИТЕЛЬНАЯ ВЕРСИЯ), бельгийские криптографы Воутер Кастрик и Томас Декру, похоже, нанесли смертельный удар по алгоритму SIKE.

Если вам интересно, SIKE — это сокращение от Инкапсуляция суперсингулярного ключа изогении, а SIDH означает Суперсингулярная изогения Диффи-Хеллмана, конкретное использование Алгоритм SIKE при этом два конца канала связи выполняют «криптотанец» в стиле DHM для обмена набором общедоступных данных, что позволяет каждому концу получить частное значение для использования в качестве одноразового секретного ключа шифрования.

Мы не будем пытаться объяснить атаку здесь; мы просто повторим то, что утверждает газета, а именно, что:

Грубо говоря, входные данные здесь включают общедоступные данные, предоставленные одним из участников криптотанца по установлению ключей, а также заранее определенные (и, следовательно, общеизвестные) параметры, используемые в процессе.

Но извлеченный вывод (информация, называемая изогения φ выше) считается никогда не раскрываемой частью процесса — так называемым закрытым ключом.

Другими словами, криптографы заявляют, что только из общедоступной информации, такой как данные, которыми открыто обменивались во время установки ключа, криптографы могут восстановить закрытый ключ одного из участников.

И как только вы узнаете мой закрытый ключ, вы можете легко и незаметно притвориться мной, поэтому процесс шифрования будет нарушен.

Судя по всему, алгоритму взлома ключей требуется около часа, чтобы выполнить свою работу, используя всего одно ядро ​​​​ЦП с такой вычислительной мощностью, которую вы найдете в обычном ноутбуке.

Это противоречит алгоритму SIKE, когда он настроен на соответствие уровню 1, базовому уровню безопасности шифрования NIST.

Что делать?

Ничего!

(Это хорошая новость.)

Как предполагают авторы статьи, отметив, что их результат пока предварительный, «при нынешнем положении дел SIDH кажется полностью несостоятельным для любой общедоступной базовой кривой».

(Это плохие новости.)

Однако, учитывая, что алгоритм SIKE еще официально не одобрен, теперь его можно либо адаптировать для предотвращения этой конкретной атаки (что, по признанию авторов, возможно), либо просто отказаться от него.

Что бы в итоге ни случилось с SIKE, это отличное напоминание о том, почему попытки изобрести собственные алгоритмы шифрования чреваты опасностью.

Это также яркий пример того, почему проприетарные системы шифрования которые полагаются на секретность самого алгоритма для поддержания своей безопасности просто неприемлемы в 2022 году.

Если алгоритм PQC, такой как SIKE, выдержал первичные проверки и исследования экспертов со всего мира более пяти лет, несмотря на то, что был раскрыт специально для того, чтобы его можно было подвергнуть общественному контролю…

…тогда вам не нужно спрашивать себя, насколько хорошо ваши самодельные, скрытые от глаз алгоритмы шифрования, вероятно, будут работать, когда они будут выпущены в дикую природу!

---