Если (вдруг) появился универсальный “квантовый компьютер” нужной мощности, то как именно будут выглядеть технические шаги по раскрытию ранее записанного TLS-трафика? Под “квантовым компьютером” здесь подразумевается аппарат, выполняющий алгоритм Шора. А в роли взламываемой криптосистемы выступает алгоритм Диффи-Хеллмана на эллиптической кривой (ECDH – типовой алгоритм для современного состояния TLS). Шаги потребуются следующие.

1.

В записи трафика присутствуют начальные TLS-сообщения, обеспечивающие распределение общего секрета. Если таких сообщений нет, то раскрыть трафик рассматриваемым способом – не выйдет. Выделить начальные сообщения нетрудно: они начинаются с байтового префикса с зафиксированным значением и имеют строгую структуру. В трафике всегда остаются ключи, согласованные сторонами по протоколу Диффи-Хеллмана (равно как и с использованием RSA или другого метода инкапсуляции). Я писал об этом ранее. Заметьте, что записываются и ключи, согласованные с использованием современных криптосистем, обладающих постквантовой стойкостью. Просто, считается, что их сложнее восстановить даже с использованием гипотетического квантового компьютера.

Из начального сообщения клиента выделяется блок с открытой частью клиентского обмена ECDH. Например, если используется ECDH на кривой P-256, то в специальном и легко обнаруживаемом блоке данных будет содержаться пара координат точки P на кривой P-256, представляющей собой открытую часть обмена ECDH. Это 64 байта (плюс дополнительные байты с указанием на используемый формат), то есть, два блока по 32 байта: координаты X и Y.

2.

Клиентская часть ECDH представляет собой результат умножения базовой точки на секретный скаляр – значение скаляра и есть секретная часть ECDH клиента: это натуральное число n. Открытая часть ECDH, точка P, это результат [n]G, где G – точка-генератор, заданная в параметрах криптосистемы.

Полученные координаты точки P “загружаются” в квантовый компьютер, который уже должен быть настроен на параметры соответствующей криптосистемы, то есть, содержать схему, реализующую алгоритм Шора (нахождения периода функции) для подгруппы кривой P-256, образованной точкой G. Как именно загружаются значения в квантовый компьютер – пока что не известно, поскольку никаких практических квантовых компьютеров создано пока что не было (ну или, если хотите, не было опубликовано их содержательных описаний). Вероятно, у этого компьютера должен быть некоторый классический интерфейс, воспринимающий значения байтов координат точек, и переходные схемы, которые преобразуют эти значения в коммутацию и состояния квантовых “гейтов/триггеров” и кубитов. Неизвестно даже, сколько этих “кубитов и гейтов” будет нужно: несколько миллионов или несколько триллионов. Что уж там говорить про схемы коммутации.

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

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

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

3.

Общий секрет в ECDH образуется путём умножения точки-генератора на произведение секретов сторон. В рассмотренном только что случае, достаточно умножить открытый параметр DH сервера Q на секрет клиента, вот так: [n]Q (именно эту операцию проделывает клиент в ходе штатного процесса установления TLS-соединения). Секрет клиента, как мы только что выяснили, был раскрыт при помощи квантового компьютера. Результат умножения даёт точку на кривой, координата X которой используется в качестве задающего значения для генерирования секретных симметричных сеансовых ключей защиты трафика TLS. Функция, генерирующая сеансовые ключи, известна. Так как защищённые записи содержат коды аутентификации, сторона, взломавшая секрет ECDH, может тут же легко проверить, что найденный секрет соответствует записанному трафику. Симметричные ключи позволяют расшифровать трафик сеанса, используя шифр, номер которого тоже записан в начальных сообщениях: эти сообщения как раз и нужны для того, чтобы, кроме прочего, стороны согласовали используемый шифр.

*

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



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

Где именно в криптосистеме электронной подписи ECDSA “работает” эллиптическая кривая?

Посмотрим, для начала, на значение подписи, которое состоит из двух параметров – (R, S). Здесь R – это координата X точки на используемой эллиптической кривой, а именно, X-координата точки k∘G, где G – точка кривой, называемая генератором (зафиксированный параметр криптосистемы), а k – секретное уникальное значение (ECDSA nonce). Запись k∘G, – “умножение на скаляр”, – означает повторное сложение точек: G⊕G⊕G⊕…⊕G, где G встречается k раз, а “⊕” – обозначает операцию в группе точек кривой, то есть, сложение точек. (Умножение тут лучше было бы записать [k]G, например, но это детали.)

На значение k накладываются различные ограничения, но это всего лишь натуральное число (конечно, так можно сказать про всё, что встречается “в компьютерах”). Структура кривой такова, что есть пары точек с совпадающими X-координатами, но различными Y-координатами. Этот момент нередко используется в атаках на реализации ECDSA. В данном случае – R это именно X-координата.

Эллиптическая кривая непосредственно использована для вычисления одного параметра подписи – R, который, впрочем, сразу “превращается” из точки, как кортежа значений, задаваемых дополнительной структурой уравнения кривой, в единственное число.

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

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

Сокращающиеся структуры не видны, а вычислить их, – то есть, обратить, – по открытым значениям и параметрам, сложно. Концептуально это напоминает, например, RSA, где внутри открытого ключа всегда содержится структура, связанная с разложением на простые множители, благодаря которой криптосистема работает. Тут необходимо обратить внимание на то, что, во многих практических реализациях, значение k может вычисляться с использованием и подписываемого сообщения, и секретного ключа – например, так делается в схеме детерминированной ECDSA. Но “классическая” ECDSA такого, вообще говоря, не требует. Это, впрочем, один из самых проблемных моментов реализаций данной криптосистемы – так, если третья сторона знает параметры генератора псевдослучайных чисел, который использовался для получения k, то эта третья сторона без особых трудностей может вычислить секретный ключ по значению подписи и подписанного сообщения (см. ниже).

Итак, эллиптическая кривая, заданная для ECDSA, использовалась для вычисления R. Где ещё встречаются операции с точками? Прежде всего – вычисление открытого ключа. Открытый ключ в ECDSA это точка на кривой, а получается он из секретного значения d путём умножения генератора: Q == d∘G. То есть, d – целое число. Принцип эквивалентен вычислению r. Однако, в отличие от r, открытый ключ Q повсеместно записывают как пару координат (X,Y), но это только способ записи, потому что достаточно сохранять X и один “бит знака” для Y.

Вторая часть подписи ECDSA – параметр s. И значение этого параметра вычисляется уже без использования операций с точками кривой. Уравнение для s следующее:

S == k^(-1)*(H + Rd)

– здесь, кроме уже определённых k, R и d (d – секретный ключ), используется значение H – это и есть подписываемое сообщение (технически, это значение хеш-функции от сообщения).

Все значения в данной формуле – это натуральные числа (даже k^(-1)), а не точки. Поэтому тут использованы другие значки для обозначения операций: “+”, “*”, “^(-1)” – это “обычные” операции сложения, умножения и взятия обратного по умножению. “Обычные” в кавычках по той причине, что вычисления проводятся по модулю некоторого числа. То есть, это привычная арифметика остатков. Положительное число, по модулю которого проводятся операции, это так называемый порядок группы точек кривой. Можно считать, что порядок – это количество доступных для вычислений точек кривой. Порядок обозначают, например, P, а тот факт, что это арифметика остатков “по P” записывают как (mod P). Так что свойства кривой тут участвуют только косвенно. Взятие обратного по умножению – k^(-1) – это нахождение такого числа, которое даст 1 (mod P) при умножении на k. Так как вычисления выполняются (mod q), то k^(-1) тоже будет целым числом. Пример: 4*2 == 1 (mod 7) – так как 8/7 – даст остаток 1. Обратите внимание, что все вычисления дальше – тоже (mod P), но отдельно этот момент упоминаться не будет, так как, для практических целей ECDSA и для простого P, свойства вычислений совпадают с привычными операциями в рациональных числах (кроме сложения точек кривой).

Раз это обычная арифметика, то и по формуле для S нетрудно увидеть, что если известны k, H, R, S, то легко вычислить секретный ключ d – просто перепишем уравнение относительно неизвестной переменной d. Значения H, R, S – публично доступны: первое из них это подписанное сообщение, а два других – сама подпись. Никаких “хитростей” эллиптической кривой тут уже не задействовано, поэтому и никакие особенности арифметики эллиптических кривых конкретно на этом направлении криптосистему не защищают. (Более того, если известно не точное значение, но какие-то дополнительные свойства k, то уравнение S можно превратить в неравенство, составить набор “приближений”, который позволит найти приближённое значение для секретного ключа, чтобы потом быстро подобрать его точно по значению открытого. Но это тема для другой записки.) Итак, при вычислении S операции на эллиптической кривой не используются.

Проверка подписи в ECDSA использует следующее уравнение:

C == (H*S^(-1))∘G ⊕ (R*S^(-1))∘Q

– обратите внимание, что тут разные обозначения операций, чтобы можно было различить операции с точками и операции с числами; а значение Q, – открытый ключ, – это d∘G. Работает вся эта схема потому, что, из-за свойств сложения в группе точек кривой, можно операцию сложения точек ⊕ спустить в натуральные числа, вот как: 3∘G ⊕ 5∘G == (G⊕G⊕G)⊕(G⊕G⊕G⊕G⊕G) == 8∘G. При этом, если подставить вместо S формулу вычисления S (см. выше), то в правой части сократится всё, кроме k. Получим, что C == k∘G, а X-координата C должна совпасть с R, если, конечно, подпись верна и вычисления верны. И здесь эллиптическая кривая используется непосредственно для вычисления итогового значения, а именно – умножение на скаляры точек G (генератор) и Q (открытый ключ), сложение получившихся точек.



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

Несколько дней назад появилась работа (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). Однако только из этого не следует автоматически вывод, что переходить требуется именно на постквантовые криптосистемы. Вот тут и начинаются особенности. Во-первых, постквантовые криптосистемы уже разработаны, уже имеют какую-то практическую “классическую” стойкость, уже реализованы, – так что их быстрее внедрить; во-вторых, задачи, на которых базируются те или иные постквантовые криптосистемы, имеют гораздо больше шансов сохранить известную сложность после обнаружения каких-то принципиально новых методов быстрой факторизации – это, конечно, тоже не гарантируется, однако для ускорения факторизации/логарифмирования до сих пор использовались математические конструкции, которые, в общем-то, стоят и за многими постквантовыми алгоритмами.



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