Несколько дней назад появилась работа (Yilei Chen), предлагающая квантовый алгоритм для быстрого (“за полиномиальное время”) решения задач теории решёток, на сложности которых основаны оценки стойкости многих современных постквантовых криптосистем. Квантовый алгоритм – это алгоритм для гипотетического квантового компьютера, то есть, дважды теоретический. Однако, в данном случае, как раз этот факт и выглядит особенно занятно.

Почему эта тема популярна? Если хотя бы теоретическое описание алгоритма верное и если его удастся развить до параметров практических версий задач (этого пока что нет, о чём прямо написано в исходной работе), то многие суперсовременные криптосистемы из класса “постквантовых” – не просто сразу потеряют постквантовую стойкость, но, возможно, даже станут менее стойкими к квантовой атаке чем, скажем, классическая RSA. Конечно, тут заведомо присутствует очень много “если”, и это всё гипотетические рассуждения. Однако и стойкость соответствующих постквантовых криптосистем к атакам на классическом компьютере – отдельный, всё ещё не очень хорошо исследованный, вопрос.

Понятно, что в статье обнаружатся ошибки и она потребует, как минимум, уточнений. Так, сегодня опубликована записка (Omri Shmueli), указывающая на недостижимые значения параметров, которые использованы в доказательстве корректности алгоритма. Это, впрочем, только добавляет арифметической занимательности, поскольку доказательство недостижимости основано на оценке количества простых чисел, меньших заданного. Дело в том, что описанная версия алгоритма, для корректной работы, требует построения набора из некоторого количества попарно простых натуральных чисел, меньших заданного порогового значения – но для определённых значений параметров таких чисел может не найтись в нужном количестве, поскольку не хватит простых. Если алгоритм нельзя исправить (это ещё тоже не факт) и это удастся доказать, то может даже так оказаться, что постквантовая стойкость криптологических задач теории решёток зависит от количества простых чисел, меньших заданного порога. А это весьма сильное и интересное ограничение. (Но, конечно, вряд ли это так.)



Комментировать »

В журнале “Интернет изнутри” опубликована моя статья “Постквантовая криптография и практика TLS в браузерах”. Статья, в основном, про то, как “квантовые вычисления” связаны с теоретико-информационной криптографией, и как это влияет на TLS в архитектурном смысле, но также рассмотрен свежий пример с Kyber768 в браузере Chrome.

Цитата:

“Квантовые вычисления в философском смысле – это попытка получить доступ на самом низком, самом прямом и «железячном» уровне к центральному «процессору» (ЦПУ) вселенных, то есть, к необозримому «чипу», на котором, возможно, окружающая действительность исполняется в режиме виртуализации. Это неплохо соответствует фольклорной интерпретации термина «квантовый» в отношении компьютера: элементы полупроводниковых чипов, находящихся внутри этого ящика, становились всё меньше и меньше, и вот, за гонкой нанометровых технологий, ситуация проваливается в квантовые элементы – получите квантовый компьютер. И действительно, пусть сам предполагаемый принцип квантовых вычислений не имеет ничего общего с уменьшением линейных размеров полупроводниковых вентилей и законами Мура, попытки физической реализации квантовых вычислителей уже сейчас подразумевают управление отдельными атомами. Если квантовый компьютер сделать не получится, эти наработки наверняка пригодятся для дальнейшей миниатюризации компьютеров классических. Что же касается теоретико-информационной криптографии, то она, похоже, выигрывает и тут.”



Комментировать »

Предположим, найдены два различных сообщения, для которых значения (криптографической) хеш-функции отличаются только в одном байте (то есть, всего несколько близких битов различаются). Пусть разрядность хеш-функции 256 бит, то есть 32 байта. Заметьте: тут важна и локализация отличий – не просто несколько битов, но ещё и в одном байте. Что именно обнаружение таких сообщений означает для хеш-функции? Как ни странно, но, без прочих обстоятельств, – практически ничего нового, кроме того, что хеш-функцию, эмпирически, станут считать менее стойкой: то, что два сообщения с описанным свойством существуют – и так было известно.

Другое дело, если предъявлен метод, позволяющий быстро находить пары сообщений с близкими значениями хеш-функции. Тогда, конечно, хеш-функция перестаёт быть действительно криптографической. Однако и в случае предъявления метода возникают всякие оговорки. Близки ли входные сообщения из пары? (Кстати, тут можно вспомнить, про нужные в некоторых задачах хеш-функции (не криптографические) с “хорошей” локализацией, – LSH.) Если близки, то как метод поиска таких сообщений связан с алгоритмом хеш-функции? Можно ли успешно отыскать сообщение, парное к заданному? Известны ли свойства получающихся разбиений? Поднимается ли структура разбиений в алгоритм поиска их представителей (то есть, можно ли формулу разбиений)? В общем, много уточнений.

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

На поиске близких значений хеш-функций, например, построена схема доказательства работы в протоколе цифровой валюты Биткойн (и далеко не только там). В биткойн-сети узлы должны подбирать входные массивы так, чтобы значение хеш-функции от них было меньше заданного порога (параметр “сложности”), это означает, что несколько старших байтов записи подряд должны быть нулевыми. То есть, все использованные значения хеш-функций (SHA-256) совпадают по нескольким последовательным крайним байтам. Эта ситуация, конечно, отличается от описанной в предыдущем абзаце, но только тем, что тут совпадает меньшее количество байтов (в исходной идее требуется различие, максимум, в одном байте). При этом, в случае с биткойнами, довольно велика вероятность того, что в ходе работы сети “майнеров” либо уже были обнаружены полноценные коллизии SHA-256, либо такие коллизии будут обнаружены в течение нескольких лет (если ничего не изменится кардинально, конечно). Это так не только по причине парадокса дней рождения, но и из-за возможных дефектов SHA-256. Другое дело, что такие коллизии вряд ли кто-то заметил – объёмов памяти для хранения всех перебираемых значений нет в принципе.



Комментировать »

В марте довольно много писали про новую атаку на SHA-256, “с обнаружением коллизий”. Вообще, тут нужно отделять академические атаки от практики, условно говоря, всяких биткойнов: в исходной работе (“New Records in Collision Attacks on SHA-2”, Li, Liu, Wang) речь идёт про академические атаки на урезанную “функцию сжатия” (см. ниже) из состава SHA-2 (SHA-256 – это разновидность SHA-2), да ещё и со специально подобранным предыдущим состоянием. Это общепринятый подход к исследованию стойкости хеш-функций, результат существенно лучше предыдущих достижений, но нужно учитывать, что он не обязательно приводит к практической атаке на полную хеш-функцию. В статье сказано именно про “практическую атаку”, это верно, однако это разная “практика”.

Возьмём в качестве примера SHA-256 и одну из практических (в академическом смысле) атак, представленных в упомянутой выше работе. Ядром схемы хеш-функции SHA-256 являются преобразования, соответствующие симметричному шифру. Повторно выполняемые раунды преобразований шифра, внутри хеш-функции, и образуют так называемую “функцию сжатия” – это важнейший элемент. Входной текст для преобразования в SHA-256 разбивается на блоки. Блок – это последовательность байтов, соответствующая разрядности функции, здесь – 256 бит или 32 байта. Блоки обрабатываются функцией сжатия, внутри которой выполняется заданное количество раундов – то есть, повторное применение одних и тех же преобразований, в цикле, к обрабатываемому блоку. Далее речь будет идти только про один блок, а не про полный входной текст.

После каждого раунда, блок, в результате применения преобразований, изменяется и потом снова подвергается тем же преобразованиям, которые опять изменяют блок. Эта комбинаторная часть позволяет добиться нужного разрежения для отображения входных блоков в выходные значения. Штатная схема SHA-256 использует 64 раунда в функции сжатия. Атака, о которой идёт речь, работает для 39 раундов (обратите внимание: с подобранным начальным состоянием – это очень важный момент).

Что это означает? Это означает, что исследователи нашли и предъявили кортеж из трёх конкретных значений (чисел или массивов байтов – как хотите), которые, будучи подставленными в урезанную до 39 раундов сжатия версию хеш-функции SHA-256, дают одинаковый результат. Одно из этих значений – это начальное состояние, устанавливаемое перед вызовом функции сжатия внутри урезанной SHA-256. То есть, при штатной реализации SHA-256 – этим состоянием либо был бы предыдущий обработанный блок, либо начальные константы из спецификации SHA-256. Два других упомянутых значения – это различающиеся в некоторых байтах входные блоки. Обработка этих блоков при указанных, весьма строгих, условиях – даёт коллизию. То есть, академическая “практическая” демонстрация, с конкретными числами. Это вполне себе строгий и разумный способ анализа стойкости преобразований. В данной науке это называется SFS-коллизия (от Semi-Free-Start). Но, опять же, очень далеко от демонстрации реальной, практической, “уничтожающей” коллизии SHA-256, то есть, демонстрации двух различных входных текстов, дающих одинаковый результат хеш-функции. (Что, конечно, не отменяет заметного продвижения.)

Сколько раундов для функции сжатия вообще важны? Важны все раунды, указанные в спецификации. Каждый раунд очень важен и блокирует атаки, успешные для урезанных вариантов. Раунды именно для этого и служат. Потому что, если значение хеш-функции изменяется даже только в результате последнего раунда, то на выходе всё равно получаются разные значения и, строго говоря, коллизии нет (но может быть “почти коллизия” и т.д.).

Естественно, обнаружение точек совпадения для уменьшенного количества раундов нередко даёт инструменты для взлома всей хеш-функции целиком. Именно поэтому академические атаки на примитивы с урезанным количеством раундов – важнейший инструмент. Однако, является ли тот факт, что коллизия найдена для более чем половины количества раундов, автоматической гарантией успешного применения того же метода к, предположим, половине оставшейся половины? Нет, совсем не является. Методы тут развиваются, так сказать, полностью “нелинейно”, так что непреодолимое вычислительное препятствие может возникнуть хоть бы и на каждом следующем раунде – потребуется полностью переделать метод атаки. Собственно, это очередное улучшение атак на SHA-2 как раз построено на новых методах, если сравнивать с теми методами, которые использовали для атак на MD5 и пр.

Конкретный пример, взятый из исходной работы: для 39 раундов SHA-256, при заданном начальном состоянии, получаются совпадающие значения для разных входных блоков (выдача программы, прилагаемой к работе):

431cadcd ce6893bb d6c9689a 334854e8 3baae1ab 038a195a ccf54a19 1c40606d
431cadcd ce6893bb d6c9689a 334854e8 3baae1ab 038a195a ccf54a19 1c40606d

Можно было бы предположить, что, раз точка совпадения найдена, то и дальнейшие раунды дадут одинаковые результаты. Но это далеко не так – состояние хеш-функции шире, чем конкретный результат преобразования блока. Так, если в той же программе указать 42 раунда (всего на три раунда больше), то значения уже заметно разойдутся:

d33c0cff 17c9de13 21f528f0 3362e217 563f1779 521a1b9c df062e86 19fb5973 
105d6c34 43ceb0ad 120ba1a0 3362e217 d6dd86e0 7da567b5 cf1ca736 19fb5973

Это, ещё раз, никак не уменьшает ценности результата для 39 раундов, но показывает, что для полной SHA-256 всё, – пока что, – хорошо.

Криптографические хеш-функции отображают сообщения произвольной длины в блоки фиксированной длины, так что, математически, коллизии там есть по определению. Другое дело, что если хеш-функция хорошо отображает множество входных текстов в, скажем, 2^256 выходных значений, то о коллизиях “на полном переборе” можно не особенно задумываться: мало кто может создать и записать даже 2^128 текстов. Атаки с обнаружением точек совпадения в функции сжатия как раз, потенциально, выявляют дефекты отображения, которые могут позволить найти коллизии без необходимости полного перебора. А возможно, что и позволят найти способы решения гораздо более сложной задачи вычисления прообраза, – то есть, подбора входного текста по значению хеш-функции.



Комментировать »

Квантовое распределение ключей требует наличия схемы удостоверения подлинности сторон – это необходимо для защиты от атак типа “человек посередине” на этапе согласования результата обмена (обнаружения ошибок). Реализовать это позволяют, например, криптосистемы электронной подписи (но не только). Однако, если учитывать риски появления универсальных квантовых компьютеров, то криптосистема электронной подписи, используемая для квантового распределения ключей, должна обладать постквантовой стойкостью. И здесь, кстати, кроется ответ на популярный, но некорректный, вопрос – защищает ли “квантовая криптография” от “квантовых компьютеров”? Нет, квантовая криптография (квантовое распределение ключей) – совсем о другом: несмотря на название, это и не криптография, в математическом смысле, а технический метод защиты каналов связи, который, вероятно, полезен при правильном применении, но его нельзя смешивать с криптографией теоретико-информационной.



Комментировать »

Добавил arm64 в свою реализацию шифра “Кузнечик” (ГОСТ Р 34.12-2015) на ассемблере для Go. Новые функции – для платформы arm64 со 128-битной арифметикой. Попутно немного изменил состав библиотеки, так что название теперь новое (см. исходники ниже). Раньше ассемблер был только для amd64 с AVX, на остальных платформах – компилировалось с “заглушкой”, в которой операции шифра реализованы просто на конструкциях Go – ассемблер, понятно, быстрее.

ARM – весьма и весьма распространённая архитектура, а использование ассемблера, как обычно, даёт прирост производительности во много раз, если сравнивать с “обычным” Go-шным вариантом (тоже оптимизированным, конечно). Однако я всё проверял на Raspberry Pi4 (RPi4), потому что другого варианта ARM-аппаратуры под рукой сейчас не оказалось (а техники Apple у меня вообще нет). Зато на Linux/arm64 в RPi4 – прирост более чем в двадцать раз. Было: примерно мегабайт в секунду для “обычной” реализации. Стало: около 23 мегабайтов в секунду для ассемблерной. Думаю, что должно работать и на других ARM-платформах, и гораздо быстрее, чем на RPi4, но пока не проверял: если кто-то использует, и обнаружит существенные несовместимости (см. ниже) – пишите, пожалуйста, в комментарии здесь или пишите почтой. Вообще, написанный ARM-код ещё есть куда оптимизировать: например, в arm64 имеется “векторная” инструкция, реализующая XOR сразу для трёх входных регистров, что тут очень полезно, но эта инструкция недоступна в процессоре RPi4 (Cortex-A72/BCM2711).

Новая версия кода “Кузнечика”, так как отличается от предыдущей, называется GOSThp. Исходный код публикую ниже. Возможно, потом оформлю в виде полноценного модуля для Golang и выложу копию на Github, а возможно – не оформлю и не выложу. Но использовать в составе проекта на Go этот пакет нетрудно: достаточно скопировать директорию gosthp (см. ещё детали ниже). Работает со старыми версиями Go (проверено для 1.7).

Файлы:

gosthp.tar.gz – всё вместе в одном архиве.
SHA-256: b3f860f15d43814db2f2becfb4c72272de6d3b49f9b0dec70712438af0a6e085
(Update, 20/01/2024: архив перезагружен – изменено описание платформ в +build, даты в комментариях, и даты создания файлов; код – без изменений.)

Внутри архива:

cmd/
	| gostrun.go		- файл с примерами и тестами.
gosthp/	- это сама библиотека.
	| docipher_amd64.go	- объявления функций для amd64.
	| docipher_amd64.s	- код на ассемблере для amd64.
	| docipher_arm64.go	- объявления функций для arm64.
	| docipher_arm64.s	- код на ассемблере для arm64.
	| docipher.go		- универсальная реализация для прочих платформ (см. +build внутри: могут быть расхождения).
	| gosthp.go		- основной модуль.
go.mod
README

Основное дополнение – docipher_arm64.s, собственно, реализация шифра для архитектуры arm64/AArch64.

Как обычно, прилагается демонстрационный код – gostrun.go. Если развернуть упомянутый выше архив в директорию, то собрать gostrun можно так:

$ cd cmd
$ go build -o ~/my-builds/gostrun gostrun.go

Go самостоятельно выберет нужные файлы в соответствии с целевой платформой. Внутри исходников – много комментариев (англ.).
Саму библиотеку можно использовать в среде Go в составе других проектов простым копированием gosthp/, разместив её либо в директорию сборки, либо в общую директорию для пакетов.

Ассемблерная реализация для ARM от x86 отличается в некоторых деталях, не алгоритмических: во-первых, очевидно, другие инструкции; во-вторых, используется больше регистров и основные операции XOR собраны в общий блок; в-третьих, изменён способ вычисления смещений для обращения к таблице значений.

Screenshot

Как обычно, основная оптимизация – использование предвычисленной таблицы. На ассемблере написаны только низкоуровневые операции шифра, то есть, преобразование блока с таблицей и раундовыми ключами. Библиотека позволяет создать экземпляр объекта, который реализует интерфейсы для доступа к шифру. Таблица, ускоряющая операции, общая для всех экземпляров, эта таблица создаётся при инициализации модуля, а потом используется процедурами, реализующими шифр, только для чтения. Строго говоря, таблиц там несколько: есть “обратная” таблица для расшифрования и несколько вспомогательных (см. исходный код). Так как значения в таблицах не зависят от конкретного ключа, то их использование не требует повторного вычисления значений. В принципе, можно было бы просто записать эти таблицы в код в виде статического массива, так часто делают, но можно и генерировать программно, что делает код менее громоздким, а на производительность никак не влияет.

Базовые процедуры шифра (зашифрование/расшифрование) используют набор ключей раундов, которые создаются при инициализации конкретного экземпляра cipher – раундовые ключи как раз зависят от ключа шифрования, поэтому записываются в конкретный экземпляр структуры, в которой используются при повторных вызовах. То есть, разворачивание ключа тут тоже производится только один раз, при создании экземпляра cipher.

Что касается совместимости. И amd64, и arm64 – достаточно широкие понятия. В этой реализации шифра “Кузнечик” используются регистры и команды для разрядности 128-бит, которая соответствует разрядности шифра – в этом, собственно, смысл. Уже использование команд “длинной” арифметики из SSE4.1 для amd64 означает, что некоторые старые процессоры, полностью попадающие в amd64, не смогут, тем не менее, исполнять скомпилированный код, поскольку не поддерживают нужных команд. То же самое относится и к arm64 (например, выше я уже упомянул, что не использую “трёхрегистровую” команду XOR по этой же причине). Данная библиотека поддержку команд не проверяет, так что, вообще говоря, это нужно отслеживать отдельно, используя механизмы детектирования свойств аппаратуры, и, соответственно, либо заменять вызываемые функции, либо выводить предупреждение пользователю.



Комментарии (7) »

В алгоритме ECDSA есть число, обычно обозначаемое k, которое используется при вычислении значения подписи, а именно – k определяет параметр r из пары (r,s) подписи. Значение r из этой пары необходимо для того, чтобы сошлась формула проверки. В исходном алгоритме k предлагается выбирать случайным образом (но без повторов, и держать в секрете). Дело в том, что если третья сторона знает k, то она может элементарным способом вычислить секретный ключ по сообщению с подписью; повторное использование k для разных сообщений, при прочих равных, так же приводит к раскрытию секретного ключа.

Можно встретить мнение, что такая особенность заложена в ECDSA специально (оставлено за скобками то, что такой подход использовался и в других, предшествующих ECDSA, криптосистемах). Действительно, если, например, k вычисляется по некоторому алгоритму генерирования псевдослучайных чисел “с секретом”, то если третьей стороне известны скрытые особенности данного алгоритма, эта сторона может раскрыть секретный ключ ECDSA, быстро подобрав k под открытое значение r, которое можно взять из подписи. (Это хрестоматийный теоретический подход к созданию бэкдоров методом “алгебраического разбиения”.)

Вообще, на этом направлении весьма легко ошибиться в программном коде, без всякого бэкдора. Либо подведёт аппаратура, обеспечивающая выдачу случайных значений. Либо вмешается тот или иной гипервизор – сейчас повсеместно используется виртуализация для размещения программного кода, вычисляющего ECDSA-подписи, с этим сложно что-то поделать, как и с тем, что инженеры DevOps обожают делать “снапшоты” виртуальных машин, а потом их восстанавливать (так себе решение) или множить (ещё хуже). Заметьте, кстати, что всё это полностью применимо и к современной ГОСТ-подписи – там математически эквивалентная схема.

Так что проблем с псевдослучайным параметром в ECDSA много. На практике, в алгоритм вычисления k так или иначе подмешивают дополнительные значения, не ограничиваясь лишь выдачей генератора псевдослучайных чисел. Это полумера. Однако есть и полностью детерминированный вариант (“deterministic ECDSA“), в котором значение k вычисляется для конкретного сочетания сообщения и секретного ключа (например, такой алгоритм поддерживается свежим OpenSSL 3.2).

Практика использования детерминированного варианта сопряжена с ещё одним занятным моментом. Если сообщение подписывается обычной ECDSA (или ГОСТ-подписью), то значение подписи будет каждый раз разным, даже для одного сообщения и одного подписывающего ключа. То есть, значение подписи псевдослучайное, и этот факт вполне может использоваться приложениями (хотя, вообще говоря, не должен бы). Соответственно, “фиксирование” значения подписи в таком приложении может что-то сломать. Но детерминированный вариант, конечно, всё равно лучше.



Комментировать »

На OpenNET пишут про RFC для децентрализованной системы имён GNS:

“Использование Curve25519 воспринимается некоторыми как весьма странный шаг, так как для ECDSA применяют другие типы эллиптических кривых, а в паре с Curve25519 обычно используют алгоритм цифровых подписей Ed25519, более современный, более безопасный и более быстрый, чем ECDSA. С точки зрения криптостойкости в том числе вызывает сомнение выбор размера закрытого ключа – 32 байта вместо 64 байт”

В GNS, действительно, используют ECDSA на кривой Curve25519. Это может, конечно, показаться странным. Однако алгоритм ECDSA работает в группе точек и вообще не зависит от выбора кривой (да, даже про “суперсингулярные кривые” тут есть занятные уточнения). Поэтому ничто не мешает взять Curve25519 вместо, например, более привычной P-256. Какие-то сугубо математические свойства Curve25519, типа наличия кофактора и т.п., вовсе и не являются необычными – такие кривые вполне себе подходят и для ECDSA. Так что, если нет доверия той же P-256, но нужен именно алгоритм ECDSA – можно взять Curve25519. Использование же Ed25519 в данном протоколе невозможно из-за особенностей преобразования ключей, о чём, собственно, сказано в RFC. Насчёт “более быстрого” алгоритма Ed25519 – это, в основном, определяется как раз параметрами кривой (поле и т.д.).

Что касается странного дополнения про 32-байтовый и 64-байтовый ключи: тут, наверное, что-то перепуталось на каком-то этапе пересказывания. В Ed25519 секретный ключ – 32-байтовый. И в ECDSA на P-256 (например) – тоже 32-байтовый. Потому что разрядность в 256 бит (32 байта) делает бессмысленным использование секретных ключей большей длины: всё равно значение сократится. А 64 байта – это общий размер подписи, а не ключа.

Можно предположить, что тут ещё сыграло следующее популярное заблуждение, которое нередко наблюдается в отношении SSH-ключей: многие считают, что, например, поскольку открытый ключ Ed25519 короче, чем ECDSA на той же P-256, он поэтому и менее “криптостойкий”. Действительно, для ECDSA/P-256 открытый ключ обычно записывается в 64 байта (иногда чуть меньше, иногда – чуть больше, зависит от кодирования), а в Ed25519 – только в половину, в 32 байта. Однако эти 64 байта ECDSA математически эквивалентны 32 байтам, там половина байтов приносит только один бит дополнительно: открытый ключ представляет собой точку на кривой, у точки – две координаты (X,Y), каждая по 32 байта, и вот полная форма записи ключа ECDSA подразумевает указание объединения X и Y, откуда и получается 64 байта; однако можно указывать только одну координату (X), а вторую (Y) – вычислять из уравнения кривой при необходимости. В такой схеме, для ECDSA, потребуется сохранить дополнительно знак, это один бит, и получается тоже около 32 байтов для записи открытого ключа. А вот в Ed25519 алгоритм предписывает всегда использовать только одну координату (ну, строго говоря, там есть ещё некоторые преобразования, но здесь они не важны). То есть, математически эти ключи совпадают по представлению, отличие тут чисто прикладное, поэтому дополнительные 32 байта записи для ECDSA не делают даже открытый ключ в два раза длиннее “криптографически” – он всё равно 256-битный (по разрядности кривой).



Комментировать »

Кстати, если вдруг придумают алгоритм быстрой факторизации больших полупростых чисел, сломав тем самым RSA, то, конечно, “популярной мотивации” для создания универсального квантового компьютера станет сильно меньше: на этом направлении всегда пишут про алгоритм Шора. А вот с необходимостью перехода на постквантовые криптосистемы, в этом случае, есть интересные особенности.

Так, обнаружение алгоритма быстрой факторизации, естественно, легко может грозить тем, что попутно обнаружится и способ быстро сломать задачи типа привычного эллиптического варианта Диффи-Хеллмана (читай – ECDSA). Однако только из этого не следует автоматически вывод, что переходить требуется именно на постквантовые криптосистемы. Вот тут и начинаются особенности. Во-первых, постквантовые криптосистемы уже разработаны, уже имеют какую-то практическую “классическую” стойкость, уже реализованы, – так что их быстрее внедрить; во-вторых, задачи, на которых базируются те или иные постквантовые криптосистемы, имеют гораздо больше шансов сохранить известную сложность после обнаружения каких-то принципиально новых методов быстрой факторизации – это, конечно, тоже не гарантируется, однако для ускорения факторизации/логарифмирования до сих пор использовались математические конструкции, которые, в общем-то, стоят и за многими постквантовыми алгоритмами.



Комментировать »

Представьте, что некоторый протокол туннелирования в Интернете устроен следующим образом: в качестве базового транспорта используется UDP (то есть, отсутствуют сессии транспортного уровня, тут это важно); применена схема “клиент-сервер”, использующая двухстороннюю аутентификацию с общим секретом, а процесс аутентификации тоже полностью зашифрован (пробное расшифрование и т.д.); используются различные IP для серверов – точек входа, а также динамически изменяемые номера портов; полезные данные тоже полностью зашифрованы – отсутствуют какие-либо открытые заголовки (кроме UDP), отсутствует фиксированная структура пакета, пакеты имеют разную длину, а адреса/номера портов изменяются в ходе соединения. Подобные протоколы есть, но в этой заметке речь о том, почему именно такой подход создаёт трудности в обнаружении и блокировании соединений.

Протокол медленный, не предназначен для создания стабильных и широких каналов, но зато он скрытый, полностью “мутирующий” и “размытый” (возможно, кто-то из читателей помнит, как в своё время появились первые развитые “полиморфные” компьютерные вирусы, содержавшие зашифрованное тело и генерируемый псевдослучайным образом “распаковщик” – теоретически, никаких статических сигнатур). Описанный протокол как раз внешне выглядит как случайный поток случайных UDP-пакетов, в котором не видно никаких сессий и контекста, не определяется внутренний статус, а общим является только адрес возможного клиента, так как он фигурирует и в отправителях, и в получателях, а вот уже входной и выходной серверные IP-адреса могут изменяться; это особенно занятно, если использовать IPv6 (за скобками оставлено преодоление NAT и некоторые другие сетевые особенности).

Теперь представьте, что некоторая система DPI должна блокировать соединения и прерывать сессии, используя в качестве флага тип протокола. Но у “размытого” протокола, описанного в предыдущем абзаце, нет устойчивых признаков, позволяющих уверенно определить его тип. Конечно, можно сказать, что такой признак всё же есть, просто он “несобственный” – исследуемый протокол “не похож ни на что известное”. Но для такого метода классификации нужно не только составить “белый список” протоколов, но ещё и так запрограммировать систему, чтобы она и классифицировала все протоколы, а это исключает всякую гибкость в пропуске трафика. Скажем, вот обнаружен UDP-пакет, который пока что не соответствует никакому контексту из уже созданных узлом DPI, инспектирующим трафик: если пакет относится к этапу установления соединения в рамках “размытого” протокола и если этот пакет не пропустить, то такое соединение не состоится. Но как определить, что это не пакет, выпавший из другой сессии “разрешённого” протокола (типа DTLS, предположим)?

Надёжное определение контекста становится затруднительным на достаточных объёмах трафика: у допустимых протоколов есть внутренние открытые заголовки, но они короткие и, в теории, могли просто совпасть, поэтому обязательно нужно взвешивать дополнительные параметры по нескольким пакетам – длину, адреса, номера портов. Но чтобы взвешивать несколько пакетов, для них придётся создать некоторую очередь измерений. А как сделать такую очередь эффективной, если туда предлагается складывать всё, что не получилось разобрать? Кроме того, задержка пакета “размытого” протокола приводит к тому, что другие пакеты просто не поступают – не из чего собирать полезный контекст в принципе. Если один “размытый” пакет пропустить, то получится, что и обмен данными случился, и тут уже вовсе не обязательно, что пакет относился к процессу аутентификации – он мог и нести полезные данные в рамках скрытой сессии. Более того, если некоторые пакеты проходят, то это означает, что сам “размытый” протокол успешно работает, преодолевая блокирующие узлы, потому что одно из заявленных свойств протокола – его внутренний статус нельзя определить даже по нескольким пакетам.

Вообще, классификация подобных протоколов с формированием контекста с целью распознавания – та ещё задача. В упрощённом виде можно представить, что классификатор работает с некоторым деревом состояний, переходы по которому определяются наличием видимой для DPI активной сессии между узлами (то, что в распространённых брандмауэрах называется Established connection), наличием ответных (парных) сообщений (это детектирование типовых “хендшейков” вида “запрос-ответ-подтверждение” на начальной стадии), соответствием заголовков транспортных пакетов и параметров адресации (адреса, номера портов), наличием заданных сигнатур и средним объёмом переданных данных. Понятно, что только лишь поиск сигнатур в конкретном пакете – тут заведомо не работает: нужно именно сопровождение состояний во времени. При этом классификация пакетов “размытого” протокола требует максимального задействования вычислительных ресурсов, нужных для расчёта эволюции только что описанного дерева – ведь каждый пакет требуется обработать, провести по функциям проверки, а потом положить информацию в буфер, чтобы позже проверить, не придёт ли какой-то ещё пакет, который можно привязать к уже полученному. Так что это всё скорее теоретические рассуждения, чем доступные на практике методы.

(Я уже писал о полностью зашифрованных протоколах раньше, в том числе, про распределение ключей и влияние TLS.)



Комментарии (3) »

Открытый ключ Kyber768 (постквантовой криптосистемы) – это 1184 байта, то есть, 9472 бита. Это заметно больше, чем занимает практический 8-килобитный ключ RSA. Для взлома такого RSA-ключа на квантовом компьютере (весьма гипотетическом), требуется количество логических кубитов в разных регистрах не меньше 24576 == 8K * 3. Но это теоретический минимум для логических кубитов, без учёта квантовых схем и возможной физической реальности. Поскольку технологические принципы реализации алгоритма Шора пока что не известны, оценки того, сколько физических кубитов и квантовых элементов потребуется для подобной разрядности, затруднены и сильно различаются, но нетрудно получить оценку в миллион (и более). И этот миллион квантовых эллементов, к тому же, может не сработать.

Естественно, это не отменяет того, что Kyber768 тут выглядит лучше, если обладает классической стойкостью. Кроме того, RSA – устаревшая криптосистема, а для коротких, относительно RSA, ключей ECDSA (например) – и кубитов потребуется поменьше, при этом прямо “растягивать” ту же ECDSA на несколько килобит – так себе идея.



Комментировать »