JEP 324: Key Agreement with Curve25519 and Curve448

Аннотация

Реализовать согласование ключей с использованием Curve25519 и Curve448, как описано в RFC 7748.

Цели

RFC 7748 определяет схему согласования ключей, которая эффективнее и безопаснее существующей схемы Диффи — Хеллмана на эллиптических кривых (ECDH). Основная цель этого JEP — API и реализация этого стандарта. Дополнительные цели реализации:

1. Разработать платформенно-независимую реализацию полностью на Java, которая при том же уровне стойкости работает быстрее существующего кода ECC (на C).
2. Обеспечить независимость времени выполнения от секретных данных при условии, что платформа выполняет сложение и умножение 64-битных целых чисел за постоянное время. Кроме того, в реализации не будет ветвлений, зависящих от секретных данных. Эти свойства важны для защиты от атак по сторонним каналам.

Что не является целью

RFC 7748 будет реализован только в провайдере SunEC. Реализация этого стандарта в других провайдерах не является целью этого JEP.

Реализация в SunEC не будет поддерживать произвольные параметры области. JCA API должен позволять задавать произвольные параметры области через расширение. Такое расширение выходит за рамки этого JEP.

Критерии успеха

1. Все тестовые векторы из RFC 7748 проходят.
2. Пропускная способность (измеряемая числом выведенных ключей в секунду в существующем бенчмарке согласования ключей) на всех платформах будет выгодно отличаться от существующей реализации ECC (с аналогичным уровнем стойкости).
3. Статистический тест (его ещё предстоит разработать) покажет, что время выполнения операции согласования ключей не зависит от закрытого ключа.

Мотивация

Криптография на основе Curve25519 и Curve448 востребована благодаря их свойствам безопасности и производительности. Обмен ключами с использованием этих кривых уже поддерживается во многих других криптографических библиотеках, например в OpenSSL, BoringSSL и BouncyCastle. Этот механизм обмена ключами — необязательный компонент TLS 1.3, а в более ранних версиях TLS он включается с помощью широко используемых расширений.

Описание

Функции X25519 и X448 будут реализованы, как описано в RFC 7748, и с их помощью будут реализованы новые службы KeyAgreement, KeyFactory и KeyPairGenerator в существующем провайдере SunEC. Для защиты от атак по сторонним каналам в реализации будет использоваться описанный в RFC 7748 метод «лестницы Монтгомери», выполняемый за постоянное время. Реализация будет обеспечивать свойство contributory behavior (вклад обеих сторон в общий секрет), сравнивая результат с 0, как описано в RFC.

Арифметика больших чисел будет выполняться с помощью новой библиотеки модульной арифметики. У этой библиотеки будет два существенных преимущества перед BigInteger:

1. Большинство операций будет выполняться за постоянное время. Время некоторых операций может зависеть от размера операндов, если эти операнды не являются секретными ни в одном из соответствующих алгоритмов. Например, время возведения в степень будет зависеть от размера показателя степени, но значение показателя в RFC 7748 не секретно. В документации API этой библиотеки будет описано поведение каждой операции по времени выполнения.
2. Производительность будет повышена за счёт отказа от операций переноса и использования свойств конкретных конечных полей, применяемых в операциях на эллиптических кривых.

Эта новая библиотека будет находиться во внутреннем пакете JDK и будет использоваться только новыми криптографическими алгоритмами. Мы ожидаем, что в ближайшем будущем она будет использоваться в реализациях EdDSA (подписи с использованием Curve25519 и Curve448) и Poly1305 (аутентификация сообщений). В библиотеке используется представление с уменьшенным основанием, созданное по образцу представления из статьи об EdDSA.

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

API

JCA API для RFC 7748 будет использовать имя «XDH» для обозначения всех служб, связанных с этим механизмом (KeyAgreement, KeyPairGenerator, KeyFactory и т. д.). Также будут определены имена алгоритмов «X25519» и «X448», означающие XDH с использованием Curve25519 и Curve448 соответственно. Это даёт удобную краткую запись (например, KeyPairGenerator.getInstance("X448")), которая к тому же упрощает поиск провайдера, поддерживающего нужную кривую. Имена вроде «X25519» и «X448» не должны быть просто псевдонимами «XDH»: служба, возвращаемая для этих имён, должна быть инициализирована правильной кривой и может отклонять любые ключи, использующие другую кривую.

AlgorithmParameterSpec: для указания используемой кривой (X25519 или X448) будет применяться новый класс NamedParameterSpec. Этот класс задаёт набор параметров одним стандартным именем и предназначен для повторного использования другими алгоритмами, работающими с именованными параметрами. Например, его можно использовать для именованных групп в алгоритме Диффи — Хеллмана (над конечным полем). NamedParameterSpec будет встроен в иерархию классов над ECGenParameterSpec, так что ECGenParameterSpec также будет являться NamedParameterSpec.

KeySpec: для задания открытых ключей можно использовать новый класс XECPublicKeySpec. У этого класса есть член BigInteger, который хранит координату u точки. Для задания закрытых ключей можно использовать новый класс XECPrivateKeySpec. У этого класса есть член — массив байтов, который хранит (закодированный) входной параметр k функций X25519 и X448, описанных в RFC 7748. У обоих классов KeySpec есть член AlgorithmParameterSpec, задающий кривую и другие параметры алгоритма.

Для открытых ключей также можно использовать существующий класс X509EncodedKeySpec. Для закрытых ключей также можно использовать существующий класс PKCS8EncodedKeySpec.

Интерфейсы Key: будут добавлены новые интерфейсы XECPublicKey и XECPrivateKey, предоставляющие доступ к информации, содержащейся в объектах ключей. Представление данных ключа в этих интерфейсах будет идентично представлению в XECPublicKeySpec и XECPrivateKeySpec. Оба интерфейса будут расширять новый интерфейс XECKey, который предоставит доступ к AlgorithmParameterSpec, задающему кривую и другие параметры алгоритма.

Пример использования API:

KeyPairGenerator kpg = KeyPairGenerator.getInstance("XDH");
NamedParameterSpec paramSpec = new NamedParameterSpec("X25519");
kpg.initialize(paramSpec); // equivalent to kpg.initialize(255)
// alternatively: kpg = KeyPairGenerator.getInstance("X25519")
KeyPair kp = kpg.generateKeyPair();

KeyFactory kf = KeyFactory.getInstance("XDH");
BigInteger u = ...
XECPublicKeySpec pubSpec = new XECPublicKeySpec(paramSpec, u);
PublicKey pubKey = kf.generatePublic(pubSpec);

KeyAgreement ka = KeyAgreement.getInstance("XDH");
ka.init(kp.getPrivate());
ka.doPhase(pubKey, true);
byte[] secret = ka.generateSecret();

Альтернативы

Было рассмотрено несколько альтернатив, связанных с реализацией:

1. Можно было бы выполнять арифметику в поле с помощью BigInteger. Первые прототипы показывают, что BigInteger примерно в 10 раз медленнее специализированной библиотеки модульной арифметики. Например, в первоначальном тестировании X25519 с BigInteger занимает около 2,5 мс против 0,25 мс для специализированной библиотеки на той же платформе. Кроме того, в BigInteger нет умножения за постоянное время, что лишило бы эти функции части устойчивости к атакам по сторонним каналам.
2. Нативная реализация (например, существующий код ECC) может обеспечить более высокую производительность. Первые прототипы показывают, что реализация на Java достаточно быстра для типичных задач. Например, X25519 (на Java) занимает около 0,25 мс, тогда как групповая операция secp256r1 (на C) на той же платформе занимает около 1 мс. Таким образом, первые результаты говорят о том, что реализация на Java должна быть достаточно быстрой.
3. Это согласование ключей можно реализовать с помощью существующего кода ECC, но такой подход не даёт всех преимуществ RFC 7748 в безопасности и производительности.

Тестирование

Тестирование будет включать тестовые векторы из RFC 7748. Эти векторы включают миллион итераций функций X25519 и X448, выполнение которых займёт около 15 минут. Если мы захотим запускать их регулярно, их можно распараллелить, разбив на пакеты по 10–100 тысяч итераций.

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

Риски и допущения

Существенный риск — сложность и тонкость реализации модульной арифметики. Этот риск можно снизить, разработав строгое доказательство корректности арифметики и проведя тщательное тестирование.